第一章 基本概念

1.1 数据关系

数据项$<![CDATA[to ]]>$数据元素$<![CDATA[to ]]>$数据对象$<![CDATA[to ]]>$数据

数据项：数据项组成数据元素，数据项是不可分割的最小单位
数据元素：组成数据的基本单位
数据对象：性质相同的数据元素的集合
数据：描述客观事物的符合

数据结构：相互之间存在一种或多种特定关系的数据元素的集合

1.2 逻辑结构和物理结构

逻辑结构：数据对象中数据元素的相互关系

• 逻辑结构包括：集合结构、线性结构、树形结构、图形结构

物理结构：数据的逻辑结构在计算机中的存储形式，也就是将数据元素存储到存储器

• 物理结构包括：顺序存储结构、链式存储结构

• 顺序存储结构：把数据元素存放在地址连续的存储单元，数据间逻辑关系和物理关系是一样的

• 链式存储结构：把数据元素存储到任意存储单元中，这些单元可以是连续的也可以是不连续的

  链式存储很灵活，不用在意存储的位置，只要有一个存放地址的指针就好了。

第二章 算法

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，且每条指令表示一个或多个操作。

2.1 算法特性

输入、输出、有穷性、确定性、可行性

• 输入输出：算法具有输入和输出
• 有穷性：算法不会出现无限循环，并且每个步骤可在可接受时间内完成
• 确定性：每个步骤都有确定的含义
• 可行性：算法的每一步都是可行的，也就是每一步都能够通过执行的有限次完成

2.2 算法设计的要求：

• 正确性
• 可读性
• 健壮性
• 时间效率高、存储量低

2.3 算法时间复杂度

在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随着n的变化情况而确定T(n)的数量级。

时间复杂度，也就是算法的时间度量，表示岁问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。

一般情况下，随着n的增大，T(n)增大最慢的方法是最优算法

用大写的O()来体现算法复杂度的记法，称为大O法。

如何推导时间复杂度：

1、常数阶：O(1)

2、线性阶：O(n)

关键在于分析循环结构内部情况，下面程序复杂度为O(n)

int i 
for (i=0;i<n;i++)
{
    //时间复杂度为O（1）的程序
}

3、对数阶：O(log n)

int count=1;
while(count<n)
{
    count=count*2 //时间复杂度为O（1）的程序
}

由于每次count*2以后，就距离n更近了，也就是说有多少个2相乘后大于n，则会退出循环，$<![CDATA[2^x=n->x=log_2n]]>$，所以时间复杂度为O(log n)

4、平方阶：O(n^2)

int i,j;
for(i=0;i<n;i++)
{
    for(j=0;j<n;j++)
    {
        //时间复杂度为O（1）的程序
    }
}

相当于循环了n*n次，时间复杂度为O(n^2)，如果外部循环m次，时间复杂度为O(n^m)

总结：时间复杂度为循环体的复杂度乘以该循环运行次数

2.4 算法时间复杂度

2.5 总结

第三章、线性表

线性表（List）：零个或多个数据元素的有限序列

• 元素之间是有顺序的：第一个元素无前驱，最后一个元素无后继，其他元素都有前驱和后继

• 线性表强调是有限的

数学表达：

3.1 线性表的抽象数据类型

3.2 线性表的顺序存储结构

顺序存储结构：用一段地址连续的存储单元一次存储线性表的数据元素

线性表存储结构代码：

顺序存储结构的三个属性：

• 存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置
• 线性表的最大存储容量：数组长度MaxSize
• 线性表的当前长度：length

3.2.1 数组计算方法

数据元素的序号和存放它的数组下标之间的对应关系：

第i+1个数据元素和第i个数据元素存储位置的关系：$<![CDATA[LOC(a_{i+1})=LOC(a_{i})+c]]>$(c为每个数据元素所占存储单元)

第i个数据元素可以由a1推出：$<![CDATA[LOC(a_i)=LOC(a_1)+(i-1)*c]]>$

线性表的存取时间性能为：O(1)

3.2.2 顺序存储结构的插入与删除

（1）获取元素

时间复杂度为$<![CDATA[O(1)]]>$

（2）插入

（3）删除

（4）时间复杂度

• 如果插入最后一个位置，或删除最后一个位置，时间复杂度为$<![CDATA[O(1)]]>$

• 如果插入第一个位置，或删除第一个元素，时间复杂度为$<![CDATA[O(n)]]>$

• 平均的情况：插入第i个位置，或删除第i个元素，需要移动n-i个元素，根据概率原理，每个位置插入或删除可概率是相同的，所以最终平均移动次数和最中间那个元素的移动次数相等为$<![CDATA[frac{n-1}{n}]]>$，所以时间复杂度还是$<![CDATA[O(n)]]>$

总结：读取的时候，复杂度为$<![CDATA[O(1)]]>$，插入或删除复杂度为$<![CDATA[O(n)]]>$，说明其适合元素个数不太变换，而存储操作更多的数据。

（5）线性表顺序存储结构的优缺点

3.3 线性表的链式存储结构

3.3.1 顺序存储结构不足的解决方法

3.3.2 线性表链式存储结构定义

链式结构：元素信息+后继元素的地址

结点Node：存储数据元素信息的域（数据域）+存储后继元素的地址的域（指针域）

单链表：每个结点只包含一个指针域的线性链表

头指针：链表第一个结点的存储位置

最后一个结点的后继不存在，即最后一个结点的指针为空（NULL）

头结点：第一个结点前设一个结点，可以不存储任何信息，也可以存储长度等附加信息

头结点与头指针的异同：

3.3 线性表的链式存储结构

带有头结点的单链表：

空链表：

设p是指向线性表第i个元素的指针，节点ai的指针域可以用p->data来表示，p->data的值是一个数据元素，节点ai的指针域可以用p->next来表示，p->next的值是一个指针，指向第i+1个元素，也就是ai+1的指针。

也就是，p->data=ai，p->next->data=ai+1

3.4 单链表的读取、插入与删除

1、读取

2、插入

不用改变其他结点，只需要让s->next和p->next的指针做一点改变即可

s->next=p->next;
p->next=s;

也就是让p的后继结点变为s的后继节点，再把s变为p的后继结点

3、删除

q=p->next;
p->next=q->next;

也就是让p的后继的后继结点，改为p的后继结点。

4、对比

3.5 单链表结构与顺序存储结构的优缺点

3.6 静态链表

用数组描述的链表叫做静态链表

数组的元素=两个数据域组成（数据域data+游标cur）

数组的第一个和最后一个元素作为特殊处理单元，不存数据

3.7 循环链表

单链表的终端结点的指针端原本为空指针，之后改为指向头结点，使整个单链表形成一个环，称为单循环链表，简称循环链表。

解决的问题：可以从当前一个结点出发，访问到列表的全部结点

3.8 循环链表

在单链表的每个结点中，再设置一个指向前驱结点的指针域，所有每个结点都有两个指针域，一个指向后继，一个指向前驱。

第四章 栈与队列

• 栈是限定仅在表尾进行插入和删除操作的线性表

• 队列是只允许在一端进行插入操作、而在另一端进行删除操作的线性表

4.1 栈的定义

栈是限定仅在表尾进行插入和删除操作的线性表

栈顶：允许插入和删除的一端
栈底：不允许任何操作
规则：先进后出（线性表）

进栈：插入
出栈：删除

4.2 栈的抽象数据类型

进栈：插入，push
出栈：删除（弹栈），pop

4.3 队列（queue）的定义

队列是只允许在一端进行插入操作、而在另一端进行删除操作的线性表

队列是一种先进先出的线性表（First in first out）的线性表，FIFO。

队尾：允许插入的一端
对头：允许删除的一端

第五章 串

由零个或多个字符组成的有限序列，又叫字符串

第六章 树

树是n个结点的有限集，n=0时，称为空树，在任意一颗非空树中：

• 有且仅有一个特定的称为根的结点（Root）
• 当n>1时，其余结点可分为m个互不相交的有限集合（T1,T2,…,Tn），其中每个集合本身又是一棵树，并且车管我根的子树（Subtree）

6.1 树的定义

树的结点包含一个数据元素及若干个指向其子树的分支，结点拥有的子树数量称为结点的度。

结点的分类：

• 叶结点/终端结点：度为0的结点
• 分支结点/非终端结点：度不为0的结点

树的度：树内各个结点的度的最大值

上图的树的度为3

结点间的关系：

结点的子树的根称为该结点的孩子，该结点称为孩子的双亲，同一个双亲的孩子称为兄弟，结点的祖先是从根节点到该结点所经分支上的所有结点。

结点的层次：

层次（Level）从根开始定义，树中结点的最大层次称为树的深度（Depth）或高度。

有序树：树中结点的各个子树看成是从左至右有次序的，不能互换
无序树：可以互换

6.2 二叉树的定义

二叉树（Binary tree）是n个结点的有限集合，该集合或者为空集（空二叉树），或者由一个根节点和两颗互不相交、分别称为根节点的左子树和右子树的二叉树组成。

二叉树的特点：

二叉树的五种形态：

6.2.1 特殊二叉树

1、斜树

所有结点都只有左子树的二叉树叫左斜树

所有结点都只有右子树的二叉树叫右斜树

2、满二叉树

所有分支节点都存在左子树和右子树，并且所有叶子都在同一层上的二叉树。

3、完全二叉树

对一棵有n个结点的二叉树按层序编号，如果编号为i的结点与同样深度的蛮二叉树中编号为i的节点在二叉树中的位置完全相同，则成全完全二叉树。

满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

完全二叉树特点：

6.2.2 二叉树的性质

1、在二叉树的第i层，至多有$<![CDATA[2^{i-1}]]>$个结点

2、深度为k的二叉树最多有2k−1个结点 版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/jiaoyangwm/article/details/80808235
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。