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

第1章绪论内容提要：数据结构研究的内容。操作对象以及它们之间的关系和操作。针对非数值计算的程序设计问题，研究计算机的 数据结构涵盖的内容：钱进结构（建性表、栈、务太、串、数纽非线性结掏树结构图结构数据结构鞭疼结构遂式结构紊引结构散列结构耻除运翳数据运算）修改运算查找运算 排序运算基本概念：数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型。数据一一所有能被计算机识别、 存储和处理的符号的集合。数据元素一一是数据的基本单位，具有完整确定的实际意义。数据对象一一具有相同性质的数据元素的集合，是数据的一个子集。数据结构一一是相互之间存在一种或多种特定关系的数据元素的集合，表示为：Data_Structure= （ D, R）数据类型一一是一个值的集合和定义在该值上的一组操作的总称。抽象数据类型一一由用户定义的一个数学模型与定义在该模型上的一组操作， 它由基本的数据类型构成。算法的定义及五个特征。算法是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。算法的基本特性：输入、输出、有穷性、确定性、可行性算法设计要求。 正确性、可读性、健壮性、效率与低存储量需求算法分析。时间复杂度、空间复杂度、稳定性学习重点：数据结构的“三要素”：逻辑结构、物理（存储）结构 及在这种结构上所定义的操作（运算）。用计算语句频度来估算算法的时间复杂度。循环队列：队空条件：front = rear(初始化时 front = rear)队满条件：front = (rear+1) % N(N=maxsize)队列长度(即数据元素个数)：L=( N+ rear- front) % N1)初始化一个空队列Status InitQueue ( Sueue &q ) / 初始化空循环队列q(q . base=(QEIemType *)malloc(sizeof(QEIemType)* QUEUE_MAXSIZE);/ 分配空间if (Iq.base) exit(OVERFLOW);/内存分配失败，退出程序q.front =q.rear=0; / 置空队歹 Ureturn OK; /Ini tQueue;2)入队操作Status En Queue(Sueue &q, QEIemType 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)出队操作Status DeQueue ( Sueue &q, QEIemType &e)若队列不空，删除循环队列q的队头元素，由e返回其值，并返回0Kif ( q.front = = q.rear) return ERROR;/ 队列空q.fron t=(q.fro nt+1) % QUEUE_MAXSIZE ;e = q.base q.front ;return OK;/ DeQueue链队列空的条件是首尾指针相等，而循环队列满的条件的判定，则有队尾加和设标记两种方法。1等于队头补充重点：1 .为什么要设计堆栈？它有什么独特用途？调用函数或子程序非它莫属； 递归运算的有力工具； 用于保护现场和恢复现场； 简化了程序设计的问题。2 .为什么要设计队列？它有什么独特用途？ 离散事件的模拟（模拟事件发生的先后顺序，例如CPU芯片中的指令译码队列）； 操作系统中的作业调度（一个CPU执行多个作业）； 简化程序设计。3 .什么叫“假溢出”？如何解决？答：在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。解决假溢出的途径采用循环队列。4 .在一个循环队列中，若约定队首指针指向队首元素的前一个位置。那么，从循环队列中IW 除一个元素时，其操作是先移动队首位置，后取出元素。5 .线性表、栈、队的异同点：相同点：逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表（只是对插入、删除运算加以限制）。不同点：运算规则不同： 线性表为随机存取； 而栈是只允许在一端进行插入和删除运算，因而是后进先出表LIFO ;队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。用途不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、OS作业调度 和简化设计等。第四章串内容提要：串是数据元素为字符的线性表，串的定义及操作。串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。串比较：int strcmp(char *s1 ,char *s2);求串长：int strle n( char *s);串连接：char strcat(char *to,char *from) 子串 T 定位：char strchr(char *s,char *c);串的存储结构，因串是数据元素为字符的线性表，所以存在“结点大小”的问题。模式匹配算法。串有三种机内表示方法：耐一一用一组地址连续的存储单元存储串垃的字存诸称序列，属ifr态存储方式.堆令少存储表示-用-组连续的存储单元存储串垃的字符序列，但存瞎空同是在程序执祎过程中彩吉 分配而得* 鹫善串的块雒捽储表示仔临链式方式存储模式匹配算法：算法目的：确定主串中所含子串第一次出现的位置(定位)定位问题称为串的模式匹配，典型函数为In dex(S,T,pos)BF算法的实现一即编写 lndex(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 非空，1 < posw StrLength(S)i=pos; j=1;while (i<=S0 && j<=TO) /如果ij二指针在正常长度范围，(if (Si = = Tj) +i, +j;则继续比较后续字符else i=i-j+2; j=1; 若不相等，指针后退重新开始匹配>f(j>TO) return i-T0;/T 子串指针正常到尾，说明匹配成功，else return 0;/否则属于i>S情况，i先到尾就不正常 /I ndex_BP补充重点：1 空串和空白串有无区别？答：有区别。空串(Null String)是指长度为零的串；而空白串(Blank String),是指包含一个或多个空白字符(空格键)的字符串2 .“空串是任意串的子串；任意串S都是S本身的子串,S本身外，S的其他子串称为S的真子串。f运建吉枪s =* uijua*'定长顺序存储结构串T有储留吾构-堆存情结构二若干函数的实现1模式匹配算法模式匹配即子串定位运算即如何实现lDd<x(S,T,pttS)SA第六章树和二叉树内容提要： 树是复杂的非线性数据结构，树，二叉树的递归定义，基本概念，术语。树：由一个或多个（n0）结点组成的有限集合T,有且仅有一个结点称为根（root），当n>1时，其余的结点分为 m （m> 0）个互不相交的有限集合T1,T2 , , , Tm。每个集合本身又是棵树，被称作这个根的子树。二叉树：是n （n0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树 组成。术语：P88 二叉树的性质，存储结构。性质1:在二叉树的第i层上至多有2i1个结点（i>0 ）。性质2：深度为k的二叉树至多有2k个结点（k>0 ）。性质3：对于任何一棵二叉树，若2度的结点数有n2个，则叶子数（n0）必定为n2 + 1性质4：具有n个结点的完全二叉树的深度必为性质5：对完全二叉树，若从上至下、从左至右编号，则编号为i的结点，其左孩子编号必为2i，其右孩子编号为2i + 1 ；其双亲的编号必为i/2 （i= 1时为根，除外）。二叉树的存储结构：一、顺序存储结构按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。若是完全/满二叉树则可以做到唯一复 原。不是完全二叉树：一律转为完全二叉树！方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。缺点：浪费空间；插入、删除不便二、链式存储结构用二叉链表即可方便表示。一般从根结点开始存储。irlt Cbtdngbt (hldd优点：不浪费空间；插入、删除方便 二叉树的遍历。指按照某种次序访问二叉树的所有结点，并且每个结点仅访问一次，得到一个线性序列。遍历规则二叉树由根、左子树、右子树构成，定义为D、 L、R若限定先左后右，则有三种实现方案：中序遍历后序遍历DLRLDR LRD先序遍历树的存储结构，树、森林的遍历及和二叉树的相互转换。回顾2 :二叉树怎样还原为树？要点：逆操作，把所有右孩子变为兄弟！讨论1 :森林如何转为二叉树？法一：各森林先各自转为二叉树；依次连到前一个二叉树的右子树上。法二：森林直接变兄弟，再转为二叉树讨论2 :二叉树如何还原为森林？要点：把最右边的子树变为森林，其余右子树变为兄弟树和森林的存储方式：树有三种常用存储方式：双亲表示法孩子表示法孩子一兄弟表示法问：树t二叉树的“连线一抹线一旋转”如何由计算机自动实现？答：用“左孩子右兄弟”表示法来存储即可。存储的过程就是树转换为二叉树的过程！树、森林的遍历：探度优先第历（先月底怎和需鹫蹩？皿1广度忧去遁历（层执】 先根遍历：访问根结点；依次先根遍历根结点的每棵子树。 后根遍历：依次后根遍历根结点的每棵子树；访问根结点。讨论： 树若采用“先转换，后遍历”方式，结果是否一样？1 .树的先根遍历与二叉树的先序遍历相同；2 .树的后根遍历相当于二叉树的中序遍历；3 .树没有中序遍历，因为子树无左右之分。淼林的逼历先序遍历深度优先遍历£先序、申序）广度优先遍历层次1若森林为空，返回；访问森林中第一棵树的根结点； 先根遍历第一棵树的根结点的子树森林； 先根遍历除去第一棵树之后剩余的树构成的森林。中序遍历若森林为空，返回；中根遍历森林中第一棵树的根结点的子树森林；访问第一棵树的根结点； 中根遍历除去第一棵树之后剩余的树构成的森林。二叉树的应用：哈夫曼树和哈夫曼编码。Huffman树：最优二叉树（带权路径长度最短的树） Huffman编码：不等长编码。树的带权路径长度：（树中所有叶子结点的带权路径长度之和）构造Huffman树的基本思想：权值大的结点用短 路径，权值小的结点用长路径。构造Huffman树的步骤（即Huffman算法）：（1）由给定的n个权值 w1, w2, , , wn 构成n棵二叉树的集合F = T1,T2, , ,Tn）（即森林），其中每棵 二叉树Ti中只有一个带权为wi的根结点，其左右子树均空。（2）在F中选取两棵根结点权值最小的树做为左右子树构造一棵新的二叉树，且让新二叉树根结点的权值等于其左右子树的根结点权值之和。（3）在F中删去这两棵树，同时将新得到的二叉树加入F中。重复和，直到F只含一棵树为止。这棵树便是Huffman树。具体操作步骤：stepl：对权值进行合并、删除与替换在权值束合忡,52 4中，总是合井当的最小的两个权。.初始令并国同吐合井(7) (11FH7K11Ft 11田回团©b.合并2 4Ft(7)(5)(6step2：按左“（T右"F对Htlffman树的所有分支编号将Huffman树与Huffman八码挂钩a 21 ri nHuffinan 编码结果：d=: , i= t a- JO, n=WFL=lbitX7+2MtX5+3bitQ+4 ） =35 （小干尊长码的 ffFL=36）学习重点：（本章内容是本课程的重点）二叉树性质及证明方法，并能把这种方法推广到K叉树。二叉树遍历，遍历是基础，由此导出许多实用的算法，如求二叉树的高度、各结点的层次数、度为0、1、2的结 点数。由二叉树遍历的前序和中序序列或后序和中序序列可以唯一构造一棵二叉树。由前序和后序序列不能唯一确定一棵 二叉树。完全二叉树的性质。树、森林和二叉树间的相互转换。哈夫曼树的定义、构造及求哈夫曼编码。补充：1-满二叉树和完全二叉树有什么区别？k-1层是满的，但最底层却允许答：满二叉树是叶子一个也不少的树，而完全二叉树虽然前在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。2. Huffman树有什么用？最小冗余编码、信息高效传输第七章图内容提要：图的定义，概念、术语及基本操作。图：记为G=（V, E ）其中：V是G的顶点集合，是有穷非空集；E是G的边集合，是有穷集。术语：见课件图的存储结构。1 邻接矩阵（数组）表示法建立一个顶点表和一个邻接矩阵 设图A = （V, E）有n个顶点，则图的邻接矩阵是一个二维数组A.Edgenn。注：在有向图的邻接矩阵中，第i行含义：以结点vi为尾的弧（即出度边）；第i列含义：以结点vi为头的弧（即入度边）。邻接矩阵法优点：容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧） 找顶点的邻接点等等。邻接矩阵法缺点：n个顶点需要n*n个单元存储边（弧）；空间效率为0 （n2）。2邻接表（链式）表示法对每个顶点vi建立一个单链表，把与vi有关联的边的信息（即度或出度边）链接起来，表中每个结点都设为3 个域：头站点表蛤点 每个单链表还应当附设一个头结点（设为2个域），存vi信息；每个单链表的头结点另外用顺序存储结构存储。邻接表的优点：空间效率高；容易寻找顶点的邻接点；邻接表的缺点：判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。图的遍历。遍历定义：从已给的连通图中某一顶点出发，沿着一些边，访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。图常用的遍历：一、深度优先搜索；二、广度优先搜索 深度优先搜索（遍历）步骤：访问起始点v; 若v的第1个邻接点没访问过，深度遍历此邻接点； 若当前邻接点已访问过，再找v的第2个邻接点重新遍历。基本思想：一一仿树的先序遍历过程。L应退回到Y8,因为V2已有标记广度优先搜索（遍历）步骤：vlTv2Tv4Tv8 Tv5±v3Tv6T 在访问了起始点V之后，依次访问V的邻接点； 然后再依次（顺序）访问这些点（下一层）中未被访问过的邻接点;直到所有顶点都被访问过为止。图的应用（最小生成树，最短路经）最小生成树（MST ）的性质如下：若U集是V的一个非空子集，若（uO, vO）是一条最小权值的边，其中 uO U , vO V-U ；则：（uO, vO）必在最小生成树上。求MST最常用的是以下两种：Kruskal （克鲁斯卡尔）算法、Prim （普里姆）算法Kruskal算法特点：将边归并，适于求稀疏网的最小生成树。Prime算法特点：将顶点归并,与边数无关，适于稠密网。Kruskal法示刚：对边操作*旧井边在带权有向图中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。 两种常见的最短路径问题：一、单源最短路径一用Dijkstra （迪杰斯特拉）算法二、所有顶点间的最短路径一用Floyd （弗洛伊德）算法一、单源最短路径（Dijkstra算法）一顶点到其余各顶点（vOj）目的：设一有向图G= （V, E）,已知各边的权值，以某指定点V。为源点，求从vO到图的其余各点的最短路径。限定各边上的权值大于或等于0。二、所有顶点之间的最短路径可以通过调用n次Dijkstra算法来完成，还有更简单的一个算法：Floyd算法（自学）。学习重点：图是应用最广泛的一种数据结构，本章也是这门课程的重点。基本概念中，连通分量，生成树，邻接点是重点。 连通图：在无向图中，若从顶点v1到顶点v2有路径，则称顶点v1与v2是连通的。如果图中任意一对 顶点都是连通的，则称此图是连通图。非连通图的极大连通子图叫做连通分量。 生成树：是一个极小连通子图，它含有图中全部n个顶点，但只有n-1条边。 邻接点：若（u,v）是E（G）中的一条边，则称u与v互为邻接顶点。图是复杂的数据结构，也有顺序和链式两种存储结构：数组表示法（重点是邻接距阵）和邻接表。这两种存储结构 对有向图和无向图均适用应熟练掌图的遍历是图的各种算法的基础，应熟练掌握图的深度、广度优先遍历。连通图的最小生成树不是唯一的，但最小生成树边上的权值之和是唯一的。握prim和kruscal算法，第二章线性表内容提要：线性表的逻辑结构定义，对线性表定义的操作。线性表的定义：用数据元素的有限序列表示n为元素兑口时称为空眈 曾：器线性表的存储结构：顺序存储结构和链式存储结构。顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。链式存储结构：其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上定相邻。通过指针来实现！不一线性表的操作在两种存储结构中的实现。数据结构的基本运算：修改、插入、删除、查找、排序1)修改一一通过数组的下标便可访问某个特定元素并修改之。核心语句：Vi=x;顺序表修改操作的时间效率是0(1)2)插入一一在线性表的第i个位置前插入一个元素实现步骤： 将第n至第i位的元素向后移动一个位置；将要插入的元素写到第i个位置；表长加1。注意：事先应判断：插入位置i是否合法？表是否已满？应当符合条件： K i < n+1或i=1, n+1 核心语句：for (j=n; j>=i;j-)aU+1=aj；ai =x;n+;插入时的平均移动次数为：n(n+1)/2 *( n+1)=n/20(n)3)删除一一删除线性表的第i个位置上的元素实现步骤： 将第i+1至第n位的元素向前移动一个位置；表长减1。注意：事先需要判断，删除位置i是否合法？应当符合条件：Ki< n或1,n核心语句：for(j=i+1;j<=n;j+)a0-1=a0；从单源点到其他顶点，以及各个顶点间的最短路径问题，掌握熟练手工模拟。补充：1 .问：当有向图中仅1个顶点的入度为0,其余顶点的入度均为1，此时是何形状？答：是树！而且是一棵有向 树！2 .讨论：邻接表与邻接矩阵有什么异同之处？1 .联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。2 .区别：对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。3 .用途：邻接矩阵多用于稠密图的存储而邻接表多用于稀疏图的存储3,若对连通图进行遍历，得到的是生成树若对非连通图进行遍历，得到的是生成森林。第八章查找内容提要：查找表是称为集合的数据结构。是元素间约束力最差的数据结构：元素间的关系是元素仅共在同一个集合中。（同 一类型的数据元素构成的集合）查找表的操作：查找，插入，删除。静态查找表：顺序表，有序表等。针对静态查找表的查找算法主要有：顺序查找、折半查找、分块查找一、顺序查找（线性查找）技巧：把待查关键字key存入表头或表尾（俗称“哨兵”），这样可以加快执行速度。int Search_Seq （ SSTable ST , KeyType key ） ST.elemO.key =key;for （ i=ST.Ie ngth; ST.elem i .key!=key; - - i ）;return i; / Search_Seq/ASL = （ 1 + n） /2，时间效率为0 （n）,这是查找成功的情况：顺序查找的特点：优点：算法简单，且对顺序结构或链表结构均适用。缺点：ASL太大，时间效率太低。二、折半查找（二分或对分查找）若关键字不在表中，怎样得知并及时停止查找？典型标志是：当查找范围的上界w下界时停止查找。ASL的含义是“平均每个数据的查找时间”，而前式是n个数据查找时间的总和，所以：ASL j 2jlog2 （n 1） 1 ： log2nn j二n三、分块查找（索引顺序查找） 思路：先让数据分块有序，即分成若干子表，要求每个子表中的数据元素值都比后一块中的 数值小（但子表内部未 必有序）。然后将各子表中的最大关键字构成一个索引表，表中还要包含每个子表的起始地址（即头指针） 特点：块间有序，块内无序。查找：块间折半，块内线性 查找步骤分两步进行： 对索引表使用折半查找法（因为索引表是有序表）在子表内采用顺序查找法（因为各子表内部是无序表）确定了待查关键字所在的子表后， 查找效率ASL分析：ASLsU+LA-B对盍引表查推的3希每块内的吐寅晞叩块的茹目二）创即当n 叫5=33 Jr分快法的枫.=3. 5而折半迭的开日1殂折半佚气£罐“驻-y-TL.E排序肝口蟆玮法咖L珂L+nU舄时何动态查找表：二叉排序树，平衡二叉树。特点：表结构在查找过程中动态生成。要求：对于给定值key,若表中存在其关键字等于key的记录，则查找成功返回；否则插入关键字等于key的记录。二叉排序树的定义-或是一棵空树；或者是具有如下性质的非空二叉树：(1)左子树的所有结点均小于根的值；(2)右子树的所有结点均大于根的值；(3)它的左右子树也分别为二叉排序树。二叉排序树的插入与删除思路：查找不成功，生成一个新结点s,插入到二叉排序树中；查找成功则返回。SearchBST (K, &t) K为待查关键字，t为根结点指针P=t； p为查找过程中进行扫描的指针while(p!=NULL) case K= p->data： 查找成功，return K< p->data : q=p ; p=p->L_child 继续向左搜索K> p->data : q=p ; p=p->R_child / 继续向右搜索查找不成功则插入到二叉排序树中s =(BiTree)malloc(sizeof(BiTNode);s->data=K; s ->L_child=NULL; s ->R_child=NULL;查找不成功，生成一个新结点s,插入到二叉排序树叶子处case t=NULL ： t=s; 若t为空，则插入的结点s作为根结点K < q->data： q->L_child=s; 若 K 比叶子小，挂左边K > q->data： q->R_child=s; 若 K 比叶子大，挂右边return OK)二叉排序树的删除操作如何实现？如何删除一个结点？假设：*P表示被删结点的指针；PL和PR分别表示*P的左、右孩子指针；若在A的Lp子甘的挖亍时上J*人姑A,血乂的*断因子从塔扣至签5E事却疔顾Mfi驴齐建时针如 / '、J 鼻 人的佶Ju0/撬转匚二学习重点：查找表是称为集合的数据结构。因元素间关系非常松散，其操作需借助其它数据结构来实现。本章列举了三种方法 (静态查找表，动态查找表)实现查找表的运算。顺序表因设置了监视哨使查找效率大大提高。有序表的平均查找长度不超过树的深度。*f表示*P的双亲结点指针；并假定*P是*f的左孩子；则可能有三种情况:I巾为叶了 L JW除此结点时“直接悔改曲域即可： 彳打只有Tt 了讨（虹或右）土锂卑吃为*f曲左曲子即町：I衍有两操子楂上悟况矍琳4查找的ASL二叉排序树的形态取决于元素的输入顺序。按中序遍历可得到结点的有序序列，应熟练掌握其建立、查找，插入和 删除算法。平衡二叉树的概念，应熟练掌握手工绘制平衡二叉树。二叉排序树的AS.<2(1 + -L)ln it1平衡二叉树的定义： 又称AVL树，即它或者是一颗空树，或者是它的左子树和右子树都是平衡二叉树，且左子树与右子树的深度之差的绝对值不超过1。平衡因子：一一该结点的左子树的深度减去它的右子树的深度。平衡二叉树的特点：任一结点的平衡因子只能取：、0或1。如果在一棵AVL树中插入一个新结点，就有可能造成失衡，此时必须重新调整树的结构，使之恢复平衡。我们称调 整平衡过程为平衡旋转。平衡旋转可以归纳为四类:轴魂" niAflS牛布囚子派1堆加垂2,龄筑忙.心5时针盖耦*野在也站占干禅阳生子樽上妞人箱点+ OtA昨平衙凶子做1期抽1> LL平衡旋转：3) LR平衡康转:若灰A的士子甘的右子+人上J6人人A, TitA的辛街因子从L堆加生7,需奂st琨好够叶汁程转.再4) RL平衡族转:ASLoK的记录,补充：1 .查找的过程是怎样的？给定一个值K，在含有n个记录的文件中进行搜索，寻找一个关键字值等于如找到则输出该记录，否则输出查找不成功的信息。2 .对查找表常用的操作有哪些？查询某个“特定的”数据元素是否在表中；查询某个“特定的”数据元素的各种属性；在查找表中插入一元素； 从查找表中删除一元素。3 .哪些查找方法？查找方法取决于表中数据的排列方式；4 .如何评估查找方法的优劣？用比较次数的平均值来评估算法的优劣。称为平均查找长度ASL=r Pi. Ci 5,使用折半查找算法时，要求被查文件：采用顺序存贮结构、记录按关键字递增有序6.将线性表构造成二叉排序树的优点： 查找过程与顺序结构有序表中的折半查找相似，查找效率高； 中序遍历此二叉树，将会得到一个关键字的有序序列(即实现了排序运算)； 如果查找不成功，能够方便地将被查元素插入到二叉树的叶子结点上，而且插入或删除时只需修改指针而不需 移动元素。第九章内部排序内容提要：排序的定义，排序可以看作是线性表的一种操作排序:将一组杂乱无章的数据按一定的规律顺次排列起来。排序的分类，稳定排序与不稳定排序的定义。稳定性一一若两个记录A和B的关键字值相等，但排序后则称这种排序算A、B的先后次序保持不变，法是 稳定的。插入排序(直接插入、折半插入，索引表插入、希尔插入排序)插入排序的基本思想是：描入排序有多种具体宴现算法:I)亘樱插入排序力折半插入排序3) 2-路插入排序-小改进4)祓描入排序J5)希尔排序一大克讲0+ 1+ , + 尸 O(n2)。每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对 象的适当位置上，直到对象全部插入为止。简言之，边插入边排序，保证子序列中随时都是排好序的。1)直接插入排序在已形成的有序表中线性查找，并在适当位置插入，把原来位置上的元素 向后顺移。例1;关镇字住列T- (13, 6阑31,篦27, 5, 11), 请写出直接插入排序的4同过程序列*13，电气 31,9,27/41【6,13，M 31, % 27,0113,6,13 ,31,9,37113,6,13*3127,5,113,31 5,11【3(* 13, 27,311,5,11【3,久®19箕 27t JI ,11 3A IK 13, 27,31时间效率：因为在最坏情况下，所有元素的比较次数总和为(其他情况下也要考虑移动元素的次数。故时间复杂度为0( n2)空间效率：仅占用 1个缓冲单元一一 O(1)算法的稳定性：因为25*排序后仍然在25的后面一一稳定直接插入排序算法的实现：void InsertSort ( SqList &L ) /对顺序表L作直接插入排序for(i = 2;i<=L.length;i+)/ 假定第一个记录有序 L.rO= L.ri;j=i-1 ；先将待插入的元素放入“哨兵”位置while(L0 .key<Lj.key) L.rU+1= L.rj;L.rj+1= L.rO;j- ；)只要子表元素比哨兵大就不断后移直到子表元素小于哨兵，将哨兵值送入当前要插入的位置(包括插入到表首)2)折半插入排序既然子表有序且为顺序存储结构，则插入时采用折半查找定可加速。优点：比较次数大大减少，全部元素比较次数仅为0 (nlog2n)。时间效率：虽然比较次数大大减少，可惜移动次数并未减少，所以排序效率仍为0 (n2)。空间效率：仍为0( 1)稳定性：稳定若记录是链表结构，用直接插入排序行否？答：行，而且无需移动元素，时间效率更高! 但请注意：单链表结构无法实现“折半查找”3）表插入排序基本思想：在顺序存储结构中，给每个记录增开一个指针分量，在排序过程中将指针内容逐个修改为已经整理（排序）过的后继记录地址。优点：在排序过程中不移动元素，只修改指针。此方法具有链表排序和地址排序的特点表插入排序算法分析： 无需移动记录，只需修改指针值。但由于比较次数没有减少，故时间效率仍为0（n2）。 空间效率肯定低，因为增开了指针分量（但在运算过程中没有用到更多的辅助单元） 稳定性：25和25*排序前后次序未变，稳定。注：此算法得到的只是一个有序链表，查找记录时只能满足顺序查找方式。5）希尔（shell）排序基本思想：先将整个待排记录序列分割成若干子序列，分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。优点：让关键字值小的元素能很快前移，且序列若基本有序时，再用直接插入排序处理，时间效率会高很多。例土 关 It 字序列3tiT 65, 97,76,13, 27t 49S 55,04），请写出希尔排序的具恃实现过程.rl 0 12345678910149386597132749*5504IS17斗9*J5046J9776130449*3S274?65977604133S49*4?55657691第 1 趟（ik=5）第 2 精（dk-Jj第 3 世（dk=l）时何效率：0n'A>T）由经验公式得到空间效率0（1； 一一因为仅占用1个缓冲单云算法的膛定性：不稳定一一为4中排序后却封了翻的前血交换排序（冒泡排序、快速排序）。交换排序的基本思想是：两两比较待排序记录的关键码，如果发生逆序（即排列顺序与排序后的次序正好相 反），则交换之，直到所有记录都排好序为止。1）冒泡排序基本思路：每趟不断将记录两两比较，并按“前小后大”（或“前大后小”）规则交换。优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；旦下趟没有交换发生，还可以提前结 束排序。 前提：顺序存储结构例：关键字序列T=（21< 25, 49. 25*t 08） * ifl写出目泡排序的具悴实现过程。2L 25,49T 25*, 14. 0821.25,15* 16, 08t49 Z, 25, 16h OR *4921,16, U8f 25, 2S*t 4916, 08 21, 25, 25S 4908,16. 21,25. 25 49冒泡排序的算法分析：时间效率：。（n2）因为要考虑最坏情况空间效率：。（1）一只在交换时用到一个缓冲单元稳定性：稳定一 25和25*在排序前后的次序未改变冒泡排序的优点：每一趟整理元素时，不仅可以完全确定一个元素的位置尾），还可以对前面（挤出一个泡到表 的元素作一些整理，所以比一般的排序要快。2）快速排序基本思想：从待排序列中任取一个元素（例如取第一个）作为中心，所有比它小的元素一律前放，所有比它大的元 素一律后放，形成左右两个子表；然后再对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩 一个。此时便为有序序列了。优点：因为每趟可以确定不止一个元素的位置，而且呈指数增加，所以特别快！前提：顺序存储结构例仁 关键字序7 八（21, 25, 49, 25*, 16, 08）.请写出快速排序的设以首元素为枢轴中社.初态：21, 25, 49, 25*, 1氐08第 1 趟：（08 1621 口（25*, 49,25）第 2 趟* （08）r 16A 21, 25*, 25, 49）第第嵌 08r 16,27, 25S 25. （49）时间效率：0（nl og2 n）因为每趟确定的元素呈指数增加空间效率：0（Iog2n）因为递归要用栈（存每层low , high和pivot）稳定性：不稳定一因为有跳跃式交换。选择排序（简单选择排序、树形选择排序、堆排序）。选择排序的基本思想是：每一趟在后面n-i