数据结构一把梭

点击稳过数据结构

第一章 绪论

一、数据结构包括两方面的内容

数据的逻辑结构：

数据元素之间的逻辑关系，也可以看作是从具体问题抽象出来的模型，描述操作对象之间的关系，它与数据的存储方式、位置无关。包括：（a）集合结构 （b）线性结构 （c）树形结构 （d）图形结构

数据结构的存储结构：

数据元素及其关系在计算机存储器内的表示，包括：（a）顺序存储 （b）链式存储 （c）索引存储

数据的逻辑结构与存储结构的关系：

存储结构是逻辑关系的映像与元素本身的映像。逻辑结构是数据结构的抽象，存储结构是数据结构的实现，两者综合起来建立了数据元素之间的结构关系。

二、算法

1、什么是算法

算法是对特定问题求解步骤的一种描述，是指令的有限序列

2、算法的特征

（a）有穷性 （b）确定性 （c）可行性 （d）输入：0
个多个输入 （e）输出：1个或多个输出

3、算法的设计要求

（a）正确性 （b）可读性 （c）健壮性 （d）效率与低存储量需求

4、时间复杂度

（a）事后统计方法 （b）事前分析估算方法

第二章 线性表

1、存储地址的计算

Loc(ai)=Loc(a1) + (i-1) * L

2、顺序表插入与删除

顺序表插入与删除一个元素的时间复杂度为O(n)

3、顺序表无序表

顺序表无序表合并的时间复杂度为O(ListLength(La) * ListLength(Lb))

二、链表

1、单链表

数据域-> data|next <-指针域

2、第一个结点的地址

需要存放在一个指针变量中，这个指针变量称为头指针。

3、头节点是第一个结点前引入的一个结点

头节点的数据域可以不存储任何信息

4、求单链表表长的算法

的时间复杂度为O(n)

5、单链表插入元素

若要在值为b的结点前插入一个元素，首先要找到其前驱结点，即P指针指向的结点，时间复杂度为O(n)，删除的时间复杂度也为O(n)。

6、创建链表

1）尾插法

L=(Lnod *)malloc(sizeof(Lnode));
L->next=NULL;
r=L;
scanf(&x);
while(x!=flag)
{
	s=(Lnode *)malloc(sizeof(Lnode));
	s->data=x;
	s->next=NULL;
	r-next=s;
	r=s;
	scanf(&x);
}
return L;

2）头插法

LinkList L;
L=(Lnode *)malloc(sizeof(Lnode));
L->next=NULL;
scanf(&x);
while(x!=flag)
{
	s=(Lnode *)malloc(sizeof(Lnode));
	s->data=x;
	s->next=L->next;
	L->next=s;
	scanf(&x);
}
return L;

三、单循环链表

四、双向链表

1、判空

->[指向中间][数据域][指向中间]

2、*p是双链表中的结点

*s是待插入的值为x的新结点，将*s插入到*p的前面
(1)p->prior=s (2)s->prior=p->prior (3)p->prior->next=s (4)s->next=p

3、双链表中结点的删除

(1)p->prior->next=p->next (2)p->next->prior=p->prior (3)free(p)

五、静态链表

1、一个用数组表示

的线性表L={zhao、qian…}，数组的每个分量都是一个结点，结点包括两个域，一个是数据域data，另一个是指针域next。与链表不同的是，next域中不再是链，而是一下个结点所在数组的下标，这个“指针”称为“静态指针”或游标

2、

0|NULL|1
1|zhao|2
3|sun |4
4|Li  |NULL

最后一个结点next域应该为NULL

第一个结点用一个数组下标为0的结点来指向，这个结点作为头节点

3、静态链表的插入和删除

不用移动元素，只需要改变静态指针（或者游标）即可

第三章 栈和队列

1、由于栈属于线性表

所以线性表的顺序存储和链式存储也适用于栈，分别称为顺序栈和链栈。

2、顺序栈

用指针base指示栈底元素在存储器中的位置，用指针top来指示栈顶元素在存储器中的位置，同时，用变量stacksize来指示当前栈的可用最大容量。

3、栈的链式存储表示

简称为链栈。与线性链表类似，链栈也用一组任意的存储单元来存储栈中的数据元素，栈中的每一个元素用一个结点来表示，每个结点由一个数据域和指针域组成。同时设一个指针top，用来指示栈顶元素所在的存储位置。

4、队列

只允许在一端进行插入操作，而另一端进行删除操作，只允许插入的一端称为队尾，只允许删除的一端称为队头。插入对应入队，删除对应出队。

5、用数组来作为队列元素

的基本载体结构，这是循环队列的实现模式

6、空的链队列

有一个非常明显的特征，即front指针和rear指针指向同一个地址。

第四章 数组

1、行优先

将数组按行向量排列，即第i+1行紧接在第i行存储

列优先：将数组元素按列向量排列，第i+1列紧接在第
i列后存储。

2、对称矩阵

[10  5  3 17
5  7  12 4 
3  12 20 23
17 4 23 13]

对应

 0  1  2  3  4  5  6  7  8  9
10  5  7  3 12 20 17  4 23 14

3、稀疏矩阵

将非零元素的两个下表(i,j)和非零元素值aij一起存放。得到每一非零元素对应的一个三元组(i,j,aij)，反之，一个三元组也唯一确定了一个稀疏矩阵中的一个非零元素。

第五章 树

1、树的结点

包含一个数据元素及若干指向其子树的分支。结点拥有的子树称为结点的度。度不为0的结点称为分支结点或非终端结点。

2、结点的祖先

是指从根到该结点所经分支上所有结点

3、树中结点

的最大层次值，称为树的深度或者高度。

4、在一棵树中

如果同层的兄弟结点左右互换位置，树表达的意思发生变换则该树为有序树。反之则为无序树。

5、双亲表示法

是假设以一组连续存储空间来存储树的所有节点的值，同时在每个结点中附设一个指示器指示其双亲结点在本连续空间中的下标位置。

6、孩子表示法

由于树中每个结点可能有多棵子树，因此可用多重链表，即每个结点具有多个指针域，其中每个指针指向一个孩子结点。

7、孩子兄弟表示法

孩子兄弟表示法又称二叉树表示法，或者二叉链表表示法，即以二叉链表作为树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子和下一个兄弟。

8、二叉树的性质

1、在二叉树中的第i层

至多有2的i-1次方个结点

2、深度为k的二叉树

至多有2的k次方-1个结点

3、对任何一颗二叉树T，

如果其终端结点树为n0，度为2的结点树为n2，则有n0=n2+1

9、设B为二叉树的边的总数目

根据树的基本性质，对于任意一棵多叉树，边和结点的数目关系始终满足：n=B+1

10、B=n1+2*n2

11、一棵深度为K、有n个结点的二叉树

称为满二叉树（没有度数为1的结点）

12、深度为k、有n个结点的二叉树

当且仅当其每个结点都如深度为K的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树

13、具有n个结点的完全二叉树的深度为

[lbn]+1

14、如果对一棵有n个结点

的完全二叉树的结点，按层序编号（从第一层到第[lbn]+1层），对任一结点i（1<=i<=n），有

1、如果i=1；

则结点i是二叉树的根，没有双亲，如果i>1，则其双亲结点编号为[i/2]

2、 如果2i=m，则

结点i没有左孩子，否则其左孩子编号必为2i

3、如果2i+1>n，则

结点没有右孩子，否则其右孩子编号必为2i+1

15、反推二叉树结构

1、在前序遍历序列

/子序列中，第一个结点时该树/子树的根结点

2、在中序遍历中/子序列中

该树的根节点在其左右子树中序序列之间

3、在后序遍历中

最后一个结点是该子树的根结点

16、指向结点前驱

和后继的指针叫做线索，加上线索的二叉链表叫做线索链表，加上线索的二叉树称为线索二叉树

17、树转换为二叉树

1、加线。

在所有兄弟结点之间加一条连线。注意，只是在亲兄弟之间加

2、去线

对树中每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的线

3、现状调整

长子连线为左孩子，兄弟连线为右孩子

18、森林转为二叉树

1、把每一棵树

分别转换为二叉树

2、从最右边

的每一棵二叉树往左，依次把右边二叉树的根结点作为左边一棵二叉树的根节点的右孩子

19、二叉树转换为树

1、加线

若其结点的左孩子结点存在，则将这个左孩子的右节点，右孩子的右节点连接起来

2、去线

删除原二叉树中所有节点与其右孩子的连线

二 哈夫曼树及其应用

1、哈夫曼树

又称最优二叉树，是一种带权路径长度最短的树

2、从树中一个结点

到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数组称为路径长度。树的路径长度是从树根到每一个结点的路径之和

3

1、叶子上的权值均相同时

完全二叉树一定是哈夫曼树，若叶子的权值不相同，则完全二叉树不一定是哈夫曼树。

2、在哈夫曼树中

权值较大的叶子离根的距离小于或等于权值较小的叶子离根的距离

3、哈夫曼树中

没有度为1的结点，即n1=0

4、哈夫曼树是无序树，左右可随意互换，

甚至树高也不唯一，只要该树的WPL值等于最小值即可

5、对一一棵有n个叶子结点

的哈夫曼树，其结点总数为n0+n1+n2=2*n2+1

第六章 图

1、在图中

我们把数据元素叫做顶点，图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为G(V,E)，其中G表示一个图，V是图中顶点的集合，E是图中连线的集合。E可以为空，但V不能为空。

2、

弧尾端 i -> j 弧头端

3、顶点Vi

的度是和Vi相关联的边的数目

4、如果无向图中

任意两个顶点都是连通的，则称G是连通图。

5、连通分量

是指无向图中极大连通子图

6、在有向图G中

任意从Vi到Vj都存在路径，则称G是强连通图

7、在有向图中

如果任意两个顶点之间都存在方向互为相反的两条弧，则称为有向完全图

8、带权的图

通常称为网

9、无向图中连接n个结点的n-1条边

构成了生成树。有向图中若干棵有向树连接n个结点，且总共具有n-1条弧，构成了生成森林

二、图的存储结构

1)、邻接表表述方法

1、带权

使用无限大的符号表示无出度

2、邻接表/逆邻接表表示法

3、邻接表避免了

邻接矩阵中的空间过度浪费，在有向图中，邻接表很方便获知某个顶点的出度，而在无向图中，这个值就是顶点度。

4、十字链表表示法

邻接表和逆邻接表的结合使用

三、图的遍历

1、深度优先遍历

（1）、访问任意一个顶点

（2）、访问该顶点的任意一个邻接点

（3）、访问步骤（2）中所选取的邻接点的任意一个邻接点

（4）、访问步骤（3）中所选取的任意一个邻接点

2、广度优先遍历

（1）、访问任意一个顶点

（2）、访问该顶点的所有邻接点

（3）、访问该顶点所有邻接点的所有邻接点

四、最小生成树

1、一个连通图的生成树

是一个极小的连通子图，它含有图中所有的顶点，但只有n-1条边，恰好将这n个顶点连通。

2、普利姆（Prim）算法

算法复杂度为O(n的平方)

（1）、任意选择一个顶点

（2）、选择该点最小权所连通的顶点

（3）、选择这两个点最小权所连通的顶点

3、克鲁斯卡尔（Kruskal）算法

（1）、找到权值最小的路径

（2）、找到次小路径

（3）、找到次次小路径

五、有向无环图及其应用

1、在一个表示工程的有向图中、

用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为AVOV网

2、设G=(V,E)是一个具有

n个顶点的有向网，V中的顶点序列为V1，V2，…Vn，假设活动Vi是活动Vj的前驱活动，则在顶点序列中顶点Vi必定在顶点Vj的前面。如果满足这样的条件，则称这样的顶点序列为一个拓扑序列。

3、拓扑排序

就是对一个有向图构造拓扑序列的过程

4、对AOV图进行拓扑

的具体方法是每次从AOV图中选择一个入度为0的顶点，输出，然后删除此顶点及所有与它相关的弧，重复上述操作

5、用弧表示每个步骤环节的活动

用顶点来表示步骤环节开始或者结束时刻的状态，而弧上的权值则表示该活动进行所需要的时间，由此构成了边表示活动的有向图

6、Vi的最早呈现时间Ve(i)

（1）、始点的Ve(i)值为0，即Ve(Vbegin)=0

（2）、如果Vi的入度为1，则Ve(i)=Ve(left)+dut(left,i)，上一个值加权

（3）、如果Vi的入度大于1，则Ve(i)=max{Ve(left(k)+dut(left,i)}

7、Vi的最晚呈现时间Vl(i)

（1）、Vl(vend)=Ve(Vend)=T

（2）、如果Vi的出度为1，则Vl(i)=Vl(right)-dut(i,right)

（3）、如果Vi的入度大于1，则Ve(i)=min{Vl(right)-dut(i,right)}

8、当Vi=Vl时，为关键路径

六、最短路径

1、最短路径

是指两个顶点之间所经过的边/弧上权值之后最小的路径

2、Dijkstra算法

时间复杂度为O(n的平方)

第七章 查找

1、顺序查找的查找成功的平均查找长度

为(n+1)/2，时间复杂度为O(n)。

2、折半查找

int Binary_Search(int data[],int n,int k)
{
	int low,high,mid;
	low=0;high=n-1;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(k<data[mid])
			high=mid-1;
		else 
			low=mid+1;
		else 
			return mid;
	}
	return 0;
}

折半查找的平均查找长度为((n+1)/n)lb(n+1)-1

当n>50时，可有近似结果ln(n+1)-1

折半查找主要应用在有序表中而顺序查找主要应用在无序表中

时间复杂度为O(lbn)

3、索引表的查找

时间复杂度为O(n的二分之一次方)

4、稠密索引

索引项一定是按照关键字有序的排列

5、分块索引

（1）、块内无序

（2）、块间有序

6、二叉排序树

（1）、若它的左子树不空，则左子树上所有结点的值均小于它的根节点的值

（2）、若它的右子树不空，则右子树上所有结点的值均大于他的根结点的值

（3）、它的左、右子树也分别为二叉排序树

构造一棵二叉排序树的目的，其实并不是为了排序，而是为了提高茶查找、插入和删除关键字的速度。

7、平衡二叉树

是一种二叉排序树，其中每个结点的左子树和右子树的高度差的绝对值不超过1.

8、哈希查找

哈希查找又称为散列表查找

哈希函数的构造方法

（1）、计算简单

所以焊锡函数的时间复杂度不应该大于其他查找技术

（2）、散列地址分布均匀

1、直接定址法

f(key)=a * key + b，要求查找表取值范围很小而且实际存储的数据存储基本上是按关键字连续的

2、数字分析法

如关键字为数字型，位数较长，其中若干位分布比较均匀，而其他位数变化较少

3、折叠法

用于事先不知道关键字分布，且位数较多的情况（学校10年来找80个学生）

4、除留取余法

Hash(key)=key mod p (p<=m) p选择为小于或等于len的一个质数

9、处理哈希冲突的方法

####（1）、开放定址法
Hi=(Hash(key)+di) mod m m:哈希表长

（2）、再哈希法

事先准备另外一套备用的哈希函数

（3）、链地址法

冲突的元素用单链表进行链接

（4）、公共溢出区法

冲突的另开一处区域

10、哈希查找是本章介绍的所有查找方法中效率最高的，可到O(c)

第八章 排序

1、直接插入排序

2、希尔排序

以5，3，1间隔比较

3、冒泡排序

4、快速排序

先比后面，再比前面，平均时间复杂度O(nlbn)，最坏为O(n的平方)

5、简单排序法

依次选取最小的、次小的、、、、与相对应的元素所在的位置互换

6、堆排序

是一棵完全二叉树，大堆顶、小堆顶

7、归并排序

分为几个部分

8、基数排序

先按个位排、再按10位拍、再按百位排。