数据结构总结

数据结构总结

一、 绪论

数据：对客观实物的符号表示，在计算机科学中指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据项：是数据的不可分割的最小单位。

数据对象：性质相同的数据元素的集合，是数据的一个子集。

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

逻辑结构：结构中的关系的描述的是数据元素之间的逻辑关系

存储结构：数据结构在计算机中的表示也叫数据的物理结构，

位：计算机中表示信息的最小单元

映像存储 的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。

非映像存储的特点是：借助指示元素存储地址的指针表示数据元素之间的逻辑关系。

数据类型：是一个值得集合和定义在这个值集的一组操作的总称。

数据类型可非为两类：

非结构的原子类型，原子类型的值是不可分解的，例如实型 指针型等。

结构类型：值是可以分解的，成分可以是结构的也可以是非结构的。可以看成是由一种数据结构和定义在其上的一组操作组成。

注：逻辑运算的约定。

与运算：对于A 与B ，当A 的值为0时，不再对B 求值。

或运算：对于A 或B ，当A 的值为非0时，不在对B 求值。

算法的五个重要特性：

1. 有穷行

2. 确定性

3. 可行性

4. 输入

5. 输出

算法设计的要求：

1. 正确性。程序不含语法错误等

2. 可读性。

3. 健壮性。

4. 效率与地存储量需求。 语句的频度是指该语句重复执行的次数。

二 线性表

线性表 List ：最常用且最简单的数据结构。

含有大量记录的线性表称为文件。

常把数据元素称为记录。

1 线性表顺序存储的表示和实现

线性表的顺序表示：用一组地址连续的存储单元一次存储线性表的数据元素。

线性表第i 个数据元素的存储地址为

LOC （ai ）=LOC（a1）+（i-1）*l

----------线性表的动态分配顺序存储结构------------

#define LIST_INIT_SIZE 100//线性表存储空间的初始分配量

#define LISTINCREMENT 10//线性表存储空间的分配增量

Typedef struct{

Elemtype *elem//存储空间基址

int length；//当前长度

int listsize；//当前非配存储容量

}sqlist；

表长为n 时，线性表进行插入和删除操作的时间复杂度为O （n ）‘

插入一个元素时大约移动表中的一半元素。

删除一个元素时大约移动表中的（n-1）\2

2 线性表的链式表示和实现

结点分为两个域：数据域（存储数据元素信息的域）和指针域（存储直接后继存储位置的域）。

链表：n 个结点链接成

不带头结点的空表判定为 L= =null

带头结点的空表判定为 L->next= =null

循环单链表为空的判定条件为 L.next= =L

线性链表的最后一个结点的指针为NULL

头结点的数据域为空，指针域指向第一个元素的指针。

两个结点中插入结点指针操作为

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

删除三个结点中的中间结点

p->next=p->next->next

先确定前驱指针 在确定后继指针

系统生成一个LNode 型结点的操作

P=（LinkList ）malloc （sizeof （LNode ））；

回收一个LNode 型结点的操作

Free(Q);

静态链表 用数组描述的链表。

循环链表 特点是表中的最后一个结点的指针域指向头结点，整个链表成一个环。 双向链表 有两个指针域，其一指向直接前驱，另一个指向直接后继。 链队列：用链表示的队列

队头指针 front 队尾指针rear

空队列的表示形式 front=rear=0

头指针始终指向队列头元素

尾指针始终指向队列尾元素的下一个位置。

循环队列中Q.front=Q.rear无法判断队列空间是空还是满。

处理方法

1 另设一个标志位以区别队列是空还是满。

2 少用一个元素空间，约定以“队列头指针在队尾指针在下一位置上”作为队列

呈满状态的标志。

顺序表和链表的比较

1 基本空间的考虑 存储密度是指节点数据本身所占的存储量除以结点结构所占的存储总量所得的值。值越大存储空间利用率越高。

顺序表是静态分配的，存储密度为1

链表是动态分配的，存储密度小于1

2顺序表适用于静态查找，要进行删除和插入操作时，需移动大量结点。 链表适用于做动态的插入和删除。

三 栈和队列

1 栈

栈：限定仅在表尾进行插入或删除操作的线性表。

栈顶：表尾端

栈底：表头

栈是先进后出的线性表。

插入栈顶元素称为入栈，删除栈顶元素称为出栈。

Top 指针指向栈顶的下一个位置 base 始终指向栈底

Top=0时栈为空

Top=base 时栈也为空

2 队列 queue

先进先出的线性表。

队尾入队 对头出队

允许插入的一端叫做队尾

允许删除的一端叫做对头

队空的条件为 q->front=q->rear

队满的条件为 q->front==(q->rear+1)%Queuesize

队列长度为 （q->rear+queuesize- q->front）%queuesize

循环队列判断队空的条件为 front=rear

循环队列判断队满的条件为 （rear+1）%m=front

在一个循环队列中删除元素时，首先需要后移队首指针。

向一个顺序表插入一个元素时，首先使栈顶指针后移一个位置，然后把新元素插入到这个位置。

在一个栈删除元素时，首先取出栈顶元素，然后栈顶指针减一。

在顺序栈中村粗与一维数组a 【m 】栈顶指针 top=-1时则为空栈。

当top=m-1时为满栈。

在一个循环队列中队首指针指向队首元素的前一个位置。

四 串

串：由零个或多个字符组成的有序序列。

串的长度：串中字符的数目n 。

空串：零个字符的串。

串的相等：两个串的长度相等，各个对应位置的字符都相等。

空格串：又一个或多个组成的串‘’

串的存储方式

1. 定长顺序存储

2. 堆分配存储

3. 串的块链存储

串和线性表逻辑结构极为相似，只是串的数据对象约束为字符集。

堆分配存储特点 一组地址连续的存储单元存放串值字符序列，但他们的存储空间是在程序执行过程中动态分配而得。

五 数组

1 数组array

数组由于一般不作插入或者删除操作，适合用顺序存储结构。

数组用顺序表存储时一般以行序为主序。

二维数组中任意一个元素aij 的位置课表达为

LOC （i ，j ）=LOC（0,0）+（b2*i+j）L

//-------------------数组的顺序存储表示————//

#include

#define MAX_ARRAY_DIM 8 //假设数组维数的最大值为8

Typedef struct {

Elemtype *base //数组元素基址，由initarray 分配

int dim ； //数组维数

int *bounds； //数组维界基址，由initarray 分配

int *constant； //数组映像函数常量基址，由initarray 分配

}array；

2 矩阵的压缩存储

压缩存储：为多个值相同的元只分配一个存储空间；对零元不分配存储空间。 特殊矩阵：值相同的元素或者零元素在矩阵中的分布有一定的规律

稀疏矩阵（sparsematrix ）：反之。

稀疏矩阵的压缩存储方法：

1 三元组顺序表

三元组中的数据元素以行序为主序进行排列。

三元组行列的置换方法。

（一） 按照b.data 中三元组的次序一次在a.data 中找到相应的三元组进

行转置。就是按照矩阵mde 列序进行转置，为了找到M 的每一

列中所有的非零元素，需要对其三元组表a.data 从第一行起整个

扫描一遍，a.data 是以m 的行序为主序来存放每个非零元的，由

此得到b.data 应有的顺序。当tu

（mu*nu）

（二） 按照a.data 中三元组的次序转置，并将转置后的三元组置入b 中

恰当的位置。如果预先确定矩阵M 中每一列的第一个非零元在

b.data 中应有的位置，那么在对a.data 中的三元组依次作转置时，

便可直接放到b.data 中恰当的位置上去。为了确定这些位置，在

转置前，应先求得M 的每一列中的非零元的个数，进而求得每

一列的每一个非零元在b.data 中应有的位置。时间复杂度为O

（nu+tu） 当tu 和mu*nu通数量级时 O （mu*nu）

2 行逻辑链接顺序表

3 十字链表

3 广义表存储结构

广义表的深度：括号嵌套的最大次数。

广义表：多个线性表的结合

广义表中的ai 是单个元素则成为原子

广义表中的ai 是广义表则成为字表。

当广义表非空时，第一个元素a1为广义表的表头（head ）

除去a1的其他元素组成的表成为广义表的表尾（tail ）

广义表的三个重要结论

一 列表的元素可以是子表，而子表的元素还可以是子表。

二 列表可为按其他列表所共享。

三 列表可以是一个递归表，列表可以是其本身的一个子表。

广义表采用链式存储结构，每个数据元素可以用一个结点表示。

六 树和二叉树

树的结点：包含一个数据元素及若干个指向其子树的分支

结点的度：结点拥有的子树数

叶子结点：度为0的结点

结点的层次：从根开始 根为第一层

堂兄弟：双亲的在同一层的结点

深度或高度：树中结点最大层次

结点的祖先：从根到该节点所经分支上的所有结点。

子孙：某结点为根的子树中的任意一结点

有序树：将树中结点的个子树看成从左到右是有次序的（不能互换） 有序数的最左边的子树称为第一个孩子，最右边的称为最后一个孩子。 无序树：反之。

森林：m 棵互不相交的树的集合。

二叉树（Bitree ）：特点是每个结点至多只有两棵子树，并且，二叉树的子树有左右之分，其次序不能任意颠倒。

二叉树的性质

1. 在二叉树的i 层上至多有2^i-1个结点。

2. 深度为k 的二叉树至多有2^k-1个结点。

3. 任何一颗二叉树终端结点数为n0，度为2的结点数为n2，则n0=n2+1

4. 有n 个结点的完全二叉树的深度为lbn+1.

满二叉树：一颗深度为k 且又2^k-1个结点的二叉树。

完全二叉树：深度为k 时，有n 个结点的二叉树，当且仅当其每一个结点都与深度为k 的满二叉树中编号从1至n 的结点一一对应。

二叉树的顺序存储结构仅适用于完全二叉树。

二叉树遍历的时间复杂度是O （n ）

线索链表：有两个标志域的二叉链表。

线索：指向结点前驱和后继的指针。

线索化：对二叉树以某种次序遍历使其变为二叉树的过程。

线索二叉树是物理结构。

实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用三叉链表结构。

单独用先序或者中序遍历都无法确定唯一的二叉树。

一棵树转化成二叉树的过程：

1 在所有兄弟结点间接一条线

2 对于每个结点，除了保留与长子的连线外，去掉该节点和其他子结点的连接。 路径长度：路径上分支数目。

树的路径长度：从树根到每一个结点的路径长度之和。

节点的带权路径长度：该结点到树根之间的路径长度与结点上权的乘积。 树的带权路径长度：树中所有叶子结点的带权路径长度之和。

赫夫曼树（最优二叉树）带权路径长度最小的二叉树。

赫夫曼树的构造：

1 根据给定的n 个权值，构成n 棵二叉树的集合F={Ti，T2，T3，。。。，Tn}，其中每个二叉树中只有一个带权为wi 的根结点，其左右子树均为空。

2 在F 中选取两颗根结点的权值最小的数作为左右子树构成一颗新的二叉树。且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。 3 在F 中删除这两颗树，同时将新得到的二叉树加入F 中。

4 重复2，3直到F 只含一棵树为止。这便是赫夫曼树。

七 图

顶点：图中的数据元素。

表示从v 到w 的一条弧。v 称为弧尾或初始点，w 为弧头或终端点。此时的图称为有向图。

完全图：有1\2 n(n-1)条变得无向图

有向完全图：具有n （n-1）条弧的有向图。

权：与图的边或弧相关的数。

顶点v 的度：和v 相关联的边的数目。

入度：以顶点v 为头的弧的数目

出度：以顶点v 为尾的弧的数目

回路或环：第一个顶点和最后一个顶点相同的路径。

简单路径：序列中顶点不重复出现的路径。

图没有顺序存储结构。

1 数组表示法

2 邻接表 优点容易找到任意顶点的第一个邻接点和下一个邻接点。

3 十字链表 优点容易找到vi 为尾的弧，也容易找到vi 为头的弧，因而容易求得顶点的出度和入度。时间复杂度与建立邻接表是相同的。

缺点 每条边的顶点都在不同的链表中，对边进行操作时不方便。

4 邻接多重表

深度优先搜索：类似于树的先根遍历。

从某个顶点出发访问此顶点，然后依次从v 的未被访问的邻接点出发深度优先遍历图，知道图中所有与v 有路径相同的顶点都被访问到。若图中还有顶点未被访问，则再选一个图中未被访问的顶点重复上述操作。

广度优先搜索：类似于树的按层次遍历从图中某点出发，访问v 之后依次访问v 的各个未曾访问的邻接点，然后分别从这些邻接点出发依次访问它们的邻接

点，若还有顶点未被访问则另选一个为被访问的点进行以上操作。

普利姆算法的时间复杂度是O （n^2）适用于稠密图

克鲁斯卡尔算法的时间复杂度是 O(elbe)适用于稀疏图

拓扑排序方法

1从有向图中选一个没有前驱的顶点且输出之。

2 从图中删除该顶点和所有以他为尾的弧。

重复上述两个步骤 知道所有顶点全部输出，或者图中不存在没有前驱的顶点位置，后一种情况说明有向图中存在环。

关键路径：路径长度（路径上各种活动持续时间之和）最长的路径

关键路径是事件结点网络中的从源点到汇点的最长距离

最短路径

地杰斯特拉算法的时间复杂度为O （n^2）

弗洛伊德算法的时间复杂度为O （n^3）

九 查找

查找表：同一类数据元素构成的集合。

静态查找表：对查找表只作查找操作的查找表。

动态查找表：查找过程中同时插入表中不含的元素，或者删除查找表中已有的元素的操作的查找表。

关键字：数据元素中某个数据项的值，用它可以标识一个数据元素。 主关键字：此关键字可以唯一的标识一个记录。

此关键字：用以标识若干记录的关键字。

一 顺序查找：从表中的最后一个记录开始，逐个进行记录的关键字和给定值比较，若相等则查找成功，不等则查找失败。

平均查找长度：为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度。

等概率情况下 顺序表的平均查找长度为：n+1\2

等概率下 顺序表查找不成功的平均查找长度是 3（n+1）\4

二 有序表查找

1 折半查找：先确定待查记录所在的范围，然后逐步缩小范围直到找到或找不到该记录为止。

概率相等时折半查找的平均查找长度为

当n>50时平均查找长度为 lb （n+1）-1

折半查找只适用于有序表并且是顺序存储结构。

查找长度为n 的线性表时时平均每个元素的平均查找长度为O （lbn ）。 2 斐波那契查找

平均性能比折半查找好，最坏情况下的性能比折半查找差。

3插值查找

只适用于关键字均匀分布的表。

三 索引顺序表查找

索引顺序表查找又称分块查找。

索引表包含两项内容：

1 关键字项 2指针项

索引表按关键字有序，则表或者有序或者分块有序。

分块有序:第二个子表中所有记录的关键字均大于第一个子表中的最大关键字，第三类子表中的所有关键字均大于第二个子表中的关键字

四 动态查找表

二叉排序树(二叉查找树) ：或者是一颗空树。或者如下1若它的左子树不空，则左子树上所有的结点的值均小于他的根结点的值。2若右子树不空，则右子树所有结点的值均大于她得根结点的值。3 左右子树也分别为二叉排序树。 二叉排序树平均查找长度最坏情况是 （n+1）\2

二叉排序树平均查找长度最好情况是 lbn

平衡二叉树：或者是一棵空树。或者 它的左右子树都是平衡二叉树，且左子树和右子树的深度只差的绝对值不超过1。

平衡因子：该结点的左子树的深度减去右子树的深度，只可能为1，0，-1。 平衡树上进行查找的时间复杂度为O （lbn ）。

二叉排序树是动态树表。最优或次优查找树是静态数表。

五 B-树和B+树

B-树的特性。

1 树中每个结点至多有m 棵子树

2若根结点不是叶子结点，则至少有两棵子树

3 除根结点之外的所有非终端结点至少有m\2棵子树

4所有非终端结点中包含下列信息

（n ，A0，K1，A1，K2，A2，…..,Kn,An ）

其中ki （i=1，….,n ）为关键字，且ki

5 所有叶子结点都出现在同一层上，并且不带信息。

B+树的特点

1 有n 棵子树的结点中含有n 个关键字

2 所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。

3 所有的非终端结点可以看成是索引部分，结点中仅含有其子树中最大的关键字。

六 哈希表

哈希表的建法

1直接定值法

哈希函数为关键字的线性函数

H （key ）=key或者H （key ）=a*key+b

仅限于 地址集合大小等于关键字大小

无冲突 限制条件比较多

2 数字分析法

假设关键字集合中的每个关键字都是由s 位数字组成（k1，k2

，….,kn ）分析关键字集中的全体，并从中提取分布均匀的若干位或他们的组合作为地址。

仅限于：能预先估计出罐体关键字的每一位上各个数字出现的频度。

3 平方取中法

若关键字的每一位都是某些数字的重复出现，出现频度很高的现象，则先求关键字的平方值，以通过平方扩大差别，同时平方值的中间几位受到整个关键字中各位的影响。

4 折叠法

若关键字的位数特别多，则可将其分割成几部分，然后取他们的折叠和为哈希地址。有移动叠加和间接叠加两种方法.

5 除留余数法

H （key ）=key mod p p

P 应为不大于m 的质数或是不含二十以下的质因子。

6 随机数法

H （key ）=random（key ）

造表的总原则是使产生冲突的可能性降到尽可能小。

处理冲突的含义：为差生冲突的地址寻找下一个地址。

哈希表只能减少冲突不能避免冲突。

处理冲突的方法

1 开放定址法

一 线性探测在散列

容易产生二次冲突

二 平方探测在散列

三随机探测在散列

2 分链地址法

将所有哈希地址相同的几句都放在同意链表中

不会产生二次冲突。

哈希链表的平均查找长度与元素的个数无关

只与装填因子有关

十 内部排序

排序：将一个数据元素的任意序列，重新排列成一个按关键字有序的的序列。 排序是稳定的：关键字相等的两个记录排序前后的顺序没有改变。

内部排序：待排序记录存放在计算机随机存储器中进行排序的过程。 外部排序：需要对外存进行访问的排序。

一 直接查序排序

将一个记录插入到已排好序的有序表，从而得到一个新的，记录数增一的有序表。 操作：每次从有序表中取一个元素，把他插在有序表的合适位置，使有序表仍有序。第一趟讲待比较的数值与他前一个数值进行比较，当前一个待比较数值大的情况下继续循环比较，一次进行下去，进行（n-1）趟扫描以后完成整个排序，结束该次循环。

时间复杂度是O （n^2）

二 折半插入排序

使用折半查找来实现，所需存储空间和直接插入排序相同，从时间上比较，折半查找仅减少了关键字间的比较次数，而移动距离不表。

时间复杂度为O （n^2）

三 2路插入排序

特点减少移动记录的次数，但不能避免移动记录。

四 表插入记录

特点不需要移动数据记录，只改变存储结构。

排序之后调整记录序列，算法用了三个指针。

P 指示第i 个记录的当前位置

I 指示第i 个记录应该在的位置

Q 指示第i+1个记录的当前位置。

五 希尔排序

减少了关键字比较次数，也减少了记录的移动。

基本思想：先将整个待排序记录序列分成为若干个子序列分别进行直接插入排序，待整个序列中的记录 基本有序 时在对全体序列进行一次直接插入排序，子序列的构成不是简单的逐段分割，而是将像个某个增量的记录组成一个子序列。 增量序列的选取的注意事项：应使增量序列中的值没有除以一之外的公因子，并且最后一个增量值必须等于一。

六 起泡排序

借助交换进行排序，首先要将第一个记录的关键字和第二个记录的关键字比较，若为逆序，将两个记录交换，以此类推，直到第n-1个记录和第n 个记录比较位置。这个过程是第一趟气泡排序，其结果是将关键字最大的记录放在最后。然后进行第二趟起泡排序，对N-1个记录进行同样的操作。以此类推，直到再一次排序中没有进行交换的记录为止。

最好情况一趟排序 比较次数n-1 移动记录次数 0

最坏情况n-1趟排序比较次数n （n-1）\2 移动记录次数 3n （n-1）\2

七 快速排序

通过一趟排序讲待排序记录分割成两个部分，，一部分关键字均比另一部分关键字小，对这两部分继续排序。假设连个指针low 和high 初值分别指向第一个数据和最后一个数据，将枢轴记录暂时存放在R 【0】的位置上，排序过程中只作R 【low 】和R 【high 】的单向移动，直到一趟排序结束后在将枢轴移到正确位置，其他部分同时进行快速排序。

就平均时间而言快速排序是最好的一种内部排序方法。

八 简单选择排序

每一趟在n-i+1(i=1,2，，。。。，n) 个记录中选取关键字最小的记录作为有序序列的第i 个记录，第i 趟简单排序是通过n-1次关键字比较，从n-i+1个关键字中选取关键字最小的记录，并和第i 个记录进行交换，共进行n-1次比较。

无论记录的初始排列如何，所需进行的关键字比较次数相同，始终是n （n-1）\2

九 堆排序

适用于记录数很大的序列

堆排序：只需要一个记录大小的辅助空间，每个待排序的记录占有一个存储空间。 始终满足 ki=

操作方法：先将文件R[1……n]建成一个大根堆，此堆初始为无序区，再降关键字最大记录R 【1】和无序区最后记录R 【n 】交换，得到新的无序区R 【1…n-1】和有序区R 【n 】，满足R 【1…n-1】.key

将无序区R[1…n-1]调整为堆，再将R[1….n-1]中关键字最大的记录和R 【n-1】

交换，得到新的无序区R 【1…n-2】和新的有序区R 【n-1】，

满足R 【1…n-2】.key

核心操作：一维数组中前后相邻的两个有序序列归并为一个有序序列。 算法较简洁，实用性很差，最大的特点是一个稳定的排序方法。 十一 基数排序

主要特点不需要进行关键字间的比较。 多关键字排序：

最高为优先（MSD 法）从主关键字开始排序，再从次高位排序，一次类推，最后将所有子序列依次连接在一起成为一个有序序列。

最低位优先（LSD 法）从最次位关键字开始排序，在对高一位的进行排序，直

注：当序列基本有序和n 比较小时一般使用直接插入排序。 N 较大时一般使用堆排序。

简单选择排序，堆排序，归并排序的时间性能不随关键字的分部而改变。考虑变坏的情况时一般使用堆排序和归并排序。 归并排序空间复杂度最高

除基数排序外，其他方法可能达到最快的时间复杂度为O （nlbn ）

平均比较次数最少的排序是快速排序。 内存容量最多的是 基数排序

简单排序包括希尔排序之外的所有插入排序，起泡排序和简单排序，其中以直接插入排序最简单，同时直接插入排序也是当记录基本有序，n 较小时最佳排序方法。