河海大学算法与数据结构考研笔记.pdf

第一章概论1.数据：信息的载体，能被计算机识别、存储和加工处理。2.数据元素：数据的基本单位，可由若干个数据项组成，数据项是具有独立含义的最小标识单位。3.数据结构：数据之间的相互关系，即数据的组织形式。它包括：1）数据的逻辑结构，从逻辑关系上描述数据，与数据存储无关，独立于计算机；2）数据的存储结构，是逻辑结构用计算机语言的实现，依赖于计算机语言。3）数据的运算，定义在逻辑结构上，每种逻辑结构都有一个运算集合。常用的运算：检索/插 入/删除/更新/排序。4.数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的存储结构是逻辑结构用计 算机语言的实现。5.数据类型：一个值的集合及在值上定义的一组操作的总称。分为：原子类型和结构类型。6.抽象数据类型：抽象数据的组织和与之相关的操作。优点：将数据和操作封装在一起实现了信 息隐藏。7.抽象数据类型ADT：是在概念层上描述问题；类：是在实现层上描述问题；在应用层上操作 对象（类的实例）解决问题。8.数据的逻辑结构，简称为数据结构，有：（1）线性结构，若结构是非空集则仅有一个开始和终端结点，并且所有结点最多只有一个直接 前趋和后继。（2）非线性结构，一个结点可能有多个直接前趋和后继。9.数据的存储结构有：1）顺序存储，把逻辑相邻的结点存储在物理上相邻的存储单元内。2）链接存储，结点间的逻辑关系由附加指针字段表示。3）索引存储，存储结点信息的同时，建立附加索引表，有稠密索引和稀疏索引。4）散列存储，按结点的关键字直接计算出存储地址。10.评价算法的好坏是：算法是正确的；执行算法所耗的时间；执行算法的存储空间（辅助存储 空间）；易于理解、编码、调试。11.算法的时间复杂度T(n)：是该算法的时间耗费，是求解问题规模n的函数。记为0(n)。时间复杂度按数量级递增排列依次为：常数阶0(1)、对数阶O(log2n)、线性阶0(n)、线性对 数阶O(nlog2n).平方阶0(22)、立方阶0(23)k次方阶0(n人k)、指数阶0(2八n)。13.算法的空间复杂度S(n)：是该算法的空间耗费，是求解问题规模n的函数。12.算法衡量：是用时间复杂度和空间复杂度来衡量的，它们合称算法的复杂度。13.算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。第二章线性表1.线性表：是由n(r)20)个数据元素组成的有限序列。2.线性表的基本运算有：1)InitList(L),构造空表，即表的初始化；2)ListLength(L),求表的结点个数，即表长；3)GetN ode(Lj),取表中第 i 个结点,要求 iWiWListLength(L)；4)LocateN ode(L,x)查找L中值为x的结点并返回结点在L中的位置，有多个x则返回首个,没有则返回特殊值表示查找失败。5)InsertList(L,x,i)在表的第i个位置插入值为x的新结点,要求liListLength(L)+l；6)DeleteList(LJ)删除表的第i个位置的结点，要求lWiWListLength(L)；3.顺序表：把线性表的结点按逻辑次序存放在一组地址连续的存储单元里。4.顺序表结点的存储地址计算公式：Loc(ai)=Loc(al)+(i-l)*C；lin5.顺序表上的基本运算(1)插入void insertlist(seqlist*L,datatype x,int i)int j;if(iL-length+l)error(position error);if(L-length =listsize)error(overflow,/);for(j=L-length-1;j=i-l;j-)L-dataj+l=L-dataj;结点后移L-datai-l=x;L-length+;在顺序表上插入要移动表的n/2结点，算法的平均时间复杂度为0(n)。(2)删除void delete(seqlist*L,int i)(int j;if(iL-length)error(position error);for(j=i;j length-l;j+)L-dataj-l=L-dataj;结点前移L-length;在顺序表上删除要移动表的(n+l)/2结点，算法的平均时间复杂度为0(n)。6.单链表：只有一个链域的链表称单链表。在结点中存储结点值和结点的后继结点的地址，data next data是数据域，next是指针域。(1)建立单链表。时间复杂度为0(n)。加头结点的优点：1)链表第一个位置的操作无需特殊处理；2)将空表和非空表的处理统一。(2)查找运算。时间复杂度为0(n)。1)按序号查找。Listnode*getnode(linklist head,int i)int j;listnode*p;p=head;j=0;while(p-next&jnext;指针下移J+；if(i=j)return p;elsereturn N ULL;2)按值查找。Listnode*locatenode(linklist head,datatype key)(listnode*p=head-next;while(p&p-data!=key)p=p-next;return p;(3)插入运算。时间复杂度为0(n)。Void insertlist(linklist head,datatype x,int i)listnode*p;p=getnode(head,i-l);if(p=N ULL);error(position error);s=(listnode*)malloc(sizeof(listnode);s-data=x;s-next=p-next;p-next=s;(4)删除运算。时间复杂度为0(n)。Void deletelist(linklist head,int i)(listnode*p,*r;p=getnode(head,i-l);if(p=N ULL|p-next=N ULL)error(position error);r=p-next;p-next=r-next;free(r);7.循环链表：是一种首尾相连的链表。特点是无需增加存储量，仅对表的链接方式修改使表的处 理灵活方便。8.空循环链表仅由一个自成循环的头结点表示。9.很多时候表的操作是在表的首尾位置上进行，此时头指针表示的单循环链表就显的不够方便，改用尾指针rear来表示单循环链表。用头指针表示的单循环链表查找开始结点的时间是0(1),查找尾结点的时间是0(n)；用尾指针表示的单循环链表查找开始结点和尾结点的时间都是0。10.在结点中增加一个指针域，prior|data|nexto形成的链表中有两条不同方向的链称为双链 表1)双链表的前插操作。时间复杂度为0(1)。Void dinsertbefore(dlistnode*p,datatype x)(dlistnode*s=malloc(sizeof(dlistnode);s-data=x;s-prior=p-prior;s-next=p;p-prior-next=s;p-prior=s;2)双链表的删除操作。时间复杂度为0(1)。Void ddeletenode(dlistnode*p)(p-prior-next=p-next;p-next-prior=p-prior;free(p);11.顺序表和链表的比较1)基于空间的考虑：顺序表的存储空间是静态分配的，链表的存储空间是动态分配的。顺序 表的存储密度比链表大。因此，在线性表长度变化不大，易于事先确定时，宜采用顺序表作为存 储结构。2)基于时间的考虑：顺序表是随机存取结构，若线性表的操作主要是查找，很少有插入、删 除操作时，宜用顺序表结构。对频繁进行插入、删除操作的线性表宜采用链表。若操作主要发生 在表的首尾时采用尾指针表示的单循环链表。12.存储密度=(结点数据本身所占的存储量)/(整个结点结构所占的存储总量)存储密度：顺序表=1,链表top=-l;2)判栈空。int stackempty(seqstack*s)return s-top=-l;3)判栈满。int stackfull(seqstack*s)return s-top=stacksize-l;4)进栈。Void push(seqstack*s,datatype x)if(stackfull(s)error(stack overflow);s-data+s-top=x;5)退栈。Datatype pop(seqstack*s)if(stackempty(s)error(stack underflow);return S-datas-top;6)取栈顶元素。Dtatatype stacktop(seqstack*s)if(stackempty(s)error(stack underflow);return S-datas-top;6.链栈：栈的链式存储结构称链栈。栈顶指针是链表的头指针。7.链栈上的基本运算：1)建栈。Void initstack(linkstack*s)s-top=N ULL;2)判栈空。Int stackempty(linkstack*s)return s-top=N ULL;3)进栈。Void push(linkstack*s,datatype x)(stacknode*p=(stacknode*)malloc(sizeof(stacknode);p-data=x;p-next=s-top;s-top=p;4)退栈。Datatype pop(linksatck*s)(datatype x;stacknode*p=s-top;if(stackempty(s)error(stack underflow);x=p-data;s-top=p-next;free(p);return x;5)取栈顶元素。Datatype stacktop(linkstack*s)(if(stackempty(s)error(stack is empty);return s-top-data;8.队列是一种运算受限的线性表，允许删除的一端称队首，允许插入的一端称队尾。队列又称为 先进先出线性表，FIFO表。9.队列的基本运算：1)initqueue(q),置空队；2)queueempty(q),判队空；3)queuefull(q),判队满；4)enqueue(q,x),入队；5)dequeue(q),出队；6)queuefront(q),返回队头元素。10.顺序队列：队列的顺序存储结构称顺序队列。设置front和rear指针表示队头和队尾元素 在向量空间的位置。11.顺序队列中存在假上溢现象，由于入队和出队操作使头尾指针只增不减导致被删元素的空 间无法利用，队尾指针超过向量空间的上界而不能入队。12.为克服假上溢现象，将向量空间想象为首尾相连的循环向量，存储在其中的队列称循环队 歹！J。i=(i+l)%queuesize13.循环队列的边界条件处理：由于无法用front=rear来判断队列的空和满。解决的方法有：1)另设一个布尔变量以区别队列的空和满；2)少用一个元素，在入队前测试rear在循环意义下加1是否等于front；3)使用一个记数器记录元素总数。14.循环队列的基本运算：1)置队空。Void initqueue(cirqueue*q)(q-front=q-rear=0;q-count=0;2)判队空。Int queueempty(cirqueue*q)return q-count=0;3)判队满。Int queuefull(cirqueue*q)return q-count=queuesize;4)入队。Void enqueue(cirqueue*q,datatype x)(if(queuefull(q)error。queue overfolw,r);q-count+;q-data q-rear=x;q-rear=(q-rear+l)%queuesize;5)出队。Datatype dequeue(cirqueue*q)(datatype temp;if(queueempty(q)error(queue underflow);temp=q-dataq-front;q-count;q-front=(q-front+l)%queuesize;return temp;6)取队头元素。Datatype queuefront(cirqueue*q)if(queueempty(q)error(queue is empty);return q-dataq-front;15.链队列：队列的链式存储结构称链队列，链队列由一个头指针和一个尾指针唯一确定。16.链队列的基本运算：1)建空队。Void initqueue(linkqueue*q)(q-front=q-rear=N ULL;2)判队空。Int queueempty(linkqueue*q)return q-front=N ULL&q-rear=N ULL;3)入队。Void enqueue(linkqueue*q,datatype x)queuenode*p=(queuenode*)malloc(sizeof(queuenode);p-data=x;p-next=N ULL;if(queueempty(q)q-front=q-rear=p;elseq-rear-next=p;q-rear=p;4)出队。Datatype dequeue(linkqueue*q)datatype x;queuenode*p;if(queueempty(q)error(queue is underflow);p=q-front;x=p-data;q-front=p-next;if(q-rear=p)q-rear=N ULL;free(p);return x;5)取队头元素。Datatype queuefront(linkqueue*q)(if(queueempty(q)error(queue is empty);return q-front-data;第四章串1.串：是由零个或多个字符组成的有限序列；包含字符的个数称串的长度；2.空串：长度为零的串称空串；空白串：由一个或多个空格组成的串称空白串；子串：串中任意个连续字符组成的子序列称该串的子串；主串：包含子串的串称主串;子串的首字符在主串中首次出现的位置定义为子串在主串中的位置；3.空串是任意串的子串；任意串是自身的子串；串常量在程序中只能引用但不能改变其值；串变量取值可以改变；4.串的基本运算1)int strlen(char*s);求串长。2)char*strcpy(char*to,char*from);串复制。3)char*strcat(char*to,char*from);串联接。4)int strcmp(char*sl,char*s2);串比较。5)char*strchr(char*s,char c);字符定位。5.串的存储结构：(1)串的顺序存储：串的顺序存储结构称顺序串。按存储分配不同分为：1)静态存储分配的顺序串：直接用定长的字符数组定义，以、0表示串值终结。#define maxstrsize 256typedef char seqstringmaxstrsize;seqstring s;不设终结符，用串长表示。Typedef structChar chmaxstrsize;Int length;seqstring;以上方式的缺点是：串值空间大小是静态的，难以适应插入、链接等操作。2)动态存储分配的顺序串：简单定义：typedef char*string;复杂定义：typedef structchar*ch;int length;hstring;(2)串的链式存储：串的链式存储结构称链串。链串由头指针唯一确定。类型定义:typedef struct nodechar data;struct node*next;linkstrnode;typedef linkstrnode*linkstring;linkstring s;将结点数据域存放的字符个数定义为结点的大小。结点大小不为1的链串类型定义：#define nodesize 80typedef struct nodechar datanodesize;struct node*next;linkstrnode;6.串运算的实现(1)顺序串上的子串定位运算。1)子串定位运算又称串的模式匹配或串匹配。主串称目标串；子串称模式串。2)朴素的串匹配算法。时间复杂度为O(n八2)。比较的字符总次数为(n-m+1)m。Int naivestrmatch(seqstring t,seqstring p)(intint m=p.length;int n=t.length;for(i=0;i=n-m;i+)j=O;k=i;while(jdata=p-data)t=t-next;p=p-next;elseshift=shift-next;t=shift;P=P；if(p=N ULL)return shift;elsereturn N ULL;第五章多维数组和广义表1.多维数组：一般用顺序存储的方式表示数组。2.常用方式有：1)行优先顺序，将数组元素按行向量排列；2)列优先顺序，将数组元素按列向量排列。3.计算地址的函数：LOC(Aij)=LOC(Aclc2)+(i-cl)*(d2-c2+l)+j-c2)*d4.矩阵的压缩存储：为多个非零元素分配一个存储空间；对零元素不分配存储空间。(1)对称矩阵：在一个n阶的方阵A中，元素满足Aij=Aji 0=i,j(k-l)/2以行优先顺序存放的Aij与SAk的关系：k=2i+j;5.稀疏矩阵：当矩阵A中有非零元素S个，且S远小于元素总数时，称为稀疏矩阵。对其压缩的方法有顺序存储和链式存储。(1)三元组表：将表示稀疏矩阵的非零元素的三元组(行号、列号、值)按行或列优先的顺序 排列得到的一个结点均是三元组的线性表，将该表的线性存储结构称为三元组表。其类型定义：#define maxsize 10000typedef int datatype;typedef structint ij;datatype v;trituplenode;typedef structtrituplenode datamaxsize;int m,n,t;tritupletable;(2)带行表的三元组表：在按行优先存储的三元组表中加入一个行表记录每行的非零元素在三 元组表中的起始位置。类型定义：#define maxrow 100 typedef structtritulpenode datamaxsize;int rowtabmaxrow;int m,n,t;rtritulpetable;6.广义表：是线性表的推广，广义表是n个元素的有限序列，元素可以是原子或一个广义表，记为LSo7.若元素是广义表称它为LS的子表。若广义表非空，则第一个元素称表头，其余元素称表尾。8.表的深度是指表展开后所含括号的层数。9.把与树对应的广义表称为纯表，它限制了表中成分的共享和递归；10.允许结点共享的表称为再入表；11.允许递归的表称为递归表；12.相互关系：线性表纯表再入表递归表；13.广义表的特殊运算：1）取表头head（LS）；2）取表尾tail（LS）;第六章树1.树：是n个结点的有限集T,T为空时称空树，否则满足：1）有且仅有一个特定的称为根的结点；2）其余结点可分为m个互不相交的子集，每个子集本身是一棵树，并称为根的子树。2.树的表示方法：1）树形表示法；2）嵌套集合表示法；3）凹入表表示法；4）广义表表示法;3.一个结点拥有的子树数称为该结点的度；一棵树的度是指树中结点最大的度数。4.度为零的结点称叶子或终端结点；度不为零的结点称分支结点或非终端结点5.根结点称开始结点，根结点外的分支结点称内部结点；6.树中某结点的子树根称该结点的孩子；该结点称为孩子的双亲；7.树中存在一个结点序列KI,K2,.Kn,使Ki为Ki+1的双亲，则称该结点序列为K1到Kn 的路径或道路；8.树中结点K到Ks间存在一条路径，则称K是Ks的祖先，Ks是K的子孙；9.结点的层数从根算起，若根的层数为1,则其余结点层数是其双亲结点层数加1；双亲在同一 层的结点互为堂兄弟；树中结点最大层数称为树的高度或深度；10.树中每个结点的各个子树从左到右有次序的称有序树，否则称无序树；11.森林是m棵互不相交的树的集合。12.二叉树：是n个结点的有限集，它或为空集，或由一个根结点及两棵互不相交的、分别称为 该根的左子树和右子树的二叉树组成。13.二叉树不是树的特殊情况，这是两种不同的数据结构；它与无序树和度为2的有序树不同。14.二叉树的性质：1）二叉树第i层上的结点数最多为2八（i-1）；2）深度为k的二叉树至多有2人k-1个结点；3）在任意二叉树中，叶子数为n0,度为2的结点数为r）2,则n0=n2+l；15.满二叉树是一棵深度为k的且有2人k-1个结点的二叉树；16.完全二叉树是至多在最下两层上结点的度数可以小于2,并且最下层的结点集中在该层最左 的位置的二叉树；17.具有N个结点的完全二叉树的深度为log2N取整加1；18.二叉树的存储结构（1）顺序存储结构：把一棵有n个结点的完全二叉树，从树根起自上而下、从左到右对所有结 点编号，然后依次存储在一个向量bOn中，bln存放结点，b0存放结点总数。各个结点编号间的关系：1）i=l是根结点；il则双亲结点是i/2取整；2）左孩子是2i,右孩子是2i+l；（要小于n）3）i（n/2取整）的结点是叶子；4）奇数没有右兄弟，左兄弟是i-1；5）偶数没有左兄弟，右兄弟是i+1；（2）链式存储结构结点的结构为：lchild|data|rchild；相应的类型说明：typedef char data;typedef struct nodedatatype data;structnode*lchild,*rchild;bintnode;typedef bintnode*bintree;19.在二叉树中所有类型为bintnode的结点和一个指向开始结点的bintree类型的头指针构成 二叉树的链式存储结构称二叉链表。20.二叉链表由根指针唯一确定。在n个结点的二叉链表中有2n个指针域，其中n+1个为空。21.二叉树的遍历方式有：前序遍历、中序遍历、后序遍历。时间复杂度为0(n)。22.线索二叉树：利用二叉链表中的n+1个空指针域存放指向某种遍历次序下的前趋和后继结 点的指针，这种指针称线索。加线索的二叉链表称线索链表。相应二叉树称线索二叉树。23.线索链表结点结构：lchild|ltag|data|rtag|rchild；ltag=O,lchild是指向左孩子的指针；I tag=l,lchild是指向前趋的线索；rtag=O,rchild是指向右孩子的指针；rtag=l,rchild是指向 后继的线索；24.查找*p在指定次序下的前趋和后继结点。算法的时间复杂度为0(h)。线索对查找前序前趋 和后序后继帮助不大。25.遍历线索二叉树。时间复杂度为0(n)。26.树、森林与二叉树的转换(1)树、森林与二叉树的转换1)树与二叉树的转换：1所有兄弟间连线；2保留与长子的连线，去除其它连线。该二叉树 的根结点的右子树必为空。2)森林与二叉树的转换：1将所有树转换成二叉树；2将所有树根连线。(2)二叉树与树、森林的转换。是以上的逆过程。27.树的存储结构(1)双亲链表表示法：为每个结点设置一个parent指针，就可唯一表示任何一棵树。Data|parent(2)孩子链表表示法：为每个结点设置一个firstchild指针，指向孩子链表头指针，链表中存 放孩子结点序号。Data|firstchild。(3双亲孩子链表表示法：将以上方法结合。Data|parent!firstchild(4)孩子兄弟链表表示法：附加两个指向左孩子和右兄弟的指针。Leftmostchild|data|right sibling28.树和森林的遍历：前序遍历一棵树等价于前序遍历对应二叉树；后序遍历等价于中序遍历对 应二叉树。29.最优二叉树(哈夫曼树)：树的路径长度是从树根到每一结点的路径长度之和。将树中的结 点赋予实数称为结点的权。30.结点的带权路径是该结点的路径长度与权的乘积。树的带权路径长度又称树的代价，是所有 叶子的带权路径长度之和。31.带权路径长度最小的二叉树称最优二叉树(哈夫曼树)。32.具有2n-l个结点其中有n个叶子，并且没有度为1的分支结点的树称为严格二叉树。33.哈夫曼编码34.对字符集编码时，要求字符集中任一字符的编码都不是其它字符的编码前缀，这种编码称前 缀码。35.字符出现频度与码长乘积之和称文件总长；字符出现概率与码长乘积之和称平均码长；36.使文件总长或平均码长最小的前缀码称最优前缀码37.利用哈夫曼树求最优前缀码，左为0,右为1。编码平均码长最小；没有叶子是其它叶子的 祖先，不可能出现重复前缀。第七章图1.图：图G是由顶点集V和边集E组成，顶点集是有穷非空集，边集是有穷集；2.G中每条边都有方向称有向图；有向边称弧；边的始点称弧尾；边的终点称弧头；G中每条 边都没有方向的称无向图。3.顶点n与边数e的关系：无向图的边数e介于0n(n-l)/2之间，有n(n-l)/2条边的称无 向完全图；有向图的边数e介于0n(n-l)之间，有n(n-l)条边的称有向完全图；4.无向图中顶点的度是关联与顶点的边数；有向图中顶点的度是入度与出度的和。所有图均满足：所有顶点的度数和的一半为边数。5.图G(V,E),如V是V的子集，E是E的子集，且E中关联的顶点均在V中，则G(V,E)是G的子图。6.在有向图中，从顶点出发都有路径到达其它顶点的图称有根图；7.在无向图中，任意两个顶点都有路径连通称连通图；极大连通子图称连通分量；8.在有向图中，任意顺序两个顶点都有路径连通称强连通图；极大连通子图称强连通分量；9.将图中每条边赋上权，则称带权图为网络。10.图的存储结构：(1)邻接矩阵表示法：邻接矩阵是表示顶点间相邻关系的矩阵。n个顶点就是n阶方阵。无向图是对称矩阵；有向图行是出度，列是入度。(2)邻接表表示法：对图中所有顶点，把与该顶点相邻接的顶点组成一个单链表，称为邻接表，adjvex|next,如要保存顶点信息加入data；对所有顶点设立头结点，vertex|firstedge,并顺 序存储在一个向量中；vertex保存顶点信息，firstedge保存邻接表头指针。11.邻接矩阵表示法与邻接表表示法的比较：1)邻接矩阵是唯一的，邻接表不唯一；2)存储稀疏图用邻接表，存储稠密图用邻接矩阵；3)求无向图顶点的度都容易，求有向图顶点的度邻接矩阵较方便；4)判断是否是图中的边，邻接矩阵容易，邻接表最坏时间为O(n)；5)求边数e,邻接矩阵耗时为O(n人2),与e无关，邻接表的耗时为O(e+n)；12.图的遍历：(1)图的深度优先遍历：类似与树的前序遍历。按访问顶点次序得到的序列称DFS序列。对邻接表表示的图深度遍历称DFS,时间复杂度为O(n+e);对邻接矩阵表示的图深度遍历称 DFSM,时间复杂度为O(n人2);(2)图的广度优先遍历：类似与树的层次遍历。按访问顶点次序得到的序列称BFS序列。对邻接表表示的图广度遍历称BFS,时间复杂度为O(n+e);对邻接矩阵表示的图广度遍历称B FSM,时间复杂度为O(n人2);13.将没有回路的连通图定义为树称自由树。14.生成树：连通图G的一个子图若是一棵包含G中所有顶点的树，该子图称生成树。有DFS生成树和BFS生成树，BFS生成树的高度最小。非连通图生成的是森林。15.最小生成树：将权最小的生成树称最小生成树。(是无向图的算法)（1）普里姆算法：1）确定顶点S、初始化候选边集T0n-2；formvex|tovex|lenght2）选权值最小的Ti与第1条记录交换；3）从Tl中将tovex取出替换以下记录的fromvex计算权；若权小则替换，否则不变；4）选权值最小的Ti与第2条记录交换；5）从T2中将tovex取出替换以下记录的fromvex计算权；若权小则替换，否则不变；6）重复n-1次。初始化时间是0（n）,选轻边的循环执行n-1-k次，调整轻边的循环执行n-2-k；算法的时间复杂度为O（n人2）,适合于稠密图。（2）克鲁斯卡尔算法：1）初始化确定顶点集和空边集；对原边集按权值递增顺序排序；2）取第1条边，判断边的2个顶点是不同的树，加入空边集，否则删除；3）重复e次。对边的排序时间是O（elog2e）；初始化时间为O（n）；执行时间是O（log2e）；算法的时间复杂 度为O（elog2e）,适合于稀疏图。16.路径的开始顶点称源点，路径的最后一个顶点称终点；17.单源最短路径问题：已知有向带权图，求从某个源点出发到其余各个顶点的最短路径；18.单目标最短路径问题：将图中每条边反向，转换为单源最短路径问题；19.单顶点对间最短路径问题：以分别对不同顶点转换为单源最短路径问题；20.所有顶点对间最短路径问题：分别对图中不同顶点对转换为单源最短路径问题；21.迪杰斯特拉算法：1）初始化顶点集Si,路径权集Di,前趋集Pi;2）设置Ss为真，Ds为0；3）选取D田最小的顶点加入顶点集；4）计算非顶点集中顶点的路径权集；5）重复3）n-1次。算法的时间复杂度为O（n人2）。22.拓扑排序：对一个有向无环图进行拓扑排序，是将图中所有顶点排成一个线性序列，满足弧 尾在弧头之前。这样的线性序列称拓扑序列。(1)无前趋的顶点优先：总是选择入度为0的结点输出并删除该顶点的所有边。设置各个顶点入度时间是O(n+e),设置栈或队列的时间是0(n),算法时间复杂度为O(n+e)。(2)无后继的顶点优先：总是选择出度为0的结点输出并删除该顶点的所有边。设置各个顶点出度时间是O(n+e),设置栈或队列的时间是0(n),算法时间复杂度为O(n+e)。求得的是逆拓扑序列。第八章排序1.文件：由一组记录组成，记录有若干数据项组成，唯一标识记录的数据项称关键字；2.排序是将文件按关键字的递增(减)顺序排列；3.排序文件中有相同的关键字时，若排序后相对次序保持不变的称稳定排序，否则称不稳定排序;4.在排序过程中，文件放在内存中处理不涉及数据的内、外存交换的称内排序，反之称外排序；5.排序算法的基本操作：1)比较关键字的大小；2)改变指向记录的指针或移动记录本身。6.评价排序方法的标准：1)执行时间；2)所需辅助空间，辅助空间为0(1)称就地排序；另要 注意算法的复杂程度。7.若关键字类型没有比较运算符，可事先定义宏或函数表示比较运算。8.插入排序(1)直接插入排序算法中引入监视哨R0的作用是：1)保存Ri的副本；2)简化边界条件，防止循环下标越界。关键字比较次数最大为(n+2)(n-l)/2；记录移动次数最大为(n+4)(n-l)/2；算法的最好时间是0(n)；最坏时间是0(n人2)；平均时间是0(n人2)；是一种就地的稳定的排 序；(2)希尔排序实现过程：是将直接插入排序的间隔变为d.d的取值要注意：1)最后一次必为1；2)避免d 值互为倍数；关键字比较次数最大为n人1.25；记录移动次数最大为1.6n八1.25；算法的平均时间是0(n人1.25)；是一种就地的不稳定的排序；9.交换排序(1)冒泡排序实现过程：从下到上相邻两个比较，按小在上原则扫描一次，确定最小值，重复n-1次。关键字比较次数最小为n-1、最大为n(n-l)/2；记录移动次数最小为0,最大为3n(n-l)/2；算法的最好时间是O(n)；最坏时间是O(n人2)；平均时间是O(n八2)；是一种就地的稳定的排 序；(2)快速排序实现过程：将第一个值作为基准，设置i,j指针交替从两头与基准比较，有交换后，交换j,io i 司时确定基准，并以其为界限将序列分为两段。重复以上步骤。关键字比较次数最好为nlog2n+nC(l),最坏为n(n-l)/2；算法的最好时间是O(nlog2n)；最坏时间是O(n八2)；平均时间是O(nlog2n)；辅助空间为O(Iog2n)；是一种不稳定排序；10.选择排序(1)直接选择排序实现过程：选择序列中最小的插入第一位，在剩余的序列中重复上一步，共重复n-1次。关键字比较次数为n(n-l)/2；记录移动次数最小为0,最大为3(n-l)；算法的最好时间是O(n人2)；最坏时间是O(n八2)；平均时间是O(n人2)；是一种就地的不稳 定的排序；(2)堆排序实现过程：把序列按层次填入完全二叉树，调整位置使双亲大于或小于孩子，建立初始大根或小 根堆，调整树根与最后一个叶子的位置，排除该叶子重新调整位置。算法的最好时间是O(nlog2n)；最坏时间是O(nlog2n)；平均时间是O(nlog2n)；是一种就 地的不稳定排序；11.归并排序实现过程：将初始序列分为2个一组，最后单数轮空，对每一组排序后作为一个单元，对2个 单元排序，直到结束。算法的最好时间是O(nlog2n)；最坏时间是O(nlog2n)；平均时间是O(nlog2n)；辅助空间 为O(n)；是一种稳定排序；12.分配排序(1)箱排序实现过程：按关键字的取值范围确定箱子的个数，将序列按关键字放入箱中，输出非空箱的关键 字。在桶内分配和收集，及对各桶进行插入排序的时间为0(n),算法的期望时间是0(n),最坏时间是O(n2)o(2)基数排序实现过程：按基数设置箱子，对关键字从低位到高位依次进行箱排序。算法的最好时间是O(d*n+d*rd)；最坏时间是O(d*n+d*rd)；平均时间是O(d*n+d*rd)；辅助空间O(n+rd)；是一种稳定排序；13.各种内部排序方法的比较和选择：(1)按平均时间复杂度分为：1)平方阶排序：直接插入、直接选择、冒泡排序；2)线性对数阶：快速排序、堆排序、归并排序；3)指数阶：希尔排序；4)线性阶：箱排序、基数排序。(2)选择合适排序方法的因素：1)待排序的记录数；2)记录的大小；3)关键字的结构和初始状态；4)对稳定性的要求；5)语言工具的条件；6)存储结构；7)时间和辅助空间复杂度。(3)结论：1)若规模较小可采用直接插入或直接选择排序；2)若文件初始状态基本有序可采用直接插入、冒泡或随机快速排序；3)若规模较大可采用快速排序、堆排序或归并排序；4)任何借助于比较的排序，至少需要O(nlog2n)的时间，箱排序和基数排序只适用于有明显结 构特征的关键字；5)有的语言没有提供指针及递归，使归并、快速、基数排序算法复杂；6)记录规模较大时为避免大量移动记录可用链表作为存储结构，如插入、归并、基数排序，但 快速、堆排序在链表上难以实现，可提取关键字建立索引表，然后对索引表排序。第九章查找1.查找的同时对表做修改操作（如插入或删除）则相应的表称之为动态查找表，否则称之为静态查 找表。2.衡量一个查找算法次序优劣的标准是在查找过程中对关键字需要执行的平均比较次数（即平均 查找长度ASL）.3.线性表上进行查找的方法主要有三种：顺序查找、二分查找和分块查找。（1）顺序查找的算法基本思想：是从表的一端开始顺序扫描线性表，依次将扫描到的结点关键 字与给定值K比较，若当前扫描到的结点关键字与k相等则查找成功；若扫描结束后，仍未找 到关键字等于K的结点，则查找失败。1）顺序查找方法可用链式存储结构和顺序存储结构实现。2）在顺序存储结构的顺序查找算法中所设的哨兵是为了简化循环的边界条件而引入的附加结点（元素），其作用是使for循环中省去判定防止下标越界的条件从而节省了比较的时间。3）在等概率情况下，查找成功时其平均查找长度约为表长的一半（n+l）/2.查找失败的话其平 均查找长度为n+1.（2）二分查找（又称折半查找），它的算法思想：是对一有序表中的元素，从初始的查找区间开 始，每经过一次与当前查找区间的中点位置上的结点关键字进行比较，若相等，则查找成功，否 则，当前查找区间的缩小一半，按k值大小在某半个区间内重复相同的步骤进行查找，直到