数据结构复习纲要.doc

第一章 绪论
一、内容提要
1 数据结构研究的内容。
2 基本概念：数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型、多形数据类型。
3 算法的定义及五个特征。
4 算法描述：类PASCAL语言。
5 算法设计要求。
6 算法分析。

二、学习重点
1 数据结构的“三要素”：逻辑结构、物理（存储）结构及在这种结构上所定义的操作（运算） 。
2 抽象数据类型的定义、表示和实现方法。
3 类PASCAL书写规范，过程（函数）中值参和变参的差别，过程调用规则。
4 用计算语句频度来估算算法的时间复杂度。

三、例题解析
1 写出以下各语句执行次数（左边括号内数字为语句序号）
(1) FOR i:=1 TO n DO
(2) FOR j:=1 to n DO
(3) [ c[I,j] := 0;
(4) FOR k:=1 TO n DO
(5) c[I,j]:=c[I,j]+a[I,k]*b[k,j]
]
[答案]：各语句执行次数（频度）分别为n+1，n(n+1), n2 , n2(n+1), n3
[分析]：最容易发生的错误，是将第一个语句的执行次数答成n。

2 编写最优算法，从小到大依次输出顺序读入的三个整数
PROC asscending;
{本算法对读入的三个整数进行排序，然后按从小到大输出}
{算法中核心语句如下}
read(a,b,c);
IF a>b
THEN [t:=a; a:=b; b:=t]; {a,b按正序排序}
IF b>c
THEN [t:=c; c:=b; {c为最大}
IF a<t THEN b:=t {b为中间值}
ELSE [b:=a; a:=t] {a,b正序}
WRITELN(a:4,b:4,c:4);
ENDP; {assending}

[分析]：本题正确算法有多种，但上面是最优算法：最好情况下只经过两次比较且无数据移动，而在最
坏情况下，也只是经过三次比较，七个赋值语句就完成了排序。
在本课程教学中，强调“好”的算法, 不仅仅是结果正确, 而且是最优的算法。这与PASCAL语言教学中的要求有很大不同。
算法是供人来阅读的，必须牢记这一点。算法中语句的书写格式采用缩进规则，保留字用大写
，其余标识符小写，提高了算法的易读性。

第二章 线性表

一 、内容提要

1．线性表是元素间约束力最强的一类数据结构。
2．线性表的逻辑结构定义，对线性表定义的操作。
3．线性表的存储结构：顺序存储结构和链式存储结构。
4．线性表的操作在两种存储结构中的实现。
5．一元多项式的线性表表示方法，及高次（稀疏）多项式的抽象数据类型定义、表示和加法的实现。

二 、学习重点

1． 线性表的逻辑结构，指线性表的数据元素间存在着线性关系。在顺序存储结构中，元素存储的先后位置反映出这种线性关系，而在链式存储结构中，是靠指针来反映这种关系的。
2． 顺序存储结构用向量（一维数组）表示，给定下标，可以存取相应元素，属于随机存取的存储结构。
3． 尽管“只要知道某结点的指针就可以存取该元素”，但因链表的存取都需要从头指针开始，顺链而行，故链表不属于随机存取结构。
4． 链表是本章学习的重点和难点。要理解头结点，首元结点和元素结点的差别。理解头结点是为了在插入、删除等操作时，为了算法的统一而设立的（若无头结点，则在第一元素前插入元素或删除第一元素时，链表的头指针总在变化）。掌握通过画出结点图来进行链表的生成、插入、删除、遍历等操作。
5． 链表操作中应注意不要使链意外“断开”。因此，若在某结点前插入一个元素，或删除某元素，必须知道该元素的前驱结点的指针。
6． 从时间和空间复杂度的角度综合比较线性表在顺序和链式两种存储结构下的特点。
7． 静态链表是又一重点和难点。应和链表进行比较、理解。例如，在有头结点的链表情况下，第一元素是p:=la^.next，而在静态链表中则i:=sa[0].next；相对p:=p^.next,有i:=sa[i].next来找到第i个元素的后继。

三、例题解析

１．设线性表以顺序存储结构存于a(1..n)中，试编写算法将该线性表就地逆置。
　　【分析】　向量逆置有几种方法，如逆向读入到另一数组中，在正向对应赋值，即：
FOR i:=n DOWNTO 1 DO b[n-i+1]:=a[i]; FOR i:=1TO n DO a[i]:=b[i];
这里要求“就地逆置”，即不能另用一数组空间。
【算法】
　　　　　PROC invert(VAR a:arr; n:integer);
　　　{a是存储线性表的一维数组，有n 个元素，本算法将a逆置。}
FOR i:=1TO (n DIV 2) DO a[i]↔a[n-i+1];
endp;
【讨论】　将n个元素的一维数组逆置，为什么循环控制变量用n div 2，而不用n？

　　　　　　　　　２．编写在单链表上进行排序的算法
　　　　　　　　　　　【分析】　这里使用插入排序。链表中插入元素要知道待插入元素位置的前驱，　　以pre表示之。结束的条件是链表为空。
　　　　 【算法】
　PROC insertsort(VAR la:linklist);
{la是带头结点的单链表的指针，本算法将链表中元素正序排序。算法的基本思想是先假定第一个元素有序，然后从第二个元素开始，依次插入到有序的表中，直到全部元素插入完为止}
　　　　　　　　　　　　　　　　　p:= la^.next^.next;{假定链表非空，即至少有一个结点}
　　　　　　　　　　　　　　　　　la^.next^.next:=nil;{设有序链表中当前只有一个结点}
found:=false;
　　　　　　　　　　　　　　　　　WHILE (p<>nil)AND NOT found DO
[s:=p^.next;{记住下一个结点}
　　　　　　　　　　　　　　　　　　　pre:=la;
q:=la^.next;
　　 found:=false;
　　　　　　　　　　　　 WHILE(q<>nil)AND NOT found DO
IF q^.data<p^.data THEN [pre:=q; q:=q^.next]
ELSE found:=true;
p^.next:=q;
pre^.next:=p;{p结点插入}
p:=s;{取下一个结点}
]
ENDP; {insertsort}
【讨论】算法中found为一布尔变量，为的是在链表到尾前，如找到p的插
入位置，即可退出WHILE循环。这里循环条件未写成：
（p<>nil）AND (q^.data<p^.data)
因为若q=nil ，则再引用q^.data是无意义的。请记住这种退出循环，引入布尔变量的作法。

3．设两个非递减有序的线性表各有m和n个元素（m>0,n>0）,分别存于一维数组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 (i>0) AND (j>0) DO
IF a[i]>b[j] THEN [a[k]:=a[i]; i:=i-1; k:=k-1]
ELSE [a[k]:=b[j]; j:=j-1; k:=k-1];
WHILE (j>0) DO [a[k]:=b[j]; j:=j-1; k:=k-1];
{若b表中尚有元素，则传至a中相应位置}
　　　【讨论】 本算法至多比较m+n次，往a中赋值m+n次。最好情况是比较n次，往a中赋值n次，该种情况是b中最小元素不小于a中最大元素。
　　　　　　问题：为什么在退出第一个WHILE循环后，不讨论（即没有）WHILE i>0的情况？

第三章 栈和队列

内容提要

1．从数据结构角度讲，栈和队列也是线性表，其操作是线性表操作的子集，属操作受限的线性表。但从数据类型的角度看，它们是和线性表大不相同的重要抽象数据类型。
2．栈的定义及操作。栈是只准在一端进行插入和删除操作的线性表，该端称为栈的顶端。
3．栈的顺序和链式存储结构，及在这两种结构下实现栈的操作。
4．栈的应用：表达式求值，递归过程及消除递归。
5．队列的定义及操作，队列的删除在一端（尾），而插入则在队列的另一端（头）。因此在两种存储结构中，都需要队头和队尾两个指针。
6．链队列空的条件是首尾指针相等，而循环队列满的条件的判定，则有队尾加1等于
队头和设标记两种方法。

学习重点

1．栈和队列操作在两种存储结构下的实现。
2．中缀表达式转成前缀、后缀表达式并求值。
3．用递归解决的问题：定义是递归的，数据结构是递归的，及问题的解法是递归的，
掌握典型问题的算法。
4． 链队列删除时为空的处理（令队尾指针指向队头）。特别是仅设尾指针的循环链队
列的各种操作的实现。
5． 循环队列队空定义为队头指针等于队尾指针，队满则可用一个单元（教材中所示）
及设标记办法（下面例题）。这里特别注意取模运算。
6． 在后续章节中要注意栈和队列的应用，如串中心对称的判定，二叉树遍历的递归
和非递归算法，图的深度优先遍历等都用到栈，而树的层次遍历、图的宽度优先遍
历等则用到队列。

例题解析

1．两栈共享一向量空间，编写入栈和出栈算法。
TYPE
TwoWayStack=RECORD {双栈共享一向量空间}
elem:ARRAY[1..m] OF elemtype;
top:ARRAY[0..1] OF 0..m+1; {两个栈顶指针}
END;
PROC inistack(VAR tws:TwoWayStack); {初始化}
{初始化双向栈tws为空}
tws.top[0]:=0; { 左端栈指针}
tws.top[1]:=m+1; { 右端栈指针}
ENDP; {inistack}

PROC PUSH(VAR tws:TwoWayStack;i:0..1; x:elemtype;VAR ofw:boolean);
{若双向栈tws不满,则将x插入到i端,成功时ofw为true,失败为false}
IF(tws.top[1]-tws.top[0])<>1
THEN {栈未满}
CASE i OF
0:tws.top[0]:=tws.top[0]+1;tws.elem[tws.top[0]]:=x;ofw:=true
1:tws.top[1]:=tws.top[1]-1;tws.elem[tws.top[1]]:=x;ofw:=true
ENDC
ELSE ofw:=false;( 栈满)
ENDP; {push}
PROC POP(VAR tws:TwoWayStack;i:0..1;VAR x:elemtype;VAR underflow:boolean);
{若双向栈tws非空,则将i端退栈,栈空时underflow为true}
CASE i OF
0:IF tws.top[0]=0 {栈空}
THEN[underflow:=true;return(underflow)]
ELSE[ tws.top[0]:=tws.top[0]-1;
x:=tws.elem[tws.top[0]+1]; {弹出元素}
];
1:IF tws.top[1]=m+1 {栈空}
THEN[underflow:=true;return(underflow)]
ELSE[ tws.top[1]:=tws.top[1]+1;
x:=tws.elem[tws.top[1]-1]; {弹出元素}
];
ENDC
ENDP; {pop }
【讨论】 上面算法中用0和1代表两端，且按操作在哪端来分两种情况进行讨论，逻辑清楚。也可用一个公式表示插入（进栈）和删除（退栈）指针位置。例如，插入时top=top+1-2*i,删除时top=top-1+2*i。表达简洁，但不如上面清楚易读。

2．将中缀表达式转换成后缀表达式，并进行表达式求值。
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 IN op) THEN ［ insert(exp2,w); read(w)　］;
ELSE CASE precede(GETTOP(s),w) OF
'<': [ PUSH(S,w); read(w) ];
'=': IF w=’)’ THEN {遇右括号后，运算符退栈并送结果表达式，
　　　　　　　　　　　　　　　　　　直至左括号}
[ x:=POP(S);
WHILE x<>’(‘ DO [insert(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 NOT empty(exp2) DO
IF NOT (w IN op) THEN ［ PUSH(sn,w); read(w)　］;
ELSE CASE precede(GETTOP(s),w) OF
'<': [ PUSH(s,w); read(w) ];
'>': [ 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:=ARRAY[0..m-1] OF elemtype;
rear,front:0..m-1
tag: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) {队满}
ELSE[cq.rear:=(cq.rear+1) MOD m;
cq.elem(cq.rear):=r;
IF cq.tag=0 THEN cq.tag:=1 {由空变不空标记}
]
ENDP;
PROC DELQUEUE(VAR cq:cyclicqueue);
　　　　　｛cq是由头尾指针和标志域的循环队列，本算法是出队操作，若队列非空｝
　　　　　｛则将队头元素出队｝
IF cq.tag=0
THEN return(false) {队空}
ELSE[cq.front:=(cq.front+1) MOD m;
IF cq.front=cq.rear THEN cq.tag:=0 {队空}
]
ENDP;

CONST m=maxlen;　　｛队列长度｝
TYPE
cyclicqueue=RECORD　　　　｛只设尾指针和队列长度的循环队列｝
elem: ARRAY[0..m-1] OF 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
THEN add_queue:=false {队列满}
ELSE [ q.rear:=(q.rear+1) mod m;
q.elem[q.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=0
THEN dd_queue:=false {队空}
ELSE [front;=(q.rear-q.length+1+m) mod m
x:=q.elem[front]
q.length:=q.length-1
]
ENDF;

第四章 串

一、内容提要

1、 是数据元素为字符的线性表，串的定义及操作。
2、 的基本操作，编制算法求串的其它操作。
3、 的存储结构，因串是数据元素为字符的线性表，所以存在“结点大小“的问题。静态和动态（块链结构，堆结构）存储的优缺点。
4、 朴素模式匹配算法及改进（KMP）算法。

二、学习重点

1、 串的基本操作，编写串的其他操作（如index,replace等）。
2、在串的模式匹配中，求匹配串的nextval 函数值。
3、尽管朴素的模式匹配的时间复杂度是O(m*n), KMP算法是O(m+n),但在一般情况下，前者实际执行时间近似O(m+n),因此至今仍被采用。KMP算法仅在主串与模式串存在许多“部分匹配”时才显得比前者块的多，其主要优点是主串不回嗍。
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中有无t}
IF i<>0
THEN [ CREATE (temp, ‘’); {t为临时串变量，存放部分结果}
m:=LENGTH(t); n:=LENGTH(s);
WHILE i<>0 DO
[ ASSIGN (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再赋给s}
]
ENDP;
FUNC index(s1:string; t:string):integer;
{本算法求串t在串s中的第一次出现。 结果是：若t在s中 ，则给出串t的第一个字符在串s中的位置，若不存在，则返回0}
j:=1;m:=length(s); n:=length(t); eq:=true;
WHILE (j<=m-n+1) AND eq DO
IF equal(substr(s,j,n),t)
THEN eq:=false
ELSE j:=j+1；
IF j<=m+n-1 THEN index:=j
ELSE index:=0
ENDF；{index}
【讨论】 本题是用给定的基本操作，编写其它操作的算法。这种类型题较多，必须严格按题的要求来做，不准选择具体存储结构。否则，即使全对，也很难得分。

2 设目标为 t=’abcaabbabcabaacbacba’,模式串 p=’abcabaa’;
(1)计算P的NEXTVAL函数值；
(2)不写出算法，只画出利用KMP算法进行模式匹配时每一趟的匹配过程；
【解答】
（1）P的 NEXTVAL 函数值如下；
j 1 2 3 4 5 6 7
_______________________________
模式p a b c a b a a
nextval(j) 0 1 1 0 1 0 2
(2)
a b c a a b b a b c a b a a c b a c b a
a b c a b 第一趟匹配
a b c 第二趟匹配
a 第三趟匹配
a b c a b a a 第四趟匹配成功
【讨论】 为写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， 数组的逻辑结构定义及存储，
2， 稀疏矩阵（含特殊矩阵）的存储及运算。
3， 广义表的定以及存储。
4， 广义表运算的递归算法。

二、学习重点

1， 数组（主要是二维）在以行序为主的存储中的地址计算方法。
2， 特殊矩阵在压缩存储时的下标变换。
3， 稀疏矩阵的三元组表存储结构及矩阵移植的算法。
4， 稀疏矩阵的十字链表存储方法及十字链表生成算法。
5， 广义表的HEAD和TAIL 运算。
6， 给定广义表画出其存储结构。
7， 从广义表的递归算法，掌握如何编写递归算法。

三、例题解析

1、字符串二维数组A[0..8,1..10] ，每个元素由6个字符组成，每个字符占一个存储单元，则（1）存放A需要多少个字节？
（2）A的第8列和第5行共占多少字节？
(3) 按行序存储时，A[8,5]和按列存储时哪个元素时的地址相同？
【解答】 （1） 540 （2） 108 （3） A[3,10]

2、编写算法，将自然数1---n2按蛇形填入n x n矩阵中。
例如，（1—42）如右图所示。
【分析】本题要求在N的方阵中填人N2个数，关键是控制
下标。设坐标原点在矩阵的左上角，且i是向下增长，j向
右增长 。原点的坐标为（1，1）。
【算法】
PROC sqrmgc(VAR a:arr;n:integer);
{ 本算法将自然数1--n2 按蛇形填入N X N 矩阵中,a是二维数组}
i:=1; j:=1; k:=1;
WHILE (i<=n) AND (j<=n) DO
[ WHILE (i<=n) AND (j>0) DO
[ a[i,j]:=k; i:=i+1; j:=j-1; k:=k+1 ]
IF j<1 THEN IF i<=n THEN j:=1
ELSE [j:=j+2;i:=n ]
ELSE [i:=n; j:=j+2]
WHILE (i>0) AND (j<=N) DO
[ a[i,j]:=k; i:=i-1; j:=j+1; k:=k+1 ]
IF i<1 THEN IF j<=n THEN i:=1
ELSE [i:=i+2;j:=n ]
ELSE [j:=n; i:=i+2 ]
]
ENDP; {sqrmgc}

3、求下列广义表操作结果：
(1) HEAD(TAIL(HEAD(((a,b),(c,d))))
(2) TAIL(HEAD(TAIL(((a,b),(c,d))))
【解答】 （1）b (2) (d)

4 、利用广义表的HEAD和TAIL操作，写出如上题的表达式，把原子banana从下列广义表中分离出来。
（1） L1=（apple,(pear),((banana)),(((orange)))）;
（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 (bt<>NIL ) AND NOT found
THEN [IF bt^.data=x
THEN [ p:=bt; found:=true ]
search (bt^.lchild, x);
search (bt^.rchild, x);
]
ENDP; {serch}
【讨论】
本算法核心语句有三个（即第一个THEN后的语句：第一个语句是“访问”根结点. 后两个语句是递归遍历（相对位置不变）。在这三个语句中，由“访问”语句所处位置不同（前、中、后），形成三种递归遍历方法：前序、中序和后序。
Found是为查到x就立即（不再遍历未遍历结点）而设立的。若要再考虑本算法的优化，则在两个调用语句中可加上
If (bt^.lchild<>NIL) AND NOT found 和
If (bt^.rchild<>NIL) AND NOT found
其优点是在左（右）为空时不必再调用，且一旦找到x就立即退出。

２．设二叉树采用二叉链表作为存储结构，试编写算法求二叉树的结点数。
【分析】
　　　　计算二叉树结点数的数学模型如下：
f(bt)=0 若bt=nil
f(bt)=f(bt^.lchild) +f(bt^.rchild) +1 否则
【算法】
　　　　FUNC nodes(bt:bitreptr):integer;
IF bt=nil
THEN nodes:=0
ELSE [ n1:=nodes(bt^.lchild)
n2:=nodes(bt^.rchild)
nodes:=ni+n2+1
]
ENDF {nodes}
【讨论】 二叉树由根、左子树、右子树三部分组成，很多问题（如求叶子、度１、度２结点数），可分解到三部分求解，上面写出数学递归模型是有普遍意义的。例如：
（１）. 二叉树相似：
　　　　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 NOT empty(s) DO
[ WHILE NOT empty(s) AND (p^.data<>x) DO
[ push(s,p); p:=p^.lchild ]
IF p^.data=x
THEN WHILE NOT (empty(s)) DO [p:=pop(s); write(p^.data) ]
ELSE {需要到右分枝去查x结点}
[q:=nil; rend:=true; {rend是为了在右分枝不空时就退出循环}
WHILE NOT empty(s) AND rend DO
[p:=pop(s);
IF p^.r=q THEN q:=p {右分枝为空时退栈}
ELSE [ push(s,p);p:=p^.rchild; rend:=false]
]
ENDP； { printansctr}

第七章 图

一、内容提要

1． 图的定义，概念、术语及基本操作。
2． 图的存储结构。
3． 图的遍历。
4． 图的应用（连通分量，最小生成树，拓扑排序，关键路经，最短路经）。

二、学习重点

图是应用最广泛的一种数据结构，本章是这门课程的重点。
1 基本概念中，连通分量，生成树，邻接点是重点。
2 图是复杂的数据结构，也有顺序和链式两种存储结构：数组表示法（重点是邻接距阵）和 邻
接表。这两种存储结构对有向图和无向图均适用。十字链表是有向图的另一种表示，将有向图的邻接表和逆邻接表合一。邻接多重表是无向图邻接表的改进，将边结点的数量减少一半（正好等于边的数量）。
3 图的遍历是图的各种算法的基础，应熟练掌握图的深度、广度优先遍历，手工模拟图的遍历中栈和队列指针状态的变化。
4 在（强）连通图中，主过程一次调用深（宽）度优先遍历过程（dfs/bfs），即可遍历完全部顶点，故可以用此方法求出连通分量的个数，并能画出遍历中形成的深（宽）度优先生成树。
5 连通图的最小生成树不是唯一的，但最小生成树边上的权值之和是唯一的。 应熟练掌握prim和kruscal算法，特别是手工分步模拟生成树的生成过程。
6 拓扑排序是在有向图上对入度（先后）为零的顶点的一种排序，结果不唯一。关键路经是在拓扑有序的前提下求出来的，从源点到汇点的最长路径。应能掌握这两种算法，并熟练手工模拟。理解“减少关键活动时间能缩短工期”，是指该活动为所有关键路径所共有，且减少到尚未改变关键路经的前提下才有效。
7 从单源点到其他顶点，以及各个顶点间的最短路经问题，掌握算法，并熟练手工模拟。

三、