严慰敏C语言版复习提纲,每章的重点归纳ds复习纲要

严慰敏C语言版复习提纲,每章的重点归纳ds复习纲要 第一章绪论 一、内容提要1数据结构研究的内容。 2基本概念数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型、多形数据类型。 3算法的定义及五个特征。 4算法描述类PASCAL语言。 5算法设计要求。 6算法分析。 二、学习重点1数据结构的“三要素”逻辑结构、物理（存储）结构及在这种结构上所定义的操作（运算）。 2抽象数据类型的定义、表示和实现方法。 3类PASCAL书写规范，过程（函数）中值参和变参的差别，过程调用规则。 4用计算语句频度来估算算法的时间复杂度。 三、例题解析1写出以下各语句执行次数（左边括号内数字为语句序号） (1)FOR i:=1TO nDO (2)FOR j:=1to nDO (3)cI,j:=0; (4)FOR k:=1TO nDO (5) (5)cI,j:=cI,j+aI,k*bk,j答案各语句执行次数（频度）分别为n+1，n(n+1),n2,n2(n+1),n3分析最容易发生的错误，是将第一个语句的执行次数答成n。 2编写最优算法，从小到大依次输出顺序读入的三个整数PROC asscending;本算法对读入的三个整数进行排序，然后按从小到大输出算法中核心语句如下read(a,b,c);IF ab THENt:=a;a:=b;b:=t;a,b按正序排序IF bc THENt:=c;c:=b;c为最大IF a 在本课程教学中，强调“好”的算法,不仅仅是结果正确,而且是最优的算法。 这与PASCAL语言教学中的要求有很大不同。 算法是供人来阅读的，必须牢记这一点。 算法中语句的书写格式采用缩进规则，保留字用大写，其余标识符小写，提高了算法的易读性。 第二章第二章线性表 一、内容提要1线性表是元素间约束力最强的一类数据结构。 2线性表的逻辑结构定义，对线性表定义的操作。 3线性表的存储结构顺序存储结构和链式存储结构。 4线性表的操作在两种存储结构中的实现。 5一元多项式的线性表表示方法，及高次（稀疏）多项式的抽象数据类型定义、表示和加法的实现。 二、学习重点11线性表的逻辑结构，指线性表的数据元素间存在着线性关系。 在顺序存储结构中，元素存储的先后位置反映出这种线性关系，而在链式存储结构中，是靠指针来反映这种关系的。 22顺序存储结构用向量（一维数组）表示，给定下标，可以存取相应元素，属于随机存取的存储结构。 33尽管“只要知道某结点的指针就可以存取该元素”，但因链表的存取都需要从头指针开始，顺链而行，故链表不属于随机存取结构。 44链表是本章学习的重点和难点。 要理解头结点，首元结点和元素结点的差别。 理解头结点是为了在插入、删除等操作时，为了算法的统一而设立的（若无头结点，则在第一元素前插入元素或删除第一元素时，链表的头指针总在变化）。 掌握通过画出结点图来进行链表的生成、插入、删除、遍历等操作。 55链表操作中应注意不要使链意外“断开”。 因此，若在某结点前插入一个元素，或删除某元素，必须知道该元素的前驱结点的指针。 66从时间和空间复杂度的角度综合比较线性表在顺序和链式两种存储结构下的特点。 77静态链表是又一重点和难点。 应和链表进行比较、理解。 例如，在有头结点的链表情况下，第一元素是p:=la.next，而在静态链表中则i:=sa0.next；相对p:=p.next,有i:=sai.next来找到第i个元素的后继。 三、例题解析设线性表以顺序存储结构存于a(1.n)中，试编写算法将该线性表就地逆置。 【分析】向量逆置有几种方法，如逆向读入到另一数组中，在正向对应赋值，即FOR i:=n DOWNTO1DO bn-i+1:=ai;FOR i:=1TO nDO ai:=bi;这里要求“就地逆置”，即不能另用一数组空间。 【算法】PROC invert(VAR a:arr;n:integer);a是存储线性表的一维数组，有n个元素，本算法将a逆置。 FOR i:=1TO(n DIV2)DO ai?an-i+1;endp;【讨论】将n个元素的一维数组逆置，为什么循环控制变量用n div2，而不用n？编写在单链表上进行排序的算法【分析】这里使用插入排序。 链表中插入元素要知道待插入元素位置的前驱，以pre表示之。 结束的条件是链表为空。 【算法】PROC insertsort(VAR la:linklist);la是带头结点的单链表的指针，本算法将链表中元素正序排序。 算法的基本思想是先假定第一个元素有序，然后从第二个元素开始，依次插入到有序的表中，直到全部元素插入完为止p:=la.next.next;假定链表非空，即至少有一个结点la.next.next:=nil;设有序链表中当前只有一个结点found:=false;WHILE(pnil)AND NOTfound DOs:=p.next;记住下一个结点pre:=la;q:=la.next;found:=false;WHILE(qnil)AND NOTfound DO IF q.data 这里循环条件未写成（pnil）AND(q.data 请记住这种退出循环，引入布尔变量的作法。 3设两个非递减有序的线性表各有m和n个元素（m0,n0）,分别存于一维数组a和b中，且a的存储空间足够大。 试编写算法将两线性表合并成一线性表，结果仍是非递减有序，要求算法的时间复杂度是o(m+n)。 【分析】两个有序线性表合并成一个有序表，教材中已有讨论，算法非常简单。 本算法要求复杂度为O(m+n)，这是着重点。 题目叙述中有“a的空间足够大”，暗示出若将m+n个元素合并到a中，不会溢出。 为使数据移动次数最少，应先将两表中最大元素置于m+n的位置上，然后相应指针减1，再比较之，直到两表中有一个指针减到0，则结束，否则，将b中剩余元素传到a中相应位置即可。 【算法】PROC union(VAR a:seqlisttp;b:seqlisttp);a,b是两个非递减有序表，顺序存储结构存储，各有m和n个元素，本算法将两表合并到a中，仍为有序表，算法时间复杂度为O(m+n)i:=m;j:=n;k:=m+n;i,j,k分别为表a,b和结果表的指针WHILE(i0)AND(j0)DO IFaibjTHENak:=ai;i:=i-1;k:=k-1ELSEak:=bj;j:=j-1;k:=k-1;WHILE(j0)DOak:=bj;j:=j-1;k:=k-1;若b表中尚有元素，则传至a中相应位置【讨论】本算法至多比较m+n次，往a中赋值m+n次。 最好情况是比较n次，往a中赋值n次，该种情况是b中最小元素不小于a中最大元素。 问题为什么在退出第一个WHILE循环后，不讨论（即没有）WHILE i0的情况？第三章栈和队列 一、 一、内容提要11从数据结构角度讲，栈和队列也是线性表，其操作是线性表操作的子集，属操作受限的线性表。 但从数据类型的角度看，它们是和线性表大不相同的重要抽象数据类型。 22栈的定义及操作。 栈是只准在一端进行插入和删除操作的线性表，该端称为栈的顶端。 33栈的顺序和链式存储结构，及在这两种结构下实现栈的操作。 44栈的应用表达式求值，递归过程及消除递归。 55队列的定义及操作，队列的删除在一端（尾），而插入则在队列的另一端（头）。 因此在两种存储结构中，都需要队头和队尾两个指针。 66链队列空的条件是首尾指针相等，而循环队列满的条件的判定，则有队尾加1等于队头和设标记两种方法。 二、 二、学习重点1栈和队列操作在两种存储结构下的实现。 2中缀表达式转成前缀、后缀表达式并求值。 3用递归解决的问题定义是递归的，数据结构是递归的，及问题的解法是递归的，掌握典型问题的算法。 44链队列删除时为空的处理（令队尾指针指向队头）。 特别是仅设尾指针的循环链队列的各种操作的实现。 55循环队列队空定义为队头指针等于队尾指针，队满则可用一个单元（教材中所示）及设标记办法（下面例题）。 这里特别注意取模运算。 66在后续章节中要注意栈和队列的应用，如串中心对称的判定，二叉树遍历的递归和非递归算法，图的深度优先遍历等都用到栈，而树的层次遍历、图的宽度优先遍历等则用到队列。 三、 三、例题解析11两栈共享一向量空间，编写入栈和出栈算法。 TYPE TwoWayStack=RECORD双栈共享一向量空间elem:ARRAY1.mOF elemtype;top:ARRAY0.1OF0.m+1;两个栈顶指针END;PROC inistack(VAR tws:TwoWayStack);初始化初始化双向栈tws为空tws.top0:=0;左端栈指针tws.top1:=m+1;右端栈指针ENDP;inistackPROC PUSH(VAR tws:TwoWayStack;i:0.1;x:elemtype;VAR ofw:boolean);若双向栈tws不满,则将x插入到i端,成功时ofw为true,失败为falseIF(tws.top1-tws.top0)1THEN栈未满CASE iOF0:tws.top0:=tws.top0+1;tws.elemtws.top0:=x;ofw:=true1:tws.top1:=tws.top1-1;tws.elemtws.top1:=x;ofw:=true ENDCELSE ofw:=false;(栈满)ENDP;pushPROC POP(VAR tws:TwoWayStack;i:0.1;VAR x:elemtype;VAR underflow:boolean);若双向栈tws非空,则将i端退栈,栈空时underflow为trueCASE iOF0:IF tws.top0=0栈空THENunderflow:=true;return(underflow)ELSEtws.top0:=tws.top0-1;x:=tws.elemtws.top0+1;弹出元素;1:IF tws.top1=m+1栈空THENunderflow:=true;return(underflow)ELSEtws.top1:=tws.top1+1;x:=tws.elemtws.top1-1;弹出元素;ENDC ENDP;pop【讨论】上面算法中用0和1代表两端，且按操作在哪端来分两种情况进行讨论，逻辑清楚。 也可用一个公式表示插入（进栈）和删除（退栈）指针位置。 例如，插入时top=top+1-2*i,删除时top=top-1+2*i。 表达简洁，但不如上面清楚易读。 22将中缀表达式转换成后缀表达式，并进行表达式求值。 PROC trnssufix(VAR exp2:string;s:stack;exp1:string);本算法将中缀表达式exp1转为后缀表达式exp2,使用运算符栈s算法基本思想是依次从中缀表达式读入字符w若w是变量，直接送入结果表达式，若w是运算符，则与栈顶运算符比较，若级别高，则进栈；若低，则栈顶元素退栈，并送入结果表达式，再取栈顶运算符比较，重复以上步骤；若w),则栈元素依次退栈，并送入结果表达式，直至)退栈initstring(exp2);initstack(s);push(s,#);op:=+,-,*,/,(,),#;操作符集合read(w);WHILE NOT(w=#)AND(GETTOP(OPTR)=#)DO IF NOT(w INop)THENinsert(exp2,w);read(w);ELSE CASEprecede(GETTOP(s),w)OF:PUSH(S,w);read(w);=:IF w=)THEN遇右括号后，运算符退栈并送结果表达式，直至左括号x:=POP(S);WHILE x(DOinsert(exp2,x);x:=POP(S)read(w);:b:=POP(S);insert(exp2,b);END;ENDP;PROC sufixeval(VAR exp2:string;s:stack;VAR sn:stack);本算法对后缀表达式exp2求值，使用运算符栈s和操作数栈sn算法基本思想是逐字符从左到右顺序读入后缀表达式。 若读入的字符w是数，则直接压入栈sn中；若w是运算符，则与栈顶运算符比较，若级别高，则进栈；否则，从运算数栈弹出两个操作数，和从运算符栈弹出的一个运算符进行相应运算，结果存入操作数栈中。 w运算符再与栈顶运算符比较优先级。 直至后缀表达式处理完毕。 这时sn栈中只剩一个数，即表达式结果。 initstring(sn);initstack(s);op:=+,-,*,/,(,),#;操作符集合read(w);从左到右顺序读入后缀表达式WHILE NOTempty(exp2)DO IFNOT(w INop)THENPUSH(sn,w);read(w);ELSE CASEprecede(GETTOP(s),w)OF:a:=POP(sn);b:=POP(sn);theta:=POP(s);PUSH(sn,operate(a theta b);END;ENDP;sufixeval 3、用设标记来判定循环队列满，编写入队和出队的算法。 本算法用设标记tag的办法，解决循环队列队满和队列空的判断问题,tag=0表示队列空，tag=1表示队列不空TYPE cyclicqueue=RECORD设头尾指针和标志域的循环队列elem:=ARRAY0.m-1OF elemtype;rear,front:0.m-1tag:0.1;为空，为非空END;PROC INITQUEDE(VAR cq:cyclicqueue);初始化cq.tag:=0;cq.tear:=cq.front:=0;ENDP;PROC ENQUEUE(VAR cq:cyclicqueue;x:elemtype);cq是由头尾指针和标志域的循环队列，本算法是入队操作，若队列不满，则将x插入到队尾IF(cq.tag=1)AND(cq.front=cq.rear)THEN return(false)队满ELSEcq.rear:=(cq.rear+1)MOD m;cq.elem(cq.rear):=r;IF cq.tag=0THEN cq.tag:=1由空变不空标记ENDP;PROC DELQUEUE(VAR cq:cyclicqueue);cq是由头尾指针和标志域的循环队列，本算法是出队操作，若队列非空则将队头元素出队IF cq.tag=0THEN return(false)队空ELSEcq.front:=(cq.front+1)MOD m;IF cq.front=cq.rear THENcq.tag:=0队空ENDP;CONST m=maxlen;队列长度TYPE cyclicqueue=RECORD只设尾指针和队列长度的循环队列elem:ARRAY0.m-1OF elemtype;rear:0.m-1;length:0.m;队列长度END;PROC INIT_queue(VAR q:cyclicqueue);初始化q.rear:=0;q.length:=0;ENDP;FUNC add_queue(VAR q:cyclicqueue;x:elemtype):boolean;q是由尾指针和长度标志的循环队列，本算法是入队操作，若队列不满，将x插入到队尾IF q.length=m THENadd_queue:=false队列满ELSEq.rear:=(q.rear+1)mod m;q.elemq.rear:=x;q.length;=q.length+1;add_queue:=true入队成功ENDF;FUNC dd_queue(VAR q:cyclicqueue;x;elemtype):boolean;q是由尾指针和长度标志的循环队列，本算法是出队操作，若队列不空，将将队头元素出列，并赋给x，队长度减IF q.length=0THEN dd_queue:=false队空ELSEfront;=(q.rear-q.length+1+m)mod mx:=q.elemfrontq.length:=q.length-1ENDF;第四章第四章串 一、内容提要 1、 1、是数据元素为字符的线性表，串的定义及操作。 2、 2、的基本操作，编制算法求串的其它操作。 3、 3、的存储结构，因串是数据元素为字符的线性表，所以存在“结点大小“的问题。 静态和动态（块链结构，堆结构）存储的优缺点。 4、 4、朴素模式匹配算法及改进（KMP）算法。 二、学习重点 1、 1、串的基本操作，编写串的其他操作（如index,replace等）。 2、在串的模式匹配中，求匹配串的nextval函数值。 3、尽管朴素的模式匹配的时间复杂度是O(m*n),KMP算法是O(m+n),但在一般情况下，前者实际执行时间近似O(m+n),因此至今仍被采用。 KMP算法仅在主串与模式串存在许多“部分匹配”时才显得比前者块的多，其主要优点是主串不回嗍。 5、 5、串操作在存储结构下的实现。 三、例题解析 1、利用串的如下基本运算create(s),assign(s,t),length(s),substr(s,start,len),concat(s1,s2),编写操作replace的算法PROC replace(VAR s:string;t,v:string);本算法实现串的置换操作，用串v置换串s中所有非重叠的t串。 i:=INDEX(s,t);判s中有无tIF i0THENCREATE(temp,);t为临时串变量，存放部分结果m:=LENGTH(t);n:=LENGTH(s);WHILE i0DOASSIGN(temp,CONCAT(temp,SUBSTR(s,1,i-1),v);用v替换t形成部分结果ASSIGN(s,SUBSTR(s,i+m,n-i-m+1);t串以后形成新s串n:=n-(i-1)-m;i:=INDEX(s,t);ASSIGN(s,CONCAT(temp,s);将剩余s连接临时串t再赋给sENDP;FUNC index(s1:string;t:string):integer;本算法求串t在串s中的第一次出现。 结果是若t在s中，则给出串t的第一个字符在串s中的位置，若不存在，则返回0j:=1;m:=length(s);n:=length(t);eq:=true;WHILE(j=m-n+1)AND eqDOIFequal(substr(s,j,n),t)THEN eq:=false ELSEj:=j+1；IF j=m+n-1THEN index:=j ELSEindex:=0ENDF；index【讨论】本题是用给定的基本操作，编写其它操作的算法。 这种类型题较多，必须严格按题的要求来做，不准选择具体存储结构。 否则，即使全对，也很难得分。 22设目标为t=abcaabbabcabaacbacba,模式串p=abcabaa; (1)计算P的NEXTVAL函数值； (2)不写出算法，只画出利用KMP算法进行模式匹配时每一趟的匹配过程；【解答】 （1）P的NEXTVAL函数值如下；j1234567_模式p a b c a b a anextval(j)0110102 (2)a b c a a bb a bc a b aa c bacbaabcab第一趟匹配abc第二趟匹配a第三趟匹配abcabaa第四趟匹配成功【讨论】为写NEXTVAL方便，可先写出NEXT函数值，在由此求NEXTVAL. 3、字符串s满足下式，其中HEAD和TAIL的定义同广义表类似，如HEAD(XYZ)=X,TAIL(XYZ)=YZ,则S=concat(head(tail(s),head(tail(tail(s)=dc求字符串s。 可供选择的答案是（A）abcd(B)acbd(C)acdb(D)adcb正确答案是（D）。 第五章数组和广义表 一、 一、内容提要1，1，数组的逻辑结构定义及存储，2，2，稀疏矩阵（含特殊矩阵）的存储及运算。 3，3，广义表的定以及存储。 4，4，广义表运算的递归算法。 二、学习重点1，1，数组（主要是二维）在以行序为主的存储中的地址计算方法。 2，2，特殊矩阵在压缩存储时的下标变换。 3，3，稀疏矩阵的三元组表存储结构及矩阵移植的算法。 4，4，稀疏矩阵的十字链表存储方法及十字链表生成算法。 5，5，广义表的HEAD和TAIL运算。 6，6，给定广义表画出其存储结构。 7，7，从广义表的递归算法，掌握如何编写递归算法。 三、例题解析 1、字符串二维数组A0.8,1.10，每个元素由6个字符组成，每个字符占一个存储单元，则 （1）存放A需要多少个字节？ （2）A的第8列和第5行共占多少字节？ (3)按行序存储时，A8,5和按列存储时哪个元素时的地址相同？【解答】 （1）540 （2）108 （3）A3,10 2、编写算法，将自然数1-n2按蛇形填入n xn矩阵中。 例如，（142）如右图所示。 【分析】本题要求在N的方阵中填人N2个数，关键是控制下标。 设坐标原点在矩阵的左上角，且i是向下增长，j向右增长。 原点的坐标为（1，1）。 【算法】PROC sqrmgc(VAR a:arr;n:integer);本算法将自然数1-n2按蛇形填入N XN矩阵中,a是二维数组i:=1;j:=1;k:=1;WHILE(i=n)AND(j=n)DOWHILE(i0)DOai,j:=k;i:=i+1;j:=j-1;k:=k+1IF j1THEN IF i0)AND(j=N)DOai,j:=k;i:=i-1;j:=j+1;k:=k+1IF i1THEN IFj=n THENi:=1ELSEi:=i+2;j:=nELSEj:=n;i:=i+2ENDP;sqrmgc 3、求下列广义表操作结果 (1) (1)HEAD(TAIL(HEAD(a,b),(c,d) (2) (2)TAIL(HEAD(TAIL(a,b),(c,d)【解答】 （1）b (2)(d) 4、利用广义表的HEAD和TAIL操作，写出如上题的表达式，把原子banana从下列广义表中分离出来。 （1） （1）L1=（apple,(pear),(banana),(orange)）; （2） （2）L2=(apple,(pear,(banana),orange);【解答】 (1)HEAD(HEAD(HEAD(TAIL(TAIL(L1) (2)HEAD(HEAD(TAIL(HEAD(TAIL(L1)第六章第六章树和二叉树 一、内容提要 1、树是复杂的非线性数据结构，树，二叉树的递归定义，基本概念，术语。 2、二叉树的性质，存储结构。 3、二叉树的遍历算法（递归，非递归）。 4、线索二叉树 5、树的存储结构，树、森林的遍历及和二叉树的相互转换。 6、二叉树的应用表达式求值、判定问题及哈夫曼树和哈夫曼编码。 二、学习重点（本章内容是本课程的重点） 1、二叉树性质及证明方法，并能把这种方法推广到K叉树。 2、二叉树遍历的递归算法，本书中介绍了三种（先、中、后序）方法，另三种也应会用。 前序和中序的非递归遍历。 遍历是基础，由此导出许多实用的算法，如求二叉树的高度、各结点的层次数、度为 0、 1、2的结点数，二叉树的相似、全等、复制等等的算法。 3、由二叉树的遍历的前序和中序序列或后序和中序序列可以唯一构造一棵二叉树，手工模拟及编写算法。 由前序和后序序列不能唯一确定一棵二叉树。 4、二叉树线索化的实质是建立结点在相应序列中的前驱和后继之间的直接联系。 在何序（前、中、后）下进行何种（全、前驱、后继）线索化，并求某结点相应的前驱和后继。 5、完全二叉树的性质，顺序存储结构和二叉树链表存储结构的相互转换。 6、树的双亲表示法和孩子兄弟表示法间的相互转换。 7、树、森林和二叉树间的相互转换（“连线”、“切线”和“旋转”）。 8、哈夫曼树的定义、构造及求哈夫曼编码。 三、例题及分析在二叉树中查找其数据域为x的结点。 如存在，返回该结点指针，否则返回空指针。 【分析】可采用递归遍历算法。 【算法】PROC search(bt:bitreptr;x:datatype);bt是bitreptr型的二叉树，x是待查找数据值,本算法递归遍历二叉树，在遍历中进行查找。 算法中p是调用本过程的过程中定义的变量，初值为NIL，查找成功后，p指向数据域为x的结点。 found是初值为false的变量。 从本过程返回后，测试found以确定是否查找成功。 IF(btNIL)AND NOTfound THENIF bt.data=x THENp:=bt;found:=truesearch(bt.lchild,x);search(bt.rchild,x);ENDP;serch【讨论】本算法核心语句有三个（即第一个THEN后的语句第一个语句是“访问”根结点.后两个语句是递归遍历（相对位置不变）。 在这三个语句中，由“访问”语句所处位置不同（前、中、后），形成三种递归遍历方法前序、中序和后序。 Found是为查到x就立即（不再遍历未遍历结点）而设立的。 若要再考虑本算法的优化，则在两个调用语句中可加上If(bt.lchildNIL)AND NOTfound和If(bt.rchildNIL)AND NOTfound其优点是在左（右）为空时不必再调用，且一旦找到x就立即退出。 设二叉树采用二叉链表作为存储结构，试编写算法求二叉树的结点数。 【分析】计算二叉树结点数的数学模型如下f(bt)=0若bt=nil f(bt)=f(bt.lchild)+f(bt.rchild)+1否则【算法】FUNC nodes(bt:bitreptr):integer;IF bt=nil THENnodes:=0ELSEn1:=nodes(bt.lchild)n2:=nodes(bt.rchild)nodes:=ni+n2+1ENDFnodes【讨论】二叉树由根、左子树、右子树三部分组成，很多问题（如求叶子、度、度结点数），可分解到三部分求解，上面写出数学递归模型是有普遍意义的。 例如（）.二叉树相似f(t1,t2)=true若t1=t2=NIL f(t1,t2)=false若t1,t2中只有一个为NIL f(t1,t2)=f(t1.lchild,t2.lchild)AND f(t1.rchild,t2.rchild)若t1,t2均不为NIL (2)求二叉树的叶子结点数f(bt)=0当bt=nil f(bt)=1当bt左右子树均为空f(bt)=f(bt.lchild)+f(bt.rchild)否则（）求二叉树所有叶子结点的最大枝长0若bt.lchild=nil且bt.rchild=nil maxl(bt.lchild)+1若bt.rchild=nil max=maxl(bt.rchild+1)若bt.lchild=nil max(maxl(bt.rchild+1),maxl(bt.rchild)+1否则打印二叉树中结点x（假定存在）的所有祖先结点。 【分析】在二叉树的递归遍历等算法中，只有后序遍历才是最后访问根结点，因此有可能保留从根结点到待查结点的踪迹，这时可用栈，存放从根结点到x结点路径中的各祖先结点。 【算法】PROC printansctr(bt:bitreptr;x:datatype);bt是bitreptr型的二叉树，x是待查找数据值,本算法输出X结点的各祖先结点。 S是工作栈，存放X的祖先结点。 查到X后，依次输出S中数据即可。 initstack(s);p:=bt;push(s,p);WHILE NOTempty(s)DOWHILE NOTempty(s)AND(p.datax)DOpush(s,p);p:=p.lchildIF p.data=x THENWHILE NOT(empty(s)DOp:=pop(s);write(p.data)ELSE需要到右分枝去查x结点q:=nil;rend:=true;rend是为了在右分枝不空时就退出循环WHILE NOTempty(s)AND rendDOp:=pop(s);IF p.r=q THENq:=p右分枝为空时退栈ELSEpush(s,p);p:=p.rchild;rend:=falseENDP；printansctr第七章第七章图 一、内容提要11图的定义，概念、术语及基本操作。 22图的存储结构。 33图的遍历。 44图的应用（连通分量，最小生成树，拓扑排序，关键路经，最短路经）。 二、学习重点图是应用最广泛的一种数据结构，本章是这门课程的重点。 11基本概念中，连通分量，生成树，邻接点是重点。 22图是复杂的数据结构，也有顺序和链式两种存储结构数组表示法（重点是邻接距阵）和邻接表。 这两种存储结构对有向图和无向图均适用。 十字链表是有向图的另一种表示，将有向图的邻接表和逆邻接表合一。 邻接多重表是无向图邻接表的改进，将边结点的数量减少一半（正好等于边的数量）。 33图的遍历是图的各种算法的基础，应熟练掌握图的深度、广度优先遍历，手工模拟图的遍历中栈和队列指针状态的变化。 44在（强）连通图中，主过程一次调用深（宽）度优先遍历过程（dfs/bfs），即可遍历完全部顶点，故可以用此方法求出连通分量的个数，并能画出遍历中形成的深（宽）度优先生成树。 55连通图的最小生成树不是唯一的，但最小生成树边上的权值之和是唯一的。 应熟练掌握prim和kruscal算法，特别是手工分步模拟生成树的生成过程。 66拓扑排序是在有向图上对入度（先后）为零的顶点的一种排序，结果不唯一。 关键路经是在拓扑有序的前提下求出来的，从源点到汇点的最长路径。 应能掌握这两种算法，并熟练手工模拟。 理解“减少关键活动时间能缩短工期”，是指该活动为所有关键路径所共有，且减少到尚未改变关键路经的前提下才有效。 77从单源点到其他顶点，以及各个顶点间的最短路经问题，掌握算法，并熟练手工模拟。 三、例题解析 1、用邻接多重表实现图的各种运算。 【分析】在邻接多重表中，每条边用一个结点表示，不象在邻接表中那样用两条边来表示。 这在图的操作中，要比其他的存储结构要复杂的多。 PROC crt_graph(var g:adjmulist);g为教材中已定义的adjmulist类型变量，本算法建立有n个结点e条边的图的存储结构FOR I:=1TO nDO【read(gi.data;gi.firstedge:=nil)】建立顶点向量，各顶点所指向的第一条边指针为nilFOR r:=1TO eDO【read(vi,vj);读两结点i:=loc_vertex(g,vi);j:=loc_vertex(g,vj)new(p);p.ivex:=i;p.jvex:=j;p.ilink:=gi.firstedge;gi.firstedeg:=p将边（vi，vj）分别插入顶点vi，vj的边结点链表中。 】ENDP;crt_graph【讨论】在本算法中，设输入的边不含有重复边，即输入（vi，vj）后，即不应再输入（vi，vj），也不应再输入（vj，vi）。 否则，本算法应添加查询功能（即下面search过程）。 查询成功时该边不再加入到图的存储结构中。 FUNC search(g:adjmulist;I,j:1.vtxnum):edgeptr;本算法在图g中查询顶点vi，vj间的边结点是否已建立。 如是，则返回该边结点的指针，否则返回nilp:=gi.firstedge;found:=false WHILE(pNIL)AND NOTfound DOIF p.ivex=i结点中ivel，jvex域均可能为iTHEN IF p.jvex=j THEN found:=true ELSEp:=p.ilink顺ilink下找ELSE IF p.ivex=jp.jvex=iTHENfound:=true ELSEp:=p.jlink顺jlink下找;ENDF;searchPROC insert_edge(VAR g:adjmulist;vi,vj:vtxptr);本算法在邻接多重表中插入边（vi，vj）i:=loc_vertex(g,vi);j:=loc_vertex(g,vj);fp:=search(g,i,j);IF fp:=nil若边（vi，vj）在图中不存在THEN【new(p);p.ivex:=i;p.jvex:=j;p.ilink:=gi.firstedge;gi.firstedge:=p;p.jlink:=gj.firstedge;gj.firstedge:=p;】ENDP;insertPROC insert_vertex(VAR g:adjmulist;v:vtxptr);本算法在邻接多重表中插入顶点V。 设顶点向量足够大，插入一顶点也就是加一个向量元素，设m是已有顶点数，则gm+1.data:=v;gm+1.firstedge:=nil;ENDP;insert_vertexPROC delete_edge(VAR g:adjmulist;vi,vj:vtxptr);本算法在邻接多重表g中删除边（vi，vj）i:=loc_vertex(g,vi);j:=loc_vertex(g,vj);fp:=search(g,i,j);IF fpnil THEN【p:=gi.firstedge;q:=nil;修改i的链表边结点(vi,vj)的前驱的指针WHILE pfp DO【q:=p;IF p.ivex=i THEN p:=p.ilink ELSEp:=p.jlink】IFq=nil删除的边是顶点vi的第一边结点THEN IF p.ivex=i THENgi.firstedge:=p.ilink ELSEgi.firstedge:=p.jlink ELSE所删除的不是vi的第一边结点IF q.ivex=i THENIFp.ivex=i THENq.ilink:=p.ilink ELSEq.ilink:=p.jlink ELSEIFp.ivex=i THENq.jlink:=p.ilink ELSEq.jlink:=p.jlink;p:=gj.firstedge;q:=nil;修改j的链表边结点(vi,vj)的前驱的指针从vj的边结点链表中找到（vi，vj）边，修改前驱指针，算法同上，故略dispose(fp);】ENDP；delete_edgePROC delete_vertex(VAR g:adjmulist;v:vtxptr);删除顶点的算法，该顶点删除后，在其顶点向量数据域中作标记，且要删除与该顶点相关的所有边i:=loc_verdex(g,v);p:=gi.firstedge;WHILE pnil DO【IFp.ivex=I THENs:=p.ilink记住下一边结点ELSE s:=p.jlink;IFi=p.ivex THENdelete_edge(g:,v,gp.jvex.data)ELSE delete_edge(g:,v,gp.ivex.data)p:=s】ENDP;delete_vertex 2、编写对图的深度优先非递归遍历算法。 【分析】使用栈，调用过程的算法同教材，对被调用过程编写如下PROC dfs(g:adjlist;v0:vtxptr);本算法从顶点v0开始。 在图g中进行深度优先遍历。 算法中visited是在主过程中已赋值false的辅助数组，s是元素为边（弧）结点的工作栈。 initstack(s);write(v0);visitedv0:=true;p:=gv.firstarc;WHILE(pnil)AND NOTempty(s)DO【WHILE pnil DOIF visitedp.adjvexTHENp:=p.nextarc ELSE【write(p.adjvex);push(s,p);visitedp.adjvex:=true;p:=gp.adjvex.fistarc;】IFNOTempty(s)THEN【p:=pop(s);p:=p.nextarc】ENDP;dfs第八章动态存储管理 一、内容提要11动态存储管理指的是在用户需要时给分配内存，而在用户结束使用时，系统要收回用户所占空间。 22可利用空间表的三种结构形式结点固定大小；分几种规格；任意大小。 33可利用空间表的两种组织形式目录表，链表。 44可利用空间表的分配方式首次拟合法，最佳拟合法，最差拟合法。 55可利用空间表的分配和回收的两种基本实现方法边界标识法，伙伴系统。 66无用单元回收和紧缩存储的概念。 二、学习重点 1、概念可利用空间表及分配方式，紧缩存储，伙伴系统，等。 2、边界表示法的分配及回收算法。 3、伙伴系统的分配及回收算法。 三、例题解析设有大小为512字节的存储，有6个用户申请大小分别为23，45，52，100，11和19字节的存储空间，然后再顺序释放大小为45，52和11的占用空间。 假设以伙伴系统实现动态存储管理。 11画出可利用空间表的初始化状态。 22画出为6个用户分配的存储空间后可利用空间表的状态，以及每个用户得到的存储块的起始地址。 33画出在3个占用块回收后可利用空间表的状态。 【解答】11因为512=29，所以初始化为20212223242526272829092, (1)23=25=32,所以要分配25字节一块占用块首址0。