数据结构图总结(五篇)

本文格式为Word版，下载可任意编辑——数据结构图总结(五篇)当工作或学习进行到一定阶段或告一段落时，需要回过头来对所做的工作认真地分析研究一下，确定成绩，找出问题，归纳出经验教训，提高认识，明确方向，以便进一步做好工作，并把这些用文字表述出来，就叫做总结。怎样写总结才更能起到其作用呢？总结应当怎么写呢？下面是我为大家带来的总结书优秀范文，希望大家可以喜欢。

key)f-lchild=p;数据结构图总结篇三

数据结构参考题目

一、选择

1.假使在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（）

a.栈b.队列c.树d.图2.下面程序段的时间繁杂度为（）for(i=0;inext=hl;b.p-next=hl;hl=p;c.p-next=hl;p=hl;d.p-next=hl-next;hl-next=p;4.两个字符串相等的条件是（）

c.都是非空串d.串的长度相等且对应的字符一致5．若以s和x分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（）

xxsxsxxx6.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（）a.0b.1c.48d.497.已知用某种排序方法对关键字序列（51，35，93，24，13，68，56，42，77）进行排序时，前两趟排序的结果为

（35，51，24，13，68，56，42，77，93）

（35，24，13，51，56，42，68，77，93）所采用的排序方法是（）

a.插入排序b.冒泡排序c.快速排序d.归并排序

8.已知散列表的存储空间为t[0..16]，散列函数h（key）=key%17,并用二次探测法处理冲突。散列表中已插入以下关键字：t[5]=39，t[6]=57和t[7]=7，则下一个关键字23插入的位置是（）

a.t[2]b.t[4]c.t[8]d.t[10]9.假使将矩阵an×n的每一列看成一个子表，整个矩阵看成是一个广义表l，即l=((a11,a21,…,an1),(a12,a22,…,an2),…，（a1n,a2n,…,ann）),并且可以通过求表头head和求表尾tail的运算求取矩阵中的每一个元素，则求得a21的运算是（）(tail(head(l)))(head(head(l)))(head(tail(l)))(head(tail(l)))10.在一个具有n个顶点的有向图中，所有顶点的出度之和为dout，则所有顶点的入度之和为（）

-1+1d.n11．从规律关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（）a线性结构b.树形结构c.线性结构和树型结构d.线性结构和图状结构

12．栈的插入和删除操作在()进行。

a．栈顶b.栈底c.任意位置d指定位置13．由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）a.24b.71c.48d.5314．一个栈的输入序列为123，则以下序列中不可能是栈的输出序列的是()a.231b.321c.312d.12315．关于栈和队列的说法中正确的是（）

a．栈和队列都是线性结构b.栈是线性结构，队列不是线性结构c.栈不是线性结构，队列是线性结构d.栈和队列都不是线性结构16．关于存储一致数据元素的说法中正确的是（）a．顺序存储比链式存储少占空间b.顺序存储比链式存储多占空间

c.顺序存储和链式存储都要求占用整块存储空间d.链式存储比顺序存储难于扩展空间

17．已知一个单链表中，指针q指向指针p的前趋结点，若在指针q所指结点和指针p所指结点之间插入指针s所指结点，则需执行（）a.q→next=s；p→next=s；b.q→next=s；s→next=p；c.q→next=s；q→next=p；d.q→next=s；s→next=q；

18．设一组记录的关键字key值为{62，50，14，27，19，35，47，56，83}，散列函数为h(key)=keymod13，则它的开散列表中散列地址为1的链中的结点个数是（）a.1b.2c.3d.419．执行下面程序段时，s语句被执行的次数为：（）for(inti=1;i=n;i++)for(intj=1;j=i;j++)s;a.n*nb.n*n/2c.n(n+1)d.n(n+1)/220．在长度为n的线性表中删除一个指针p所指结点的时间繁杂度是（）a．o(n)b.o(1)c.o(log2n)d.o(n2)21．设一个栈的输入序列是a，b，c，d，则所得到的输出序列（输入过程中允许出栈）不可能出现的是（）

a.a，b，c，db.a，b，d，cc.d，c，b，ad.c，d，a，b22．关于串的表达中，正确的是（）a．空串是只含有零个字符的串b.空串是只含有空格字符的串

c.空串是含有零个字符或含有空格字符的串

d.串是含有一个或多个字符的有穷序列

23．在具有m个单元的循环队列中，队头指针为front，队尾指针为rear，则队满的条件是（）

a．front==rear

b.(front+1)%m==rear

+1==front

d.(rear+1)%m==front24．设有二维数组

1a［n］［n］表示如下：23456，则a［i］［i］（0≤i≤n-1）的d.i2/2值为（）

a．i*(i-1)/2b.i*(i+1)/2c.(i+2)*(i+1)/225．高度为h的完全二叉树中，结点数最多为（）

ha．2h-1b.2h+1c.2-1d.2h26．由m棵结点数为n的树组成的森林，将其转化为一棵二叉树，则该二叉树中根结点的右子树上具有的结点个数是（）

-1c.n(m-1)d.m(n-1)27．在一个具有n个顶点的无向图中，每个顶点度的最大值为（）a.nb.n-1c.n+1d.2(n-1)28．关于无向图的邻接矩阵的说法中正确的是（）a.矩阵中非全零元素的行数等于图中的顶点数

b.第i行上与第i列上非零元素总和等于顶点vi的度数c.矩阵中的非零元素个数等于图的边数

d.第i行上非零元素个数和第i列上非零元素个数一定相等

29．设一组记录的关键字key值为{62，50，14，28，19，35，47，56，83}，散列函数为h(key)=keymod13，则它的开散列表中散列地址为1的链中的结点个数是（）a.1b.2c.3d.430．设有一组初始关键字值序列为（49，81，55，36，44，88），则利用快速排序的方法，以第一个关键字值为基准得到的一次划分为（）

a.36，44，49，55，81，88b.44，36，49，55，81，88c.44，36，49，81，55，88d.44，36，49，55，88，81

二、填空题

1.数据是计算机加工处理的对象（）。2.数据结构的概念包括数据的规律结构、数据在计算机中的存储方式和数据的运算三个方面()。

3.线性表是由n≥0个一致类型组成的有限序列（）。4.栈是一种后进先出的线性表（）。

5.从循环链表的某一结点出发，只能找到它的后继结点，不能找到它的前驱结点（）。6.单链表设置头结点的目的是为了简化运算（）。7.树的最大特点是一对多的层次结构（）。8.组成数据的基本单位称为数据元素（）。

9.从非循环链表的某一结点出发，既能找到它的后继结点，又能找到它的前驱结点（）。

10.单链表结点的指针域是用来存放其直接后继结点的首地址的（）

11.数据的存储结构是数据的规律结构的存储映象（）。

12.用顺序表来存储线性表时，不需要另外开拓空间来保存数据元素之间的相互关系（）。

13.在非线性结构中，至少存在一个元素不止一个直接前驱或不止一个直接后驱（）。14.树的最大特点是一对多的层次结构（）。15.队列的特点是先进先出（）。

16.由后序遍历序列和中序遍历序列能唯一确定一颗二叉树（）。17.数据的存储结构独立于计算机（）。18.线性表简称为〞顺序表〞。（）

19.对数据的任何运算都不能改变数据原有的结构特性（）。20.从循环单链表的任一结点出发，可以找到表中的所有结点（）。21.栈是一种先进先出的线性表（）。22.链表的主要缺点是不能随机访问（）。23.二叉树是树的特别形式（）。24.冒泡排序法是稳定的排序（）。25.算法是对解题方法和步骤的描述（）。26.算法可以用任意的符号来描述（）。

27.数据的规律结构可以看作是从具体问题抽象出来的数学模型（）。

28.线性表的顺序存储方式是按规律次序将元素存放在一片地址连续的空间中（）。29.栈是一种先进后出的线性表（）。

30.将插入和删除限定在表的同一端进行的线性表是队列（）。

三、画图题

1.请根据以下二元组画出相应的数据结构

k={15,11,20,8,14,13}r={15,11,15,20,11,8,11,14,14,13}2.请根据以下二元组画出相应的数据结构

k={a,b,c,d,e,f,g,h,i,j}r={,,,,,,,,}3．请根据以下二元组画出相应的数据结构k={1,2,3,4,5,6,7}r={1,2,1,3,1,4,2,1,2,4,3,5,3,6,3,7,4,1,4,5,5,1,5,3,5,4,6,5,6,7,7,3}4.请根据以下二元组画出相应的数据结构k={1,2,3,4,5,6,7}r={(1,2),(1,3),（2,3），(2,4),(2,5),(3,7),(4,6),(5,6)，（6,7）}

四、运算题

1．已知一个图的顶点集v和边集h分别为：

v＝{0，1，2，3，4，5，6，7}

e＝{（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}；

依照克鲁斯卡尔算法得到最小生成树，拭写出在最小生成树中依次得到的各条边。______，______，______，______，______，______，______。

2.一个线性表为b=（12，23，45，57，20，03，78，31，15，36），设散列表为ht[0..12]，散列函数为h（key）=key%13并用线性探查法解决冲突，请画出散列表，并计算等概率状况下查找成功的平均查找长度。

平均查找长度：（写出计算过程）

3．已知一个图的顶点集v和边集h分别为：

v＝{0，1，2，3，4，5，6，7}

e＝{（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}；

依照普里姆算法得到最小生成树，试写出在最小生成树中依次得到的各条边。（从顶点2出发）

____

__，___

_，___

___，__

____，______，______，______。4.写出下图所示的二叉树的前中后序遍历结果：

前序：中序：后序：

5.设有一个输入数据的序列是{46,25,78,62,12,80},试画出从空树起，逐个输入各个数据而生成的二叉排序树。

五、编程题

1.请编写一个算法，实现十进制整数与二进制数的转换。voidshi_to_er(unsignedx){2.写出二分法查找的算法：

intsearch_bin(keytypek,sstablest){3.请编写一个算法，实现单链表的就地逆置（单链表不带头结点）。linklist*invertlink(linklist*h){

数据结构图总结篇四

试验：线性表的基本操作

学习把握线性表的顺序存储结构、链式存储结构的设计与操作。对顺序表建立、插入、删除的基本操作，对单链表建立、插入、删除的基本操作算法。

1.顺序表的实践

1)建立4个元素的顺序表s=sqlist[]={1，2，3，4，5}，实现顺序表建立的基本操作。

2)在sqlist[]={1，2，3，4，5}的元素4和5之间插入一个元素9，实现顺序表插入的基本操作。

3)在sqlist[]={1，2，3，4，9，5}中删除指定位置（i=5）上的元素9，实现顺序表的删除的基本操作。2.单链表的实践

3.1)建立一个包括头结点和4个结点的（5，4，2，1）的单链表，实现单链表建立的基本操作。

2)将该单链表的所有元素显示出来。

3)在已建好的单链表中的指定位置（i=3）插入一个结点3，实现单链表插入的基本操作。

4)在一个包括头结点和5个结点的（5，4，3，2，1）的单链表的指定位置（如i=2）删除一个结点，实现单链表删除的基本操作。5)实现单链表的求表长操作。

1.开启vc++。

2.建立工程：点file-new，选project标签，在列表中选win32consoleapplication，再在右边的框里为工程起好名字，选好路径，点ok-finish。至此工程建立完毕。

3.创立源文件或头文件：点file-new，选file标签，在列表里选c++sourcefile。给文件起好名字，选好路径，点ok。至此一个源文件就被添加到了你刚创立的工程之中。

4．写好代码

5．编译－＞链接－＞调试

线性是我们学习数据结构中，碰见的第一个数据结构。学习线性表的重点把握顺序表和单链表的各种算法和时间性能分析。线性表右两种存储方式即顺序存储结构和链式存储结构。通过学习我知道了对线性表进行建立、插入、删除，同时单链表也是进行建立、插入、删除。而对于顺序表的插入删除运算，其平均时间繁杂度均为0（n）.通过这次的学习，把握的太熟练，主要是课本上的知识点没有完全的理解，回去我会多看书，理解重要的概念。总之，这次试验我找到了自己的不足之处，以后会努力的。

试验二：栈的表示与实现及栈的应用

（1）把握栈的顺序存储结构及其基本操作的实现。（2）把握栈后进先出的特点，并利用其特性在解决实际问题中的应用。（3）把握用递归算法来解决一些问题。

1.编写程序，对于输入的任意一个非负十进制整数，输出与其等值的八进制数。

2.编写递归程序，实现n！的求解。3.编写递归程序，实现以下函数的求解。

n,n0,1fib(n)fib(n1)fib(n2),n1

4.编写程序，实现hanoi塔问题。1.开启vc++。

2.建立工程：点file-new，选project标签，在列表中选win32consoleapplication，再在右边的框里为工程起好名字，选好路径，点ok-finish。至此工程建立完毕。

3.创立源文件或头文件：点file-new，选file标签，在列表里选c++sourcefile。给文件起好名字，选好路径，点ok。至此一个源文件就被添加到了你刚创立的工程之中。

4．写好代码

5．编译－＞链接－＞调试

通过这次的学习我把握了栈这种抽象数据类型的特点，并能在相应的应用任务中正确选用它；总的来说，栈是操作受限的线性表，是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特别含义，称为栈顶（top），相应地，表头端称为栈底（botton）；栈又称为后进先出（lastinfirstout）的线性表,简称lifo结构，由于它的修改是按后进先出的原则进行的。

加上这个试验，我已经学了线性表（顺序表，单链表）和栈，知道它们都是线性表，而且对以后的学习有很大的作用，可以说这是学习以后知识的总要基础。

试验三：二叉树的建立及遍历

（1）把握利用先序序列建立二叉树的二叉链表的过程。（2）把握二叉树的先序、中序和后序遍历算法。

1.编写程序，实现二叉树的建立，并实现先序、中序和后序遍历。如：输入先序序列abc###de###，则建立如下图所示的二叉树。

并显示其先序序列为：abcde中序序列为：cbaed后序序列为：cbeda1.开启vc++。

2.建立工程：点file-new，选project标签，在列表中选win32consoleapplication，再在右边的框里为工程起好名字，选好路径，点ok-finish。至此工程建立完毕。

3.创立源文件或头文件：点file-new，选file标签，在列表里选c++sourcefile。给文件起好名字，选好路径，点ok。至此一个源文件就被添加到了你刚创立的工程之中。

4．写好代码

5．编译－＞链接－＞调试

这次试验是关于二叉树的常见操作，主要是二叉树的建立和遍历，在这次试验中我按先序方式建立二叉树的，而遍历方式则相对要多一些，有递归的先序、中序、后序遍历，和非递归的先序、中序、后序遍历，此外还有层次遍历.二叉树高度和叶子个数的计算和遍历相差不大，只是加些判断条件，总体来说，本次试验不太好做，期间出现了好多规律错误，变量初始化的问题等，不过经过细心排查最终都一一解决了。

试验四：查找与排序

（1）把握折半查找算法的实现。（2）把握冒泡排序算法的实现。

1.编写折半查找程序，对以下数据查找37所在的位置。5，13，19，21，37，56，64，75，80，88，922.编写冒泡排序程序，对以下数据进行排序。49，38，65，97，76，13，27，491.开启vc++。

2.建立工程：点file-new，选project标签，在列表中选win32consoleapplication，再在右边的框里为工程起好名字，选好路径，点ok-finish。至此工程建立完毕。

3.创立源文件或头文件：点file-new，选file标签，在列表里选c++sourcefile。给文件起好名字，选好路径，点ok。至此一个源文件就被添加到了你刚创立的工程之中。

4．写好代码

5．编译－＞链接－＞调试

（1）查找算法的代码如下所示：#include“stdio.h〞#include“malloc.h〞#defineoverflow-1#defineok1#definemaxnum100#definen10typedefintelemtype;typedefintstatus;typedefstruct{

elemtype*elem;

intlength;}sstable;statusinitlist(sstablest){inti,n;

=

(elemtype*)

malloc(elemtype));

if(!)return(overflow);

printf(“输入元素个数和各元素的值:〞);

scanf(“%dn〞,n);

for(i=1;i=n;i++){

(maxnum*sizeof

scanf(“%d〞,[i]);}

=n;

returnok;}intseq_search(sstablest,elemtypekey){

inti;

[0]=key;

for(i=;[i]!=key;--i);

returni;}intbinarysearch(sstablest,elemtypekey){

intmid,low,high,i=1;

low=1;

high=;

while(low=high)

{

mid=(low+high)/2;

if([mid]==key)

returnmid;

elseif(keyhigh=mid-1;

else

}

return0;}voidmain(){sstablest;initlist(st);

elemtypekey;intn;printf(“key=〞);

scanf(“%d〞,key);

printf(“nn〞);

/*printf(“afterseqsearch::〞);

n=seq_search(st,key);

printf(“positionisin%dnn〞,n);*/

printf(“afterbinarysearch::〞);

n=binarysearch(st,key);

low=mid+1;if(n)printf(“positionisin%dnn〞,n);else

}试验结果如下所示：

（2）排序算法的代码如下所示：#include“stdio.h〞#include“malloc.h〞#defineoverflow-1#defineok1#definemaxnum100#definen10typedefintelemtype;typedefintstatus;typedefstruct{

elemtype*elem;

intlength;}sstable;statusinitlist(sstablest)printf(“notinnn〞);{inti,n;

(elemtype));

if(!)return(overflow);

printf(“输入元素个数和各元素的值:〞);

scanf(“%dn〞,n);

for(i=1;i=n;i++){

scanf(“%d〞,[i]);}

=n;

returnok;}voidsort(sstablest){

inti,j,t;

for(i=1;ifor(j=i+1;j=;j++)

if([i][j]){t=[i];=

(elemtype*)

malloc

(maxnum*sizeof

}

}[i]=[j];[j]=t;voiddisplay(sstablest){inti;

for(i=1;i=;i++){

printf(“%d

〞,[i]);}

}voidmain(){

sstablest;initlist(st);intn;printf(“beforesort::n〞);display(st);sort(st);printf(“naftersort::n〞);display(st);}试验结果如下所示：

通过这次试验,我明白了程序里的折半查找和冒泡查找.其实排序可以有好多种，但是其目的应当都是为了能够在海量的数据里迅速查找到你要的数据信息，折半查找是种比较快的方式，但前提是要是有序的排序才可以。对于有序表，查找时先取表中间位置的记录关键字和所给关键字进行比较，若相等，则查找成功；假使给定值比该记录关键字大，则在后半部分继续进行折半查找；否则在前半部分进行折半查找，直到查找范围为空而查不到为止。折半查找的过程实际上死先确定待查找元素所在的区域，然后逐步缩小区域，直到查找成功或失败为止。算法中需要用到三个变量，low表示区域下界，high表示上界，中间位置mid=(low+high)/2.而冒泡查找则是从小到大的排序.

数据结构图总结篇五

一、基本概念

1、数据元素是数据的基本单位。

2、数据项是数据不可分割的最小单位。

3、数据结构的

规律结构（抽象的，与实现无关）

物理结构（存储结构）顺序映像（顺序存储结构）位置“相邻〞非顺序映像（链式存储结构）指针表示关系

4、算法特性：算法具有正确性、有穷性，确定性，（可行性）、输入，输出正确性：能按设计要求解决具体问题，并得到正确的结果。

有穷性：任何一条指令都只能执行有限次，即算法必需在执行有限步后终止。确定性：算法中每条指令的含义必需明确，不允许由二义性

可行性：算法中待执行的操作都十分基本，算法应当在有限时间内执行完毕。

输入：一个算法的输入可以包含零个或多个数据。输出：算法有一个或多个输出

5、算法设计的要求：

（1）正确性：算法应能满足设定的功能和要求。（2）可读性：思路明了、层次明显、易读易懂。

（3）健壮性：输入非法数据时应能作适当的反应和处理。

（4）高效性（时间繁杂度）：解决问题时间越短，算法的效率就越高。（5）低存储量（空间繁杂度）：完成同一功能，占用存储空间应尽可能少。

二、线性表

1、线性表list：最常用且最简单的数据结构。含有大量记录的线性表称为文件。

2、线性表是n个数据元素的有限序列。

线性结构的特点：①“第一个〞②“最终一个〞③前驱④后继。

3、顺序表——线性表的顺序存储结构特点

a)规律上相邻的元素在物理位置上相邻。b)随机访问。

2)表长为n时，线性表进行插入和删除操作的时间繁杂度为o（n），插入一个元素时大约移动表中的一半元素，删除一个元素时大约移动表中的（n-1）2。

4、线性表的链式存储结构1)类型定义

简而言之，“数据+指针〞

2)不带头结点的空表判定为l==null带头结点的空表判定为l-next==null循环单链表为空的判定条件为==l线性链表的最终一个结点的指针为null头结点的数据域为空，指针域指向第一个元素的指针。

5、顺序表和单链表的比较

6、顺序存储：优点：存储密度大，可随机存储

缺点：大小固定；不利于增减节点;存储空间不能充分利用；容量难扩展链式存储：优点：易于插入删除；可动态申请空间；表容量仅受内存空间限制缺点：增加了存储空间的开销；不可以随机存储元素

三、栈与队列

1、栈

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

栈是先进后出的线性表。

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

类似于顺序表，插入和删除操作固定于表尾。

3、队列

先进先出的线性表。队尾入队对头出队

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

4、链队列

1.树的定义

树（tree）：是n（n≥0）个有限数据元素的集合。在任意一棵非空树t中：

（1）有且仅有一个特定的称为树根（root）的结点，根结点无前趋结点；

（2）当n1时，除根结点之外的其余结点被分成m(m0)个互不相交的集合t1，t2，„，tm，其中每一个集合ti（1≤i≤m）本身又是一棵树，并且称为根的子树。2.基本术语：

结点的度数：结点的非空子树（即后缀）个数叫作结点的度数

树叶、分支结点：左（右）子树均为空二叉树的结点称作树叶否则称作分支结点。

结点的层数：规定根的层数是0，其余结点的层数等于其父结点的层数加1孩子和双亲：树的深度：

树的度数：树中度数最大的结点度数叫作树的度数树林：是由零个或多个不相交的树所组成的集合。3.二叉树性质：

1)二叉树的第i层上至多有2i-1个结点。2)深度为k的二叉树至多有2k-1个结点。满二叉树：深度为k，有2k-1个结点。

完全二叉树：给满二叉树的结点编号，从上至下，从左至右，n个结点的完全二叉树中结点在对应满二叉树中的编号正好是从1到n。

3)叶子结点n0，度为2的结点为n2，则n0=n2+1。考虑结点个数：n=n0+n1+n2考虑分支个数：n-1=2n2+n1可得n0=n2+1

5.遍历二叉树（先序dlr、中序ldr、后序lrd）方法与c语言描述

由二叉树的递归定义可知，一棵二叉树由根结点（d）、根结点的左子树（l）和根结点的右子树（r）三部分组成。因此，只要依次遍历这三部分，就可以遍历整个二叉树。一般有三种方法：先序(前序)遍历dlr（根左右）、中序遍历ldr（左根右）、后序遍历lrd（左右根）。

7.树和森林

树的存储结构

双亲表示法，孩子表示法，孩子兄弟表示法。特点：双亲表示法简单求得双亲，但不简单求得孩子；孩子表示法简单求得孩子，但求双亲麻烦；两者可以结合起来使用。孩子兄弟表示法，简单求得孩子和兄弟，求双亲麻烦，也可以增加指向双亲的指针来解决。

赫夫曼编码(前缀码)向左分支为0，向右分支为1，从根到叶子的路径构成叶子的前缀编码。

五、图1．

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

有向完全图：具有n（n-1）条弧的有向图。权：与图的边或弧相关的数。

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

入度：以顶点v为头的弧的数目出度：以顶点v为尾的弧的数目回路或环：第一个顶点和最终一个顶点一致的路径。

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

边(弧)多则需要存储空间多。

·十字链表：

十字链表是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来的一种链表。在十字链表中，对应于有向图中每一条弧有一个结点，对应于每个顶点有一个结点。

·邻接多重表3.图的遍历

1)深度优先（dfs）探寻

访问方式：从图中某顶点v出发：a）访问顶点v；

b）从v的未被访问的邻接点出发，继续对图进行深度优先遍历，若从某点出发所有邻接点都已访问过，退回前一个点继续上述过程，若退回开始点，终止。2)广度（宽度，bfs）优先探寻a）访问顶点v；

b）访问同v相邻的所有未被访问的邻接点w1,w2,„wk；

c）依次从这些邻接点出发，访问它们的所有未被访问的邻接点;依此类推，直到图中所有访问过的顶点的邻接点都被访问；

4.生成树和最小生成树

每次遍历一个连通图将图的边分成遍历所经过的边和没有经过的边两部分，将遍历经过的边同图的顶点构成一个子图，该子图称为生成树。因此有dfs生成树和bfs生成树。

1)最小生成树

·kruskal算法

一句话，“不构成环的状况下，每次选取最小边〞。

-网

用顶点表示活动，边表示活动的优先关系的有向图称为aov网。

拓扑排序：对aov网络中顶点构造拓扑有序序列的过程。拓扑排序的方法(1)在有向图中选一个没有前驱的顶点且输出之(2)从图中删除该顶点和所有以它为尾的弧6.关键路径

aoe网，关键路径

aoe网(activityonedge)——带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间。在工程上常用来表示工程进度计划。

关键路径：从源点到汇点的最长的一条路径，或者全部由关键活动构成的路径。7.最短路径

(1)迪杰斯特拉算法

求一个顶点到其他各顶点的最短路径。

算法：(a)初始化：用起点v到该顶点w的直接边(弧)初始化最短路径，否则设为∞；

(b)从未求得最短路径的终点中选择路径长度最小的终点u：即求得v到u的最短路径；

(c)修改最短路径：计算u的邻接点的最短路径，若(v,„,u)+(u,w)(v,„,w)，则以(v,„,u,w)代替。

(d)重复(b)-(c)，直到求得v到其余所有顶点的最短路径。特点：总是依照从小到大的顺序求得最短路径。

六、查找

1.查找分为：静态查找表、动态查找表、哈希查找表2.静态查找表：对查找表只作查找操作的查找表。动态查找表：查找过程中同时插入表中不含的元素，或者删除查找表中已有的元素的操作的查找表。

3.顺序查找：顺序查找又称线性查找，是最基本的查找方法之一。顺序查找既适用于顺序表，也适用于链表。

4.二分法（折半）查找：是一种效率较高的查找方法，但前提是表中元素必需按关键字有序（按关键字递增或递减）排列。

5.索引顺序表查找又称分块查找。分块查找：块内无序、块间有序、如何分块效率最高

6.动态查找表：二叉排序树查找：二叉排序树的生成

二叉