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

《数据结构知识点全面总结精华版.docx》由会员分享，可在线阅读，更多相关《数据结构知识点全面总结精华版.docx（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1章 绪论 内容提要： 数据结构探讨的内容。针对非数值计算的程序设计问题，探讨计算机的操作对象以与它们之间的关系与操作。数据结构涵盖的内容： 基本概念：数据, 数据元素, 数据对象, 数据结构, 数据类型, 抽象数据类型。数据全部能被计算机识别, 存储与处理的符号的集合。数据元素是数据的基本单位，具有完整确定的实际意义。数据对象具有相同性质的数据元素的集合，是数据的一个子集。数据结构是相互之间存在一种或多种特定关系的数据元素的集合，表示为： Data_Structure=（D, R）数据类型是一个值的集合与定义在该值上的一组操作的总称。抽象数据类型由用户定义的一个数学模型与定义在该模型上的一

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

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

4、应当符合条件： 1in+1 或 i=1, n+1 核心语句：for (j=n; j=i; j-)aj+1=a j ; a i =x; n+; 插入时的平均移动次数为：n(n+1)/2（n+1）n/2O(n) 3) 删除删除线性表的第i个位置上的元素 实现步骤： 将第i+1 至第n 位的元素向前移动一个位置； 表长减1。 留意：事先须要推断，删除位置i 是否合法 应当符合条件：1in 或 i=1, n 核心语句：for ( j=i+1; j=n; j+ )aj-1=aj; n-; 依次表删除一元素的时间效率为:T（n)=(n-1)/2 O(n) 依次表插入, 删除算法的平均空间困难度为O(1)单

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

6、出p=head;for( i=1; idata=i+a-1; / 第一个结点值为字符ap-next=(node*)malloc(m); /为后继结点“挖坑”！p=p-next； /让指针变量P指向后一个结点p-data=i+a-1; /最终一个元素要单独处理p-next=NULL ; /单链表尾结点的指针域要置空！void display() /字母链表的输出 p=head; while (p) /当指针不空时循环（仅限于无头结点的状况） printf(%c,p-data); p=p-next; /让指针不断“顺藤摸瓜”（2） 单链表的修改(或读取）思路：要修改第i个数据元素，必需从头指针起始

7、终找到该结点的指针p， 然后才能：pdata=new_value 读取第i个数据元素的核心语句是：Linklist *find(Linklist *head ,int i) int j=1; Linklist *p; P=head-next; While(p!=NULL)&(jnext; j+; return p; 3. 单链表的插入链表插入的核心语句：Step 1：s-next=p-next;Step 2：p-next=s ；6. 单链表的删除删除动作的核心语句（要借助协助指针变量q）：q = p-next; /首先保存b的指针，靠它才能找到c；p-next=q-next; /将a, c两结

8、点相连，淘汰b结点；free(q) ； /彻底释放b结点空间7. 双向链表的插入操作：设p已指向第 i 元素，请在第 i 元素前插入元素 x： ai-1的后继从 ai ( 指针是p)变为 x（指针是s) : s-next = p ; p-prior-next = s ; ai 的前驱从 ai-1 ( 指针是p-prior)变为 x ( 指针是s); s-prior = p -prior ; p-prior = s ; 8. 双向链表的删除操作：设p指向第 i 个元素，删除第 i 个 元素后继方向：ai-1的后继由 ai ( 指针p)变为 ai+1(指针 p -next ); p -prior-

9、next = p-next ; 前驱方向：ai+1的前驱由 ai ( 指针p)变为ai-1 (指针 p - prior ); p-next-prior = p -prior ; 数组的逻辑结构定义与存储数组： 由一组名字相同, 下标不同的变量构成N维数组的特点：n个下标，每个元素受到n个关系约束一个n维数组可以看成是由若干个n1维数组组成的线性表。存储：事先约定按某种次序将数组元素排成一列序列，然后将这个线性序列存入存储器中。 在二维数组中，我们既可以规定按行存储，也 可以规定按列存储。设一般的二维数组是Ac1.d1, c2.d2，则行优先存储时的地址公式为：二维数组列优先存储的通式为： 稀疏

10、矩阵（含特殊矩阵）的存储与运算。 稀疏矩阵：矩阵中非零元素的个数较少（一般小于5%）学习重点： 线性表的逻辑结构，指线性表的数据元素间存在着线性关系。在依次存储结构中，元素存储的先后位置反映出这种线性关系，而在链式存储结构中，是靠指针来反映这种关系的。 依次存储结构用一维数组表示，给定下标，可以存取相应元素，属于随机存取的存储结构。 链表操作中应留意不要使链意外“断开”。因此，若在某结点前插入一个元素，或删除某元素，必需知道该元素的前驱结点的指针。 驾驭通过画出结点图来进行链表（单链表, 循环链表等）的生成, 插入, 删除, 遍历等操作。 数组（主要是二维）在以行序/列序为主的存储中的地址计算

11、方法。 稀疏矩阵的三元组表存储结构。 稀疏矩阵的十字链表存储方法。补充重点：1.每个存储结点都包含两部分：数据域与指针域(链域)2.在单链表中，除了首元结点外，任一结点的存储位置由 其干脆前驱结点的链域的值 指示。 3.在链表中设置头结点有什么好处？ 头结点即在链表的首元结点之前附设的一个结点，该结点的数据域可以为空，也可存放表长度等附加信息，其作用是为了对链表进行操作时，可以对空表, 非空表的状况以与对首元结点进行统一处理，编程更便利。4. 如何表示空表？（1）无头结点时，当头指针的值为空时表示空表；（2）有头结点时，当头结点的指针域为空时表示空表。5.链表的数据元素有两个域，不再是简洁数据

12、类型，编程时该如何表示？ 因每个结点至少有两个重量，且数据类型通常不一样，所以要采纳结构数据类型。6.sizeof(x) 计算变量x的长度（字节数）； malloc(m) 开拓m字节长度的地址空间，并返回这段空间的首地址； free(p) 释放指针p所指变量的存储空间，即彻底删除一个变量。7. 链表的运算效率分析：（1）查找 因线性链表只能依次存取，即在查找时要从头指针找起，查找的时间困难度为 O(n)。（2） 插入与删除 因线性链表不须要移动元素，只要修改指针，一般状况下时间困难度为 O(1)。但是，假如要在单链表中进行前插或删除操作，因为要从头查找前驱结点，所耗时间困难度将是 O(n)。例

13、：在n个结点的单链表中要删除已知结点*P，需找到它的前驱结点的地址，其时间困难度为 O（n）8. 依次存储与链式存储的区分与优缺点？ 依次存储时，逻辑上相邻的数据元素，其物理存放地址也相邻。依次存储的优点是存储密度大，存储空间利用率高；缺点是插入或删除元素时不便利。链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。链式存储的优点是插入或删除元素时很便利，运用敏捷。缺点是存储密度小，存储空间利用率低。 依次表相宜于做查找这样的静态操作； 链表宜于做插入, 删除这样的动态操作。 若线性表的长度变更不大，且其主要操作是查找，则采纳依次表；

14、 若线性表的长度变更较大，且其主要操作是插入, 删除操作，则采纳链表。9. 推断：“数组的处理比其它困难的结构要简洁”，对吗？答：对的。因为 数组中各元素具有统一的类型； 数组元素的下标一般具有固定的上界与下界，即数组一旦被定义，它的维数与维界就不再变更。数组的基本操作比较简洁，除了结构的初始化与销毁之外，只有存取元素与修改元素值的操作。10. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 行下标 , 列下标 与 元素值 。 11. 写出右图所示稀疏矩阵的压缩存储形式。解：介绍3种存储形式。法1：用线性表表示： （( 1,2,12) ，(1,3,9)

15、， (3,1,-3)， (3,5,14)， (4,3,24)， (5,2,18) ，(6,1,15)， (6,4,-7)）法2：用十字链表表示用途：便利稀疏矩阵的加减运算方法：每个非0元素占用5个域法3：用三元组矩阵表示：稀疏矩阵压缩存储的缺点：将失去随机存取功能代码：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( ) /字母线性表的显示，即

16、读表操作 int i; for( i=0; iM)上溢 else stop+=e;依次栈出栈函数POP()status Pop( ) if(top=L) 下溢 else e=s-top; return(e); 队列的定义与操作，队列的删除在一端（队尾），而插入则在队列的另一端（队头）。因此在两种存储结构中，都须要队头与队尾两个指针。队列：只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。链队列结点类型定义： typedef Struct QNode QElemType data; /元素 Struct QNode *next; /指向下一结点的指针 Qnode , * QueueP

17、tr ;链队列类型定义： typedef struct QueuePtr front ; /队首指针 QueuePtr rear ; /队尾指针 LinkQueue;链队示意图： 空链队的特征：front=rear 链队会满吗？一般不会，因为删除时有free动作。除非内存不足！ 入队（尾部插入）：rear-next=S; rear=S; 出队（头部删除）：front-next=p-next;2. 依次队依次队类型定义：#define QUEUE-MAXSIZE 100 /最大队列长度 typedef struct QElemType *base; /队列的基址 int front; /队首指针

18、 int rear; /队尾指针 SqQueue建队核心语句：q . base=(QElemType *)malloc(sizeof (QElemType ）* QUEUE_MAXSIZE; /安排空间依次队示意图：循环队列：队空条件 : front = rear (初始化时：front = rear )队满条件： front = (rear+1) % N (N=maxsize)队列长度（即数据元素个数）：L=（Nrearfront）% N 1） 初始化一个空队列Status InitQueue ( SqQueue &q ) /初始化空循环队列 qq . base=(QElemType *)m

19、alloc(sizeof(QElemType）* QUEUE_MAXSIZE); /安排空间if (!q.base) exit(OVERFLOW);/内存安排失败，退出程序 q.front =q.rear=0; /置空队列 return OK; /InitQueue;2） 入队操作Status EnQueue(SqQueue &q, QElemType e)/向循环队列 q 的队尾加入一个元素 e if ( (q.rear+1) % QUEUE_MAXSIZE = = q.front ) return ERROR ; /队满则上溢，无法再入队 q.rear = ( q . rear + 1 )

20、 % QUEUE_MAXSIZE; q.base q.rear = e; /新元素e入队 return OK; / EnQueue;3） 出队操作Status DeQueue ( SqQueue &q, QElemType &e) /若队列不空，删除循环队列q的队头元素， /由 e 返回其值，并返回OK if ( q.front = = q.rear ) return ERROR;/队列空 q.front=(q.front+1) % QUEUE_MAXSIZE ; e = q.base q.front ; return OK; / DeQueue 链队列空的条件是首尾指针相等，而循环队列满的条

21、件的判定，则有队尾加1等于队头与设标记两种方法。补充重点：1. 为什么要设计堆栈？它有什么独特用途？ 调用函数或子程序非它莫属； 递归运算的有力工具； 用于爱护现场与复原现场； 简化了程序设计的问题。2.为什么要设计队列？它有什么独特用途？ 离散事务的模拟（模拟事务发生的先后依次,例如 CPU芯片中的指令译码队列）； 操作系统中的作业调度（一个CPU执行多个作业）； 简化程序设计。3. 什么叫“假溢出” ？如何解决？答：在依次队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。解决假溢出的途径采纳循环队列。4.在一个循环队列中，若约定队首指针指向队首元

22、素的前一个位置。那么，从循环队列中删除一个元素时，其操作是先 移动队首位置 ，后 取出元素。5.线性表, 栈, 队的异同点：相同点：逻辑结构相同，都是线性的；都可以用依次存储或链表存储；栈与队列是两种特殊的线性表，即受限的线性表（只是对插入, 删除运算加以限制）。不同点： 运算规则不同：线性表为随机存取；而栈是只允许在一端进行插入与删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入, 另一端进行删除运算，因而是先进先出表FIFO。 用途不同，线性表比较通用；堆栈用于函数调用, 递归与简化设计等；队列用于离散事务模拟, OS作业调度与简化设计等。第四章 串内容提要： 串是数据元素为字

23、符的线性表，串的定义与操作。串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。串比较：int strcmp(char *s1,char *s2); 求串长：int strlen(char *s); 串连接：char strcat(char *to,char *from) 子串T定位：char strchr(char *s,char *c); 串的存储结构，因串是数据元素为字符的线性表，所以存在“结点大小”的问题。模式匹配算法。串有三种机内表示方法：模式匹配算法：算法目的：确定主串中所含子串第一次出现的位置（定位）定位问题称为串的模式匹配，典型函数为Index(S,

24、T,pos)BF算法的实现即编写Index(S, T, pos)函数BF算法设计思想：将主串S的第pos个字符与模式T的第1个字符比较， 若相等，接着逐个比较后续字符；若不等，从主串S的下一字符（pos+1）起，重新与T第一个字符比较。 直到主串S的一个连续子串字符序列与模式T相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配胜利。否则，匹配失败，返回值 0。Int Index_BP(SString S, SString T, int pos) /返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0. / 其中，T非空，1posStrLength(S) i=pos; j

25、=1; while ( i=S0 & jT0) return i-T0; /T子串指针j正常到尾，说明匹配胜利， else return 0; /否则属于iS0状况，i先到尾就不正常 /Index_BP补充重点：1.空串与空白串有无区分？答：有区分。空串(Null String)是指长度为零的串；而空白串(Blank String),是指包含一个或多个空白字符 (空格键)的字符串.2. “空串是随意串的子串；随意串S都是S本身的子串，除S本身外，S的其他子串称为S的真子串。” 第六章 树与二叉树内容提要： 树是困难的非线性数据结构，树，二叉树的递归定义，基本概念，术语。树：由一个或多个(n0)

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

27、 从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号为2i1；其双亲的编号必为i/2（i1 时为根,除外）。 二叉树的存储结构：一, 依次存储结构按二叉树的结点“自上而下, 从左至右”编号，用一组连续的存储单元存储。若是完全/满二叉树则可以做到唯一复原。不是完全二叉树：一律转为完全二叉树！方法很简洁，将各层空缺处统统补上“虚结点”，其内容为空。缺点：奢侈空间；插入, 删除不便 二, 链式存储结构用二叉链表即可便利表示。一般从根结点起先存储。优点：不奢侈空间；插入, 删除便利 二叉树的遍历。指根据某种次序访问二叉树的全部结点，并且每个结点仅访问一次，得到一个线性序列。遍历规则二

28、叉树由根, 左子树, 右子树构成，定义为D, L, R若限定先左后右，则有三种实现方案： DLR LDR LRD先序遍历 中序遍历 后序遍历 树的存储结构，树, 森林的遍历与与二叉树的相互转换。 回顾2：二叉树怎样还原为树？ 要点：逆操作，把全部右孩子变为兄弟！ 探讨1：森林如何转为二叉树？ 法一： 各森林先各自转为二叉树； 依次连到前一个二叉树的右子树上。 法二：森林干脆变兄弟，再转为二叉树 探讨2：二叉树如何还原为森林？ 要点：把最右边的子树变为森林，其余右子树变为兄弟树与森林的存储方式：树有三种常用存储方式：双亲表示法 孩子表示法 孩子兄弟表示法问：树二叉树的“连线抹线旋转” 如何由计算

29、机自动实现？答：用“左孩子右兄弟”表示法来存储即可。存储的过程就是树转换为二叉树的过程！树, 森林的遍历： 先根遍历：访问根结点；依次先根遍历根结点的每棵子树。 后根遍历：依次后根遍历根结点的每棵子树；访问根结点。探讨：树若采纳“先转换，后遍历”方式，结果是否一样？1. 树的先根遍历与二叉树的先序遍历相同； 2. 树的后根遍历相当于二叉树的中序遍历；3. 树没有中序遍历，因为子树无左右之分。 先序遍历若森林为空，返回；访问森林中第一棵树的根结点；先根遍历第一棵树的根结点的子树森林；先根遍历除去第一棵树之后剩余的树构成的森林。 中序遍历若森林为空，返回；中根遍历森林中第一棵树的根结点的子树森林；

30、访问第一棵树的根结点；中根遍历除去第一棵树之后剩余的树构成的森林。 二叉树的应用：哈夫曼树与哈夫曼编码。Huffman树：最优二叉树（带权路径长度最短的树）Huffman编码：不等长编码。树的带权路径长度：（树中全部叶子结点的带权路径长度之与）构造Huffman树的基本思想：权值大的结点用短路径，权值小的结点用长路径。构造Huffman树的步骤（即Huffman算法）：(1) 由给定的 n 个权值 w1, w2, , wn 构成n棵二叉树的集合F = T1, T2, , Tn （即森林） ，其中每棵二叉树 Ti 中只有一个带权为 wi 的根结点，其左右子树均空。(2) 在F 中选取两棵根结点权

31、值最小的树 做为左右子树构造一棵新的二叉树，且让新二叉树根结点的权值等于其左右子树的根结点权值之与。(3) 在F 中删去这两棵树，同时将新得到的二叉树加入 F中。(4) 重复(2) 与(3) , 直到 F 只含一棵树为止。这棵树便是Huffman树。详细操作步骤：学习重点：（本章内容是本课程的重点） 二叉树性质与证明方法，并能把这种方法推广到K叉树。 二叉树遍历，遍历是基础，由此导出很多好用的算法，如求二叉树的高度, 各结点的层次数, 度为0, 1, 2的结点数。 由二叉树遍历的前序与中序序列或后序与中序序列可以唯一构造一棵二叉树。由前序与后序序列不能唯一确定一棵二叉树。 完全二叉树的性质。

32、树, 森林与二叉树间的相互转换。 哈夫曼树的定义, 构造与求哈夫曼编码。补充：1.满二叉树与完全二叉树有什么区分？答：满二叉树是叶子一个也不少的树，而完全二叉树虽然前k-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。2. Huffman树有什么用？最小冗余编码, 信息高效传输第七章 图内容提要： 图的定义，概念, 术语与基本操作。 图：记为 G( V, E ) 其中：V 是G 的顶点集合，是有穷非空集； E 是G 的边集合，是有穷集。 术语：见课件 图的存储结构。1.邻接矩阵(数组)表示法 建立一个顶点表与一个邻接矩阵 设图 A = (V, E) 有 n

33、个顶点，则图的邻接矩阵是一个二维数组 A.Edgenn。注：在有向图的邻接矩阵中， 第i行含义：以结点vi为尾的弧(即出度边）； 第i列含义：以结点vi为头的弧(即入度边）。邻接矩阵法优点：简洁实现图的操作，如：求某顶点的度, 推断顶点之间是否有边（弧）, 找顶点的邻接点等等。邻接矩阵法缺点：n个顶点须要n*n个单元存储边(弧);空间效率为O(n2)。2. 邻接表(链式)表示法 对每个顶点vi 建立一个单链表，把与vi有关联的边的信息（即度或出度边）链接起来，表中每个结点都设为3个域: 每个单链表还应当附设一个头结点（设为2个域），存vi信息； 每个单链表的头结点另外用依次存储结构存储。邻接表

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

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

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

37、顶点v1与v2是连通的。 假如图中随意一对顶点都是连通的, 则称此图是连通图。 非连通图的极大连通子图叫做连通重量。 生成树：是一个微小连通子图，它含有图中全部n个顶点，但只有n-1条边。 邻接点：若 (u, v) 是 E(G) 中的一条边，则称 u 与 v 互为邻接顶点。 图是困难的数据结构，也有依次与链式两种存储结构：数组表示法（重点是邻接距阵）与邻接表。这两种存储结构对有向图与无向图均适用 图的遍历是图的各种算法的基础，应娴熟驾驭图的深度, 广度优先遍历。 连通图的最小生成树不是唯一的，但最小生成树边上的权值之与是唯一的。 应娴熟驾驭prim与kruscal算法，特殊是手工分步模拟生成树

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

39、章 查找 内容提要： 查找表是称为集合的数据结构。是元素间约束力最差的数据结构：元素间的关系是元素仅共在同一个集合中。（同一类型的数据元素构成的集合） 查找表的操作：查找，插入，删除。 静态查找表：依次表，有序表等。 针对静态查找表的查找算法主要有:依次查找, 折半查找, 分块查找 一, 依次查找（线性查找） 技巧：把待查关键字key存入表头或表尾（俗称“哨兵”），这样可以加快执行速度。int Search_Seq( SSTable ST , KeyType key )ST.elem0.key =key; for( i=ST.length; ST.elem i .key!=key; - - i ); return i; / Search_Seq/ASL（1n）/2，时间效率为 O(n)，这是查找胜利的状况:依次查找的特点：优点：算法简洁，且对依次结构或链表结构均适用。缺点： ASL 太大，时间效率太低。 二, 折半查找（二分或对分查找） 若关键字不在表中，怎样得知并与时停止查找？ 典型标记是：当查找范围的上界下界时停止查