算法与数据结构 期末考试复习

算法与数据结构算法与数据结构复习复习2013秋季秋季l属于程序设计的一个重要内容，训练如何对数据信息进行抽象。属于程序设计的一个重要内容，训练如何对数据信息进行抽象。算法与数据结构的主要内容算法与数据结构的主要内容l对数据信息进行抽象，从逻辑关系上，可以得到四大类数据结对数据信息进行抽象，从逻辑关系上，可以得到四大类数据结构：构： 集合集合 线性结构（线性表、栈、队列、串、数组）线性结构（线性表、栈、队列、串、数组） 树形结构树形结构 图状结构或网状结构图状结构或网状结构l对应四种逻辑关系，均可以采用两种存储结构进行物理存储：对应四种逻辑关系，均可以采用两种存储结构进行物理存储： 顺序存储结构顺序存储结构 链式存储结构（指针型链表、数组型静态链表）链式存储结构（指针型链表、数组型静态链表）l对应四种逻辑关系，均可以设计出具体的操作方法对应四种逻辑关系，均可以设计出具体的操作方法 结构的初始化、销毁，数据的查找、插入、删除、比较等结构的初始化、销毁，数据的查找、插入、删除、比较等l对四种逻辑关系的操作方法进行了具体的编程实现，也例举了对四种逻辑关系的操作方法进行了具体的编程实现，也例举了它们的一些具体应用。它们的一些具体应用。多项式的表示和操作多项式的表示和操作离散事件系统模拟离散事件系统模拟递归程序的实现递归程序的实现文本编辑系统的设计文本编辑系统的设计霍夫曼编码方法霍夫曼编码方法判定树的构造判定树的构造最短路径、关键路径、拓扑排序最短路径、关键路径、拓扑排序l对于集合结构，研究了两种重要操作，即排序和查找对于集合结构，研究了两种重要操作，即排序和查找第一章第一章 绪论绪论1、基本概念和术语、基本概念和术语“数据结构数据结构”课程的研究内容及在计算机科学中的地位；课程的研究内容及在计算机科学中的地位；数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型；数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型；逻辑结构和物理结构、顺序存储结构和链式存储结构；逻辑结构和物理结构、顺序存储结构和链式存储结构；2、抽象数据类型的表示和实现、抽象数据类型的表示和实现 三元组表示法；三元组表示法； 熟悉类熟悉类c语言的语法；语言的语法； 3、算法和算法分析、算法和算法分析 算法的定义和算法的定义和5个重要特性；个重要特性； 算法设计的算法设计的4个要求及含义；个要求及含义； 算法效率的度量算法效率的度量 渐进时间复杂度的概念；渐进时间复杂度的概念； 简单算法的时间复杂度的估算；简单算法的时间复杂度的估算；第二章第二章 线性表线性表1、线性表的类型定义、线性表的类型定义 线性结构线性结构 线性表的定义及特性线性表的定义及特性2、线性表的顺序表示和实现、线性表的顺序表示和实现 线性表的动态分配顺序存储结构线性表的动态分配顺序存储结构 线性表插入、删除算法，线性表插入、删除算法，算法算法2.4、2.5 插入、删除算法的平均时间复杂度的估算插入、删除算法的平均时间复杂度的估算3、线性表的链式表示和实现、线性表的链式表示和实现 线性链表的概念线性链表的概念 线性单链表的存储结构和创建、线性单链表的存储结构和创建、插入插入、删除、合并算法、删除、合并算法 循环链表的概念、特点循环链表的概念、特点 双向链表的存储结构和插入删除算法，双向链表的存储结构和插入删除算法，算法算法2.18、2.194、一元多项式的表示与相加算法、一元多项式的表示与相加算法typedef struct PNode float coef；/系数系数 int expn； /指数指数 struct PNode *next； PNode，PLinkList；相加算法要求读懂、理解，算法相加算法要求读懂、理解，算法2.23pabxs例如：在线性链表两个数据元素例如：在线性链表两个数据元素a和和b间插入间插入x, 已知已知p指针指针指向指向a。s-next = p-next;p-next = s;Status ListInsert_L(LinkList &L, int i, ElemType e) /在位置在位置i插入元素插入元素e e；p = L; j = 0;while (p & jnext; +jif (!p | ji-1) return ERROR; /指定的插入位置超界；指定的插入位置超界；s = ( LinkList) malloc ( sizeof (LNode) );s-data = e; s-next = p-next;p-next = s;return OK; nOnT第三章第三章 栈和队列栈和队列1、栈的表示和实现、栈的表示和实现栈的概念、特点、表示和实现（栈的概念、特点、表示和实现（顺序存储结构顺序存储结构）；）；栈的初始化、取栈顶元素、栈的初始化、取栈顶元素、元素的入栈、出栈算法元素的入栈、出栈算法，47页；页；2、栈的应用、栈的应用 数制转换算法，算法数制转换算法，算法3.13.1； 求解求解n n阶阶HanoiHanoi塔问题的递归过程和算法，算法塔问题的递归过程和算法，算法3.53.5；3、队列的定义、特点、队列的定义、特点链队列的表示和实现、元素的插入链队列的表示和实现、元素的插入和和删除算法删除算法；循环队列的表示和实现循环队列的表示和实现、元素的插入和删除算法元素的插入和删除算法；离散事件模拟过程、算法、运行结果，离散事件模拟过程、算法、运行结果，算法算法3.7；顺序栈顺序栈typedef structSElemType * base;SElemType * top;intstacksize;SqStack; 栈的存储结构栈的存储结构Status Push(SqStack &S, SElemType e)Status Push(SqStack &S, SElemType e) if(S.top S.base = S.stacksize) if(S.top S.base = S.stacksize)/栈满，追加空间；栈满，追加空间； S.base = (SElemType S.base = (SElemType * *) realloc(S.base,) realloc(S.base, (S.stacksize +STACKINCREMENT) (S.stacksize +STACKINCREMENT) * * sizeof(SElemType) sizeof(SElemType)； if(!S.base) exit (OVERFLOW);if(!S.base) exit (OVERFLOW); S.top = S.base + S.stacksize; S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; S.stacksize += STACKINCREMENT; * * S.top + + =e; S.top + + =e; /先将元素压入堆栈，后移动指针；先将元素压入堆栈，后移动指针； return OK;return OK; Status Pop(SqStack &S, SElemType &e)Status Pop(SqStack &S, SElemType &e) if(S.top = = S.base)return ERROR; if(S.top = = S.base)return ERROR; /堆栈为空；堆栈为空； e = e = * *- -S.top; - -S.top; /先移动指针先移动指针, ,再将元素弹出堆栈；再将元素弹出堆栈； return OK;return OK; 栈顶指针栈顶指针top等于等于栈底指栈底指针针base时，栈是空栈。时，栈是空栈。top123450进栈进栈A栈满栈满BCDEF 非空栈的非空栈的栈顶指针栈顶指针始终指向栈顶元素始终指向栈顶元素的下一个位置。的下一个位置。toptoptoptoptoptop出栈出栈123450ABCDEFtoptoptoptop=base栈空栈空toptoptop=base123450栈空栈空basetop=base先把元素压入堆栈，先把元素压入堆栈，再移动指针。再移动指针。先移动指针，再把先移动指针，再把栈顶元素弹出。栈顶元素弹出。n只能在栈顶进行数据元素的入栈和出栈操只能在栈顶进行数据元素的入栈和出栈操作。作。 Status EnQueue (LinkQueue &Q, QElemType e) Status EnQueue (LinkQueue &Q, QElemType e) / / 插入元素插入元素e e为为Q Q的新的队尾元素的新的队尾元素 p = new QNode;p = new QNode; if (!p) exit (OVERFLOW); if (!p) exit (OVERFLOW); /存储分配失败存储分配失败 p-data = e; p-next = NULL;p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; Q.rear-next = p; Q.rear = p; return OK; return OK; / 结点类型结点类型 typedef struct QNode QElemType data; struct QNode *next; QNode, * QueuePtr;/ / 链队列类型链队列类型typedef struct QueuePtr front; / 队头指针队头指针 QueuePtr rear; / 队尾指针队尾指针 LinkQueue; Status DeQueue (LinkQueue &Q, QElemType &e) Status DeQueue (LinkQueue &Q, QElemType &e) / / 若队列不空，则删除若队列不空，则删除Q Q的队头元素，的队头元素， /用用 e e 返回其值，并返回返回其值，并返回OKOK；否则返回；否则返回ERRORERROR if (Q.front = Q.rear) return ERROR; if (Q.front = Q.rear) return ERROR; p = Q.front-next; e = p-data; p = Q.front-next; e = p-data; Q.front-next = p-next; Q.front-next = p-next; if (Q.rear = = p) Q.rear = Q.front; if (Q.rear = = p) Q.rear = Q.front; /防止队尾指针丢失；防止队尾指针丢失； delete (p); delete (p); return OK; return OK; #define MAXQSIZE 100 /最大队列长度最大队列长度typedef struct QElemType *base; / / 动态分配存储空间动态分配存储空间 int front; / / 头指针，若队列不空，指向队列头元素头指针，若队列不空，指向队列头元素; ; int rear; / / 尾指针，若队列不空，指向队列尾元素的下一个位置尾指针，若队列不空，指向队列尾元素的下一个位置; ; SqQueue;0M-11frontrear.Status EnQueue (SqQueue &Q, ElemType e) Status EnQueue (SqQueue &Q, ElemType e) / / 插入元素插入元素e e为为Q Q的新的队尾元素的新的队尾元素; ; if (Q.rear+1) % MAXQSIZE = Q.front) if (Q.rear+1) % MAXQSIZE = Q.front) return ERROR; return ERROR; /队列满队列满 Q.baseQ.rear = e;Q.baseQ.rear = e; Q.rear = (Q.rear+1) % MAXQSIZE; Q.rear = (Q.rear+1) % MAXQSIZE; return OK; return OK; Status DeQueue (SqQueue &Q, ElemType &e) Status DeQueue (SqQueue &Q, ElemType &e) / / 若队列不空，则删除若队列不空，则删除Q Q的队头元素，的队头元素， / / 用用e e返回其值，并返回返回其值，并返回OK;OK;否则返回否则返回ERRORERROR if (Q.front = Q.rear) return ERROR; if (Q.front = Q.rear) return ERROR; e = Q.baseQ.front; e = Q.baseQ.front; Q.front = (Q.front+1) % MAXQSIZE; Q.front = (Q.front+1) % MAXQSIZE; return OK; return OK;第四章第四章 串串1、串类型的定义、表示和实现、串类型的定义、表示和实现 定长顺序存储表示定长顺序存储表示 堆分配存储表示堆分配存储表示 串的块链存储表示串的块链存储表示 串的抽象数据类型定义串的抽象数据类型定义 串和串的基本概念串和串的基本概念串串(String)(String)是零个或多个字符组成的有限序列。一般是零个或多个字符组成的有限序列。一般记作记作S=aS=a1 1 a a2 2 a a3 3 a an n，其中，其中S S是串名，单引号括是串名，单引号括起来的字符序列是串值；起来的字符序列是串值；a ai i(1(1i in)n)可以是字母、数可以是字母、数字或其它字符；串中所包含的字符个数称为串的字或其它字符；串中所包含的字符个数称为串的长度长度。空串空串(Empty String)(Empty String)是长度为零的串，它不包含任何是长度为零的串，它不包含任何字符。字符。空白串空白串(Blank String)(Blank String)是由一个或多个空格组成的串。是由一个或多个空格组成的串。 注意：空串和空白串不同，例如注意：空串和空白串不同，例如和和分别表分别表示长度为示长度为1 1的空白串和长度为的空白串和长度为0 0的空串。的空串。定长顺序存储表示定长顺序存储表示#define MAXSTRLEN 255 / / 用户可在用户可在255255以内定义串长以内定义串长typedef unsigned char SStringMAXSTRLEN + 1; /0/0号单元存放串的长度号单元存放串的长度(PASCAL(PASCAL风格风格) )堆分配存储表示堆分配存储表示typedef struct char *ch; / / 若是非空串，则按串长分配存储区，否则若是非空串，则按串长分配存储区，否则chch为为NULL;NULL; int length; / / 串长度串长度; ; HString;串的块链存储表示串的块链存储表示#define CHUNKSIZE 80 #define CHUNKSIZE 80 / / 可由用户定义的块大小可由用户定义的块大小; ;typedef struct Chunk typedef struct Chunk / / 结点结构结点结构; ; char chCUNKSIZE; char chCUNKSIZE; struct Chunk struct Chunk * *next;next; Chunk; Chunk;typedef struct typedef struct / / 串的链表结构串的链表结构; ; Chunk Chunk * *head, head, * *tail; tail; / / 串的头和尾指针串的头和尾指针; ; int curlen; int curlen; / / 串的当前长度串的当前长度; ; LString; LString;第六章第六章 树和二叉树树和二叉树1 1、树的定义及基本术语、树的定义及基本术语 树的抽象数据类型表述树的抽象数据类型表述 基本术语基本术语2 2、二叉树的定义、性质和存储结构、二叉树的定义、性质和存储结构 二叉树的抽象数据类型表述二叉树的抽象数据类型表述 二叉树的性质二叉树的性质1、2、3、4 二叉树的存储结构二叉树的存储结构（顺序存储结构和链式存储结构）（顺序存储结构和链式存储结构）3 3、二叉树的遍历与构造、二叉树的遍历与构造 算法算法6.1、6.2、6.34 4、树和森林、树和森林 树的存储结构树的存储结构（孩子兄弟表示法）（孩子兄弟表示法） 森林和二叉树的转换森林和二叉树的转换5 5、赫夫曼树的定义、赫夫曼树的定义、构造方法构造方法及其应用（判定树、赫夫曼编码）及其应用（判定树、赫夫曼编码） 算法算法6.12抽象数据类型定义抽象数据类型定义ADT Tree 数据对象数据对象D：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。 数据关系数据关系R：若若D为空集，则称为空树；若为空集，则称为空树；若D仅含一个数据元仅含一个数据元素，则素，则R为空集，否则为空集，否则R=H,H是如下二元关系：是如下二元关系： (1) 在在D中存在惟一的称为根的数据元素中存在惟一的称为根的数据元素root，它在关系，它在关系H下无下无前驱；前驱； (2) 若若D-root，则存在，则存在D-root的一个划分的一个划分D1，D2, , Dm (m0)，对任意，对任意jk (1j，km)有有DjDk=，且对任意的，且对任意的i(1im)，惟一存在数据元素，惟一存在数据元素xiDi, 有有H; (3) 对应于对应于D-root的划分，的划分，H- , , 有惟一的一个划分有惟一的一个划分H1,H2, , Hm (m0)，对任意，对任意jk (1j，km)有有HjHk=，且对任意的，且对任意的i(1im)，Hi是是Di上的上的二元关系，二元关系，(Di，Hi)是一颗符合本定义的树，称为根是一颗符合本定义的树，称为根root的子树。的子树。 基本术语基本术语(1)结点结点(node)表示树中的元素，包括数据项及若干指向其表示树中的元素，包括数据项及若干指向其子树的分支子树的分支;(2)结点的度结点的度(degree)结点拥有的子树数量结点拥有的子树数量;(3)叶子叶子(leaf)度为度为0的结点；的结点；(4)孩子孩子(child) 结点子树的根称为该结点的孩子；结点子树的根称为该结点的孩子；(5)双亲双亲(parents)孩子结点的上层结点叫该结点的双亲；孩子结点的上层结点叫该结点的双亲；(6)兄弟兄弟(sibling)同一双亲的孩子；同一双亲的孩子；(7)树的度树的度一棵树中各结点的度的最大值；一棵树中各结点的度的最大值；(8)结点的层次结点的层次(level)从根结点算起，根为第一层，它的孩子从根结点算起，根为第一层，它的孩子为第二层为第二层；(9)深度深度(depth)树中结点的最大层次数；树中结点的最大层次数；(10)森林森林(forest)m(m 0)棵互不相交的树的集合；棵互不相交的树的集合；二叉树性质二叉树性质证明：用归纳法证明之证明：用归纳法证明之: i=1时，只有一个根结点，时，只有一个根结点， ，结论成立；，结论成立； 假设对所有假设对所有j(1 j1，则则其双亲是其双亲是 i/2 ； (2)如果如果2in，则结点则结点i无左孩子；如果无左孩子；如果2i n，则其左孩子是则其左孩子是2i； (3)如果如果2i+1n，则结点则结点i无右孩子；如果无右孩子；如果2i+1 n，则其右孩则其右孩子是子是2i+1；1log2nn深度为个结点的完全二叉树的具有性质性质4：证明：设深度为证明：设深度为K，根据性质，根据性质2和完全二叉树的定义：和完全二叉树的定义： 2k-1-1n2k-1 或者或者 2k-1n2k ；K-12nlchild);Pop(S, p); /完成循环，最后入栈的是一个空指针；完成循环，最后入栈的是一个空指针；if (!StackEmpty(S) Pop(S, p); if (! Visit(p-data) return ERROR;Push(S, p-rchild);return OK；ABCDEFGpiP-A(1)ABCDEFGpiP-AP-B(2)ABCDEFGpiP-AP-BP-C(3)p=NULLABCDEFGiP-AP-B访问：访问：C(4)pABCDEFGiP-A访问：访问：C B(5)ABCDEFGiP-AP-D访问：访问：C Bp(6)ABCDEFGiP-AP-DP-E访问：访问：C Bp(7)ABCDEFGiP-AP-D访问：访问：C B Ep(8)ABCDEFGiP-AP-DP-G访问：访问：C B EP=NULL(9)ABCDEFGiP-A访问：访问：C B E G Dp(11)ABCDEFGiP-AP-F访问：访问：C B E G Dp(12)ABCDEFGiP-AP-D访问：访问：C B E Gp(10)ABCDEFGiP-A访问：访问：C B E G D Fp=NULL(13)ABCDEFGi访问：访问：C B E G D F Ap(14)ABCDEFGi访问：访问：C B E G D F Ap=NULL(15)森林与二叉树的转换森林与二叉树的转换 树与二叉树树与二叉树可以通过二叉链表作为媒介实现二者间的可以通过二叉链表作为媒介实现二者间的映射关系。映射关系。 森林与二叉树森林与二叉树同样可以通过二叉链表作为媒介实现二同样可以通过二叉链表作为媒介实现二者间的映射关系。者间的映射关系。ACBED树ABCDE二叉树二叉树 A B C D E A B C D E A B C D E 对应对应存储存储存储存储解释解释解释解释构造构造HuffmanHuffman树的方法树的方法HuffmanHuffman算法算法构造构造HuffmanHuffman树的步骤树的步骤1 1、根据给定的、根据给定的n n个权值个权值w1,w2,w1,w2,wnwn，构造构造n n棵棵只有根结点的二叉树，第只有根结点的二叉树，第i i棵树的棵树的权值为权值为w wi i；形成；形成一个森林。一个森林。2 2、在森林中选取两棵根结点权值最小的树作左右在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和权值为其左右子树根结点权值之和, ,并并在森林中删在森林中删除这两棵树，同时将新得到的二叉树加入森林中；除这两棵树，同时将新得到的二叉树加入森林中；3 3、重复上述两步直到只含一棵树为止，这棵树即重复上述两步直到只含一棵树为止，这棵树即赫夫曼树。赫夫曼树。例例a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d461118例例 w=5, 29, 7, 8, 14, 23, 3, 1151429 7823 3 1114297823 113588715142923358111135819142923871511358192923148715292914871529113581923421135819234229148715295810011358192342291487152958第七章第七章 图图1 1、图的定义和术语、图的定义和术语2 2、图的存储结构、图的存储结构 数组表示法数组表示法 邻接表邻接表 十字链表十字链表 邻接多重表邻接多重表 采用邻接矩阵表示法，构造无向网采用邻接矩阵表示法，构造无向网G，算法算法7.2 采用十字链表表示法，构造有向图采用十字链表表示法，构造有向图G，算法算法7.33 3、图的遍历、图的遍历 深度优先搜索的过程和算法，深度优先搜索的过程和算法，算法算法7.4、 7.5 广度优先搜索的过程和算法，广度优先搜索的过程和算法，算法算法7.64 4、图的连通性问题、图的连通性问题 最小生成树的概念、最小生成树的概念、普里姆算法普里姆算法、克鲁斯卡尔算法思想克鲁斯卡尔算法思想 普里姆算法，算法普里姆算法，算法7.95 5、有向无环图及其应用、有向无环图及其应用 拓扑排序的概念和算法，拓扑排序的概念和算法，算法算法7.12 关键路径的概念和算法，关键路径的概念和算法，算法算法7.13、7.14 AOV-网和网和AOE-网的概念网的概念 6 6、最短路径、最短路径 最短路径的概念最短路径的概念 从某一源点到其余各顶点的最短路径，从某一源点到其余各顶点的最短路径，迪杰斯特拉算迪杰斯特拉算 法，算法法，算法7.15 构造最小生成树的方法构造最小生成树的方法方法一：普里姆方法一：普里姆(Prim)算法算法1、算法思想：设、算法思想：设N=(V,E)是连通网，是连通网，TE是是N上最小生上最小生成树中边的集合；成树中边的集合；2、初始令、初始令U=u0,(u0 V), TE= ；3、在所有、在所有u U,v V-U的边的边(u,v) E中，找一条代价最中，找一条代价最小的边小的边(u0,v0)；4、将、将(u0,v0)并入集合并入集合TE，同时同时v0并入并入U；5、重复上述操作直至、重复上述操作直至U=V为止，则为止，则T=(V,TE)为为N的的最小生成树；最小生成树；例例1654326513566425131163141643142116432142516543214253 方法二：克鲁斯卡尔方法二：克鲁斯卡尔(Kruskal)算法算法算法思想：算法思想：1、设连通网、设连通网N=(V,E)，令最小生成树的令最小生成树的初始状态为只有初始状态为只有n个顶个顶点而无边的非连通图点而无边的非连通图T=(V, )，每个顶点自成一个连通分量，每个顶点自成一个连通分量;2、在、在E中选取代价最小的边，若该边依附的顶点落在中选取代价最小的边，若该边依附的顶点落在T中不同的中不同的连通分量上，则将此边加入到连通分量上，则将此边加入到T中；否则，舍去此边，选取下中；否则，舍去此边，选取下一条代价最小的边一条代价最小的边;3、依此类推，直至、依此类推，直至T中所有顶点都在同一连通分量上为止中所有顶点都在同一连通分量上为止。例例165432651356642516543212345最短路径最短路径如果用带权的有向图表示一个交通运输网，图中：如果用带权的有向图表示一个交通运输网，图中：顶点顶点表示城市；表示城市；边边表示城市间的交通联系；表示城市间的交通联系；权权表示此线路的长度或沿此线路运输所花的时间或费用等；表示此线路的长度或沿此线路运输所花的时间或费用等；如何寻找如何寻找最短路径最短路径？即？即寻找寻找从某顶点出发，沿图的边到达另一顶从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径；点所经过的路径中，各边上权值之和最小的一条路径；问题的提出问题的提出迪杰斯特拉迪杰斯特拉(Dijkstra)(Dijkstra)算法思想算法思想按路径长度的递增顺序，依次产生最短路径按路径长度的递增顺序，依次产生最短路径;假设图中所示为从源点到其余各点之间的最短路径，在其中必有假设图中所示为从源点到其余各点之间的最短路径，在其中必有一条相对最短的路径；一条相对最短的路径；源点源点a 在在相对最短的相对最短的路径上，必定只含一条弧且路径上，必定只含一条弧且权值最小。因权值最小。因此，只此，只要在所有从源点出发的弧中查找权值最小者，可得要在所有从源点出发的弧中查找权值最小者，可得相对最短路径相对最短路径; ;长度次短的路径可能有两种情况长度次短的路径可能有两种情况: : 它可能是从源点直接到该点的路径它可能是从源点直接到该点的路径; ; 也可能是，从源点到也可能是，从源点到a, a, 再从再从a a到该点；到该点；其余依次类推，直至求出源点到各顶点的全部最短路径。其余依次类推，直至求出源点到各顶点的全部最短路径。 从某个源点到其余各顶点的最短路径从某个源点到其余各顶点的最短路径假设假设 Distk 表示当前所求得的从源点到表示当前所求得的从源点到k的最短路径，显然，的最短路径，显然， Distk = 或或 = + + ；求最短路径步骤求最短路径步骤: :首先，令首先，令S=VS=V0 0 ，T=T=其余顶点其余顶点 ，V V0 0到到T T中顶点对应的路径长度：中顶点对应的路径长度： 若存在若存在V ，为，为V 弧上的权值；弧上的权值； 若不存在若不存在 ，为为 ；其次，从其次，从T T中选取一个与中选取一个与V V0 0路径长度路径长度最小的顶点最小的顶点j j，加入，加入S S； 对对T T中顶点的中顶点的路径长度路径长度进行修改：若加进进行修改：若加进j j作中间顶点，从作中间顶点，从V V0 0到到V Vi i的路径长度比不加的路径长度比不加j j时时的路径短，则修改此路径长度的路径短，则修改此路径长度。重复上述步骤，直到重复上述步骤，直到S S中包含所有顶点，即中包含所有顶点，即S=VS=V为止。为止。138 30 32V213-1330 32V1-13302220V3-192220V4终点终点 从从V0到各终点的最短路径及其长度到各终点的最短路径及其长度V1V2V3V4V5V6Vj-2120V6516432085623013717329第九章第九章 查找查找概念：关键字概念：关键字1、静态查找表、静态查找表 顺序表的查找，顺序表的查找，算法算法9.1 有序表的查找，有序表的查找，算法算法9.2 索引顺序表的查找算法思想索引顺序表的查找算法思想 上述三种查找方式的平均查找长度上述三种查找方式的平均查找长度 判定树的概念与结构特点判定树的概念与结构特点2、动态查找表、动态查找表 二叉排序树的特性以及查找、插入、删除算法，二叉排序树的特性以及查找、插入、删除算法， 9.5(b)、9.6、9.8 平衡二叉树的概念平衡二叉树的概念 B-树和树和B+树的概念树的概念 B-树的查找算法，算法树的查找算法，算法9.133、哈希表、哈希表u哈希表的概念哈希表的概念u哈希函数的构造方法哈希函数的构造方法直接定址法直接定址法除留余数法除留余数法u处理冲突的方法处理冲突的方法开放定址法开放定址法链地址法链地址法u哈希表的查找过程哈希表的查找过程1B-树的定义树的定义B-树是一种 平衡平衡 的 多路多路 查找查找 树： root 50 15 71 84 3 8 20 26 43 56 62 78 89 96平衡树的特性平衡树的特性 树中所有叶子结点均不带信息，且在树树中所有叶子结点均不带信息，且在树中的同一层次上中的同一层次上; 根结点或为叶子结点，或至少含有两棵根结点或为叶子结点，或至少含有两棵子树子树; 其余所有非叶结点均至少含有其余所有非叶结点均至少含有 m/2 棵棵子树，至多含有子树，至多含有 m 棵子树棵子树; ; 在在 m 阶的阶的B-树上，每个非终端结点可能树上，每个非终端结点可能含有：含有： n 个个关键字关键字 Ki（1 in） nm n 个个指向记录的指针指向记录的指针 Di（1in） n+1 个个指向子树的指针指向子树的指针 Ai（0in）;多叉树的特性多叉树的特性 非叶结点中的非叶结点中的多个关键字均自小至大多个关键字均自小至大有有序排列，即：序排列，即：K1 K2 Kn; 且且 Ai-1 所指子树上所有关键字均小于所指子树上所有关键字均小于Ki; Ai 所指子树上所有关键字均大于所指子树上所有关键字均大于Ki; ; 非终端结点中包含的信息：非终端结点中包含的信息： (n,A0,K1,A1,K2,Kn,An)查找树的特性查找树的特性一棵一棵4阶阶B-树树t ta ac cd de ef fg g35351 118181 111111 127271 139391 199991 14747535364643 3434378782 2FFFFFFFFFFFFb bh hB+树的结构特点：树的结构特点： 每个中间结点中含有每个中间结点中含有 n 个关键字和个关键字和 n 个指个指向记录的指针向记录的指针；2B+树树:是是B-树的一种变型树的一种变型 每个每个中间结点中间结点中的关键字中的关键字 Ki 即为其相应即为其相应指针指针 Ai 所指子树中所指子树中关键字的最大值关键字的最大值；所有叶子结点都处在所有叶子结点都处在同一层次上同一层次上，每个叶子，每个叶子结点中关键字的个数均介于结点中关键字的个数均介于 m/2 和和 m 之间，之间，包括包括 m/2 和和 m 。并且，所有并且，所有叶子结点彼此相叶子结点彼此相链接构成一个有序链表链接构成一个有序链表，其头指针指向含最小，其头指针指向含最小关键字的结点；关键字的结点；数据库中的数据库中的非簇索引非簇索引和和簇索引簇索引5757第第10章章 排序排序u排序的概念、稳定排序、排序算法的时间复杂度排序的概念、稳定排序、排序算法的时间复杂度极限极限O(nlogn)u各种排序方法的基本思想、过程、性能，给出一各种排序方法的基本思想、过程、性能，给出一个序列，能够手工推演出各趟排序结果。个序列，能够手工推演出各趟排序结果。直接插入排序、表插入排序、希尔排序直接插入排序、表插入排序、希尔排序快速排序快速排序堆排序堆排序归并排序归并排序基数排序基数排序本文观看结束！谢 谢欣 赏！祝各位身体健康！万事如意！