数据结构知识点全面总结—精华版

《数据结构知识点全面总结—精华版》由会员分享，可在线阅读，更多相关《数据结构知识点全面总结—精华版（50页珍藏版）》请在装配图网上搜索。

1、数据结构知识点全面总结一精 华版第1章 绪论 内容提要：数据结构研究的内容针对非数值计算的程序设计问题，研究计算机的 操作对象以及它们之间的关系和操作。数据结构涵盖的内容：釀性鰭构（蜒性宴.a *臥串.沁）图结杓索引结掏散列结梅插入运勞桂裁运算 杏栈运ff基本概念：数据、数据元素、数据对象、数 据结构、数据类型、抽象数据类型。数据所有能被计算机识别、存储和处理的符号的集合。数据元素_是数据的基本单位，具有完整确定 数据对象 具有相同性质的数据元素的集合， 是数据的一个子集数据结构是相互之间存在一种或多种特定关系的数据元素的集合，表示为：Data_Structure= （ D, R）数据类型是一

2、个值的集合和定义在该值上 的一组操作的总称。抽象数据类型由用户定义的一个数学模型与定义在该模型上的一组操作，它由基本的数据类型构成。算法的定义及五个特征。算法是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的 计算步骤。算法的基本特性：输入、输出、有穷性、确定性、 可行性算法设计要求。 正确性、可读性、健壮性、效率与低存 储量需求算法分析。时间复杂度、空间复杂度、稳定性学习重点：数据结构的“三要素”：逻辑结构、物理（存 储）结构及在这种结构上所定义的操作（运算）。用计算语句频度来估算算法的时间复杂度。 第二章线性表内容提要：线性表的逻辑结构定义，对线性表定义的操 作。

3、线性表的定义：用数据元素的有限序列表示线性表的存储结构：顺序存储结构和链式存储结构。顺序存储定义：把逻辑上相邻的数据元素存储在 物理上相邻的存储单元中的存储结构。链式存储结构：其结点在存储器中的位置是随 意的，即逻辑上相邻的数据元素在物理上 不一定 相邻。通过指针来实现！线性表的操作在两种存储结构中的实现。 数据结构的基本运算：修改、插入、删除、查找、1) 修改一一通过数组的下标便可访问某个特定 元素并修改之。核心语句：Vi=x;顺序表修改操作的时间效率是0(1)2) 插入一一在线性表的第i个位置前插入一个 元素实现步骤： 将第n至第i位的元素向后移动一个位置； 将要插入的元素写到第i个位置；

4、 表长加1。注意：事先应判断：插入位置i是否合法？表 是否已满？应当符合条件：K i =i; j-) aj+1=a j ；a i =x;n+;插入时的平均移动次数为：n(n+1)/2十(n+1)=n /2 0(n)3) 删除一一删除线性表的第i个位置上的元素 实现步骤： 将第i+1至第n位的元素向前移动一个位 置； 表长减1。注意：事先需要判断，删除位置i是否合法？ 应当符合条件：K i n 或i=1, n核心语句：for ( j=i+1; j=n; j+ )aj-1=aj;n_;顺序表删除一元素的时间效率为：T(n)=(n-1)/2 0(n)顺序表插入、删除算法的平均空间复杂度为0(1)单链

5、表：(1)用单链表结构来存放26个英文字母组成的线性 表(a, b, c,，z),请写出C语言程序。#in clude#in clude typedef struct no dechar data;struct node *n ex t;一般需要3个指针/数据元素的个数/*结构类型定义好no de;node *p,*q,*head;变量int n ;int m=sizeof( no de);之后，每个node类型的长度就固定了，void build() 要一个个慢慢链入m求一次即可*/字母链表的生成。int i;head=( no de*)malloc(m); m=sizeof( no de)

6、前面已求出 p=head;/因尾结点要for( i=1; idata=i+ a -1;/ 第一个结点值为字符ap-n ext=(no de*)malloc(m);II 为后继结点“挖坑”！p=p-next; II让指针变量P指向后一个结点p-data=i+ a -1;素要单独处理p- next=NULL ;结点的指针域要置空！void display。p=head;while (p)(仅限于无头结点的情况)prin tf(%c,p-data); p=p-n ex t;断“顺藤摸瓜”/最后一个元/单链表尾字母链表的输出当指针不空时循环/让指针不(2)单链表的修改(或读取)思路：要修改第i个数据元

7、素，必须从头指针起 一直找到该结点的指针p，然后才能：pdata=n ew_value读取第i个数据元素的核心语句是：Linklist *find(Linklist *head ,int i)int j=1;Li nklist *p;P=head-n ex t;While(p!=NULL)&(jn ext;j+;return p;家結点的生成方式：S- (node*) ma I loc (m): 5-dattf=;S-next=p-next3单链表的插入pPO C - ZLk*7E 链表插入的核心语句：Step 1: s-next=p-next;Step 2: p-next=s ;6.单链表的

8、删除删除动作的核心语句（要借助辅助指针变量q = p-n ex t;靠它才能找到c;p-n ext=q-n ex t;b结点；free(q)；间/首先保存b的指针，将a、c两结点相连，淘汰彻底释放b结点空7.双向链表的插入操作:T XJ设p已指向第i元素，请在第i元素前插入元素x: ai-1的后继从ai （指针是p）变为x （指针是 s）:s-n ext= p;p-prior- n ext = s ; ai的前驱从ai-1 （指针是p-prior）变为x（指针是s）;s-priorp-prior = s ;8.双向链表的删除操作：= p -prior ;p鼻卡*1 $设p指向第i个元素，删除第

9、i个元素 后继方向：ai-1的后继由 ai （指针p）变为 ai+1（指针 p -next ）;p-prio r-n ext=p-n ext ;前驱方向：ai+1的前驱由ai （指针p）变为ai-1 （指针 p - prior ）;p-n ext-prior = p -prior ;数组的逻辑结构定义及存储数组：由一组名字相同、下标不同的变量构成 N维数组的特点：n个下标，每个元素受到n个 关系约束一个n维数组可以看成是 由若干个n1维数组 组成的线性表。存储：事先约定按某种次序将数组元素排成一列 序列，然后将这个线性序列存入存储器中。在二维数组中，我们既可以规定按行存储，也可以规定按列存储。

10、釦3書刖5设一般的二维数组是Ac1.d1,c2.d2,则行优先存储时的地址公式为：LOC （驹）LOC（响，I （i-Ci） *（dj-C211） *L二维数组列优先存储的通式为：I.OCaijH ,OC（aq, A （j稀疏矩阵（含特殊矩阵）的存储及运算。稀疏矩阵：矩阵中非零元素的个数较少（ 般小于5%）学习重点：线性表的逻辑结构，指线性表的数据元素间 存在着线性关系。在顺序存储结构中，元素存储 的先后位置反映岀这种线性关系,而在链式存储 结构中，是靠指针来反映这种关系的。顺序存储结构用一维数组表示，给定下标， 可以存取相应元素，属于 随机存取的存储结构。链表操作中应注意不要使链意外“断开”

11、。因 此，若在某结点前插入一个元素，或删除某元素， 必须知道该元素的 前驱结点的指针。掌握通过画出结点图来进行链表（单链表、 循环链表等）的生成、插入、删除、遍历等操作。数组（主要是二维）在以 行序/列序为主的存 储中的地址计算方法。稀疏矩阵的三元组表存储结构。稀疏矩阵的十字链表存储方法。补充重点：1每个存储结点都包含两部分： 数据域和指针域 （链域）2. 在单链表中，除了首元结点外，任一结点的存 储位置由 其直接前驱结点的链域的值 指示。3. 在链表中设置头结点有什么好处？头结点即在链表的首元结点之前附设的一 个结点，该结点的数据域可以为空，也可存放表 长度等附加信息,其作用是为了对链表进行

12、操作 时，可以对空表、非空表的情况以及对首元结点 进行统一处理，编程更方便。4. 如何表示空表？（1）无头结点时，当头指针的值为空时表示空 表；（2）有头结点时，当头结点的指针域为空时表 示空表。5. 链表的数据元素有两个域，不再是简单数据类 型，编程时该如何表示？因每个结点至少有两个分量，且数据类型通常 不一致，所以要采用结构数据类型。6. sizeof（x）计算变量x的长度（字节数）；malloc（m）开辟m字节长度的地址空间，并返回这段空间的首地址；free(p)释放指针p所指变量的存储空 间，即彻底删除一个变量。7. 链表的运算效率分析：(1) 查找因线性链表只能顺序存取，即在查找时要

13、从头指 针找起，查找的时间复杂度为 O( n)。(2) 插入和删除因线性链表不需要移动元素，只要修改指针，一 般情况下时间复杂度为 0(1)。但是，如果要在单链表中进行前插或删除操作， 因为要从头查找前驱结点，所耗时间复杂度将是 0(n)。例：在n个结点的单链表中要删除已知结点*P， 需找到它的前驱结点的地址，其时间复杂度为O (n)8. 顺序存储和链式存储的区别和优缺点？顺序存储时，逻辑上相邻的数据元素，其物 理存放地址也相邻。顺序存储的优点是存储密度 大，存储空间利用率咼；缺点是插入或删除元素 时不方便。链式存储时，相邻数据元素可随意存放，但 所占存储空间分两部分，一部分存放结点值，另 一

14、部分存放表示结点间关系的指针。 链式存储的 优点是插入或删除元素时很方便，使用灵活。缺 点是存储密度小，存储空间利用率低。 顺序表适宜于做查找这样的静态操作:链表宜于做插入、删除这样的动态操作。 若线性表的长度变化不大，且其主要操作是 查找，则采用顺序表； 若线性表的长度变化较大，且其主要操作是 插入、删除操作，则采用链表。9. 判断：“数组的处理比其它复杂的结构要简 单”，对吗？答：对的。因为一一 数组中各元素具有统一的类型; 数组元素的下标一般具有 固定的上界和下 界，即数组一旦被定义，它的维数和维界就不再 改变。 数组的基本操作比较简 单,除了结构的初始化 和销毁之外，只有存取元素和修改

15、元素值的操 作。10. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示 该元素的行下标、列下标和元素值。11. 写出右图所示稀疏矩阵的压缩存储形式。 解：介绍3种存储形式。n 9法1：用线性表表示：3 24 “(1212)，(1,3,9),(3,1,-3),(3,5,14),(4,3,24),(5,2,18)，(6,1,15)，(6,4,-7)法2：用十字链表表号仕箕d示I H- 4*-F-=t| H-用途：方便稀疏矩阵的加减运算方法：每个非0元素占用5个域卅打呷斗屮卅斗尸医- 法3:用三元组矩阵表示:iJ111212213331心4351454324苗52i

16、e6115B6斗-7稀疏矩阵压缩存储的缺点：将失去随机存取功能 代码：1用数组V来存放26个英文字母组成的线性表(a, b, c,，z),写出在顺序结构上生成和显示该表的C语言程序。char V30;void build()字母线性表的生成，即建表操作int i;V0=a;for( i=1;i=n-1;i+ )Vi=Vi-1+1;void display( ) /字母线性表的显示，即读表操作int i;for( i=0;i=n-1;i+ )printf( %c, vi);printf( n );void main(void)/主函数，字母线性表的生成和输出n=26;/ n是表长，是数据元素的个

17、数，而不是V的实际下标build();display();第三章栈和队列内容提要：从数据结构角度来讲，栈和队列也是线性表, 其操作是线性表操作的子集，属操作受限的线性 表。但从数据类型的角度看，它们是和线性表大 不相同的重要抽象数据类型。栈的定义及操作。栈是只准在一端进行插入 和删除操作的线性表，该端称为栈的顶端。插入元素到栈顶的操作，称为入栈。从栈顶删除最后一个元素的操作，称为出栈M)上溢else stop+=e;顺序栈出栈函数POP()status Pop() if(top=L) 下溢else e=s-top; return(e);队列的定义及操作，队列的删除在一端（队 尾）,而插入则在队

18、列的另一端（队头）。因此在 两种存储结构中，都需要队头和队尾两个指针。 队列：只能在表的一端进行插入运算，在表的另 一端进行删除运算的线性表。链队列结点类型定义：typedef Struct QNode/元素QElemTypedata;Struct QNode*n ext; II 指向下一结点的指针Qn ode , * QueuePtr ;链队列类型定义：typedef struct QueuePtrfront ; / 队首指针QueuePtrrear ; II 队尾指针 Lin kQueue;链队示意图：rairH CFH.-gi3 空链队的特征：fron t=rear 链队会满吗？ 一般不

19、会，因为删除时有free 动作。除非内存不足！ 入队（尾部插入）：rear-next=S; rear=S; 出队（头部删除）:front-next=p-next;2顺序队顺序队类型定义：#defi neQUEUE-MAXSIZE 100 II 最大队列长度typedef struct QEIemType *base; / 队列的基址int队首指针int队尾指针SqQueue建队核心语句：q . base=(QEIemType(QEIemType )* QUEUE_MAXSIZE;front rear;*)malloc(sizeof/分配空间顺序队示意图:讨湫tkihi入 EM 尾Mlfi人h

20、rear+ ,O|rtar|-f； 岀 EM 头刖删斷 1 frmm. e Q|froit|;循环队列:队空条件:front = rear（初始化时: front = rear )队满条件： front = (rea叶1)% N(N=maxsize)队列长度(即数据元素个数)：L= ( N + rear front) % N1) 初始化一个空队列StatusInitQueue ( SqQueue &q ) /初始化空循环队列qq.base=(QEIemType*)malloc(sizeof(QEIemType)* QUEUE_MAXSIZE);分配空间if (!q.base) exit(OVE

21、RFLOW);/ 内存分配失败，退出程序q.front =q.rear=0; / 置空队列return OK; /I ni tQueue;2) 入队操作StatusEn Queue(SqQueue&q,QElemType e)/向循环队列q的队尾加入一个元素 eif ( (q.rear+1) % QUEUE_MAXSIZE =q.fro nt )return ERROR ; / 队 满则上溢，无法再入队q.rear = ( q . rear +1) %QUEUE_MAXSIZE;q.base q.rear = e;新元素 e入队return OK;/ En Queue;3) 出队操作Statu

22、sDeQueue ( SqQueue &q,QElemType &e)/若队列不空，删除循环队列q的队头元素，/由e返回其值，并返回OKif ( q.front = = q.rear ) returnERROR;/队列空q.fro nt=(q.fro nt+1)%QUEUE_MAXSIZE ;e = q.base q.fr ont ;return OK;/ DeQueue链队列空的条件是首尾指针相等，而循环队 列满的条件的判定，则有队尾加1等于队头和设 标记两种方法。补充重点：1为什么要设计堆栈？它有什么独特用途？ 调用函数或子程序非它莫属； 递归运算的有力工具； 用于保护现场和恢复现场； 简

23、化了程序设计的问题。2为什么要设计队列？它有什么独特用途？ 离散事件的模拟（模拟事件发生的先后顺序 例如CPU芯片中的指令译码队列）； 操作系统中的作业调度（一个CPU执行多个 作业）； 简化程序设计3什么叫“假溢出”？如何解决？答：在顺序队中，当尾指针已经到了数组的上界， 不能再有入队操作，但其实数组中还有空位置， 这就叫假溢出”。解决假溢出的途径米用循环队列。4. 在一个循环队列中，若约定队首指针指向队首 元素的前一个位置。那么，从循环队列中删除一 个元素时，其操作是先 移动队首位置，后 取 出元素。5. 线性表、栈、队的异同点：相同点：逻辑结构相同，都是线性的；都可以用 顺序存储或链表存

24、储；栈和队列是两种特殊的线 性表，即受限的线性表（只是对插入、删除运算 加以限制）。不同点：运算规则不同：线性表为随机存取；而栈是只允许在一端进行插入和删除运算，因而 是后进先出表LIFO ;队列是只允许在一端进行插入、另一端进行删除 运算，因而是先进先出表FIFO。用途不同，线性表比较通用；堆栈用于函数 调用、递归和简化设计等；队列用于离散事件模 拟、OS作业调度和简化设计等。第四章串 内容提要：串是数据元素为字符的线性表，串的定义及 操作。串即字符串，是由零个或多个字符组成的有限序 列，是数据元素为单个字符的特殊线性表。串比较：int strcmp(char *s1,char *s2);求

25、串长：int strlen(char *s);串连接：char strcat(char *to,char *from) 子串 T 定位：char strchr(char *s,char *c);串的存储结构，因串是数据元素为字符的线 性表，所以存在“结点大小”的问题。模式匹配算法。串有三种机内表示方法：砒 一用-组排肚连续的存袖单元存确串俏的字非傭箝序狗* M靜息存储片血堆分配存储盍用S5 車的块忧存据去不卄噸一曲方式沖副模式匹配算法：算法目的：确定主串中所含子串第一次出现的位 置(定位)if (Si = = Tj ) +i, +j; 则继续定位问题称为串的模式匹配，典型函数为lndex(S,

26、T,pos)BF算法的实现一即编写Index(S, T, pos)函数BF算法设计思想：将主串S的第pos个字符和模式T的第1个字符 比较，若相等，继续逐个比较后续字符；若不等，从主串S的下一字符(pos+1)起, 重新与T第一个字符比较。直到主串S的一个连续子串字符序列与模 式T相等。返回值为S中与T匹配的子序列第 一个字符的序号，即匹配成功。否则，匹配失败，返回值 0。Int In dex_BP(SStri ng S, SStri ng T, i nt pos) 返回子串T在主串S中第pos个字符之后的 位置。若不存在，则函数值为 0./ 其中，T 非空，K pos StrLength(S

27、)i=pos; j=1;while ( iv=S0 & jTO) return i-T0;/T 子串指针 j 正常到尾，说明匹配成功，else return 0;/否则属于iS0情况，i先到尾就不正常 /I ndex_BP补充重点：1. 空串和空白串有无区别？答：有区别。空串(Null String)是指长度为零的串；而空白串(Biank String),是指包含一个或多个 空白字符(空格键)的字符串.2. “空串是任意串的子串；任意串S都是S本身 的子串，除S本身外，S的其他子串称为S的真 子串。”适砂构 S = 0)结点组成的有限集合T， 有且仅有一个结点称为根(root)，当n1时， 其

28、余的结点分为m(m 0)个互不相交的有限集 合T1,T2，Tm。每个集合本身又是棵树， 被称作这个根的子树。二叉树：是n (n 0)个结点的有限集合，由一 个根结点以及两棵互不相交的、分别称为左子树 和右子树的二叉树组成。术语：P88二叉树的性质，存储结构。性质1:在二叉树的第i层上至多有2i-1个结点（i0 ）。性质2:深度为k的二叉树至多有2k-1个结点（k0）。性质3:对于任何一棵二叉树，若2度的结点数 有n2个，则叶子数（n0）必定为n2 + 1 性质4:具有n个结点的完全二叉树的深度必为 性质5:对完全二叉树，若从上至下、从左至右 编号，则编号为i的结点，其左孩子编号必为 2i，其右

29、孩子编号为 2i+ 1;其双亲的编号必为 i/2 （i = 1时为根,除外）。二叉树的存储结构：一、顺序存储结构按二叉树的结点“自上而下、从左至右”编号， 用一组连续的存储单元存储。若是完全/满二叉树则可以做到唯一复原。不是完全二叉树：一律转为完全二叉树！方法很简单，将各层空缺处统统补上“虚结点”， 其内容为空。缺点：浪费空间；插入、删除不便二、链式存储结构用二叉链表即可方便表示。一般从根结点开始存 储。血吗 Jifta lid优点：不浪费空间；插入、删除方便二叉树的遍历。指按照某种次序访冋二叉树的所有结点，并且每 个结点仅访问一次，得到一个线性序列。遍历规则二叉树由根、左子树、右子树构成，定

30、义为D、L、R若限定先左后右，则有三种实现方案：DLRLDRLRD先序遍历中序遍历后序遍历树的存储结构，树、森林的遍历及和二叉树 的相互转换。回顾2:二叉树怎样还原为树？要点：逆操作，把所有右孩子变为兄弟！讨论1森林如何转为二叉树？法一： 各森林先各自转为二叉树； 依次 连到前一个二叉树的右子树上。法二：森林直接变兄弟，再转为二叉树讨论2： 二叉树如何还原为森林？要点：把最右边的子树变为森林，其余右子树变为兄弟树和森林的存储方式：树有三种常用存储方式：双亲表示法孩子表示法孩子一兄弟表示法问：树-二叉树的“连线一抹线一旋转”如何由计算机自动实现？答：用“左孩子右兄弟”表示法来存储即可。 存储的过

31、程就是树转换为二叉树的过程！firstchU data1Inextsibim树、森林的遍历:律桂忧先ifi出先變、h电）广庵憶先境历（层衣1于拥不舟右右、 先根遍历：访问根结点；依次先根遍历根结 点的每棵子树。 后根遍历：依次后根遍历根结点的每棵子树; 访问根结点。讨论：树若采用“先转换，后遍历”方式，结果 是否一样？1. 树的先根遍历与二叉树的先序遍历相同；2. 树的后根遍历相当于二叉树的中序遍历；3. 树没有中序遍历，因为子树无左右之分。森林的#1历-广度优先掃历层机）先序遍历若森林为空，返回；访问森林中第一棵树的根结点；先根遍历第一棵树的根结点的子树森林; 先根遍历除去第一棵树之后剩余的

32、树构成的森 林。中序遍历若森林为空，返回；中根遍历森林中第一棵树的根结点的子树森林； 访问第一棵树的根结点；中根遍历除去第一棵树之后剩余的树构成的森 林。二叉树的应用：哈夫曼树和哈夫曼编码。 Huffman树：最优二叉树（带权路径长度最短的 树）Huffman编码：不等长编码。树的带权路径长度：=沪（树中所有叶子结点的带权路径长度之和）构造Huffman树的基本思想：权值大的结点用 短路径，权值小的结点用长路径。构造Huffman树的步骤（即Huffman算法）： 由给定的n个权值 w1, w2,wn 构成n 棵二叉树的集合F = T1, T2,Tn （即森 林），其中每棵二叉树Ti中只有一个

33、带权为wi的根结点，其左右子树均空(2) 在F中选取两棵根结点权值最小的树 做为 左右子树构造一棵新的二叉树，且让新二叉树根 结点的权值等于其左右子树的根结点权值之和。(3) 在F中删去这两棵树，同时将新得到的二叉 树加入F中。(4) 重复(2)和(3),直到F只含一棵树为止。这 棵树便是Huffman树。具体操作步骤：tepl=对权隹进行合井、1除与替帳 权值集合仏5. N对屮.鱼是合并当前醱忌小胯苒牛按1.初输c.合并何佝d合旳咼11F dl5HnulFH7H11Fi吐亡同：按左*(r右*严对伽初树的所有分支骗号*3 Huffman 峪 lluffmai编码 it钩Huffnmfg码结果：

34、d= , i=l ,.(、 n=l I IWVlbitX7+2bitXt (2+4) =3& (小于寻緒ftWfV36)学习重点：(本章内容是本课程的重点)二叉树性质及证明方法，并能把这种方法推 广到K叉树。二叉树遍历，遍历是基础，由此导出许多实 用的算法，如求二叉树的高度、各结点的层次数、 度为0、1、2的结点数。由二叉树遍历的前序和中序序列或后序和中 序序列可以唯一构造一棵二叉树。由前序和后序 序列不能唯一确定一棵二叉树。完全二叉树的性质。树、森林和二叉树间的相互转换。哈夫曼树的定义、构造及求哈夫曼编码。补充：1.满二叉树和完全二叉树有什么区别？答：满二叉树是叶子一个也不少的树， 而完全二

35、 叉树虽然前k-1层是满的，但最底层却允许在右 边缺少连续若干个结点。满二叉树是完全二叉树 的一个特例。2.Huffman树有什么用?最小冗余编码、信息高效传输第七章图内容提要：图的定义，概念、术语及基本操作。图：记为 G = ( V, E )其中：V是G的顶点集合，是有穷非空集； E是G的边集合，是有穷集。术语：见课件图的存储结构。1.邻接矩阵(数组)表示法 建立一个顶点表和一个邻接矩阵 设图A = (V, E)有n个顶点，则图的邻接 矩阵是一个二维数组 A.Edgenn。注：在有向图的邻接矩阵中，第i行含义：以结点vi为尾的弧（即出度边）； 第i列含义：以结点vi为头的弧（即入度边）。 邻

36、接矩阵法优点：容易实现图的操作，如：求某 顶点的度、判断顶点之间是否有边（弧）、找顶 点的邻接点等等。邻接矩阵法缺点：n个顶点需要n*n个单元存储 边（弧）;空间效率为0（n2）。2邻接表（链式）表示法 对每个顶点vi建立一个单链表，把与 vi有 关联的边的信息（即度或出度边）链接起来，表 中每个结点都设为3个域：*UI1 dati lirsLarC n 劭 tat info.LA11八J* I椒豊如n 1甘fiU帕i冈IrM M J M -fll苗込丨KA 下f邀蹇CMtB 每个单链表还应当附设一个头结点（设为 2 个域），存vi信息； 每个单链表的头结点另外用顺序存储结构存 储。邻接表的优

37、点：空间效率高；容易寻找顶点的邻 接点；邻接表的缺点：判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。图的遍历。遍历定义：从已给的连通图中某一顶点出 发，沿着一些边，访遍图中所有的顶点，且使每 个顶点仅被访问一次，就叫做图的遍历，它是图 的基本运算。图常用的遍历：一、深度优先搜索；二、广度优 先搜索深度优先搜索（遍历）步骤： 访问起始点V； 若V的第1个邻接点没访问过，深度遍历此 邻接点； 若当前邻接点已访问过，再找 v的第2个邻 接点重新遍历。基本思想：仿树的先序遍历过程。广度优先搜索（遍历）步骤：在访问了起始点V之后，依次访问V的邻接占八、J 然后再依次（顺序）访问这

38、些点（下一层） 中未被访问过的邻接点；直到所有顶点都被访问过为止。图的应用（最小生成树，最短路经）最小生成树（MST ）的性质如下：若U集是 V的一个非空子集，若（uO, vO）是一条最小权值的 边，其中uO U, vO V-U ;贝廿：（uO, vO）必在 最小生成树上。求MST最常用的是以下两种：Kruskal （克鲁斯 卡尔）算法、Prim （普里姆）算法Kruskal算法特点：将边归并，适于求稀疏网的 最小生成树。Prime算法特点：将顶点归并，与边数无关，适 于稠密网。在带权有向图中A点（源点）到达B点（终点） 的多条路径中，寻找一条各边权值之和最小的路 径，即最短路径。两种常见的最

39、短路径问题：一、单源最短路径一用Dijkstra （迪杰斯特拉） 算法二、所有顶点间的最短路径一用 Floyd （弗洛伊 德）算法一、单源最短路径（Dijkstra算法）一顶点到其余 各顶点（vOj）目的：设一有向图G= （V, E）,已知各边 的权值，以某指定点vO为源点，求从vO到图的 其余各点的最短路径。限定各边上的权值大于或 等于0。二、所有顶点之间的最短路径可以通过调用n次Dijkstra算法来完成，还 有更简单的一个算法：Floyd算法（自学）。学习重点：图是应用最广泛的一种数据结构，本章也是这门课程的重点。基本概念中，连通分量，生成树，邻接点是重点。 连通图：在无向图中，若从顶点

40、v1到顶 点v2有路径，则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的，则称此图是连通图。非连通图的极大连通子图叫做 连通分量。 生成树：是一个极小连通子图，它含有图 中全部n个顶点，但只有n-1条边。 邻接点：若（u, v）是E（G）中的一条边， 则称u与v互为邻接顶点。图是复杂的数据结构，也有顺序和链式两种 存储结构：数组表示法（重点是邻接距阵）和邻 接表。这两种存储结构对有向图和无向图均适用图的遍历是图的各种算法的基础，应熟练掌 握图的深度、广度优先遍历。连通图的最小生成树不是唯一的，但最小生 成树边上的权值之和是唯一的。应熟练掌握prim 和kruscal算法，特别是手工分

41、步模拟生成树的生成过程从单源点到其他顶点，以及各个顶点间的最 短路径问题，掌握熟练手工模拟。补充：1问：当有向图中仅1个顶点的入度为0,其余顶 点的入度均为1,此时是何形状？答：是树！而且是一棵有向树！2讨论：邻接表与邻接矩阵有什么异同之处？1. 联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。2. 区别：对于任一确定的无向图，邻接矩阵是唯一的（行 列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。3. 用途：邻接矩阵多用于稠密图的存储而邻接表多用于稀疏图的存储3.若对连通图进行遍历，得到的是生成树 若对非连通图进行遍历，得到的是生成森林。第

42、八章 查找内容提要：查找表是称为集合的数据结构。是元素间约 束力最差的数据结构：元素间的关系是元素仅共 在同一个集合中。(同一类型的数据元素构成的 集合)查找表的操作：查找，插入，删除。 静态查找表：顺序表，有序表等。针对静态查找表的查找算法主要有：顺序查 找、折半查找、分块查找一、顺序查找(线性查找)技巧：把待查关键字key存入表头或表尾(俗 称“哨兵”)，这样可以加快执行速度。int Search_Seq( SSTable ST , KeyType key )ST.elem0.key =key;for( i=ST.length; ST.elem i .key!=key; - i )；ret

43、urn i; / Search_Seq/ASL =( 1 + n) /2，时间效率为 0(n)，这是查找成功的情况:顺序查找的特点：优点：算法简单，且对顺序结构或链表结构均 适用。缺点：ASL太大，时间效率太低。二、折半查找（二分或对分查找） 若关键字不在表中，怎样得知并及时停止 查找？典型标志是：当查找范围的上界w下界时 停止查找。ASL的含义是“平均每个数据的查找时间” 而前式是n个数据查找时间的总和，所以：ASL j 2j 1-log 2（n 1） 1 log 2 nn j in三、分块查找（索引顺序查找）思路：先让数据分块有序，即分成若干子表，要 求每个子表中的数据元素值都比后一块中的数 值小（但子表内部未必有序）。然后将各子表中 的最大关键字构成一个索引表，表中还要包含每 个子表的起始地址（即头指针）。特点：块间有序，块内无序。