自学考试：数据结构考前资料汇编.doc

数据结构考前资料汇编一、各章内容重点(1)1二、各章内容重点(1)19三、数据结构（c语言版）选择、填空题45四、数据结构（c语言版）选择、填空题答案55五、数据结构（c语言版）试题（简答、计算）59六、数据结构c语言版简答、计算题答案79一、各章内容重点(1)第一章概论1.1基本概念和术语数据是信息的载体,能被计算机识别、存储和加工处理。数据元素是数据的基本单位，可由若干个数据项组成，数据项是具有独立含义的最小标识单位。数据结构包括：1）数据的逻辑结构，从逻辑关系上描述数据，与数据存储无关，独立于计算机；2）数据的存储结构，是逻辑结构用计算机语言的实现，依赖于计算机语言。3）数据的运算，定义在逻辑结构上，每种逻辑结构都有一个运算集合。常用的：检索/插入/删除/更新/排序。数据类型是一个值的集合及在值上定义的一组操作的总称。分为原子类型和结构类型。抽象数据类型是抽象数据的组织和与之相关的操作。其优点是将数据和操作封装在一起实现了信息隐藏。adt是在概念层上描述问题；类是在实现层上描述问题；在应用层上操作对象（类的实例）解决问题。数据的逻辑结构有：1）线性结构，若结构是非空集则仅有一个开始和终端结点，并且所有结点最多只有一个直接前趋和后继。2）非线性结构，一个结点可能有多个直接前趋和后继。数据的存储结构有：1）顺序存储，把逻辑相邻的结点存储在物理上相邻的存储单元内。2）链接存储，结点间的逻辑关系由附加指针字段表示。3）索引存储，存储结点信息的同时，建立附加索引表，有稠密索引和稀疏索引。4）散列存储，按结点的关键字直接计算出存储地址。1.2学习数据结构的意义程序设计的实质是选择一个好的数据结构，设计一个好的算法。算法取决于描述实际问题的数据结构。1.3算法的描述和分析算法是任意一个良定义的计算过程，以一个或多个值输入，并产生一个或多个值输出。是用来解决一个计算问题的工具。问题的输入实例是满足问题陈述中所给出的限制、为计算该问题的解所需要的所有输入构成。评价算法的好坏是：1）算法是正确的；2）要考虑算法所耗的时间、存储空间（辅助存储）、易于理解，编码，调试。算法所耗时间是每条语句执行时间之和，每条语句的执行时间是该语句执行次数与执行时间的乘积。算法求解问题的输入量称问题的规模。算法的时间复杂度t(n)是该算法的时间耗费，是求解问题规模n的函数。当问题规模趋向无穷大时，把t(n)的数量阶称算法的渐进时间复杂度，记为o(n)。常见的时间复杂度排列为：常数阶、对数阶、线性阶、线性对数阶、平方阶、立方阶、k次方阶、指数阶。算法的空间复杂度s(n)是该算法的空间耗费，是求解问题规模n的函数。算法的渐进空间复杂度简称空间复杂度。算法的时间复杂度和空间复杂度合称算法的复杂度。第二章线性表2.1线性表的逻辑结构线性表是由n(n0)个数据元素组成的有限序列，当n=0是称为空表，非空的线性表记为(a1,a2,a3an)。线性表的基本运算有：1）initlist(l),构造空表，即表的初始化；2）listlength(l),求表的结点个数，即表长；3）getnode(l,i),取表中第i个结点，要求1ilistlength(l)；4）locatenode(l,x)查找l中值为x的结点并返回结点在l中的位置，有多个x则返回首个，没有则返回特殊值表示查找失败。5）insertlist(l,x,i)在表的第i个位置插入值为x的新结点，要求1ilistlength(l)+1；6）deletelist(l,i)删除表的第i个位置的结点，要求1ilistlength(l)；2.2线性表的顺序存储结构2.2.1顺序表顺序表是把线性表的结点按逻辑次序存放在一组地址连续的存储单元里。结点的存储地址计算公式：loc(ai)=loc(a1)+(i-1)*c；1in顺序表的定义：#define listsize 100typedef int datatype;typedef structdatatype datalistsize;int length;seqlist;2.2.2顺序表山的基本运算1插入void insertlist(seqlist *l,datatype x,int i)int j;if(il-length+1)error(“positionerror”);if(l-length=listsize)error(“overflow”);for(j=l-length-1;j=i-1;j-)l-dataj+1=l-dataj;l-datai-1=x;l-length+;在顺序表上插入要移动表的n/2结点，算法的平均时间复杂度为o(n)。2删除void delete(seqlist *l,int i)int j;if(il-length)error(“positionerror”);for(j=i;jlength-1;j+)l-dataj-1=l-dataj;l-length-;在顺序表上删除要移动表的（n+1）/2结点，算法的平均时间复杂度为o(n)。23线性表的链式存储结构用链接方式存储的线性表称链表。231单链表在结点中除了存储结点值还存储结点的后继结点的地址，data|next,data是数据域，next是指针域，只有一个链域的链表称单链表。单链表结点的定义。typedef char datatype;typedef struct nodedatatype data;struct node *next;listnode;typedef listnode *linklist;listnode *p;linklist head;结点的动态生成p=(listnode *)malloc(sizeof(listnode);结点的回收free(p);1建立单链表。时间复杂度为o(n)。1）头插法建表。 105 / 105linkcreatelistf(void)char ch;linklist head;listnode *s;head=null;ch=getchar();while(ch!=n)s=(listnode *)malloc(sizeof(listnode);s-data=ch;s-next=head;head=s;ch=getchar();return head;2)尾插法建表。linkcreatelistr(void)char ch;linklist head;listnode *s,*r;s=null;r=null;while(ch=getchar()!=n)s=(listnode *)malloc(sizeof(listnode);s-data=ch;if(head=null)head=s;elser-next=s;r=s;if(r!=nnull)r-next=null;return head;在链表开始结点前附加一个头结点的优点是：1）链表第一个位置的操作无需特殊处理；2）将空表和非空表的处理统一。3）带头结点的尾插法建表。linklistcreatelisr1(void)char ch;linklist head=(listnode *)malloc(sizeof(listnode);listnode *s,*r;r=head;while(ch=getchar()！=n)s=(listnode *)malloc(sizeof(listnode);s-data=ch;r-next=s;r=s;r-next=null;return head;2查找运算。时间复杂度为o(n)。1）按序号查找。listnode *getnode(linklist head,int i)int j;listnode*p;p=head;j=0;while(p-next&jnext;j+;if(i=j)returnp;elsereturnnull;2）按值查找。listnode*locatenode(linklisthead,datatypekey)listnode*p=head-next;while(p&p-data!=key)p=p-next;returnp;3插入运算。时间复杂度为o(n)。voidinsertlist(linklisthead,datatypex,inti)listnode*p;p=getnode(head,i-1);if(p=null);error(“positionerror”);s=(listnode*)malloc(sizeof(listnode);s-data=x;s-next=p-next;p-next=s;4删除运算。时间复杂度为o(n)。voiddeletelist(linklisthead,inti)listnode*p,*r;p=getnode(head,i-1);if(p=null|p-next=null)error(“positionerror”);r=p-next;p-next=r-next;free(r);2.3.2循环链表。循环链表是一种首尾相连的链表。特点是无需增加存储量，仅对表的链接方式修改使表的处理灵活方便。单链表是将终端结点的指针域指向表头结点或开始结点。为使空表和非空表处理一致可设置一个头结点。用头指针表示的单循环链表查找开始结点的时间是o(1),查找尾结点的时间是o(n)；用尾指针表示的单循环链表查找开始结点和尾结点的时间都是o(1)。233双链表在结点中增加一个指针域，prior|data|next。形成的链表中有两条不同方向的链称为双链表。双链表结点定义。typedefstructdlistnodedatatypedata;structdlistnode*prior,*next;dlistnode;typedefdlistnode*dlinklist;dlinklisthead;1)双链表的前插操作。时间复杂度为o(1)。voiddinsertbefore(dlistnode*p,datatypex)dlistnode*s=malloc(sizeof(dlistnode);s-data=x;s-prior=p-prior;s-next=p;p-prior-next=s;p-prior=s;2)双链表的删除操作。时间复杂度为o(1)。voidddeletenode(dlistnode*p)p-prior-next=p-next;p-next-prior=p-prior;free(p); 2.4顺序表和链表的比较。1）基于空间的考虑：顺序表的存储空间是静态分配的，链表的存储空间是动态分配的。顺序表的存储密度比链表大。因此，在线性表长度变化不大，易于事先确定时，宜采用顺序表作为存储结构。2）基于时间的考虑：顺序表是随机存取结构，若线性表的操作主要是查找，很少有插入、删除操作时，宜用顺序表结构。对频繁进行插入、删除操作的线性表宜采用链表。若操作主要发生在表的首尾时采用尾指针表示的单循环链表。第三章栈和队列31栈311栈的定义及基本运算栈是限制仅在表的一端进行插入和删除运算的线性表又称为后进先出表（lifo表）。插入、删除端称为栈顶，另一端称栈底。表中无元素称空栈。基本运算有：1）initstack(s),构造一个空栈；2）stackempty(s),判栈空；3）stackfull(s),判栈满；4）push(s,x),进栈；5）pop(s),退栈；6）stacktop(s)，取栈顶元素。312顺序栈栈的顺序存储结构称顺序栈。顺序栈的类型定义为：#definestacksize100typedefchardatatype;typedefstructdatatypedatastacksize;inttop;seqstack;当栈满时，做进栈运算必定产生空间溢出，称“上溢”。当栈空时，做退栈运算必定产生空间溢出，称“下溢”。上溢是一种错误应设法避免，下溢常用作程序控制转移的条件。在顺序栈上的基本运算：1）置空栈。voidinitstack(seqstack*s)s-top=-1;2)判栈空。intstackempty(seqstack*s)returns-top=-1;3)判栈满。intstackfull(seqstack*s)returns-top=stacksize-1;4)进栈。voidpush(seqstack*s,datatypex)if(stackfull(s)error(“stackoverflow”);s-data+s-top=x;5)退栈。datatypepop(seqstack*s)if(stackempty(s)error(“stackunderflow”);returns-datas-top-;6)取栈顶元素。dtatatypestacktop(seqstack*s)if(stackempty(s)error(“stackunderflow”);returns-datas-top;3.1.3链栈栈的链式存储结构称链栈。栈顶指针是链表的头指针。链栈的类型定义：typedefstructstacknodedatatypedata;structstacknode*next;stacknode;typedefstructstacknode*top;linkstack;链栈上的基本运算：1）建栈。voidinitstack(linkstack*s)s-top=null;2)判栈空。intstackempty(linkstack*s)returns-top=null;3)进栈。voidpush(linkstack*s,datatypex)stacknode*p=(stacknode*)malloc(sizeof(stacknode);p-data=x;p-next=s-top;s-top=p;4)退栈。datatypepop(linksatck*s)datatypex;stacknode*p=s-top;if(stackempty(s)error(“stackunderflow”);x=p-data;s-top=p-next;free(p);returnx;5)取栈顶元素。datatypestacktop(linkstack*s)if(stackempty(s)error(“stackisempty”);returns-top-data;3.2队列321队列的基本定义和计算。队列是一种运算受限的线性表，允许删除的一端称队首，允许插入的一端称队尾。队列又称为先进先出线性表，fifo表。队列的基本运算：1）initqueue(q),置空队；2）queueempty(q),判队空；3）queuefull(q),判队满；4）enqueue(q,x),入队；5）dequeue(q),出队；6）queuefront(q),返回队头元素。322顺序队列。队列的顺序存储结构称顺序队列。设置front和rear指针表示队头和队尾元素在向量空间的位置。顺序队列中存在“假上溢”现象，由于入队和出队操作使头尾指针只增不减导致被删元素的空间无法利用，队尾指针超过向量空间的上界而不能入队。为克服“假上溢”现象，将向量空间想象为首尾相连的循环向量，存储在其中的队列称循环队列。i=(i+1)%queuesize循环队列的边界条件处理：由于无法用front=rear来判断队列的“空”和“满”。解决的方法有：1）另设一个布尔变量以区别队列的空和满；2）少用一个元素，在入队前测试rear在循环意义下加1是否等于front；3）使用一个记数器记录元素总数。循环队列的类型定义：#definequeuesize100typedefchardatatype;typedefstructintfront;intrear;intcount;datatypedataqueuesize;cirqueue;1)置队空。voidinitqueue(cirqueue*q)q-front=q-rear=0;q-count=0;2)判队空。intqueueempty(cirqueue*q)returnq-count=0;3)判队满。intqueuefull(cirqueue*q)returnq-count=queuesize;4)入队。voidenqueue(cirqueue*q,datatypex)if(queuefull(q)error(“queueoverfolw”);q-count+;q-dataq-rear=x;q-rear=(q-rear+1)%queuesize;5)出队。datatypedequeue(cirqueue*q)datatypetemp;if(queueempty(q)error(“queueunderflow”);temp=q-dataq-front;q-count-;q-front=(q-front+1)%queuesize;returntemp;6)取队头元素。datatypequeuefront(cirqueue*q)if(queueempty(q)error(“queueisempty”);returnq-dataq-front;323链队列队列的链式存储结构称链队列，链队列由一个头指针和一个尾指针唯一确定。链队列的定义：typedefstructqueuenodedatatypedata;structqueue*next;queuenode;typedefstructqueuenode*front;queuenode*rear;linkqueue;1)建空队。voidinitqueue(linkqueue*q)q-front=q-rear=null;2)判队空。intqueueempty(linkqueue*q)returnq-front=null&q-rear=null;3)入队。voidenqueue(linkqueue*q,datatypex)queuenode*p=(queuenode*)malloc(sizeof(queuenode);p-data=x;p-next=null;if(queueempty(q)q-front=q-rear=p;elseq-rear-next=p;q-rear=p;4)出队。datatypedequeue(linkqueue*q)datatypex;queuenode*p;if(queueempty(q)error(“queueisunderflow”);p=q-front;x=p-data;q-front=p-next;if(q-rear=p)q-rear=null;free(p);returnx;5)取队头元素。datatypequeuefront(linkqueue*q)if(queueempty(q)error(“queueisempty”);returnq-front-data;第四章串41串及其运算411串的基本概念。串是由零个或多个字符组成的有限序列；包含字符的个数称串的长度；长度为零的串称空串；由一个或多个空格组成的串称空白串；串中任意个连续字符组成的子序列称该串的子串；包含子串的串称主串；子串的首字符在主串中首次出现的位置定义为子串在主串中的位置；空串是任意串的子串；任意串是自身的子串；串常量在程序中只能引用但不能改变其值；串变量取值可以改变；412串的基本运算1）intstrlen(char*s);求串长。2）char*strcpy(char*to,char*from);串复制。3）char*strcat(char*to,char*from);串联接。4）intstrcmp(char*s1,char*s2);串比较。5）char*strchr(char*s,charc);字符定位。42串的存储结构421串的顺序存储串的顺序存储结构称顺序串。按存储分配不同分为：1）静态存储分配的顺序串：直接用定长的字符数组定义，以“0”表示串值终结。#definemaxstrsize256typedefcharseqstringmaxstrsize;seqstrings;不设终结符，用串长表示。typedefstructcharchmaxstrsize;intlength;seqstring;以上方式的缺点是：串值空间大小是静态的，难以适应插入、链接等操作。2）动态存储分配的顺序串：简单定义：typedefchar*string;复杂定义：typedefstructchar*ch;intlength;hstring;4.2.2串的链式存储串的链式存储结构称链串。链串由头指针唯一确定。类型定义：typedefstructnodechardata;structnode*next;linkstrnode;typedeflinkstrnode*linkstring;linkstrings;将结点数据域存放的字符个数定义为结点的大小。结点大小不为1的链串类型定义：#definenodesize80typedefstructnodechardatanodesize;structnode*next;linkstrnode;4.2.3串运算的实现1顺序串上的子串定位运算。子串定位运算又称串的模式匹配或串匹配。主串称目标串；子串称模式串。朴素的串匹配算法。时间复杂度为o(n2)。比较的字符总次数为（n-m+1）m。intnaivestrmatch(seqstringt,seqstringp)inti,j,k;intm=p.length;intn=t.length;for(i=0;i=n-m;i+)j=0;k=i;while(jdata=p-data)t=t-next;p=p-next;elseshift=shift-next;t=shift;p=p;if(p=null)returnshift;elsereturnnull;第五章多维数组和广义表51多维数组一般用顺序存储的方式表示数组。常用方式有：1）行优先顺序，将数组元素按行向量排列；2）列优先顺序，将数组元素按列向量排列。计算地址的函数：loc(aij)=loc(ac1c2)+(i-c1)*(d2-c2+1)+j-c2)*d52矩阵的压缩存储为多个非零元素分配一个存储空间；对零元素不分配存储空间。1对称矩阵在一个n阶的方阵a中，元素满足aij=aji0=i,j(k-1)/2以行优先顺序存放的aij与sak的关系：k=2i+j;522稀疏矩阵当矩阵a中有非零元素s个，且s远小于元素总数时，称为稀疏矩阵。对其压缩的方法有顺序存储和链式存储。1三元组表将表示稀疏矩阵的非零元素的三元组（行号、列号、值）按行或列优先的顺序排列得到的一个结点均是三元组的线性表，将该表的线性存储结构称为三元组表。其类型定义：#definemaxsize10000typedefintdatatype;typedefstructinti,j;datatypev;trituplenode;typedefstructtrituplenodedatamaxsize;intm,n,t;tritupletable;2.带行表的三元组表在按行优先存储的三元组表中加入一个行表记录每行的非零元素在三元组表中的起始位置。类型定义：#definemaxrow100typedefstructtritulpenodedatamaxsize;introwtabmaxrow;intm,n,t;rtritulpetable;5.3广义表的概念广义表是线性表的推广。广义表是n个元素的有限序列，元素可以是原子或一个广义表，记为ls。若元素是广义表称它为ls的子表。若广义表非空，则第一个元素称表头，其余元素称表尾。表的深度是指表展开后所含括号的层数。把与树对应的广义表称为纯表，它限制了表中成分的共享和递归；允许结点共享的表称为再入表；允许递归的表称为递归表；相互关系：线性表纯表再入表递归表；广义表的特殊运算：1）取表头head(ls)；2）取表尾tail(ls);第六章树61树的概念树是n个结点的有限集t，t为空时称空树，否则满足1）有且仅有一个特定的称为根的结点；2）其余结点可分为m个互不相交的子集，每个子集本身是一棵树，并称为根的子树。树的表示方法：1）树形表示法；2）嵌套集合表示法；3）凹入表表示法；4）广义表表示法；一个结点拥有的子树数称为该结点的度；一棵树的度是指树中结点最大的度数。度为零的结点称叶子或终端结点；度不为零的结点称分支结点或非终端结点根结点称开始结点，根结点外的分支结点称内部结点；树中某结点的子树根称该结点的孩子；该结点称为孩子的双亲；树中存在一个结点序列k1，k2，kn，使ki为ki+1的双亲，则称该结点序列为k1到kn的路径或道路；树中结点k到ks间存在一条路径，则称k是ks的祖先，ks是k的子孙；结点的层数从根算起，若根的层数为1，则其余结点层数是其双亲结点层数加1；双亲在同一层的结点互为堂兄弟；树中结点最大层数称为树的高度或深度；树中每个结点的各个子树从左到右有次序的称有序树，否则称无序树；森林是m棵互不相交的树的集合。62二叉树621二叉树的定义二叉树是n个结点的有限集，它或为空集，或由一个根结点及两棵互不相交的、分别称为该根的左子树和右子树的二叉树组成。二叉树不是树的特殊情况，这是两种不同的数据结构；它与无序树和度为2的有序树不同。622二叉树的性质1）二叉树第i层上的结点数最多为2(i-1)；2）深度为k的二叉树至多有2k-1个结点；3）在任意二叉树中，叶子数为n0，度为2的结点数为n2，则n0=n2+1；满二叉树是一棵深度为k的且有2k-1个结点的二叉树；完全二叉树是至多在最下两层上结点的度数可以小于2，并且最下层的结点集中在该层最左的位置的二叉树；4）具有n个结点的完全二叉树的深度为log2n取整加1；623二叉树的存储结构1顺序存储结构把一棵有n个结点的完全二叉树，从树根起自上而下、从左到右对所有结点编号，然后依次存储在一个向量b0n中，b1n存放结点，b0存放结点总数。各个结点编号间的关系：1）i=1是根结点；i1则双亲结点是i/2取整；2）左孩子是2i,右孩子是2i+1；（要小于n）3）i（n/2取整）的结点是叶子；4）奇数没有右兄弟，左兄弟是i-1；5）偶数没有左兄弟，右兄弟是i+1；2链式存储结构结点的结构为：lchild|data|rchild；相应的类型说明：typedefchardata;typedefstructnodedatatypedata;structnode*lchild,*rchild;bintnode;typedefbintnode*bintree;在二叉树中所有类型为bintnode的结点和一个指向开始结点的bintree类型的头指针构成二叉树的链式存储结构称二叉链表。二叉链表由根指针唯一确定。在n个结点的二叉链表中有2n个指针域，其中n+1个为空。63二叉树的遍历二叉树的遍历方式有：前序遍历、中序遍历、后序遍历。时间复杂度为o(n)。64线索二叉树利用二叉链表中的n+1个空指针域存放指向某种遍历次序下的前趋和后继结点的指针，这种指针称线索。加线索的二叉链表称线索链表。相应二叉树称线索二叉树。线索链表结点结构：lchild|ltag|data|rtag|rchild；ltag=0,lchild是指向左孩子的指针；ltag=1,lchild是指向前趋的线索；rtag=0,rchild是指向右孩子的指针；rtag=1,rchild是指向后继的线索；1查找*p在指定次序下的前趋和后继结点。算法的时间复杂度为o(h)。线索对查找前序前趋和后序后继帮助不大。2遍历线索二叉树。时间复杂度为o(n)。65树和森林651树、森林与二叉树的转换1树、森林与二叉树的转换树与二叉树的转换：1）所有兄弟间连线；2）保留与长子的连线，去除其它连线。该二叉树的根结点的右子树必为空。森林与二叉树的转换：1）将所有树转换成二叉树；2）将所有树根连线。2二叉树与树、森林的转换。是以上的逆过程。652树的存储结构1. 双亲链表表示法：为每个结点设置一个parent指针，就可唯一表示任何一棵树。data|parent2孩子链表表示法：为每个结点设置一个firstchild指针，指向孩子链表头指针，链表中存放孩子结点序号。data|firstchild。双亲孩子链表表示法：将以上方法结合。data|parent|firstchild3. 孩子兄弟链表表示法：附加两个指向左孩子和右兄弟的指针。leftmostchild|data|rightsibling653树和森林的遍历前序遍历一棵树等价于前序遍历对应二叉树；后序遍历等价于中序遍历对应二叉树。66哈夫曼树及其应用661最优二叉树（哈夫曼树）树的路径长度是从树根到每一结点的路径长度之和。将树中的结点赋予实数称为结点的权。结点的带权路径是该结点的路径长度与权的乘积。树的带权路径长度又称树的代价，是所有叶子的带权路径长度之和。带权路径长度最小的二叉树称最优二叉树（哈夫曼树）。具有2n-1个结点其中有n个叶子，并且没有度为1的分支结点的树称为严格二叉树。662哈夫曼编码压缩的过程称编码，解压的过程称解码；对字符集编码时，要求字符集中任一字符的编码都不是其它字符的编码前缀，这种编码称前缀码。字符出现频度与码长乘积之和称文件总长；字符出现概率与码长乘积之和称平均码长；使文件总长或平均码长最小的前缀码称最优前缀码利用哈夫曼树求最优前缀码，左为0，右为1。编码平均码长最小；没有叶子是其它叶子的祖先，不可能出现重复前缀。第七章图71图的概念图g是由顶点集v和边集e组成，顶点集是有穷非空集，边集是有穷集；g中每条边都有方向称有向图；有向边称弧；边的始点称弧尾；边的终点称弧头；g中每条边都没有方向的称无向图。顶点n与边数e的关系：无向图的边数e介于0n(n-1)/2之间，有n(n-1)/2条边的称无向完全图；有向图的边数e介于0n(n-1)之间，有n(n-1)条边的称有向完全图；无向图中顶点的度是关联与顶点的边数；有向图中顶点的度是入度与出度的和。所有图均满足：所有顶点的度数和的一半为边数。图g（v，e），如v是v的子集，e是e的子集，且e中关联的顶点均在v中，则g(v,e)是g的子图。在有向图中，从顶点出发都有路径到达其它顶点的图称有根图；在无向图中，任意两个顶点都有路径连通称连通图；极大连通子图称连通分量；在有向图中，任意顺序两个顶点都有路径连通称强连通图；极大连通子图称强连通分量；将图中每条边赋上权，则称带权图为网络。72图的存储结构7.2.1邻接矩阵表示法邻接矩阵是表示顶点间相邻关系的矩阵。n个顶点就是n阶方阵。无向图是对称矩阵；有向图行是出度，列是入度。722邻接表表示法对图中所有顶点，把与该顶点相邻接的顶点组成一个单链表，称为邻接表，adjvex|next,如要保存顶点信息加入data；对所有顶点设立头结点，vertex|firstedge,并顺序存储在一个向量中；vertex保存顶点信息，firstedge保存邻接表头指针。邻接矩阵表示法与邻接表表示法的比较：1）邻接矩阵是唯一的，邻接表不唯一；2）存储稀疏图用邻接表，存储稠密图用邻接矩阵；3）求无向图顶点的度都容易，求有向图顶点的度邻接矩阵较方便；4）判断是否是图中的边，邻接矩阵容易，邻接表最坏时间为o(n)；5）求边数e，邻接矩阵耗时为o(n2)，与e无关，邻接表的耗时为o(e+n)；73图的遍历731图的深度优先遍历图的深度优先遍历类似与树的前序遍历。按访问顶点次序得到的序列称dfs序列。对邻接表表示的图深度遍历称dfs，时间复杂度为o(n+e);对邻接矩阵表示的图深度遍历称dfsm，时间复杂度为o(n2);732图的广度优先遍历图的广度优先遍历类似与树的层次遍历。按访问顶点次序得到的序列称bfs序列。对邻接表表示的图广度遍历称bfs，时间复杂度为o(n+e);对邻接矩阵表示的图广度遍历称bfsm，时间复杂度为o(n2);74生成树和最小生成树将没有回路的连通图定义为树称自由树。741生成树连通图g的一个子图若是一棵包含g中所有顶点的树，该子图称生成树。有dfs生成树和bfs生成树，bfs生成树的高度最小。非连通图生成的是森林。742最小生成树将权最小的生成树称最小生成树。（是无向图的算法）1普里姆算法：1）确定顶点s、初始化候选边集t0n-2；formvex|tovex|lenght2）选权值最小的ti与第1条记录交换；3）从t1中将tovex取出替换以下记录的fromvex计算权；若权小则替换，否则不变；4）选权值最小的ti与第2条记录交换；5）从t2中将tovex取出替换以下记录的fromvex计算权；若权小则替换，否则不变；6）重复n-1次。初始化时间是o(n),选轻边的循环执行n-1-k次，调整轻边的循环执行n-2-k；算法的时间复杂度为o(n2)，适合于稠密图。2克鲁斯卡尔算法：1）初始化确定顶点集和空边集；对原边集按权值递增顺序排序；2）取第1条边，判断边的2个顶点是不同的树，加入空边集，否则删除；3）重复e次。对边的排序时间是o(elog2e)；初始化时间为o(n)；执行时间是o(log2e)；算法的时间复杂度为o(elog2e)，适合于稀疏图。75最短路径路径的开始顶点称源点，路径的最后一个顶点称终点；单源最短路径问题：已知有向带权图，求从某个源点出发到其余各个顶点的最短路径；单目标最短路径问题：将图中每条边反向，转换为单源最短路径问题；单顶点对间最短路径问题：以分别对不同顶点转换为单源最短路径问题；所有顶点对间最短路径问题：分别对图中不同顶点对转换为单源最短路径问题；迪杰斯特拉算法：1）初始化顶点集si,路径权集di,前趋集pi；2）设置ss为真，ds为0；3）选取di最小的顶点加入顶点集；4）计算非顶点集中顶点的路径权集；5）重复3）n-1次。算法的时间复杂度为o(n2)。76拓扑排序对一个有向无环图进行拓扑排序，是将图中所有顶点排成一个线性序列，满足弧尾在弧头之前。这样的线性序列称拓扑序列。1无前趋的顶点优先总是选择入度为0的结点输出并删除该顶点的所有边。设置各个顶点入度时间是o(n+e)，设置栈或队列的时间是o(n)，算法时间复杂度为o(n+e)。2无后继的顶点优先总是选择出度为0的结点输出并删除该顶点的所有边。设置各个顶点出度时间是o(n+e)，设置栈或队列的时间是o(n)，算法时间复杂度为o(n+e)。求得的是逆拓扑序列。第八章排序81基本概念文件有一组记录组成，记录有若干数据项组成，唯一标识记录的数据项称关键字；排序是将文件按关键字的递增（减）顺序排列；排序文件中有相同的关键字时，若排序后相对次序保持不变的称稳定排序，否则称不稳定排序；在排序过程中，文件放在内存中处理不涉及数据的内、外存交换的称内部排序，反之称外部排序；排序算法的基本操作：1）比较关键字的大小；2）改变指向记录的指针或移动记录本身。评价排序方法的标准：1）执行时间；2）所需辅助空间，辅助空间为o(1)称就地排序；另要注意算法的复杂程度。若关键字类型没有比较运算符，可事先定义宏或函数表示比较运算。82插入排序821直接插入排序实现过程：voidinsertsort(seqlistr)inti,j;for(i=2;i=n;i+)if(ri.keyri-1.keyr0=ri;j=i-1;dorj+1=rj;j-;while(r0.keyrj.key);rj+1=r0;算法中引入监视哨r0的作用是：1）保存ri的副本；2）简化边界条件，防止循环下标越界。关键字比较次数最大为(n+2)(n-1)/2；记录移动次数最大为(n+4)(n-1)/2；算法的最好时间是o(n)；最坏时间是o(n2)；平均时间是o(n2)；是一种就地的稳定的排序；8.2.2希尔排序实现过程：是将直接插入排序的间隔变为d。d的取值要注意：1）最后一次必为1；2）避免d值互为倍数；关键字比较次数最大为n1.25；记录移动次数最大为1.6n1.25；算法的平均时间是o(n1.25)；是一种就地的不稳定的排序；83交换排序831冒泡排序实现过程：从下到上相邻两个比较，按小在上原则扫描一次，确定最小值，重复n-1次。关键字比较次数最小为n-1、最大为n(n-1)/2；记录移动次数最小为0，最大为3n(n-1)/2；算法的最好时间是o(n)；最坏时间是o(n2)；平均时间是o(n2)；是一种就地的稳定的排序；832快速排序实现过程：将第一个值作为基准，设置i,j指针交替从两头与基准比较，有交换后,交换j，i。i=j时确定基准，并以其为界限将序列分为两段。重复以上步骤。关键字比较次数最好为nlog2n+nc(1)、最坏为n(n-1)/2；算法的最好时间是o(nlog2n)；最坏时间是o(n2)；平均时间是o(nlog2n)；辅助空间为o(log2n)；是一种不稳定排序；84选择排序841直接选择排序实现过程：选择序列中最小的插入第一位，在剩余的序列中重复上一步，共重复n-1次。关键字比较次数为n(n-1)/2；记录移动次数最小为0，最大为3(n-1)；算法的最好时间是o(n2)；最坏时间