《数据结构C语言版》复习重点计算机NET_高等教育-大学课件.pdf

学习好资料 欢迎下载 数据结构(C语言版)复习重点 重点在二、三、六、七、九、十章，考试内容两大类：概念，算法 第 1 章、绪论 1.数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。2.数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。3.数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。其4类基本结构：集合、线性结构、树形结构、图状结构或网状结构 4.逻辑结构：是数据元素之间的逻辑关系的描述。5.物理结构（存储结构）：是数据结构在计算机中的表示（又称映像）。其4种存储结构：顺序存数结构、链式存数结构、索引存数结构、散列存数结构 6.算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。其5个重要特性：有穷性、确定性、可行性、输入、输出 7.时间复杂度：算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间度量记作，T(n)=O(f(n)；他表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称做算法的渐进时间复杂度，简称时间复杂度。例如：(a)+x;s=0;(b)for(i=1;i=n;+i)+x;s+=x;(c)for(j=1;j=n;+j)for(k=1;knext 为第一个结点地址，L-next=NULL为空表。生成结点：p=(LinkList)malloc(sizeof(LNode)回收结点：free(q)客观事物的符号表示在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称数据元素是数据的基本单位在计算机程序中通常作为一个整体进行考虑和处理数据结构是相互之间存在一种或多种特定关系的数据元理结构存储结构是数据结构在计算机中的表示又称映像其种存储结构顺序存数结构链式存数结构索引存数结构散列存数结构算法是对特定问题求解骤的一种描述它是指令的有限序列其中每一条指令表示一个或多个操作其个重要特性记作他表示随问题规模的增大算法执行时间的增长率和的增长率相同称做算法的渐进时间复杂度简称时间复杂度例如含基本操作增的语句的频度分别为和则这个程序段的时间复杂度分别为和分别称为常量阶线性阶和平方阶还可呈现学习好资料 欢迎下载 2)循环链表特点：表中最后一个结点的指针域指向头结点，整个链表形成一个环。循环链表的操作与线性链表基本一致，差别仅在于算法中的循环条件不是 P 或P-next 是否为空，而是它们是否等于头指针。3)双向链表特点：有 2 个指针域，其一指向直接后继，另一指向直接前趋。客观事物的符号表示在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称数据元素是数据的基本单位在计算机程序中通常作为一个整体进行考虑和处理数据结构是相互之间存在一种或多种特定关系的数据元理结构存储结构是数据结构在计算机中的表示又称映像其种存储结构顺序存数结构链式存数结构索引存数结构散列存数结构算法是对特定问题求解骤的一种描述它是指令的有限序列其中每一条指令表示一个或多个操作其个重要特性记作他表示随问题规模的增大算法执行时间的增长率和的增长率相同称做算法的渐进时间复杂度简称时间复杂度例如含基本操作增的语句的频度分别为和则这个程序段的时间复杂度分别为和分别称为常量阶线性阶和平方阶还可呈现学习好资料 欢迎下载 第 3 章、栈和队列 1.栈：是限定仅在表尾进行插入或删除操作的线性表。表尾端称为栈顶，表头端称为栈底，不含有元素的空表称为空栈；栈又称为后进先出的线性表。2.队列：是一种先进先出的线性表，它只允许在表的一端进行插入，而另一端删除元素。允许插入的一端叫做队尾，允许删除的一端则称为队头。1)链队列：用链表示的队列。一个队列需要两个分别指示队头和队尾的指针（分别成为头指针和尾指针）才能确定唯一。和单链表一样，也给链队列添加一个头结点，并令头指针指向头结点。2)循环队列：与顺序栈类似，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个指针 front和 rear 分别指示队列头元素及队列尾元素的位置。初始化建空队列时，令 front=rear=0，每当插入新的队列尾元素时，“尾指针增 1”；每当删除队列头元素时，“头指针增 1”。客观事物的符号表示在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称数据元素是数据的基本单位在计算机程序中通常作为一个整体进行考虑和处理数据结构是相互之间存在一种或多种特定关系的数据元理结构存储结构是数据结构在计算机中的表示又称映像其种存储结构顺序存数结构链式存数结构索引存数结构散列存数结构算法是对特定问题求解骤的一种描述它是指令的有限序列其中每一条指令表示一个或多个操作其个重要特性记作他表示随问题规模的增大算法执行时间的增长率和的增长率相同称做算法的渐进时间复杂度简称时间复杂度例如含基本操作增的语句的频度分别为和则这个程序段的时间复杂度分别为和分别称为常量阶线性阶和平方阶还可呈现学习好资料 欢迎下载 第 4 章、串 1.串：是由零个或多个字符组成的有限序列。第 5 章、数组和广义表 客观事物的符号表示在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称数据元素是数据的基本单位在计算机程序中通常作为一个整体进行考虑和处理数据结构是相互之间存在一种或多种特定关系的数据元理结构存储结构是数据结构在计算机中的表示又称映像其种存储结构顺序存数结构链式存数结构索引存数结构散列存数结构算法是对特定问题求解骤的一种描述它是指令的有限序列其中每一条指令表示一个或多个操作其个重要特性记作他表示随问题规模的增大算法执行时间的增长率和的增长率相同称做算法的渐进时间复杂度简称时间复杂度例如含基本操作增的语句的频度分别为和则这个程序段的时间复杂度分别为和分别称为常量阶线性阶和平方阶还可呈现学习好资料 欢迎下载 1.数组特点：与线性表一样，所有数据元素都必须属于同一数据类型。2.数组的顺序存储结构：由于数组一般不作插入或删除操作，一旦建立了数组，则结构中的数据元素个数和元素之间的关系就不会发生变动，因此采用顺序存储结构表示数组。存储位置计算：假设每个数据元素需占用 L个存储单元，则二维数组 A中任一元素 aij 的存储位置可由下式确定 以行序为主序的存储结构：LOC(i,j)=LOC(0,0)+(b2*i+j)*L 以列序为主序的存储结构：LOC(i,j)=LOC(0,0)+(b2*j+i)*L 式中 LOC(i,j)是 aij的存储位置；LOC(0,0)是 a00 的存储位置，即二维数组 A的起始存储位置，也称基地址或基址；b2 在以行序为主序的存储结构时为每行存储元素的个数(列数)，在以列序为主序的存储结构时为每列存储元素的个数(行数)。3.广义表：是线性表的推广，也有人称其为列表（lists，用复数形式以示与统称的表 list 的区别）。记作 LS=(a1,a2,an)，其中 LS是广义表(a1,a2,an)的名称，n 是它的长度。在线性表的定义中，ai(1 i n)只限于是单个元素。而在广义表的定义中，ai 可以是单个元素，也可以是广义表，分别称为广义表 LS 的原子和子表。例如：第 6 章、树和二叉树 1.二叉树：是一种树型的结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于 2 的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。2.二叉树的性质：1)性质 1：在二叉树的第 i 层上至多有 2 的 i 减 1 次方个结点(i 1)。2)性质 2：深度为 k 的二叉树至多有2 的 k 次方减 1 个结点(k 1)。深度为 k 的二叉树至少有k 个结点(k 1)。深度为 k 的完全二叉树至少有 2 的 k 次方减 2 的 k 减 1 次方个结点(k 1)。3)性质 3：对任何一棵二叉树 T，如果其终端结点数为 n0，度为 2 的结点数为n2，则 n0=n2+1。4)性质 4：具有 n 个结点的完全二叉树的深度为log2n+1。5)性质 5：如果对一棵有 n 个结点的完全二叉树（其深度为log2n+1）的结点按层序编号（从第 1 层到第log2n+1层，每层从左到右），则对任一结点 i（1客观事物的符号表示在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称数据元素是数据的基本单位在计算机程序中通常作为一个整体进行考虑和处理数据结构是相互之间存在一种或多种特定关系的数据元理结构存储结构是数据结构在计算机中的表示又称映像其种存储结构顺序存数结构链式存数结构索引存数结构散列存数结构算法是对特定问题求解骤的一种描述它是指令的有限序列其中每一条指令表示一个或多个操作其个重要特性记作他表示随问题规模的增大算法执行时间的增长率和的增长率相同称做算法的渐进时间复杂度简称时间复杂度例如含基本操作增的语句的频度分别为和则这个程序段的时间复杂度分别为和分别称为常量阶线性阶和平方阶还可呈现学习好资料 欢迎下载 ABCDEHIFGJKi n）有：a)如果 i=1，则结点 i 是二叉树的根，无双亲；如果 i1，则其双亲 PARENT(i)是结点i/2。b)如果 2in，则结点 i 无左孩子（结点 i 为叶子结点）；否则其左孩子 LCHILD(i)是结点 2i。c)如果 2i+1n，则结点 i 无右孩子；否则其右孩子 RCHILD(i)是结点 2i+1。3.满二叉树：一颗深度为 k 且有 2 的 k 次方减 1 个结点的二叉树。4.完全二叉树：深度为 k 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应。5.遍历二叉树：1)根据二叉树写遍历结果：a)先序遍历（先根遍历）：DLR-+a*b-c d/e f b)中序遍历（中根遍历）：LDR a+b*c-d-e/f c)后序遍历（后根遍历）：LRD a b c d-*+e f/-2)根据遍历结果画二叉树：一棵二叉树的先序、中序和后序序列分别如下，其中有部分未给出，试求出空格处的结点字符，并画出该二叉树。先序：_B_EHI_FG_K 中序：D_HEIA_CJG_ 后序：_H_EBF_KG_A 解题思路：a)由先序或后序确定根结点；如本题后序最后一个为 A，根结点为 A，所以先序第一个空就为A。b)在中序找出根结点，根结点左侧为左子树，右侧为右子树；如本题D_HEI为左子树，_CJG_ 为右子树。c)由先序确定紧跟在根结点后的左子树根；如本题紧跟在 A后的是 B，B为左子树根，中序根结点的左子树只有一个空，所以为B。d)继续由中序确定左子树根的左右子树，左侧为左子树，右侧为右子树；如本题 B的左子树为 D，右子树为HEI，所以先序第二个空为 D。e)重复 c)、d)步骤确定整棵左子树；如本题先序中紧跟在D后的是 E，E 为 B的右子树，由中序中看出 E左子树为 H，右子树为 I，补充后序填空，前两空分别为 D和 I。f)由后序确定右子树根的左子树，再由中序确定右子树根；如本题紧跟在B后的是 F，F为右子树根的左子树，已知中序_CJG_为右子树，F只可能第一个空，-+/a*b-efcd客观事物的符号表示在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称数据元素是数据的基本单位在计算机程序中通常作为一个整体进行考虑和处理数据结构是相互之间存在一种或多种特定关系的数据元理结构存储结构是数据结构在计算机中的表示又称映像其种存储结构顺序存数结构链式存数结构索引存数结构散列存数结构算法是对特定问题求解骤的一种描述它是指令的有限序列其中每一条指令表示一个或多个操作其个重要特性记作他表示随问题规模的增大算法执行时间的增长率和的增长率相同称做算法的渐进时间复杂度简称时间复杂度例如含基本操作增的语句的频度分别为和则这个程序段的时间复杂度分别为和分别称为常量阶线性阶和平方阶还可呈现学习好资料 欢迎下载 那第二个空为 K，补全先序、中序、后序填空并可画出二叉树。6.森林与二叉树的转换：1)树转换成二叉树：连兄弟，留长子，删孩子。a)连线，连接所有兄弟结点。b)删线，仅保留双亲与长子结点的连线，删除与其他孩子结点之间的连线。c)整理，原有的长子结点为左子树，从兄弟转换为孩子的结点为右子树。d)注意，由于树根没有兄弟结点，固树转换为二叉树后，二叉树根结点的右子树必为空。2)森林转换成二叉树：连树根及兄弟，留长子，删孩子。a)连线，连接每棵树的根结点及所有兄弟结点。b)删线，仅保留双亲与长子结点的连线，删除与其他孩子结点之间的连线。c)整理，第一棵树根结点为二叉树根结点，原有的长子结点为左子树，从兄弟转换为孩子的结点为右子树。3)二叉树转换成树：连左孩子的右孩子及其右孩子，删原树右孩子。a)连线，若某结点 X存在左孩子 XL，则将这个左孩子的右孩子结点 XLR、左孩子的右孩子的右孩子结点 XLRR、左孩子的右孩子的右孩子的右孩子结点 XLRRR 都与 X结点连线。b)删线，删除原二叉树的所有双亲与右孩子结点的连线。c)整理，原二叉树根结点为树根结点。客观事物的符号表示在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称数据元素是数据的基本单位在计算机程序中通常作为一个整体进行考虑和处理数据结构是相互之间存在一种或多种特定关系的数据元理结构存储结构是数据结构在计算机中的表示又称映像其种存储结构顺序存数结构链式存数结构索引存数结构散列存数结构算法是对特定问题求解骤的一种描述它是指令的有限序列其中每一条指令表示一个或多个操作其个重要特性记作他表示随问题规模的增大算法执行时间的增长率和的增长率相同称做算法的渐进时间复杂度简称时间复杂度例如含基本操作增的语句的频度分别为和则这个程序段的时间复杂度分别为和分别称为常量阶线性阶和平方阶还可呈现学习好资料 欢迎下载 4)二叉树转换成森林：连左孩子的右孩子及其右孩子，删原树右孩子。a)连线，若某结点 X存在左孩子 XL，则将这个左孩子的右孩子结点 XLR、左孩子的右孩子的右孩子结点 XLRR、左孩子的右孩子的右孩子的右孩子结点 XLRRR 都与 X结点连线。b)删线，删除原二叉树的所有双亲与右孩子结点的连线。c)整理，调整为多棵树的森林。客观事物的符号表示在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称数据元素是数据的基本单位在计算机程序中通常作为一个整体进行考虑和处理数据结构是相互之间存在一种或多种特定关系的数据元理结构存储结构是数据结构在计算机中的表示又称映像其种存储结构顺序存数结构链式存数结构索引存数结构散列存数结构算法是对特定问题求解骤的一种描述它是指令的有限序列其中每一条指令表示一个或多个操作其个重要特性记作他表示随问题规模的增大算法执行时间的增长率和的增长率相同称做算法的渐进时间复杂度简称时间复杂度例如含基本操作增的语句的频度分别为和则这个程序段的时间复杂度分别为和分别称为常量阶线性阶和平方阶还可呈现学习好资料 欢迎下载 7.赫夫曼树：又称最优树，是一类带权路径长度最短的树。a)两个最小数值组成一对，小的在前，大的在后；如上图中 2 与 4 最小，2 在前，4 在后。b)将两个最小数值的和算作一个数，再与其他数重复a)步骤；如上图中 2 与 4的和为 6，5 与 6 最小，5 在前，6 在后。c)最后计算 WPL，它等于每个数值乘以从根结点到这个数值的连线个数的积之和；如上图中 WPL=2*3+4*3+5*2+7*1=35。8.赫夫曼编码：a)在赫夫曼树上，左分支代表 0，右分支代表 1。b)由根结点到指定结点的路径(从上到下把 0、1 连起来)，就是该结点的赫夫曼编码；如上图(d)中 a 为 0，b 为 10，c 为 110，d 为 111。第 7 章、图 1.图：多个结点，结点之间的关系可以是任意的，图中任意两个数据元素之间都有可能相关。2.无向完全图：有 n(n-1)/2 条边的无向图。3.有向完全图：有 n(n-1)条边的有向图。4.入度：以顶点 V为头的弧的数目称为 V的入度。5.出度：以 V为尾的弧的数目称为 V的出度。6.连通图：在无向图中，任意两个顶点之间都有路径。7.连通分量：在无向图中的极大连通子图。客观事物的符号表示在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称数据元素是数据的基本单位在计算机程序中通常作为一个整体进行考虑和处理数据结构是相互之间存在一种或多种特定关系的数据元理结构存储结构是数据结构在计算机中的表示又称映像其种存储结构顺序存数结构链式存数结构索引存数结构散列存数结构算法是对特定问题求解骤的一种描述它是指令的有限序列其中每一条指令表示一个或多个操作其个重要特性记作他表示随问题规模的增大算法执行时间的增长率和的增长率相同称做算法的渐进时间复杂度简称时间复杂度例如含基本操作增的语句的频度分别为和则这个程序段的时间复杂度分别为和分别称为常量阶线性阶和平方阶还可呈现学习好资料 欢迎下载 8.邻接矩阵：无向图的邻接矩阵关于主对角线对称，在整个矩阵中非零元素的个数等于边个数的 2 倍，第 i 行和第 i 列中非零元素的个数等于该结点的度。9.邻接表：无向图的邻接矩阵关于主对角线对称，在整个矩阵中非零元素的个数等于边个数的 2 倍，第 i 行和第 i 列中非零元素的个数等于该结点的度。客观事物的符号表示在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称数据元素是数据的基本单位在计算机程序中通常作为一个整体进行考虑和处理数据结构是相互之间存在一种或多种特定关系的数据元理结构存储结构是数据结构在计算机中的表示又称映像其种存储结构顺序存数结构链式存数结构索引存数结构散列存数结构算法是对特定问题求解骤的一种描述它是指令的有限序列其中每一条指令表示一个或多个操作其个重要特性记作他表示随问题规模的增大算法执行时间的增长率和的增长率相同称做算法的渐进时间复杂度简称时间复杂度例如含基本操作增的语句的频度分别为和则这个程序段的时间复杂度分别为和分别称为常量阶线性阶和平方阶还可呈现学习好资料 欢迎下载 10.深度优先遍历：从图中某个顶点出发，搜索与之相关联的顶点，选择一个访问（从左到右，从上到下）；再从该顶点出发，搜索与之相关联且未访问过的顶点，选择一个访问；重复上步骤，直到没有相关联且未访问过的顶点；后退一个顶点继续搜索访问，直到所有顶点都被访问过。V0V1V2V3V4 a)从 V0出发，先找到 V0的关联顶点 V3。b)由 V3出发，找到 V1；由 V1出发，没有关联的顶点。c)回到 V3，从 V3出发，找到 V2；由 V2出发，没有关联的顶点。d)回到 V3，再回到 V0，由 V0出发，找到 V4。e)从 V4出发，找到 V1，因为 V1已经被访问过了，所以不访问。所以最后顺序是 V0,V3,V1,V2,V4。客观事物的符号表示在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称数据元素是数据的基本单位在计算机程序中通常作为一个整体进行考虑和处理数据结构是相互之间存在一种或多种特定关系的数据元理结构存储结构是数据结构在计算机中的表示又称映像其种存储结构顺序存数结构链式存数结构索引存数结构散列存数结构算法是对特定问题求解骤的一种描述它是指令的有限序列其中每一条指令表示一个或多个操作其个重要特性记作他表示随问题规模的增大算法执行时间的增长率和的增长率相同称做算法的渐进时间复杂度简称时间复杂度例如含基本操作增的语句的频度分别为和则这个程序段的时间复杂度分别为和分别称为常量阶线性阶和平方阶还可呈现学习好资料 欢迎下载 11.广度优先遍历：从图中某个顶点出发，搜索与之相关联的顶点，逐个访问（从左到右，从上到下）；再从这些顶点出发，搜索与之相关联且未访问过的顶点，逐个访问；重复上步骤，直到所有顶点都被访问过。V0V1V2V3V4 a)从 V0出发，先找到 V0的关联顶点 V3、V4。b)由 V3出发，找到 V1、V2；由 V4出发，找到 V1，因为 V1已经被访问过了，所以不访问。c)由 V1出发，没有关联的顶点；由 V2出发，没有关联的顶点。所以最后顺序是 V0,V3,V4,V1,V2。12.最小生成树：1)普里姆算法：连相邻权值最小的。2)克鲁斯卡尔算法：先连权值最小的，再依次连。客观事物的符号表示在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称数据元素是数据的基本单位在计算机程序中通常作为一个整体进行考虑和处理数据结构是相互之间存在一种或多种特定关系的数据元理结构存储结构是数据结构在计算机中的表示又称映像其种存储结构顺序存数结构链式存数结构索引存数结构散列存数结构算法是对特定问题求解骤的一种描述它是指令的有限序列其中每一条指令表示一个或多个操作其个重要特性记作他表示随问题规模的增大算法执行时间的增长率和的增长率相同称做算法的渐进时间复杂度简称时间复杂度例如含基本操作增的语句的频度分别为和则这个程序段的时间复杂度分别为和分别称为常量阶线性阶和平方阶还可呈现学习好资料 欢迎下载 13.拓扑排序：由某个集合上的一个偏序得到该集合上的一个全序的操作。14.关键路径：路径长度最长的路径。客观事物的符号表示在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称数据元素是数据的基本单位在计算机程序中通常作为一个整体进行考虑和处理数据结构是相互之间存在一种或多种特定关系的数据元理结构存储结构是数据结构在计算机中的表示又称映像其种存储结构顺序存数结构链式存数结构索引存数结构散列存数结构算法是对特定问题求解骤的一种描述它是指令的有限序列其中每一条指令表示一个或多个操作其个重要特性记作他表示随问题规模的增大算法执行时间的增长率和的增长率相同称做算法的渐进时间复杂度简称时间复杂度例如含基本操作增的语句的频度分别为和则这个程序段的时间复杂度分别为和分别称为常量阶线性阶和平方阶还可呈现学习好资料 欢迎下载 1)如图，先求各事件的最早发生时间（顺序为 V1V9）V1 的最早发生时间为 0，V2 的最早发生时间为 6，V3 的最早发生时间为 4，V4的最早发生时间为 5。对于 V5，需要 V2，V3 均发生，V2 发生且完成的时间为6+1=7；V3发生且完成的时间为 4+1=5，因而 V5的最早发生时间为 7。同理可求出各顶点的最早发生时间：V1 V2 V3 V4 V5 V6 V7 V8 V9 e(i)0 6 4 5 7 7 16 14 18 2)求各事件的最晚发生时间（顺序为 V9V1）V9的最晚时间为 18，V8的最晚时间为 18-a11=14，V7的最晚时间为 18-a10=16，V6的最晚时间为 14-a9=10，V5的最晚时间为 V7的最晚时间减去 a7 和 V8的最晚时间减去 a8 两者较小的，则 V5的最晚时间为 7，同理可得其他顶点的最晚发生时间：V1 V2 V3 V4 V5 V6 V7 V8 V9 l(i)0 6 6 8 7 10 16 14 18 则 li与 ei相等的事件即为关键事件 即：V1，V2，V5，V7，V8，V9 可得关键路径：V1，V2，V5，V7，V9或 V1，V2，V5，V8，V9 3)求各活动的最早发生时间 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 e(i)0 0 0 6 4 5 7 7 7 16 14 4)求各活动的最晚发生时间 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 l(i)6-6=0 6-4=2 8-5=3 7-1=6 7-1=6 10-2=8 16-9=7 14-7=7 14-4=10 18-2=16 18-4=14 则 li与 ei相等的活动即为关键活动 即：a1，a4，a7，a8，a10，a11 可得关键路径：V1，V2，V5，V7，V9或 V1，V2，V5，V8，V9 15.最短路径：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径。1)迪杰斯特拉算法：客观事物的符号表示在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称数据元素是数据的基本单位在计算机程序中通常作为一个整体进行考虑和处理数据结构是相互之间存在一种或多种特定关系的数据元理结构存储结构是数据结构在计算机中的表示又称映像其种存储结构顺序存数结构链式存数结构索引存数结构散列存数结构算法是对特定问题求解骤的一种描述它是指令的有限序列其中每一条指令表示一个或多个操作其个重要特性记作他表示随问题规模的增大算法执行时间的增长率和的增长率相同称做算法的渐进时间复杂度简称时间复杂度例如含基本操作增的语句的频度分别为和则这个程序段的时间复杂度分别为和分别称为常量阶线性阶和平方阶还可呈现学习好资料 欢迎下载 2)弗洛伊德算法：客观事物的符号表示在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称数据元素是数据的基本单位在计算机程序中通常作为一个整体进行考虑和处理数据结构是相互之间存在一种或多种特定关系的数据元理结构存储结构是数据结构在计算机中的表示又称映像其种存储结构顺序存数结构链式存数结构索引存数结构散列存数结构算法是对特定问题求解骤的一种描述它是指令的有限序列其中每一条指令表示一个或多个操作其个重要特性记作他表示随问题规模的增大算法执行时间的增长率和的增长率相同称做算法的渐进时间复杂度简称时间复杂度例如含基本操作增的语句的频度分别为和则这个程序段的时间复杂度分别为和分别称为常量阶线性阶和平方阶还可呈现学习好资料 欢迎下载 方法：两条线，从左上角开始计算一直到右下角 如下所示：给出矩阵，其中矩阵 A是邻接矩阵，而矩阵 Path 记录 u,v 两点之间最短路径所必须经过的点。客观事物的符号表示在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称数据元素是数据的基本单位在计算机程序中通常作为一个整体进行考虑和处理数据结构是相互之间存在一种或多种特定关系的数据元理结构存储结构是数据结构在计算机中的表示又称映像其种存储结构顺序存数结构链式存数结构索引存数结构散列存数结构算法是对特定问题求解骤的一种描述它是指令的有限序列其中每一条指令表示一个或多个操作其个重要特性记作他表示随问题规模的增大算法执行时间的增长率和的增长率相同称做算法的渐进时间复杂度简称时间复杂度例如含基本操作增的语句的频度分别为和则这个程序段的时间复杂度分别为和分别称为常量阶线性阶和平方阶还可呈现学习好资料 欢迎下载 最后 A3即为所求结果。客观事物的符号表示在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称数据元素是数据的基本单位在计算机程序中通常作为一个整体进行考虑和处理数据结构是相互之间存在一种或多种特定关系的数据元理结构存储结构是数据结构在计算机中的表示又称映像其种存储结构顺序存数结构链式存数结构索引存数结构散列存数结构算法是对特定问题求解骤的一种描述它是指令的有限序列其中每一条指令表示一个或多个操作其个重要特性记作他表示随问题规模的增大算法执行时间的增长率和的增长率相同称做算法的渐进时间复杂度简称时间复杂度例如含基本操作增的语句的频度分别为和则这个程序段的时间复杂度分别为和分别称为常量阶线性阶和平方阶还可呈现学习好资料 欢迎下载 第 9 章、查找 1.查找表：是由同一类型的数据元素（或记录）构成的集合。2.关键字：是数据元素（或记录）中某个数据项的值，用它可以标识（识别）一个数据元素（或记录）。3.静态查找表：查询某个特定的数据元素是否在查找表中，检索某个特定的数据元素的各种属性。1)顺序查找法：从表中最后一个记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之若直至第一个记录，其关键字和给定值比较都不相等，则表明表中没有所查记录，查找不成功。其存储结构要求：以顺序表或线性链表表示的静态查找表。其平均查找长度：假设每个记录的查找概率相等，即 Pi=1/n，则在等概率情况下顺序查找的平均查找长度为，ASL=(n+1)/2。2)折半查找法（二分查找法）：先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。其存储结构要求：以有序表表示的静态查找表。其平均查找长度：假设表中每个记录的查找概率相等（Pi=1/n），则查找成功时折半查找的平均查找长度为，ASL=(n+1)/n*log2(n+1)-1。3)索引顺序表查找法（分块查找法）：先确定待查记录所在的块（子表），然后在块中顺序查找。其存储结构要求：以索引顺序表表示的静态查找表。其平均查找长度：将长度为 n 的表均匀地分成 b 块，每块含有 s 个记录，即b=n/s；又假设表中每个记录的查找概率相等，则每块查找概率为 1/b，块中每个记录的查找概率为 1/s，若用顺序查找确定所在块，则分块查找的平均查找长度为，ASL=(n/s+s)/2+1；若用折半查找确定所在块，则分块查找的平均查找长度为，ASL log2(n/s+1)+s/2。4.动态查找表：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素。1)二叉排序树：或者是一棵空树；或者是具有下列性质的二叉树：1、若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；2、若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；3、它的左、右子树也分别为二叉排序树。2)平衡二叉树（AVL树）：它或者是一棵空树；或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过 1。若将二叉树上结点的平衡因子 BF 定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1、0 和 1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。客观事物的符号表示在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称数据元素是数据的基本单位在计算机程序中通常作为一个整体进行考虑和处理数据结构是相互之间存在一种或多种特定关系的数据元理结构存储结构是数据结构在计算机中的表示又称映像其种存储结构顺序存数结构链式存数结构索引存数结构散列存数结构算法是对特定问题求解骤的一种描述它是指令的有限序列其中每一条指令表示一个或多个操作其个重要特性记作他表示随问题规模的增大算法执行时间的增长率和的增长率相同称做算法的渐进时间复杂度简称时间复杂度例如含基本操作增的语句的频度分别为和则这个程序段的时间复杂度分别为和分别称为常量阶线性阶和平方阶还可呈现学习好资料 欢迎下载 下面即四种情况分别为：左左、右右、左右、右左，每种情况又有两个图、，是该情况的最简单的图形，是该情况的一般的图形。设 x 为最小不平衡子树的根结点，y 为刚插入的点 左左：即在 x 的左孩子 a 的左孩子 c 上插入一个结点y（该结点也可以是c,如图），即 y 可以是 c，也可以是 c 的左孩子（如图），也可以是 c 的右孩子（不在画出）。图就不用说了，结点 x 和结点 a 变换，则树平衡了；那么图就是树中的一般情况了 a 结点有右孩子 d，那要进行 x 和 a 变换，那么 a 的右孩子放哪啊？很简单，如图放在 x 的左孩子上；分析：xd,da,所以 d 可作为 x 的左孩子，且可作为 a 的右孩子中的孩子。下边这样的类似情况不再一一分析，自己分析分析 实现：找到根结点 x，与它的左孩子 a 进行交换即可使二叉树树再次平衡；客观事物的符号表示在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称数据元素是数据的基本单位在计算机程序中通常作为一个整体进行考虑和处理数据结构是相互之间存在一种或多种特定关系的数据元理结构存储结构是数据结构在计算机中的表示又称映像其种存储结构顺序存数结构链式存数结构索引存数结构散列存数结构算法是对特定问题求解骤的一种描述它是指令的有限序列其中每一条指令表示一个或多个操作其个重要特性记作他表示随问题规模的增大算法执行时间的增长率和的增长率相同称做算法的渐进时间复杂度简称时间复杂度例如含基本操作增的语句的频度分别为和则这个程序段的时间复杂度分别为和分别称为常量阶线性阶和平方阶还可呈现学习好资料 欢迎下载 右右：即在 x 的右孩子 a 的右孩子 c 上插入一个结点y（该结点也可以是c,如图），即 y 可以是 c，也可以是 c 的右孩子（如图），也可以是 c 的左孩子（不在画出）。实现：找到根结点 x，与它的右孩子 a 进行交换即可使二叉树树再次平衡；左右：即在 x 的左孩子 a 的右孩子 c 上插入一个结点y（该结点也可以是c,如图），即 y 可以是 c，也可以是 c 的右孩子（如图），也可以是 c 的左孩子（不在画出）。这个左右和下边的右左，稍微复杂了点，需要进行两次交换，才能达到平衡，注意这时 y 是 c 的右孩子，最终 y 作为 x 的左孩子；若 y 是 c 的左孩子，最终 y作为 a 的右孩子，画图分析一下下边类似，不再敖述。实现：找到根结点 x，让 x 的左孩子 a 与 x 的左孩子 a 的右孩子 c 进行交换，然后再让 x 与 x 此时的左孩子 c 进行交换，最终达到平衡；右左：即在 x 的右孩子 a 的左孩子 c 上插入一个结点y（该结点也可以是c,如图），即 y 可以是 c，也可以是 c 的右孩子（如图），也可以是 c 的左孩子（不在画出）。实现：找到根结点 x，让 x 的右孩子 a 与 x 的右孩子 a 的左孩子 c 进行交换，然后再让 x 与 x 此时的右孩子 c 进行交换，最终达到平衡；上边的四种情况包含了所有插入时导致不平衡的情况，上面给出的仅仅是一棵大客观事物的符号表示在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称数据元素是数据的基本单位在计算机程序中通常作为一个整体进行考虑和处理数据结构是相互之间存在一种或多种特定关系的数据元理结构存储结构是数据结构在计算机中的表示又称映像其种存储结构顺序存数结构链式存数结构索引存数结构散列存数结构算法是对特定问题求解骤的一种描述它是指令的有限序列其中每一条指令表示一个或多个操作其个重要特性记作他表示随问题规模的增大算法执行时间的增长率和的增长率相同称做算法的渐进时间复杂度简称时间复杂度例如含基本操作增的语句的频度分别为和则这个程序段的时间复杂度分别为和分别称为常量阶线性阶和平方阶还可呈现学习好资料 欢迎下载 树中的最小不平衡子树，一定要想清楚，别迷了！另外一定要注意这个交换操作，比如 a 与 b 交换（a 在上，b 在下），b 一定要占据 a 的位置！什么意思？就是 b要放在（覆盖）储存 a 的那块内存上，再通俗点说，若 a 是 x 的左孩子，则交换后 b 要做 x 的左孩子；这就是所谓的 b 占据 a 的位置！5.哈希表：1)构造方法：a)直接定址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key 或 H(key)=akey+b，其中 a 和 b 为常数（这种散列函数叫做自身函数）。若其中 H(key）中已经有值了，就往下一个找，直到 H(key）中没有值了，就放进去。b)数字分析法：分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。c)平方取中法：当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。这是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址。d)折叠法：将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。数位叠加可以有移位叠加和间界叠加两种方法。移位叠加是将分割后的每一部分的最低位对齐，然后相加；间界叠加是从一端向另一端沿分割界来回折叠，然后对