《2022年数据结构知识点全面总结—精华版2.docx》由会员分享，可在线阅读，更多相关《2022年数据结构知识点全面总结—精华版2.docx（29页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第1章绪论内容提要： 数据结构争论的内容；针对非数值运算的程序设计问题,争论运算机的操作对象 以及它们之间的 关系和操作 ；数据结构涵盖的内容： 基本概念：数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型；数据 全部能被运算机识别、储备和处理的符号的集合；数据元素 是数据的基本单位,具有完整确定的实际意义；数据对象 具有相同性质的数据元素的集合,是数据的一个子集；数据结构 是相互之间存在一种或多种特定关系的数据元素的集合,表示为：Data_Structure= （ D, R ）数据类型 是一个值的集合和定义在该值上的一组操作的总称；抽象数据类型 由用户定义的一个数学模型与定义在该模型
2、上的一组操作, 它由基本的数据类型构成； 算法的定义及五个特点；算法 是对特定问题求解步骤的一种描述,它是指令的有限序列,是一系列输入转换为输出的运算步骤；算法的基本特性 ：输入、输出、有穷性、确定性、可行性 算法设计要求；正确性、可读性、健壮性、效率与低储备量需求 算法分析；时间复杂度、空间复杂度、稳固性学习重点： 数据结构的“三要素” ：规律结构 、物理（储备）结构 及在 这种结构上所定义的操作（运算） ； 用运算语句频度来估算算法的时间复杂度；其次章 线性表内容提要： 线性表的储备结构：次序储备结构和链式储备结构；次序储备定义：把规律上相邻 的数据元素储备在物理上相邻的储备单元中的储备结
3、构；链式储备结构 : 其结点在储备器中的位置是随便的,定相邻；通过 指针 来实现！即规律上 相邻的数据元素在物理上不一 线性表的操作在两种储备结构中的实现；数据结构的基本运算：修改、插入、删除、查找、排序1) 修改通过数组的下标便可拜访某个特定元素并修改之；核心语句 :Vi=x;次序表修改操作的时间效率是O12) 插入在线性表的第i 个位置前插入一个元素实现步骤：将第 n 至第 i 位的元素向后移动一个位置；将要插入的元素写到第i 个位置；表长加 1；留意：事先应判定: 插入位置 i 是否合法 .表是否已满 .应当符合条件：1 i n+1或i=1, n+1核心语句：for j=n; j=i;
4、j-aj+1=a j ; a i =x;n+;插入时的平均移动次数为：nn+1/2 （ n+1） n/2On3) 删除删除线性表的第i 个位置上的元素实现步骤：将第 i+1至第 n 位的元素向前移动一个位置；表长减 1；留意：事先需要判定,删除位置应当符合条件：1 i n核心语句：或i 是否合法 .i=1, n 线性表的规律结构定义,对线性表定义的操作；线性表的定义：用数据元素的有限序列表示for j=i+1; j=n; j+ aj-1=aj;n-;次序表插入、删除算法的平均空间复杂度为O1次序表删除一元素的时间效率为:T（ n=n-1/2 On单链表：（ 1）用单链表结构来存放26 个英文字
5、母组成的线性表（a, b,c, z） ,请写出 C 语言程序；#include #include typedef struct node char data;struct node *next;node;node *p,*q,*head;/ 一般需要 3 个指针变量int n ;/ 数据元素的个数int m=sizeofnode;/* 结构类型定义好之后,每个node 类型的长度就固定了,m 求一次即可 */void build / 字母链表的生成；要一个个渐渐链入int i;head=node*mallocm;/m=sizeofnode前面已求出p=head;for i=1; idata=i
6、+ a -1;/ 第一个结点值为字符a p-next=node*mallocm;/ 为后继结点“挖坑” ！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 个数据元素,必需从头指针起始终找到该结点的指针p, 然后才能： pdata=new_value
7、读取第 i 个数据元素的核心语句是：Linklist *findLinklist *head ,int iint j=1;Linklist *p;P=head-next;Whilep.=NULL&jnext; j+;return p;链表插入的核心语句：Step 1： s-next=p-next; Step 2： p-next=s；6.单链表的删除删除动作的核心语句（要借助帮助指针变量q）：q = p-next;p-next=q-next; freeq ；/ 第一储存 b 的指针,靠它才能找到c；/将 a、c 两结点相连,剔除b 结点；/完全释放 b 结点空间7.双向链表的插入操作：3.单链表
8、的插入设 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-next =p-next;前驱方向： ai+1 的前驱由 ai 指针 p变为 ai-1 指针 p - pri
9、or ;p-next-prior = p -prior ; 数组的规律结构定义及储备数组： 由一组名字相同、下标不同的变量构成N 维数组的特点： n 个下标,每个元素受到n 个关系约束一个 n 维数组可以看成是由如干个 n 1 维数组 组成的线性表；储备：事先商定按某种次序将数组元素排成一列序列,然后将这个线性序列存入储备器中；在二维数组中,我们既可以规定按行储备,也可以规定按列储备；设一般的二维数组是Ac1.d1, c2.d2 ,就行优先储备时的地址公式为：二维数组列优先储备的通式为： 稀疏矩阵（含特殊矩阵）的储备及运算；稀疏矩阵：矩阵中非零元素的个数较少（一般小于5%）学习重点： 线性表的
10、规律结构,指线性表的数据元素间存在着线性关系 ；在次序储备结构中,元素储备的 先后位置 反映出这种线性关系,而在链式储备结构中,是靠指针来反映这种关系的； 次序储备结构用一维数组表示,给定下标,可以存取相应元素,属于随机存取 的储备结构； 链表操作中应留意不要使链意外“断开”；因此,如在某结点前插入一个元素,或删除某元素,必需知道该元素的前驱结点的指针 ； 把握通过画出结点图来进行链表（单链表、循环链表等）的生成、插入、删除、遍历等操作； 数组（主要是二维）在以行序 /列序 为主的储备中的地址运算方法； 稀疏矩阵的三元组表储备结构； 稀疏矩阵的十字链表储备方法；补充重点：1. 每个储备结点都包
11、含两部分：数据域和指针域 链域 2. 在单链表中, 除了首元结点外, 任一结点的储备位置由其直接前驱结点的链域的值指示；3. 在链表中设置头结点有什么好处？头结点即在链表的首元结点之前附设的一个结点,该结点的 数据域可以为空, 也可存放表长度 等附加信息, 其作用是为了对链表进行操作时,可以对 空表、 非空表 的情形以及对 首元结点 进行统一处理,编程更便利；4. 如何表示空表？（1） 无头结点时,当头指针的值为空时表示空表；（2） 有头结点时,当头结点的指针域为空时表示空表；5. 链表的数据元素有两个域,不再是简洁数据类型,编程时该如何表示？因每个结点至少有两个重量,且数据类型通常不一样,所
12、以要采纳结构数据类型；6. sizeofx运算变量 x 的长度（字节数） ；mallocm 开创 m 字节长度的地址空间,并返回这段空间的首地址； freep 释放指针 p 所指变量的储备空间,即完全删除一个变量；7.链表的运算效率分析：（ 1）查找因线性链表只能次序存取,即在查找时要从头指针找起,查找的时间复杂度为On ；（ 2） 插入和删除因线性链表不需要移动元素,只要修改指针,一般情形下时间复杂度为O1 ；但是,假如要在单链表中进行前插或删除操作,由于要从头查找前驱结点,所耗时间复杂度将是 On ；例：在 n 个结点的单链表中要删除已知结点*P ,需找到它的 前驱结点的地址 ,其时间复杂
13、度为 O （ n）8. 次序储备和链式储备的区分和优缺点？次序储备时, 规律上相邻的数据元素,其物理存放地址也相邻； 次序储备的优点是储备密度大,储备空间利用率高；缺点是插入或删除元素时不便利；链式储备时, 相邻数据元素可随便存放, 但所占储备空间分两部分, 一部分存放结点值, 另一部分存放表示结点间关系的指针；链式储备的优点是插入或删除元素时很便利,使用敏捷；缺点是储备密度小,储备空间利用率低； 次序表相宜于做查找这样的静态操作； 链表宜于做插入、删除这样的动态操作； 如线性表的长度变化不大,且其主要操作是查找,就采纳次序表； 如线性表的长度变化较大,且其主要操作是插入、删除操作,就采纳链表
14、；9. 判定：“数组的处理比其它复杂的结构要简洁”,对吗？ 答：对的；由于 数组中各元素具有统一的类型； 数组元素的下标一般具有固定的上界和下界,即数组一旦被定义,它的维数和维界就不再转变；数组的 基本操作比较简 单,除了结构的初始化和销毁之外,只有存取元素和修改元素值的操作；10. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素,它包含有三个数据项,分别表示该元素的行下标、列下标和 元素值；11. 写出右图所示稀疏矩阵的压缩储备形式；解：介绍 3 种储备形式；法 1：用线性表表示：（ 1,2,12, 1,3,9 , 3,1,-3 , 3,5,14,4,3,24 , 5,2,18,6,1,
15、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 / 字母线性表的显示,即读表操作int i;for i=0;iM上溢 else stop+=e;次序栈出栈函数 POP sta
16、tus Pop iftop=L 下溢 else e=s-top;returne; 队列的定义及操作,队列的删除在一端（队尾）,而插入就在队列的另一端（队头）；因此在两种储备结构中,都需要队头和队尾两个指针；队列：只能在表的一端进行插入运算,在表的另一端进行删除运算的线性表；链队列结点类型定义：typedef Struct QNodeQElemTypedata;/ 元素StructQNode*next;/指向下一结点的指针Qnode , * QueuePtr ; 链队列类型定义： typedefstruct QueuePtrfront ; / 队首指针QueuePtrrear ; / 队尾指针L
17、inkQueue;链队示意图：空链队的特点： front=rear链队会满吗？一般不会,由于删除时有free 动作；除非内存不足！入队（尾部插入） ： rear-next=S; rear=S;出队（头部删除） ： front-next=p-next; 2.次序队次序队类型定义：#defineQUEUE-MAXSIZE100/ 最大队列长度typedefstruct QElemType*base;/队列的基址intfront;/队首指针intrear;/ 队尾指针SqQueue建队核心语句：q . base=QElemType *mallocsizeof QElemType）* QUEUE_MA
18、XSIZE;/ 安排空间次序队示意图：循环队列：队空条件 :front = rear初始化时： front = rear 队满条件： front = rear+1 % NN=maxsize队列长度（即数据元素个数） ： L= （ N rear front ） % N 1）初始化一个空队列StatusInitQueue SqQueue&q / 初始化空循环队列qq . base=QElemType *mallocsizeofQElemType）* QUEUE_MAXSIZE;/ 安排空间if .q.baseexitOVERFLOW;/内存安排失败,退出程序q.front =q.rear=0; /
19、 置空队列return OK; /InitQueue;2） 入队操作StatusEnQueueSqQueue&q,QElemType e/ 向循环队列q 的队尾加入一个元素eif q.rear+1 %QUEUE_MAXSIZE = =q.frontreturnERROR ; / 队满就上溢,无法再入队q.rear = q . rear + 1 %QUEUE_MAXSIZE;q.base q.rear = e;/ 新元素 e 入队returnOK;/ EnQueue;3） 出队操作StatusDeQueue SqQueue&q,QElemType &e/ 如队列不空,删除循环队列q 的队头元素,
20、/由 e 返回其值,并返回OKif q.front = = q.rear return ERROR;/ 队列空q.front=q.front+1 % QUEUE_MAXSIZE ; e = q.base q.front ;return OK;/ DeQueue 链队列空的条件是首尾指针相等,而循环队列满的条件的判定,就有队尾加1 等于队头和设标记两种方法；补充重点：1. 为什么要设计堆栈？它有什么特殊用途？ 调用函数或子程序非它莫属； 递归运算的有力工具； 用于爱护现场和复原现场； 简化了程序设计的问题；2. 为什么要设计队列？它有什么特殊用途？ 离散大事的模拟（模拟大事发生的先后次序,例如
21、CPU 芯片中的指令译码队列） ； 操作系统中的作业调度（一个CPU 执行多个作业） ； 简化程序设计；3. 什么叫“假溢出”？如何解决？答：在次序队中,当尾指针已经到了数组的上界,不能再有入队操作,但其实数组中仍有空位置,这就叫“假溢出” ；解决假溢出的途径采纳循环队列；4. 在一个循环队列中,如商定队首指针指向队首元素的前一个位置；那么,从循环队列中删除一个元素时,其操作是先移动队首位置,后 取出元素 ；5. 线性表、栈、队的异同点：相同点：规律结构相同, 都是线性的；都可以用次序储备或链表储备；栈和队列是两种特殊的线性表,即受限的线性表（只是对插入、删除运算加以限制）；不同点： 运算规章
22、不同： 线性表为随机存取；而栈是只答应在一端进行插入和删除运算,因而是后进先出表LIFO ；队列是只答应在一端进行插入、另一端进行删除运算,因而是先进先出表FIFO ； 用途不同,线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散大事模拟、 OS 作业调度和简化设计等；第四章 串内容提要 ： 串是数据元素为字符的线性表,串的定义及操作；串即字符串,是由零个或多个字符组成的有限序列,是数据元素为单个字符的特殊线性表；串比较： int strcmpchar *s1,char *s2;求串长： int strlenchar *s;串连接： charstrcatchar *to,char
23、 *from子串 T 定位： char strchrchar *s,char *c; 串的储备结构,因串是数据元素为字符的线性表,所以存在“结点大小”的问题；模式匹配算法；串有三种机内表示方法：模式匹配算法：算法目的：确定主串中所含子串第一次显现的位置（定位） 定位问题称为串的模式匹配,典型函数为IndexS,T,pos BF 算法的实现即编写IndexS, T, pos函数BF 算法设计思想：将主串 S 的第 pos 个字符和模式 T 的第 1 个字符比较, 如相等,连续逐个比较后续字符；如不等,从主串 S 的下一字符（ pos+1）起,重新与 T 第一个字符比较；直到主串 S 的一个连续子
24、串字符序列与模式T 相等；返回值为 S 中与 T 匹配的子序列第一个字符的序号,即匹配胜利；否就,匹配失败,返回值0；Int Index_BPSString S, SString T, int pos / 返回子串 T 在主串 S 中第 pos 个字符之后的位置；如不存在,就函数值为0./ 其中, T 非空, 1 posStrLengthS i=pos;j=1;while i=S0 & jT0 return i-T0;/T 子串指针 j 正常到尾, 说明匹配胜利,else return 0;/否就属于 iS0 情形, i 先到尾就不正常 /Index_BP补充重点：1. 空串和空白串有无区分？
25、 答：有区分；空串 Null String 是指长度为零的串；而空白串 BlankString, 是指包含一个或多个空白字符 空格键 的字符串 .2. “空串是任意串的子串；任意串S 都是 S 本身的子串,除 S 本身外, S 的其他子串称为 S的真子串；”第六章 树和二叉树内容提要： 树是复杂的非线性数据结构,树,二叉树的递归定义,基本概念,术语；树：由一个或多个 n 0结点组成的有限集合T,有且仅有一个结点称为根（root）,当 n1时,其余的结点分为mm 0个互不相交的有限集合T1,T2 , Tm；每个集合本身又是棵树,被称作这个根的子树；二叉树：是 n（ n0）个结点的有限集合,由一个
26、根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成；术语： P88 二叉树的性质,储备结构；性质 1: 在二叉树的第 i 层上至多有 2i-1 个结点（ i0 ）；性质 2: 深度为 k 的二叉树至多有 2k-1 个结点（ k0 ）；性质 3: 对于任何一棵二叉树,如2 度的结点数有 n2 个,就叶子数（ n0）必定为 n2 1性质 4: 具有 n 个结点的完全二叉树的深度必为性质 5: 对完全二叉树,如从上至下、从左至右编号,就编号为i的结点,其左孩子编号必为 2i ,其右孩子编号为2i1；其双亲的编号必为i/2 （i 1 时为根 ,除外）；二叉树的储备结构：一、次序储备结构按二叉
27、树的结点“自上而下、从左至右”编号,用一组连续的储备单元储备；如是完全 /满二叉树就可以做到唯独复原；不是完全二叉树：一律转为完全二叉树！方法很简洁,将各层空缺处统统补上“虚结点”,其内容为空；缺点：铺张空间；插入、删除不便二、链式储备结构用二叉链表即可便利表示；一般从根结点开头储备；优点：不铺张空间；插入、删除便利 二叉树的遍历；指根据某种次序拜访二叉树的全部结点,并且每个结点仅拜访一次,得到一个线性序列；遍历规章二叉树由根、左子树、右子树构成,定义为D、 L 、R如限定先左后右,就有三种实现方案：DLRLDRLRD先序遍历中序遍历后序遍历 树的储备结构,树、森林的遍历及和二叉树的相互转换；
28、回忆 2：二叉树怎样仍原为树？要点：逆操作,把全部右孩子变为兄弟！ 争论 1：森林如何转为二叉树？法一： 各森林先各自转为二叉树；依次连到前一个二叉树的右子树上；法二：森林直接变兄弟,再转为二叉树争论 2：二叉树如何仍原为森林？要点：把最右边的子树变为森林,其余右子树变为兄弟树和森林的储备方式：树有三种常用储备方式：双亲表示法孩子表示法孩子兄弟表示法问：树二叉树的“连线抹线旋转”如何由运算机自动实现？ 答：用“左孩子右兄弟”表示法来储备即可；储备的过程就是树转换为二叉树的过程！树、森林的遍历： 先根遍历：拜访根结点；依次先根遍历根结点的每棵子树； 后根遍历：依次后根遍历根结点的每棵子树；拜访根
29、结点；争论：树如采纳“先转换,后遍历”方式,结果是否一样？1. 树的先根遍历与二叉树的先序遍历相同；2. 树的后根遍历相当于二叉树的中序遍历；3. 树没有中序遍历,由于子树无左右之分； 先序遍历如森林为空,返回；拜访森林中第一棵树的根结点；先根遍历第一棵树的根结点的子树森林；先根遍历除去第一棵树之后剩余的树构成的森林； 中序遍历如森林为空,返回；中根遍历森林中第一棵树的根结点的子树森林； 拜访第一棵树的根结点；中根遍历除去第一棵树之后剩余的树构成的森林； 二叉树的应用：哈夫曼树和哈夫曼编码；Huffman 树：最优二叉树（带权路径长度最短的树） Huffman 编码：不等长编码；树的带权路径长
30、度：（树中全部叶子结点的带权路径长度之和） 构造 Huffman 树的基本思想：权值大的结点用短路径,权值小的结点用长路径；构造 Huffman 树的步骤（即 Huffman 算法）：(1) 由给定的 n 个权值 w1, w2, wn 构成 n 棵二叉树的集合 F = T1, T2, , Tn （即森林） ,其中每棵二叉树Ti中只有一个带权为wi的根结点,其左右子树均空；(2) 在 F 中选取两棵根结点权值最小的树做为左右子树构造一棵新的二叉树,且让新二叉树根结点的权值等于其左右子树的根结点权值之和；(3) 在 F 中删去这两棵树,同时将新得到的二叉树加入F 中；(4) 重复 2和3 , 直到
31、 F 只含一棵树为止；这棵树便是Huffman 树；详细操作步骤：学习重点：（本章内容是本课程的重点） 二叉树性质及证明方法,并能把这种方法推广到K 叉树； 二叉树遍历,遍历是基础,由此导出很多有用的算法,如求二叉树的高度、各结点的层次数、度为 0、1、2 的结点数； 由二叉树遍历的前序和中序序列或后序和中序序列可以唯独构造一棵二叉树；由前序和后序序列不能唯独确定一棵二叉树； 完全二叉树的性质； 树、森林和二叉树间的相互转换； 哈夫曼树的定义、构造及求哈夫曼编码；补充：1. 满二叉树和完全二叉树有什么区分？答：满二叉树是叶子一个也不少的树,而完全二叉树虽然前k-1 层是满的,但最底层却答应在右
32、边缺少连续如干个结点；满二叉树是完全二叉树的一个特例；2. Huffman 树有什么用？ 最小冗余编码、信息高效传输第七章 图内容提要： 图的定义,概念、术语及基本操作；图：记为G V, E 其中： V是 G 的顶点集合,是有穷非空集；E 是 G 的边集合,是有穷集；术语：见课件 图的储备结构；1.邻接矩阵 数组表示法 建立一个顶点表和一个邻接矩阵 设图 A = V , E 有 n 个顶点,就图的邻接矩阵是一个二维数组A.Edgenn ；注：在有向图的邻接矩阵中,第 i 行含义：以结点 vi 为尾的弧 即出度边）； 第 i 列含义：以结点 vi 为头的弧 即入度边）；邻接矩阵法优点：简洁实现图
33、的操作,如：求某顶点的度、判定顶点之间是否有边（弧）、找顶点的邻接点等等；邻接矩阵法缺点： n 个顶点需要 n*n 个单元储备边 弧;空间效率为On2；2.邻接表 链式 表示法 对每个顶点 vi建立一个单链表,把与vi 有关联的边的信息（即度或出度边）链接起来,表中每个结点都设为3 个域 : 每个单链表仍应当附设一个头结点（设为2 个域）,存 vi 信息； 每个单链表的头结点另外用次序储备结构储备；邻接表的优点：空间效率高；简洁查找顶点的邻接点；邻接表的缺点： 判定两顶点间是否有边或弧,需搜寻两结点对应的单链表,没有邻接矩阵便利； 图的遍历；遍历定义：从已给的连通图中某一顶点动身,沿着一些边,
34、访遍图中全部的顶点,且使每个顶点仅被拜访一次,就叫做图的遍历,它是图的基本运算；图常用的遍历：一、深度优先搜寻；二、广度优先搜寻深度优先搜寻（遍历）步骤： 拜访起始点 v; 如 v 的第 1 个邻接点没拜访过,深度遍历此邻接点； 如当前邻接点已拜访过,再找v 的第 2 个邻接点重新遍历；基本思想：仿树的先序遍历过程；广度优先搜寻（遍历）步骤： 在拜访了起始点 v 之后,依次拜访v 的邻接点； 然后再依次（次序）拜访这些点（下一层）中未被拜访过的邻接点； 直到全部顶点都被拜访过为止； 图的应用（最小生成树,最短路经）最小生成树（ MST ）的性质如下：如U 集是 V 的一个非空子集,如 u0,
35、v0 是一条最小权值的边,其中 u0U ,v0V-U ；就： u0, v0必在最小生成树上；求 MST 最常用的是以下两种：Kruskal （克鲁斯卡尔）算法、Prim （普里姆）算法Kruskal 算法特点：将边归并,适于求稀疏网的最小生成树；Prime 算法特点 : 将顶点归并,与边数无关,适于稠密网；在带权有向图中A 点（源点）到达 B 点（终点）的多条路径中,查找一条各边权值之和最小的路径,即最短路径；两种常见的最短路径问题：一、 单源最短路径用Dijkstra （迪杰斯特拉）算法二、全部顶点间的最短路径用Floyd （弗洛伊德）算法一、单源最短路径Dijkstra 算法 一顶点到其余
36、各顶点（v0j）目的： 设一有向图 G=（ V, E）,已知各边的权值,以某指定点v0 为源点,求从 v0 到图的其余各点的最短路径；限定各边上的权值大于或等于0；二、全部顶点之间的最短路径可以通过调用 n 次 Dijkstra 算法来完成,仍有更简洁的一个算法：Floyd 算法（自学） ；学习重点： 图是应用最广泛的一种数据结构,本章也是这门课程的重点； 基本概念中,连通重量,生成树,邻接点是重点； 连通图： 在无向图中 , 如从顶点 v1 到顶点 v2 有路径 , 就称顶点 v1 与 v2 是连通的；假如图中任意一对顶点都是连通的, 就称此图是连通图；非连通图的极大连通子图叫做连通重量；
37、生成树： 是一个微小连通子图,它含有图中全部n 个顶点,但只有 n-1 条边； 邻接点： 如 u, v是 EG 中的一条边,就称u 与 v 互为邻接顶点； 图是复杂的数据结构,也有次序和链式两种储备结构：数组表示法（重点是邻接距阵） 和邻接表；这两种储备结构对有向图和无向图均适用 图的遍历是图的各种算法的基础,应娴熟把握图的深度、广度优先遍历； 连通图的最小生成树不是唯独的,但最小生成树边上的权值之和是唯独的；应娴熟把握 prim 和 kruscal 算法,特殊是手工分步模拟生成树的生成过程； 从单源点到其他顶点,以及各个顶点间的最短路径问题,把握娴熟手工模拟；补充：1. 问：当有向图中仅1
38、个顶点的入度为 0,其余顶点的入度均为1,此时是何外形？ 答：是树！而且是一棵有向树！2. 争论：邻接表与邻接矩阵有什么异同之处？1. 联系：邻接表中每个链表对应于邻接矩阵中的一行, 链表中结点个数等于一行中非零元素的个数；2. 区分：对于任一确定的无向图,邻接矩阵是唯独的（行列号与顶点编号一样）, 但邻接表不唯独（链接次序与顶点编号无关）；3. 用途：邻接矩阵多用于稠密图的储备而邻接表多用于稀疏图的储备3.如对连通图进行遍历,得到的是生成树如对非连通图进行遍历,得到的是生成森林；第八章查找内容提要： 查找表是称为集合的数据结构；是元素间约束力最差的数据结构：元素间的关系是元素仅共在同一个集合
39、中； （同一类型的数据元素构成的集合） 查找表的操作：查找,插入,删除； 静态查找表：次序表,有序表等；针对静态查找表的查找算法主要有:次序查找、折半查找、分块查找一、次序查找（线性查找）技巧：把待查关键字key 存入表头或表尾（俗称“哨兵”）,这样可以加快执行速度；int Search_Seq SSTableST , KeyTypekey ST.elem0.key =key;for i=ST.length; ST.elem i .key.=key;- - i; return i; / Search_Seq/ASL （ 1 n）/2 ,时间效率为On ,这是查找胜利的情形:次序查找的特点：优点
40、：算法简洁,且对次序结构或链表结构均适用；缺点： ASL太大,时间效率太低；二、折半查找（二分或对分查找）如关键字不在表中,怎样得知并准时停止查找？典型标志是：当查找范畴的上界下界时停止查找；ASL 的1含义m 是 “j 平1 均每n 个1数据的查找时间” ,而前式是 n 个数据查找时间的总和, 所以：ASLj2n j 1log 2 n11nlog 2 n三、分块查找（索引次序查找）思路： 先让数据分块有序, 即分成如干子表, 要求每个子表中的数据元素值都比后一块中的数值小（但子表内部未必有序）；然后将各子表中的最大关键字构成一个索引表,表中仍要包含每个子表的起始地址（即头指针）；特点：块间有序,块内无序；查找：块间折半,块内线性 查找步骤分两步进行： 对索引表使用折半查找法（由于索引表是有序表）；