自学考试数据结构重点总结023312015年整理

.自考数据结构重点〔2014整理第一章概论1.瑞士计算机科学家沃思提出：算法+数据结构=程序。算法是对数据运算的描述,而数据结构包括逻辑结构和存储结构。由此可见,程序设计的实质是针对实际问题选择一种好的数据结构和设计一个好的算法,而好的算法在很大程度上取决于描述实际问题的数据结构。2.数据是信息的载体。数据元素是数据的基本单位。一个数据元素可以由若干个数据项组成,数据项是具有独立含义的最小标识单位。数据对象是具有相同性质的数据元素的集合。3.数据结构指的是数据元素之间的相互关系,即数据的组织形式。数据结构一般包括以下三方面内容：数据的逻辑结构、数据的存储结构、数据的运算①数据的逻辑结构是从逻辑关系上描述数据,与数据元素的存储结构无关,是独立于计算机的。数据的逻辑结构分类:线性结构和非线性结构②数据元素及其关系在计算机内的存储方式,称为数据的存储结构〔物理结构。数据的存储结构是逻辑结构用计算机语言的实现,它依赖于计算机语言。③数据的运算。最常用的检索、插入、删除、更新、排序等。4.数据的四种基本存储方法:顺序存储、链接存储、索引存储、散列存储〔1顺序存储：通常借助程序设计语言〔2链接存储：通常借助于程序语言的指针来描述。〔3索引存储：索引表由若干索引项组成。关键字是能唯的数组描述。一标识一个元素的一个或多个数据项的组合。〔4散列存储：该方法的基本思想是：根据元素的关键字直接计算出该元素的存储地址。5.算法必须满足5个准则：输入,0个或多个数据作为输入；输出,产生一个或多个输出；有穷性,算法执行有限步后结束；确定性,每一条指令的含义都明确；可行性,算法是可行的。算法与程序的区别：程序必须依赖于计算机程序语言,而一个算法可用自然语言、计算机程序语言、数学语言或约定的符号语言来描述。目前常用的描述算法语言有两类：类Pascal和类C。6.评价算法的优劣：算法的"正确性"是首先要考虑的。此外,主要考虑如下三点：①执行算法所耗费的时间,即时间复杂性；②执行算法所耗费的存储空间,主要是辅助空间,即空间复杂性；③算法应易于理解、易于编程,易于调试等,即可读性和可操作性。以上几点最主要的是时间复杂性,时间复杂度常用渐进时间复杂度表示。7.算法求解问题的输入量称为问题的规模,用一个正整数n表示。8.常见的时间复杂度按数量级递增排列依次为：常数阶0<1>、对数阶0<logn>、线性阶0<n>、线性对数阶0<nlogn>、22平方阶0<n2>立方阶0<n3>、…、k次方阶0<nk>、指数阶0<2n>和阶乘阶0<n!>。9.一个算法的空间复杂度S<n>定义为该算法所耗费的存储空间,它是问题规模n的函数,它包括存储算法本身所占的存储空间、算法的输入输出数据所占的存储空间和算法在运行过程中临时占用的存储空间。第二章线性表1.数据的运算是定义在逻辑结构上的,而运算的具体实现是在存储结构上进行的。2.只要确定了线性表存储的起始位置,线性表中任意一个元素都可随机存取,所以顺序表是一种随机存取结构。3.常见的线性表的基本运算:<1>置空表InitList〔L构造一个空的线性表L。<2>求表长ListLength〔L求线性表L中的结点个数,即求表长。<3>GetNode〔L,i取线性表L中的第i个元素。<4>LocateNode〔L,x在L中查找第一个值为x的元素,并返回该元素在L中的位置。若L中没有元素的值为x,则返回0值。<5>InsertList〔L,i,x在线性表L的第i个元素之前插入一个值为x的新元素,表L的长度加1。<6>DeleteList〔L,i删除线性表L的第i个元素,删除后表L的长度减1。4.顺序存储方法：把线性表的数据元素按逻辑次序依次存放在一组地址连续的存储单元里的方法。顺序表〔SequentialList：用顺序存储方法存储的线性表称为顺序表。顺序表是一种随机存取结构,顺序表的特点是逻辑上相邻的结点其物理位置亦相邻。5.顺序表上实现的基本运算：-1-/13

〔1插入：该算法的平均时间复杂度是〔2删除：顺序表上做删除运算6.采用链式存储结构可以避免频繁移动大量元素。一个单链表可由头指针唯一确定,因此单链表可以用头指针的名字来命名。①生成结点变量的标准函数p=<ListNode*>malloc<sizeof<ListNode>>；//函数malloc分配一个类型为ListNode的结点变量的空间,并将其首地址放入指针变量p中②释放结点变量空间的标准函数free<p>；//释放p所指的结点变量空间③结点分量的访问方法二：p-﹥data和p-﹥next:指针变量p的值——结点地址,结点变量*p的值——结点内容p->data=ch;②//将读入的数据放入新结点的数据域中p->next=head;③head=p;④〔2尾插法建表：算法：p=<ListNode*>malloc<sizeof<ListNode>>;p->data=ch;②//将读入的数if<head==NULL>rear->next=p;③//将新结点插到*r之后向新表尾开始结点之前附一加个结点。存放在头结点的指针域中,所以在链表的第一个特殊处理;链表是否为空,其头指针都是指向头结点的非空指针〔空表中头结点的指针域空,因此空表和非空表的处理也就统一了。它具有两个优点:⒈由于开始结点的上操作一致,无须进行⒉无论位置上的操作就和在表的其它位置阴影表示该部分不存储信息。在有的应用中可用于存放表长等附加信息。具体算法：r=head;//尾指针初值也指while<<ch=getchar<>>!='\n'>{*>malloc<sizeof<ListNode>>;//生成新结点s->data=ch;//将读入的r->next=NULL;//终端结点的指针域置空,或空表的头结点指针域置空三个算法的时间复杂度均为O<n>。8.单链表上的查找：〔带头结点〔1按结点序号查找：序号为0的是头结点。p=head;j=0;//从头结点开始扫描while<p->next&&j<i>{//顺指针向后扫描,直到p->next为NULL或i=j为止p=p->next;j++;.〔2按结点值查找：ListNode*p=head->next;//从开始结点比较。表非空,p初始值指向开始结点while<p&&p->data!=key>//直到p为NULL或p->data为key为止returnp;//若p=NULL,则查找失败,否则p指向值为key的结点,即插入到a与a之间。i-1is=<ListNode*>malloc<sizeof<ListNode>>;②r=p->next;②//使r指向被删除的结点aip->next=r->next③;//将a从链上摘下i//释放结点a的空间给存储池free<r>;④i算法的时间复杂度也是O〔n。p指向被删除的前一个结点。链表上实现的插入和删除运算—在单链表中,将终端结点的指针域NULL改为指向表,无须移动结点,仅需修改指针。11.单循环链表头结点或开始结点即可。判断空链表的条件是head==head->next;12.仅设尾指针的单循环链表:用尾指针rear表示的单循环链表对开始结点a和终端结点a查找时间都是O<1>。而1n进行,因此,实用中多采用尾指针表示单循环链表。判断空链表的条件为表的操作常常是在表的首尾位置上rear==rear->next;13.循环链表：循环链表的特点是无须增加存储量,仅对表的链接方式稍作改变,即可使得表处理更加方便灵活。若在尾指针表示的单循环链表上实现,则只需修改指针,无须遍历,其执行时间是O<1>。具体算法：LinkListConnect<LinkListA,LinkListB>{//假设A,B为非空循环链表的LinkListp=A->next;//①保存A表的头结点位置A->next=B->next->next;//②B表的开始结点链接到A表尾尾指针free<B->next>;//③释放B表的头结点B->next=p;//④returnB;//返回新循环链表的循环链表中没有NULL指针。操作时,其终止条件就不再是像非循环链表那样判别p或p-＞next是否为-3-/13尾指针涉及遍历在单链表中,从一已知结点出发,只能访问到该结点及其后续结点,无法找到该结点之前的其它结点。而在单循环链表中,从任一结点出发都可访问到表中所有结点,这一优点使某些运算在单循环链表上易于实现。14.双向链表:双〔向链表中有两条方向不同的链,即每个结点中除next域存放后继结点地址外,还增加一个指向其③将头结点和尾结点链接起来,为双〔向循环链表。15.双voidDInsertBefore<DListNode*p,DataTypex>{//在带头结点的双链表中,将值为x的新结点插入*p之前,设p≠NULL{//在带头结点的双链表中,删除结点*p,设p->prior->next=p->next;//①p->next->prior=p->prior;//②free<p>;//③与单链表上的插入和删除操作不同的是,在双链表中插入和删除必须同时修两改个方向上的指针。上述两个算法的时16.顺序表和链表时间性能：a、线性表：经常性的查找；b、链式存储结构：经常空间性能：a、对数据量大小事先能够知道的用线性表；b、数据量变化较大的用链式存储结构。存储密度越大,存储空间的利用率越高。显然,顺序表的存储密度是1,链表的存储密度肯定小于1。第三章栈和队列1.栈称为后进先出〔LastInFirstOut的线性表,简称为LIFO表。比较栈也是用数组表示的。进栈操作：进栈时,需要将S-＞top加1,①S-＞②"上溢"现象--当栈满时,再做进栈运算产生空间溢出的现退栈操作：退栈时,需将S-＞top减1,①S-＞top<0表示空栈②"下溢"现象--当栈空时,做退栈运算产生的溢出现象。下溢是正常现象,常用作程序控制转移的条件。空栈时栈顶指针不能是0,只能是-1。象。当程序中同时使分别设在顺序存储空间的两端,让两个栈顶各自向中间延伸。当一个栈中的多而栈使用的空间超过共享空间的一半时,只要另一个栈的元素不多,那么前者就可以占用后者的部分存储空间。用两个栈时,可以将两个栈的栈底.当Top1=Top2-1时,栈满2.为了克服顺序存储分配固定空间所产生的溢出和空间浪费问题。可采用链式存储结构来3.允许删除的一端称为队头〔Front,允许插入的一端称为队尾〔Rear,当队列中没有元素时称为空队列,队列亦称作先进先出〔FirstInFirstOut的线性表,简称为FIFO表。队列的顺序存储结构称为顺序队列,顺序队列实际上是一个受限的：将新元素插入rear所指的位置,然后将rear加1。在非空队列里,头指针始指终向队头元素,而队尾指针始指终向队尾元素的下一位置。而栈顶指针指向栈顶元素。4.循环队列：为充分利用数组空间,克服上溢,可将数组空间想象为一个环状空间,并称这种环状数组表示的队列为循环队列。循环队列中进行出队、入队操作时,头尾指针仍要加1,朝前移动。只不过当头尾指针指向向量上界〔QueueSize-1时,其加1操作的结果是指向向量的下界0。这种循环意义下的加1操作可以描述为：②方法i=<i+1>%QueueSize；循环队列中,由于入队时尾指针；出队时头指针向前追赶尾指针,造成队空和队满时头尾指针均相等。因此,无法通过条件Q.front==Q.rear来判别队列是"空"还是"满"。方法至少有三种：①另设一个标志位以区别队列是空②设置一个计数器记录队列中元素的总数〔③少用一个元素的空间。约定入队前,测试尾指针在循环意义下加1后是否等于头指针,若相等则认为队列满即⑤出队temp=Q->data[Q->front];.为了简化处理,在队头结点之前附加一个头结点,并设队头指针指向此结点。链队列的基本运算:〔带头结点〔1构造空队：Q->rear=Q->front；Q->rear->next=NULL;〔2判队空：returnQ->rear==Q->front;〔3入队：QueueNode*p=<QueueNode*>malloc<sizeof<QueueNode>>;//申请新结点p->data=x;p->next=NULL;Q->rear->next=p;Q->rear=p;//*p链到原队尾结点后//队尾指针指向新的尾〔4出队：当队列长度大于1时,只需修改头结点指针,尾指针不变s=Q->front->next;Q->front->next=s->next;x=s->data;free<s>;returnx;当队列长度等于1时,不仅要修改头结点指针,还要修改尾指针s=Q->front->next;Q->front->next=NULL;Q->rear==Q->front;x=s->data;free<s>;returnx;〔5取队头元素：returnQ->front->next->data;因为有头结点,所以用了next①和链栈类似,无须考虑判队满的运算及上溢。②在出队算法中,一般只需修改队头指针。但当原队中只有一个结点时,该结点既是队头也是队尾,故删去此结点时亦需修改尾指针,且删去此结点后队列变空。7.用计算机来处理计算算术表达式问题,首先要解决的问题是如何将人们习惯书写的中缀表达式转换成后缀表达式。第四章多维数组和广义表1.数组的顺序存储方式:一般采用顺序存储方法表示数组。〔1行优先顺序a,a,…,a,a,a,…,a,……,a,a,…,a11121n21222nm1〔2列优先顺序a,a,…,a,a,a,…,a,……,a,a,…,am2mn1121m11222m21nPascal和C语言是按行优先顺序存储的,而Fortran语言是按列优先顺序存储的。2nmn2.为了节省存储空间,可以对矩阵中有许多值相同或值为零的元素的矩阵,采用压缩存储。特殊矩阵是指相同值的元素或零元素在矩阵中的分布有一定的规律。常见的有对称矩阵、三角矩阵。〔1对称矩阵在一个n阶方阵A中,若元素满足下述性质：a=a0≤i,j≤n-1ijji称为n阶对称矩阵,它的元素是关于主对角线对称的,所以只需要存储矩阵上三角或下三角元素即可,让两个对称的元素共享一个存储空间。矩阵元素a和数组元素sa[k]之间的关系是ijk=i×<i+1>/2+ji≥j0≤k<n<n+1>/2-1k=j×<j+1>/2+ii＜j0≤k<n<n+1>/2-1〔2三角矩阵：以主对角线划分,三角矩阵有上三角和下三角两种。上三角矩阵是指它的下三角<不包括主角线>中的元素均为常数c或零；下三角矩阵的主对角线上方均为常数c或零。一般情况,三角矩阵的常数c均为零。三角矩阵的压缩存储：三角矩阵中的重复元素c可共享一个存储空间,其余的元素正好有n×<n+1>/2个,因此,三角矩阵可压缩存储在一维数组sa[n<n+1>/2+1]中,其中c存放在数组的最后一个元素中。三角矩阵的压缩存储结构是随机存取结构。3.稀疏矩阵:设矩阵A中有s个非零元素,若s远远小于矩阵元素的总数,则称A为稀疏矩阵。为了节省存储单元,可mn用压缩存储方法只存储非零元素。由于非零元素的分布一般是没有规律的,因此在存储非零元素。进行压缩存储通常有两类方法：顺序存储<三元组表>和链式存储<十字链表>。稀疏矩阵的压缩存储会失去非零元素的同时,还必须存储非零元素所在的行、列位置,所以可用三元组<i,j,a>来确定ij稀疏矩阵随机存取功能。4.广义表是线性表的推广,又称列表。广义表是n<n≥0>个元素a,a,…,a,…,a的有限序列。其中a或者是原子或者是一个广义表。12ini①广义表通常用圆括号括起来,用逗号分隔其中的元素。②为了区分原子和广义表,书写时用大写字母表示广义表,用小写字母表示原子。③若广义表Ls非空<n≥1>,则a是LS的表头,其余元素组成的表<a,a,…,a>称为Ls的表尾。2l④广义表具有递归和共享的性质1n-6-/13

.广义表的深度：一个表展开后所含括号的层数称为广义表的深度。19.广义表是一种多层次的线性结构,实际上这就是一种树形结构。任何一个非空广义表的表头可以是原子,也可以是子表,而其表尾必定是子表。head=<a,b>=a,tail<a,b>=<b>对非空表A和<y>,也可继续分解。注意:广义表<>和<<>>不同。前者是长度为0的空表,对其不能做求表头和表尾的运算；而后者是长度为l的由空表作元素的广义表,可以分解得到的表头和表尾均是空表<>。广义表是一种有层次的非线性结构,通常采用链式存储结构,每个元素用一个结点表示,结点由3个域构成,其中一个是tag标志位,用来区分结点是原子还是子表,当tag为零时结点是子表,第二个域为slink,用以存放子表的地址；当tag为1时结点是原子,第二个域为data,用以存放元素值。第五章树和二叉树1.树的表示法：最常用的是树形图表示法；还有3种嵌套集合、凹形、广义表。树结构的基本术语〔1结点的度<Degree>树中的一个结点拥有的子树数称为该结点的度<Degree>。一棵树的度是指该树中结点的最度大数。度为零的结点称为叶子<Leaf>或终端结点。度不为零的结点称分支结点或非终端结点。除根结点之外的分支结点统称为内部结点。根结点又称为开始结点。〔2①路径〔path若树中存在一个结点序列k,k,…,k,使得k是k的双亲<1≤i<j>,则称该结点序列是从k到kj12iii+1l的一条路径<Path>。一个结点的祖先是从根结点到该结点路径上所经过的所有结点,而一个结点的子孙则是以该结点为根的子树中的所有结点。结点的层数<Level>从根起算：根的层数为1,其余结点的层数等于其双亲结点的层数加1。双亲在同一层的结点互为堂兄弟。树中结点的最层大数称为树的高度<Height>或深度<Depth>。若将树中每个结点的各子树看成是从左到右有次序的<即不能互换>,则称该树为有序树<OrderedTree>；否则称为无序树<UnoderedTree>。若不特别指明,一般讨论的树都是有序树。森林<Forest>是m<m≥0>棵互不相交的树的集合。树和森林的概念相近。删去一棵树的根,就得到一个森林；反之,加上一个结点作树根,森林就变为一棵树。3.二叉树与度数为2的有序树不同：在有序树中,虽然一个结点的孩子之间是有左右次序的,但是若该结点只有一个孩子,就无须区分其左右次序。而在二叉树中,即使是一个孩子也有左右之分。二叉树的性质：性质1二叉树第i层上的结点数目最多为2i-1<i≥1>。例如5层的二叉树,第5层上的结点数目最多为24=16性质2深度为k的二叉树至多有2k-1个结点<k≥1>。例如深度为5的二叉树,至多有25-1=31个结点性质3在任意-棵二叉树中,若终端结点的个数为n,度为2的结点数为n,则n=n+1。例如一棵深度为4的二叉树〔a,02o2其终端结点数n为8,度为2的结点树为7,则8=7+1,n=n+1成立0o2〔b其终端结点数n为6,度为2的结点树为5,则6=5+1,n=n+1成立0o2满二叉树：一棵深度为k且有2k-1个结点的二又树称为满二叉树。满二叉树的特点：〔1每一层上的结点数都达到最值大。即对给定的高度,它是具有最多结点数的二叉树。〔2满二叉树中不存在度数为1的结点,每个分支结点均有两棵高度相同的子树,且树叶都在最下一层上。完全二叉树：若一棵深度为k的二叉树,其前k-1层是一棵满二叉树,而最下面一层上的结点都集中在该层最左边的若干位置上,则此二叉树称为完全二叉树。特点：〔1满二叉树是完全二叉树,完全二叉树不一定是满二叉树。〔2在满二叉树的最下一层上,从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。〔3在完全二叉树中,若某个结点没有左孩子,则它一定没有右孩子,即该结点必是叶结点。性质4具有n个结点的完全二叉树的深度为。⌊logn⌋+1或⌈log<n+1>⌉例,具有100个结点的完全二叉树的深度为:⌊lg100⌋+1=7,26=6427=128所以⌊lg100⌋=6,⌈lg<100+1>⌉=74.完全二叉树的编号特点：完全二叉树中除最下面一层外,各层都充满了结点。每一层的结点个数恰好是上一层结点个数的2倍。从一个结点的编号就可推得其双亲,左、右孩子等结点的编号。编号从0开始①若i=0,则q为根结点,无双亲；否则,q的双亲i编号为⌊<i-1>/2⌋。②若2i+1<n,则q的左孩子的编号是2i+1；否则,q无左孩子,即q必定是叶子。iii-7-/13i

i对于完全二叉树而言,使用顺序存储结构既简单又节省存储空间。但对于一般二叉树来说,采用顺序存储时,为了使用结点在数组中的相对位置来表示结点之间的逻辑关系,就必须增加一些虚结点使其成为完全二叉树的形式。5.链式存储结构:二叉树的每个结点最多有两个孩子。用链接方式存储二叉树时,每个结点除了存储结点本身的数据b、按完全二叉树的层次顺序建立结点。具有n个结点的二叉链表中,共有2n个指针域。其中有n-1个用来指示结点的左、右孩子,其余的n+1个为空。二叉树遍历算法中的递归终止条件是二叉树为空。递归工作栈中包括两项：一项是递归调用的语句编号,另一项则是指向根结点的指针。已知一棵二叉树的前序和中序遍历序列或中序和后序遍历序列,可唯一确定一棵二叉树。具体方法如下：首先根据前序或后序遍历序列确定二叉树的各子树的的根,然后根据中序遍历序列确定各子树根的左右子树。6.线索二叉树：n个结点的二叉链表必定存在n+1个空指针域,可以利用这些空指针域,存放指向结点在某种遍历次序下的前趋和后继结点的指针,这种指向前驱和后继结点的指针称为"线索",这种加上线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树<ThreadedBinaryTree>。其中:ltag和rtag是增加的两个标志域,用来区分结点的左、右指针域是指向其左、右孩子的指针,还是指向其前趋或后继的线索。图中的实线表示指针,虚线表示线索。线索二叉树中,一个结点是叶结点的充要条件为：7.二叉树的线索化:把对一棵二叉线索链表结构中所有结点的空指针域按照某种遍历次序加线索的过程称为线索化。和中序遍历算法一样,递归过程中对每结点仅做一次访问。因此对于n个结点的二叉树,线索化的算法时间复杂度为O<n>。8.树、森林到二叉树的转换：树中每个结点最多只有一个最左边的孩子<长子>和一个右邻的兄弟。将树转换成二叉树：①在所有兄弟结点之间加一道连线；②对每个结点,除了保留与其长子的连线外,去掉该结点与其它孩子的连线。由于树根没有兄弟,故树转化为二叉树后,二叉树的根结点的右子树必为空。将森林中的每棵树转化成二叉树,然后再将二叉树的根节点看做兄弟连在一起,形成一棵二叉树方式是：若二叉树中结点x是双亲y的左孩子,则把x的右孩子,右孩子的右孩子,…,都与y用连线连起来,最后去掉所有双亲到右孩子的连线。.10.树的存储结构：〔1双亲链表表示法的实现注意：或祖先<包括根>；求指定结点的孩子或其它空间的序号。涉及孩子及其子孙的运算,但不便于实现与双亲有关的运算。别指向该结点最左孩子和右邻兄弟的指针域,即可树得的孩子兄弟链表表示。注意：这种存储结构的最大优点是：它和二叉树的二叉链完全一样。可利用二叉树的算法来实现对树的操作。11.树的一般都只给出两种次序遍历树的方法：前序<先根次序>遍历和后序<后根次序>遍历。①前序遍历一棵树②后序遍历一棵树等价于中序遍历该树对应的对下面<a>图中所示的序遍历和后序遍历,则得到该森林的前序序列和后序序列分别为ABCDEFIGJH和而<b>图所示二叉树的前序序列和中序序列也分别为ABCDEFIGJH和BDCAIFJGHE。①前序遍历森林等同于前序遍历该森林对应的二叉树②后序遍历森林等同于中序遍历该森林对应的二叉树12.从根结点到某结点之间的路径长度与该结点上权的乘积称为该结点的径长度之和称为树的带权路径长度。带权路径长度WPL最小的二叉树称为哈夫曼树或最优二叉树。哈夫曼树不一定是二叉树。哈夫曼树又称为最优树,是一类带权路径长度最短的树。二叉树。带权路径长度,树种所有叶子结点的带权路完全二叉树就是这种路径长度最短的二叉树。①只有叶结点上的权值均相同时,完全二叉树一定是最优二叉树,否则完全二叉树不一定是最优二叉树。②最优二叉树中,权越大的叶子离根越近。③最优二叉树的形态不唯一,WPL最小。13.哈夫曼算法:注意：①初始森林中的n棵二叉树,每棵树有一个孤立的结点,它们既是根,又是叶子②n个叶子的哈夫曼树要经过n-1次合并,产生n-1个新结点。最终求的得哈夫曼树中共有2n-1个结点。③哈夫曼树是严格的二叉树,没有度数为1的分支结点。14.哈夫曼编码：数据压缩过程称为编码,反之,解压缩的过程称为解码。设计一种长短不等的编码,则必须保证任一字符的编码都不是另一个字符编码的前缀,这种编码称为前缀编码。可以利用支字符组成的串作为该叶节点的字符编码。因此设计电文总长最短的二进制前缀编码,就是以n种字符出现的的编码就是哈夫曼编码。译码过程是从树根结点出发,逐个读入电文中的-9-/13二叉树来设计二进制的前缀编码,其左分支表示字符0,右分支表示字符1,则以根结点到叶结点路径上的分频率作为权构造一棵哈夫曼树,由哈夫曼树求得二进制码。.第六章1.图G由两个集合构成,顶点集合和边集合,也可以图G只有顶点而没有边。用尖括号表示图的有向边<v,v>,有向边ji又称为弧,起点称为弧尾,终点称为弧头。无向图的顶点对用圆括号表示<v,v>。ij在无向图中,称v和v相邻接,在有向图中称顶点v邻接到v,顶点v邻接于vijijji在无向图中,n的取值范围是0-n<n-1>/2,将具有n<n-1>/2条边的无向图称为无向完全图。在有向图中,n的取值范围是0-n<n-1>,将具有n<n-1>条边的有向图称为有向完全图。无向图中,顶点的度定义为以该顶点为一个端点的边的数目,有向图的度等于出度和入度之和。在无向图中,任意两顶点都有路径,则称两顶点连通。若图G中的任意两个顶点都连通,称G为连通图。无向图的极XX通子图称为连通分量,显然,任何连通图的连通分量只有一个,即其自身,而非连通的无向图有多个连通分量。在有向图中,图G中任意两顶点连通,称为强连通图,极XX通子图称为强连通分量。若在一个图的每条边上标上某种数值,该数值称为该边的权。边上带权的图称为带权图,带权的连通图称为网络。2.图的存储结构：邻接矩阵和邻接表表示法。图的顶点编号从0开始。邻接矩阵表示法：<v,v>或<v,v>是边,则值为1,不是边则值为0。iijj无向图的邻接矩阵是按主对角线对称的。若G是带权图,只要把1换成相应边上的权值即可,0的位置上可以不动或将其换成无穷表大示。无向图的邻接矩阵表示法可以仅存储主对角线以下的元素,时间复杂度为O<n2>邻接表表示法：邻接表是图的一种链式存储结构。将无向图的邻接表称为边表,将有向图的邻接表称为出边表,将邻接表的表头向量称为顶点表。若无向图有n个顶点和e条边,则它的邻接表共有n个头结点和2e个表结点。建立邻接表的时间复杂度是O<n+e>。图的邻接表表示不是唯一的,这是因为在每个顶点的邻接表中,各边结点的链接次序可以是任意的,其具体链接次序与边的输入次序和生成算法有关。3.图的遍历：遍历图的算法是求解图的连通性、图的拓扑排序等算法的基础。图的遍历常用的是深度优先搜索遍历和广度优先搜索遍历两种方法。深度优先搜索遍历<DFS>类似于前序<先根>遍历。按访问顶点的先后次序得到的顶点序列称为图的深度优先遍历序列,或简称为DFS序列。共需要搜索n2个矩阵元素,时间复杂广度优先搜索遍历<BFS>类似于树的按层次遍历,先被访问的顶点,其邻接点也先被访问,就是先进先出。度为邻接矩阵O<n2>或邻接表O<n+e>,空间复杂度都是O<n>。度为邻接矩阵O<n2>或邻接表O<n+e>。时间复杂4.生成树是连通图的包含图中所有顶点的一个极小连通子图,一个图的极小连通子图恰为一个无回路的连通图,也就是说,若图中任意添加一条边,就会出现回路,若去掉任意一条边,都会使之成为非连通图。因此,一个具有n个顶点的生成树有且仅有n-1条边,但有n-1条边的图不一定是生成树,同一个图可以有不同的生成树。生成树定义为：若从图的某顶点出发,可以系统的访问到图的所有顶点,则遍历时经过的边和图的所有顶点所构成的子图,称为该图的生成树。最小生成树：图的生成树不唯一,把权值最小的生成树称为最小生成树〔MST。构造最小生成树的算法：普里姆Prim算法的时间复杂度为O〔n2与网中边数无关适于稠密图。克鲁斯卡尔Kruskal算法的时间复杂度为O〔eloge,主要取决于边数,较适合于稀疏图。5.最短路径：Dijkstra迪杰斯特拉算法,提出了按路径长度递增的顺序产生诸顶点的最短路径算法。拓扑排序：子工程称为活动,顶点代表活动,有向边代表活动的先后关系。这样的有向无环图DAG称为顶点活动网,简称为AOV网。将有向无环图G中所有顶点排成一个线性序列,若<u,v>∈E〔G,则在线性序列u在v之前,这种线性序列称为拓扑序列。由AOV网构造拓扑序列的过程称为拓扑排序。检测的方法是：对有向图构造其顶点的拓扑序列,若网中所有顶点都在他的拓扑序列中,则AOV网必定不存在环。AOV网的拓扑序列不是唯一的。拓扑排序的描述思想：a、在有向图中选一个没有前趋<入度为零>的顶点,且输出之。b、从有向图中删除该顶点及其与该顶点有关的所有边。c、重复上述步骤,直到全部顶点都已输出或图中剩余的顶点中没有前趋顶点为止。d、输出剩余的无前趋结点。拓扑排序实际上是对邻接表表示的图G进行遍历的过程。时间复杂度是O<n+e>。第七章排序1.如果待排序文件中存在多个关键字相同的记录,经过排序后,这些具有相同关键字的记录之间的相对次序保持不变,该排序方法是稳定的；反之,则是不稳定的。排序在内存中处理,不涉及数据的内外存交换,称为内部排序,反之为外部排序。内部排序又分为五类：插入、选择、-10-/13

.交换、归并和分配排序。在排序过程中需进行两种操作：比较两个关键字的大小、改变指向记录的指针或移动记录本身,而待排序记录的存储形式一般有三种：顺序结构、链式结构和辅助表。评价排序算法的标准：执行算法需要的时间,以及算法所需要的附加空间。还有算法本身的复杂度。排序的时间开销,一般情况下可用算法中关键字的比较次数和记录的移动次数来衡量。2.插入排序：每次将一个待排序记录按其关键字大小插入到前面已排好序的文件中的适当位置。直接插入排序：每次从无序区取出第一个元素把它插入到有序区的适当位置,使之成为新的有序区,经过n-1次插入后完成。算法中R[0]作用：保存R[i]副本,监视数组下标变量j是否越界。所以R[0]称为哨兵。每次的比较是从后往前比较的。时间复杂度最好是O<n>,最坏是O<n2>,所以是O<n2>。空间复杂度O<1>,所以是就地排序。是稳定的算法。初始情况是有序区中只有一个元素R[1],无序区中R[2..n]。希尔排序<缩小增量排序>：算法不稳定。记录的总比较次数和总移动次数都要比直接插入排序少得多,特别是当n越大越明显。希尔排序的时间依赖于增量序列,最后一个增量必须是1,尽量避免增量互为倍数的情况。3.交换排序：两两比较待排序记录的关键字,如果发现两个记录的次序相反时即进行交换,直到没有反序位置。冒泡排序<起泡排序>：通过相邻元素之间比较和交换,使较小移向顶部,从后往前两两比较。时间复杂度最好是O<n>,最坏是O<n2>,所以是O<n2>。是稳定的排序算法。快速排序<划分交换排序>：是冒泡排序的改进。比较和交换从两端向中间进行。一趟快速排序步骤：设两个指针i和j,初值分别为low和high,基准为x=R[i],首先从j位置开始向前搜索第一个小于基准x.key的记录存入i所指位置上,i自增1,然后从i所指位置向后搜索找到第一个大于基准x.key的记录存入j所指位置上,j自减1,重复直至i=j为止。快速排序是不稳定的。有非常好的时间复杂度,优于其他各种排序算法,O<nlogn>,但是当记录关键字有序或基本有2序时复杂度反而大了使之转变成冒泡排序为O<n2>。快速排序是递归的,需要一个栈空间,空间复杂度O<logn>。24.选择排序：每一趟在待排序的记录中选出关键字最小的记录,依次存放在已排序好的记录序列的最后。直接选择排序：初始时,R[1..n]为无序区,R[1]为空；第一趟是在R[1..n]中选出最小的记录与R[1]交换,R[1]为有序区；第二趟是在R[2..n]中选出最小的记录与R[2]交换,R[1..2]为有序区。时间复杂度O<n2>,是不稳定的。初始情况是有序区为空,无序区中R[1..n],第一趟从R[1..n]选择最小记录与R[1]交换。堆排序：是对直接选择排序的改进,是一种树形选择排序。基本思想：在排序过程中,将记录数组R[1..n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系,在当前无序区中选择关键字最大或最小记录。每一趟排序：将当前无序区调整为一个大根堆,选取关键字最大的堆顶记录,将他和无序区中最后一个记录交换。堆排序是一个不断建堆的过程。构造堆的过程：R[1]作为二叉树的根,R[2..n]依次逐层从左到右顺序排列,构成一棵完全二叉树,任意结点R[i]的左孩子是R[2i],右孩子是R[2i+1],双亲是R⌊i/2⌋,此称为筛选法。从⌊n/2⌋开始。每一趟的时间复杂度是O<logn>,整个堆排序的时间复杂度是O<nlogn>。225.归并排序：首先将待排序文件看成n个长度为1的有序子文件,把这些子文件两两归并,得到⌈n/2⌉个长度为2的有序子文件,然后再将他们两两归并,如此反复,直到得到一个长度为n的有序文件,此称为二路归并排序。每一趟归并排序的时间复杂度是O<n>,所以总的时间复杂度是O<nlogn>。26.分配排序：前面方法都至少需要进行⌈nlogn⌉次比较,而分配排序将时间复杂度降为O<n>。箱排序<桶排序>：基数排序：是对箱排序的改进和推广。箱排序只适用于关键字取值范围较小的情况,否则所需箱子数目太多。每个分量可能取值的个数rd称为基数,基数的选择和关键字的分解因关键字的类型而异。d趟箱排序。基数排序中,没有进行关键字的比较和记录的移动,而只是扫描链表和进行指针赋值,所以排序的时间主要用在修改指针上,初始化链表时间为O<n>。7.内部排序方法分析比较：本章除基数排序外,都是在顺序表上实现的。时间复杂度空间复杂度稳定性直接插入O<n2>O<1>O<1>稳定不稳定稳定插入希尔排序O<nlogn>或O<n1.25>2交换冒泡排序O<n2>O<1>-11-/13.O<logn>不稳定快速排序O<nlogn>2直接选择O<n2>2O<1>O<1>O<n>不稳定不稳定稳定选择堆排序O<nlogn>2归并排序归并排序O<nlogn>2基数排序O<d*<rd+n>>rd是基数,O<rd+n>稳定分配排序箱排序d是关键字位数.n是元素个数选取排序方法时需要考虑的主要因素：a、待排序的记录个数,b、记录本身的大小和存储结构,c、关键字的分布情况,d、对排序稳定性的要求,e、时间和空间复杂度要等排序方法的选取：a、若待排序的一组记录数目n较小<如n≤50>时,可采用插入排序或选择排序；b、n较大时,则应采用快速排序、或冒泡排序；d、当n很大,而且无关的排序方法是选择排序。,可采用链式存储结构。索引表进行排序。堆排序或归并排序；c、若待排序记录按关键字基本有序时,则宜选用直接插入排序关键字位数较少时,采用链式基数排序较好；e、关键字比较次数与记录的初始排列顺序一般的排序方法都可以在顺序结构上实现,当记录本身信息量较大时插入、归并、基数排序易于在链表上实现；快速排序和堆排序可以提取关键字建立索引表,然后对第八章：查找1.查找又称检索,是数运算查找的主要操作是关键字的比较,因劣的标准。2.顺序表的查：找顺序查和找二分查找顺序查找又称线性查：找查找成功的平均查找长度<n+1>/2,即约为表长的一半。如果查找成功和不成功机会相等,那么平均查找长度3<n+1>/4。优点是简单,对表的结构无任何要求,无论是顺序存储和链式存储、无论是否有序,都同样适用,缺点是效率低。对于有序表来说,该算法的平均查找长度是<n+1>/2。二分查找<折半查找>：要求查对找象的线性表必须是顺序存储结构的有序表。查找过程是递归的。每个子树的根节点对应当前查找区间的中位记录R[mid],它的左子树和右子树分别对应区间的左子表和右子表,通常树称为二叉判定树。由于二分查是找在有序表上进行的,所以其对应的判定树必定是一棵二叉排序树。二叉判定树一定是二叉排序树,二叉排序树又称为二叉查找树。从判定树上可见,关键字较的次数最多不超过据处理中经常使用的一种重要运算。查找也分为内查和找外查。找此把查找过程中的平均比较次数<也称为平均查找长度>作为衡量算法效率优树中将此比较的次数恰好为该结点在树中的层数。因此,二分查找算法在查找成功时进行关键字比判定树的深度。查找成功时的平均查找长度<n+1>/nlog<n+1>-1,当n很大时,可近似用2log<n+1>-1表示。因为判定树度数小于2的结点只可能在最下面的两层,所以n个结2的完全二叉树的深度相同,即为点的判定树的深度和n个结点⌈log<n+1>⌉。可见,二分查的找最坏性能和平均性能相当接近。2二叉判定树的输出：每次以⌊<low+high>/2⌋为根建树。3.索引顺序查找<分块查找>：是一种介于顺序查和找二分查找之间的查方找法。要求分块有序,前一块的最大关键字小于后一块的最小关键字,抽取各块中的最大关键字及其起始位置构成索引表。分块查的找基本思想是：首先查索找引表,可用二分查或找顺序查找,然后在确定的块中进行顺序查。找平均查找长度：二分查找log<n/s+1>+s/2,顺序查找<s2+2s+n>/2s。4.三种查方找法比较顺序查找缺点是n较大时,查找成功约为<n+1>/2,失败需要比较n+1次。二分查找成功时约为log<n+1>-1,但是他要求表以顺序存储且按关键字有序,适用于表不易变动且又经常查找的2情况。块查找的优点是,在表中插入或删除一个记录时,只要找到该记录所属的块,就可以在该块内进行插入或删除操作,因为块内记录是无序的,所以插入或删除比较容易,无需移动大量记录。主要缺点是需要增加一个辅助数组的存储将初始表块排序的运算,它也不适用于链式存储结构。上述三种查的找时间复杂度分别是O<n>、O<logn>和O<n的平方根>5.二叉排序树<二叉查找树>：或者是一于根节点的值。b、若左子树非空,则左子树上所有结分空间和2棵空树,或者具有下面性质：a、若右子树非空,则右子树上所有结点的值均大点的