六大专业课之数据结构与算法参考书

第一章绪为什么要学习数据结和软、硬件的发展，非数值计算问题越来越显得重要。据统计，处理非数值计算性问[1]学生信息检索系统。当我们需要查找某个学生的有关情况的时候；或者想查诸如此类的还有自动查号系统、考试查分系统、仓库库存管理系统等。在这类文 男98女98刘女99男99男99女2000男2000男2000刘女2001男2001862862刘5174200020019899（b）索引 （d）年级索引1.1学生信息查询系统中的数据[2]八皇后问题。在八皇后问题中，处理过程不是根据某种确定的计算法则，而。 。 。 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。 。。。。 。。。。[3]教学计划编排问题。一个教学计划包含许多课程，在教学计划包含的许多课到vj之间存在有向边<vi，vj>，则表示课程i必须先于课程j进行。无接1.3（DaaO）或（DtaEtlss，A和顶点BA和。数据结构（DataStructure）是指互相之间存在着一种或多种关系的数据元素的集合。 1.4四类基本结构的示意其中，D是数据元素的有限集，R是D上关系的有限集。1.5所示。1.5数据结构课程内容体构已成为一种新的趋势，越来越们所重视。数据类式所有可能的取值范围，以及在这些值上允许进行的操作。因此，数据类型（DataType）是抽象抽象数据类型（AbstructDataType，简称ADT）是指一个数学模型以及定义在该模算法特算法描算法性能分析与规模（通常用正整数n表示法中原操作重复执行的次数是规模n的某个函数T(n)。f(n)≤

f(n)＝例如，一个程序的实际执行时间为T(n)＝2.7n3+3.8n2+5.3。则T(n)＝Ο(n3)Complexity第二章线性线性表的逻线性表需要说明的是：ai为序号为i的数据元素（i=1,2,…,n），通常它的数据类型抽生类型;在字符串中，它是字符型;等等。线性表的基本操Init_List(L)Length_List(L)⑶取表元：的那个元素的序号或地址，称为查找成功否则，在L中未找到值为⑸插入操作：⑹删除操作：体的算法，而算法的实现只有在结构确立之后。线性表的顺序及运算实序块元种式用图1设a１的地址为Loc(a１，每个数据元素占d个地址，则第i个数据元素的地址为： 因此需用一个变lastlast起一个

………图2.1线性表的顺序示意 } L所示。表长别存放在L.data[0]至L.data[L.last]中 *L 序表图2.2线性表的顺序示意基本运 的实SeqList*init_SeqList({SeqList*L; returnL;}算法{SeqList*L;}(a1，a2，，ai-1，ai，ai+1，，an)成为表长为n+1表:)i的取值范围为1<=i<=n+1 intif(L- /*结点移动 return(1); }算法…………x……1n-MAXSIZE-插入 插入图2.3顺序表中的插aiann－i＋1iEin

ni

pi(ni1)n

n Eini

pi(ni1)

n1i

(ni1)2删除运算Dele线性表的删除运算是指将表中第i个元素从线性表中去掉，删除后使原表长为n的 (a1，a2，...，ai-1，ai，ai+1，...，an)n－1(a1，a2，...，ai-1ai+1，...，an)i的取值范围为：1<=i<=n修改last指针(相当于修改表长)…………1MAXSIZE- 图2.4顺序表中的删除intDelete_SeqList(SeqList*L;int{ /*检查空表及删除位置的 }算法删除第i个元素，i1<=i<=n否则第i个元素不存在，因此，要检查删除ai+1～ann-i个元素，所以平均移动数据元素的次nEdei

pi(ni nEde

i

p(ni)ini

(ni)n2a1起依次和x比较，直到找到一个与x相等的数到与x相等的元素，返回-1。 intif(i>L- returni;/*返回的是位置}算法a1=xan=xn次成功。平均比较次数为（n+1）/2，时顺序例2．1(a1，a2，...，an)重新排a1为界的两部分：a1前面的值均a1小，a1a1大(这里假设数据元素的类型具有可比性,不妨设为整型)，操作前后如图2.5所示。这一操作称为划分。a1也称为基准。aIa1a1a1之间......划分 划分图2.5顺序表的划void inti,j; /*将基准置入x中if(L- y=L-for(j=i-1;j>=0;j--)/*移动}}算法及置入，所以移动i-1+2次，在情况下，a1后面的结点都小于a1，故总的移动次数为： i

(i12)i

(i1)n*(n32即情况下移动数据时间性能为Ｏ(ｎ２)算法思路：依次扫描通过A和B的元素，比较当前的元素的值，将较小值的元素赋给C， A, SeqList while(i<=A.last&&j<=B.last)if(A.date[i]<B.date[j])elseC-while(j<=B.last)}算法算法的时间性能是O(m+n)，其中m是A的表长，n是B的表长表，均用向量表示，表长分别为m和nA′和BAB中除去最大共同前缀 =进行比较，A>B函数返回1；A=B返回0；A<B返回-1。intA[],B[];int inti=0,j,AS[],BS[],ms=0,ns=0;/*AS,BS作为while(A[i]==B[i]) for{++;}forBS[j-i]=B[j];ns/*求B′,ms为B′的长度if(ms==ns&&ms==0)returnelseif(ms==0&&ns>0||ms>0&&ns>0&&AS[0]<BS[0])return–1;elsereturn1;}算法算法的时间性能是O(m+n)线性表的链式和运算实据元间的逻辑关系来，因此对线性表的插入、删除不需要移动数据元素。ai之外，还需要和aiai+1所在的存贮单元的地 datatypedata;}

图2.6单链表结点结如图2.7是线性表(a1,a2,a3,a4,a5,a6,a7,a8)对应的链式结构示意图当然必须将第一个结点的地址160H中，最后一个结点没有后一个结点的地址放在了指针变量L、H中，头指针为“NULL”则表示一个空表。……∧………………图2.8链表示意H图2.7链式结

p->datap-P图 个结点的地址，即链表的头指针；将操作中用到指向某结点的指针变量说明为LNode* *p；则语句：所示。P所指的结点为*p，*p的类型为LNode型，所以该结点的数据域为(*p).data或 单链表上基本运算的实建入一个数据元素则申请一个结点，然后插在链表的头部，如图2.10展现了线性表：∧∧∧∧∧∧∧∧∧∧∧图2.10在头部插 Creat_LinkList1( Lnode*s;int while(x!=flag) }return}算法如图2.11展现了在链表的尾部插入结点建立链表的过程。rr指向新H=NULLr=NULL/*初始状态HHHHHHHHHH∧图2.11在尾部插入建立单 Creat_LinkList2({LinkListL=NULL; int while(x!=flag){ (L==NULL)L=s;/*第一个结点的处理*/elser->next=s; /*r指向新的尾结点*/}ifr!=NULL)r->next=NULL;/*对于非空表，最后结点的指针域放空指针return}算法H∧H∧∧∧图2.12结点的单链 Length_LinkList1(LinkListLnode* /*p指向头结点 while(p- /*p所指的j个结点 }算法 if(p==NULL) 0;/*空表的情况 while(p->next){p=p->next;j++} }算法上头结点之后则不用在以后的算法中不加说明则认为单链表是结点的。 * L, {Lnode intj=0;{p=p->next;j++;}if(j==i)returnp;elsereturn}算法 *Locate_LinkList( L, { *p=L-return}算法算法2.11(a)、(b)的时间复杂度均为O(n)p×②p×②①sq①p×③s②图2.13在*p之后插入 图2.14在*p之前插入前插结点：设ｐ指向链表中某结点，ｓ指向待插入的值为x的新结点，将*s插入while(q- 实我们关心的更是数据元间的逻辑关系，所以仍然可以将*s插入到*p的后面，然 L,inti, { * ifprintf(＂参数i错＂);return0;/*第i-1个不存在不能插入else));s-s->next=p return1;}算法算法2.12的时间复杂度为O(n)qp×qp× 图 删除显然找*p前驱的时间复杂性为O(n)s=p-) {LinkList ifelse{if(p->next==NULL)s=p->next;/*s指向第i个结点 /*释放*s*/return}算法算法2.13的时间复杂度为O(n)单链表不具有按序号随机的特点，只能从头指针开始一个个顺序进行循环链域，则使得链表头尾结点相连，就构成了单循环链表。如图2.16所示。H H(a)非空 (b)空图2.16结点的单循环链表若用尾指针R1、R2来标识，则时间性能为O(1)。操作如下：p=R1–>next; /*保存R1的头结点指针*/R1->next=R2->next->next;/*头尾连接*/(R2->next);/*释放第二个表的头结点*/R2- /*组成循环链表……× ……× ×图 双向链pp->next，而找其前驱则只能从该链表的头指针开

图设ppp->prior->nextpH

(a)非空图2.19结点的双循环链2.20p ②①④③双向链表中结点的插入：设p指向双向链表中某结点，s2.20p ②①④③图 设p指向双向链表中某结点，删除*p。操作示意图如图2.21所示。 ①2.21双向链表中静态链是将当前sd中的空结点组成的链表。 454531278912345 7892.22静态链数组sd的定义如下#define …/*足够大的数 }SNode;/*结点类型 int {}t将它还给AV，相关语句为：sd[t].next=AV; intp,s; {if(AV!=- return }}算法单链表∧∧图 reverse(Linklist{ p=H->next;/*p指向第一个数据结点H->next=NULL;/*将原链表置为空表 q->next=H H-}}算法该算法只是对链表中顺序扫描一边即完成了倒置，所以时间性能为O(n)2.6L2.23的操作。(a)为点并删除之；p指向下一个；依此类推，p指向最后结点时算法结束。∧∧∧∧图 { p=H->next;/*p指向第一个结点while(p->next) /*找到重复结点，用r指向，删除*r }/*while(q- }算法该算法的时间性能为O(n2)例2.7设有两个单链表A、B，其中元素递增有序，编写算法将A、B归并成一个按元算法思路：利用A、B两表有序的特点，依次进行比较，将当前值较小者摘下，插 /*设A、B均为结点的单链表{LinkListC;LNode {s=q;q=q- /*whileif(p==NULL) }}算法该算法的时间性能为O(m+n)顺序表和链表的比讨论可知它们各有优缺点，顺序有三个优点：不用为表示结点间的逻辑关系而增加额外的开销 第三章栈和队栈３.１.１栈的定义及基本表（LastInFirstOut，简称LIFO表。入3.1栈示意⑴栈初始化：Init_Stack(s)初始条件：栈s不存在⑵判栈空：Empty_Stack(s)初始条件：栈s已存在⑶入栈：初始条件：栈s⑷出栈：初始条件：栈s存在且⑸读栈顶元素：Top_Stack(s)初始条件：栈s存在且非 栈的实现和运算实的任一个端点，而栈顶是随着插入和删除而变化的，用一个inttop来作为栈顶的指针，指明当前栈顶的位置，同样将data和top封装在一个结构中，顺序栈的类型描述如下：#defineMAXSIZE1024 图(a)是空栈，图(c)A、B、C、D、E5个元素依次入栈之后，图(d)是在图(c)之后E(c)5(d)33.2栈顶指top与栈中数据元素的关SeqStack{SeqStack*s;s->top=-1;returns;}intEmpty_SeqStack(SeqStack if(s->top==-1)return1; return0;} {if(s->top==MAXSIZE- return0;/*栈满不能入栈 }

return1;} Pop_SeqStack(SeqStack*s,datatype (Empty_SeqStack(s))return0;/*栈空不能出栈*/else{ return1 } ifEmpty_SeqStacksreturn0;/*栈空elsereturn(s->data[s->top]}栈满时，不能入栈;否则出现空间溢出，引起错误，这种现象称为上溢。链表的结构相同，在此用LinkStack表示，即有： {datatypedata;说明top为栈顶指针 top且没有必要象单链表那样为了运算方便附加一个头结点。通常将链栈表示成图3.3的形式。 } top

∧∧图3.3链栈示意 } {StackNode*s;tN;returntop;} Pop_LinkStack top, if（top==NULL）returnNULL;else{*x=top->data;p=(p); }}栈的应用举例3.1简单应用：数制转换问NN8（整除N%8（求余3低166606高（3456）10后依次出栈好是转换结果。N≠0，则将Nrs2;若N=0，将栈s的内容依次出栈，用Nr int top while(N while(NPush_SeqStack&s，Nr { /*余数入栈N=Nr N=Nr /*商作为被除数继续 while(top!=- Pop_SeqStack(&s，&x) {x=s[top--printf(“%d”，x) 算法 算法中的直接用int向量S和int变量top作为一个栈来使用，往往初学者将栈视为一个很复杂3.1(a)那样，对余数的入栈操作：Push_SeqStack&s，Nr);因为是用c语言描3.2利用栈实现迷宫的求解设迷宫为m行n列，利用maze[m][n]来表示一个迷宫，maze[i][j]=01其中：0表示通路，1表示不通，当从某点向下试探时，中间8个方向可以（3.4）而四个角点有3个方向，其它边缘点有5个方向，为使问题简单化我们用3.4表示的迷宫是一个6×8的迷宫。（1，1（m，n

11111111111110111011111101011111101000001110111011111100110001101100110111111111111234567图

#definem6/*迷宫的实际行*/#definen8/**/intmaze[m+2][n+2]; {int}item;这样对move(x，y)v(0<=v<=7)到达的新点（i，j）的坐标：i=x+move[v].x;j=y+move[v].y;(x-1，y-

(x-

(x-xy00xy00111121031-40-5-6071(x+1y+1)3.5与点(x，y)8个点

3.6增量数组对于图3.4所示迷宫，依次入栈为：{intxyd*横纵坐标及方向栈的定义仍然为： sijmark[i][j]1，下次再试探这个位置时就不能再走了。另]{栈顶元素＝＞（xyd）出栈;求出下一个要试探的方向d++; {（xyd）求新点坐标(i,j ((x,ｙ)==(ｍ,n))结束;elsed=0}elsed++}} intmaze[m][n];{SeqStacks; intx,y,d,i,j;temp.x=1;temp.y=1;temp.d=-1;Push-_SeqStack(s，temp); Pop_SeqStack(s,＆temp)x=temp.x;y=temp.y;d=temp.d+1; i=x+move[d].x; (maze[i][j]==0) temp={x,y,d};Push_SeqStack(s,temp);x=i;y=j;maze[x][y]=-1; (x==m&&y= return1/*迷宫有路elsed=0} /*while*/ 0/*迷宫无路*/}3.3表达式求、、*、/、%、^（乘方）和括号。（）— 表达式作为一个满足表达式语则的串，如表达式“3*2^（4+2*2-１*3）-s1和算符栈s2。当自左至右（;乘;的级别是不同的。当遇到右括号“”直^342211(04）-- 对象栈 算符栈 33(3入栈*3*入栈22入栈^^入栈((入栈44入栈++入栈22入栈**入栈22入栈-2+2=4，结果入栈4+4=8，结果入栈-入栈１1入栈**入栈33入栈)8-35入栈(出-2^532入栈(-入栈55入栈(96-5,91入栈图 中缀表达式3*2^（4+2*2-１*3）-5的求值过-5”的后缀表达式为：“32422*+13*-^*5- chardatetype; /*A表示的表达式运算结果 swhile(ch!=’#’){ (ch!=运算符)Push_SeqStacksch)else{Pop_SeqStack(s,&a);Pop_SeqStacks&b)/*取出两个运算量*/switch(ch).{casech==’+’： c=a+b;break;casech==’-’： c=a-b;break;casech==’*’：c=a*b;break;casech==’/’：c=a/b;break;casech==’%’：c=a%b;break;}}} result;}

３3２４２２*计算２＊２，将结果４入＋１３*计算１＊３，将结果４入—^*55-空图 B数组中存放，遇到运算符时类似于中缀表达式求值时对运算符的处理过程，但运算符出栈后不是进行相应的运算，而是将B中存放。读者不难写出算法，例 栈与递归归定义的，这时用递归方法可以使许多问题的结果大大简化，以n!为例：n!的定义为n!

intfact(int if(n= else (n*fact(n-1))}Record到本次的调用处。下面以求3!为例说明执行调用时工作栈中的状况。m=fact(n);}intfact(int fif(n==0)f=1;return

01233.9递归工作栈示}其中R1fact时返回点地址，R2为factfactn1)时返设主函数中n=3 returnf； returnf returnf 图 fact(3)的执行过队队列的定义及基(FIFO---FirstInFirstOut)的数据结构：即插入在表一端进行，而删除在表的另一端进行，这种数据结构称为队或队列，把允许插入的一端叫队尾(rear)，把允许删除a3、a4a5，出队时的顺序将依然是a1、a2、a3、a4a5。出 入 a43.11队列示意在⑴队列初始化：Init_Queue(q)初始条件：队q⑵入队操作：初始条件：队q操作结果：对已存在的队列q，插入一个元素x⑶出队操作： 队q存在且非⑷读队头元素： 队q存在且非Empty_Queue(q)初始条件：队q存在q10队列的实现及运算实1define data[MAXSIZE];/*队员 intrear,front;/*队头队尾指针 sq->data[0]---sq->data[MAXSIZE-置空队则为：sq->front=sq->rear=- /*x中队满时：mMAXSIZEm=0。front=-1front=5front=5(a)空(b)3(d)假溢出现3.12队列操作示意3.13循环队列示意设MAXSIZE=10，图3.14是循环队列操作front=4front=-1front=5front=5(a)4(b)队(c)(d)队3.1４循环队列操从图3.14所示的循环队可以看出，(a)中具有a5、a6、a7、a8四个元素，此时front=4,rear=8；随着a9~a1410个元素---front=4,rear=4,方法之一是附设一个队中元素个数的变量如num，当num==0时队空，num==MAXSIZE时为队队尾指针加1就会从后面赶上队头指针，这种情况下队满的条件是：(rear+1)%MAXSIZE==front，也能和空队区别typedefstruct int /*队头队尾指针int /*队中元素的个数 /*循环队c_SeQueue*{q=malloc(sizeof(c_SeQueue));return} return /*队满不能入队}

return /*入队完成} return /*队空不能出队}*x=q->data[q->front];/*读出队头元素return /*出队完成}} elsereturn0;}链为了操作上的方便，我们分别需要一个头指针和尾指针，如图3.15所示。

图3.15链队示意

∧∧rear{datatypedata; { …∧…∧(a)非空∧q∧

∧∧ (b)空队 (c)链队中只有一个元素结点图3.16头尾指针封装在一起的链队创建一个结点的空队 LQueuep=malloc(sizeof(QNode));/*申请链队头结点*/ returnq;} } {if(q->front==q->rear) return1;} QNnodeif(Empty_LQueue(q) *x=p->data;/*队头元素放x中*//*只有一个元素时，出队后队空，此时还要要修改队尾指针参考图return}}队列应用举 被一次，所以num至多等于m*n。sq的每一个结构有三个域：x,y和pre，其中x,y分头、队尾指针：front和rear用来指向队头和队尾元素。 intx,y;intintfront,rear;（１,１intmaze[m][n]；/*迷宫数组*/intfront,rear；intx,y,i,j,v;sq[０].x=1;sq[０].y=1;sq[０].pre=-1;/* while(front<=rear)/*队列不空 x=sq[front].x;y=sq[front].y;for(v=0;v<8;v++){i=x+move[v].x;j=x+move[v].y;if(maze[i][j]==0) sq[rear].x=i;sq[rear].y=j;sq[rear].pre=front;}if{printpath(sq,rear);/*打印迷宫*/restore(maze);/*恢复迷宫*/return1;} front++;/*当前点搜索完，取下一个点搜索 return0;}voidprintpath(sqtypesq[],intrear)/*打印迷宫路径 doprintf((%d,%d)＂,sq[i].xsq[i].y }算法1101010010210110100110 3456

91011 131415161718123332446123175488011223456778993.18迷宫搜索过运行结果：(6,8)(5,7)(4,6)(4,5)(3,4)(3,3)中始终保持当前的若干条，以便满足快速查询。第四章串及其基本运串的基s=＂s1s2…sn其中s是串名；在本书中，引号作为串的定界符，引号引起来的字符序列为串值，引单位，i是它在整个串中的序号n为串的长度，表示串中所包含的字符个数，当n=0时，串的基操作条件：串s存操作结果：求出串s的长度。操作结果：将s2的串值赋值给s1s1原来的值被覆盖掉。３．连接操作：StrConcat(s1,s2,s)或StrConcat(s1,s2)操作条件：串s1,s2例如：s1=＂he＂，s2=＂bei＂，前者操作结果是s=＂hebei＂；后者操作结果是s1=＂hebei＂。４．求子串SubStr(操作结果：返回从串s的第ilen的子串。len=0得到的是空串。例如：SubStr(＂abcdefghi＂,3,4)=＂cdef＂操作条件：串s1,s2操作结果：若s1==s20；若s1<s2,返回值<0；若s1>s2,返回值>0。６．子串定位StrIndex(s,t)：找子串t在主串s中首次出现的位置操作条件：串s,t存在操作结果：若t∈s，则操作返回t在s中首次出现的位置，否则返回值为-1。操作结果：将串t插入到串s的第i个字符位置上，s的串值发生改变。８．串删除StrDelete(s,i,len)操作结果：删除串s中从第i个字符开始的长度为len的子串，s的串值改变。９．串替换StrRep(s,t,r)操作条件：串s,t,r存在，t不为空操作结果：用串r替换串s中出现的所有与串t相等的不的子串，s的串值改变。串的定长顺序及基本运串的定长顺序#defineMAXSIZE256chars[MAXSIZE]; } MAXSIZE-abcdefghijk…图4.1串的顺序方式比如C语言中处理定长串的方法就是这样的，它是用’\0’来表示串的结束。这种方法 MAXSIZE-abcdefghijk…图4.2串的顺序方式设定长串空间：chars[MAXSIZE+1];用s[0]存放串的实际长度，串值存放在定长顺序串的基本运串联接：把两个串s1和s2首尾连接成一个新串s，即：s<=s1+s2chars1[],s2[],s[];{inti=0,j,len1, 0/*s长度不够 return1;}２．求子

算法intStrSub(char*t,char*s,inti,int/*tsi字符开始的长度为len的子串1≤i≤串长{intslen;for(j=0;j<len;j++)t[j]=s[i+j-}

算法 {intwhile(s1[i]==s2[i]&&s1[i]!=’\0’)i++;return(s1[i]-s2[i]);}模式匹s和ts数返回t在s中的首次出现的位置(或序号)，否则匹配失败，返回-1。t也称为模式。s1与t1s2与t1进行比较，...，直到s较s的某一个si与t的字tj不同s返回到本趟开始字符的下一个字符，即明本趟匹配成功，本趟的起始位置是i-j+1或i-t[0]，否则，匹配失败。4.3简单模式匹配的匹配过 StrIndex_BF(char*s,char/*从串s的第一个字符开始找首次与串t相等的子串 intwhile(i<=s[0]&&j<=t[0] if {i=i-j+2;j=1;/*回溯if(j>t[0])return(i- /*匹配成功，返回位置elsereturn}算法该算法简称为BF算法。下面分析它的时间复杂度，设串s长度为n，串t长度为m。匹配成功的情况下，考虑两种情况：mi-1+mn-m+1n

n

(npi(i1m)

(i1m)2 即最好情况下的时间复杂度是O(n+m)设匹配成功发生在si处，则面i-1趟匹配中共比较了(i-1)*m次，第i趟成功的匹配共比较了m次，所以总共比较了i*m次，因此好情况下平均比较的次数是：pi(im)

1(im)

m(nm

即情况下的时间复杂度是O(n*m)位在pos处。算法4.4是pos=1的情况。BFBF(Knuth)，莫里斯(Morris)和特(Pratt)同时设计的，简称KMP算法(1)KMP,4.3所示的匹配过程，在第三趟匹配过程中，s3~s6和t1~t4是匹配成功趟中有s4=t2，而t1≠t2，肯定有t1≠s4。同理第五趟也是没有必要的，所以从第三趟之后s6和t4s6=t4，而t1=t4s6=t1，因此第六趟的比较可以从第s7和t2itk，即si和tji不动，模式ttk和si＂t1t2…tk-1=＂si-k+1si-k+2…si-1＂(4.1)(4.1)式左边是tk前面的k-1个字符，右边是si前面的k-1个字符。而本趟匹配失败是在si和tj之处，已经得到的部分匹配结果是：＂t1t2…tj-1＂=＂si-j+1si-j+2…si-1＂＂tj-k+1tj-k+2…tj-1=＂si-k+1si-k+2…si-1＂(4.3)(4.3)tj前面的k-1个字符，右边是si前面的k-1个字符，＂t1t2…tk-1＂=＂tj-k+1tj-k+2…tj-1＂中的前k-1tj字符前面的k-1个字符相等时，模式t就可以向右“滑动”至使tk和si对准，继续向右进行比较即可。符序列的构成，而与主串s无关。我们用next[j]表示tj对应的k值，根据以上分析，next①next[j]②为了使t的右移不丢失任何匹配成功的可能，当存在多个满足(4.4)式的k③如果在tj前不存在满足(4.4)式的子串，此时若t1≠tj，则k=1;若t1=tj，则k=0;这时“滑动”的最远，为j-1个字符即用t1和sj+1继续比较。

当max{k|1<=k<j且＂t1t2 tk-1＂=＂tj-k+1tj-k+2 tj-1当不存在上面的k且 当不存在上面的k且j123456789abcaababc011021311KMP算在求得模式的nexti和j分别指示主串和模式中的比较字符i的初值为pos，j的初1。若在匹配过si≠tji和j分别增值时字符比较相等，则i和j分别增１继续进行匹配j退到值为零（即模式的第/*从串s的第post相等的子串 intwhile(i<=s[0]&&j<=t[0])/*都没遇到结束符 if(j>t[0])returni-t[0];/*匹配成功，返回位置else }

图4.4利用模式next函数进行匹配的过程示如何求next函数的定义出发用递推的方法求得next函数值。 ＂t1t2… tk-1＂=＂tj-k+1tj-k+2… tj-1＂ next[j+1]=?可能有两种情况：第一种情况：若tk＝tj＂t1t2 tk＂=＂tj-k+1tj-k+2 tj 第二种情况：若tk≠tj＂t1t2 tk＂≠＂tj-k+1tj-k+2 tj 个字符和“主串”中的第j个字符相比较。若next[k]=k′，且tk′＝tj，则说明在主串中第j+1个字符之前存在一个最大长度为k′的子串，使得＂t1t2 tk′＂=＂tj-k′+1tj-k′+2 tj 直至tj和模式中的某个字符匹配成功或者不存在任何k′(1<k′<k<…<j)满足(4.10)，此时若t1≠tj+1，则有：next[j+1]=1 否则若t1=tj+1，则有 /*求模式t的next值并寸入next数组中｛int{while(j>0&&t[i]!=t[j])j=next[j]; if(t[i]==t[j])next[i]=next[j]; }}4.6的时间复杂度是O(m)；所以4.5的时间复杂度O(n*m)，但在一般情况串的堆结串名的映如设s1=＂abcdef＂，s2=＂hij＂，常见的串名－串值映象索引表有如下几种： intlength;/*串长char*stradr;/*起始地址}4.5带长度的索引 char }4.6带末尾指针的索引typedef inttag;/*特征位*/ {char*stradr;}堆结store[SMAX+1根据每个串的长度，动态的为每个串在堆空间里4.8所示，是一个堆结构示意图。阴影部分是已经为存在的串分配过的，为未分配部分的起始地址，每当向store中存放一个串时，要填上该串的索引4.8基于堆结构的基本运 intstradr;/*起始地址}voidStrAssign(HString*s1,char/*将一个字符型数组s2中的字符串送入堆store中,是自由区的指针 inti=0,len;if(len<0|| return0; }}算法 StrCopy(Hstring*s1,Hstring/*该运算将堆store中的一个串s2到一个新串s1中{intif(+s2.lengt-1>SMAX)return else{for(i=0;i<s2.length;i++)s1->stradr=}}算法 /*该运算将串s中第i个字符开始的长度为len的子串送到一个新串t中{intif(i<0||len<0||len>s.len-i+1)return else{t->length=len;}}算法HStrings1,s2;HString*s;{HStringStrCopyStrCopy}算法5.1数数组的逻辑结………5.1mn列的二赋值操作：给定一组下标，或修改与其相对应的数据元素数组的内存映对象维种：CN循;a21，a12，a22，a13，a23;5.3（b）图5.22×3数组的逻辑状 (a)以行为主 (b)以列为主5.32×3数组的物理状址单元，那么aij的物理地址可用一线性寻址函数计算：LOC(aij)=LOC(a11)+((i-1)*n+j-1)*有j-1个数组元素。LOC(aij)=LOC(a00)+(i*n+j)*l推广到一般的二维数组：A[c1..d1][c2..d2]，则aij的物理地址计算函数LOC(aij)=LOC(ac1c2)+((i-c1)*(d2-c2+1)+(j-c2)同理对于三维数组Amnp，即m×n×p数组，对于数组元素aijk其物理地址LOC(aijk)=LOC(a111)+((i-1)*n*p+(j-1)*p+k-2 a推广到一般的三维数组：A[c1..d1][c2..d2][c3..d3]，则aijk的物理地址为：LOC(i,j)=LOC(ac1c2c3ic1*(d2c21)*d3c31jc2*(d3c31)+(kc3))*l三维数组的逻辑结构和以行为主序的分2 aaaaaaaaaaaaaaaaaaaa5.4三维数组示意一个3*4*25．1若矩阵Am×n中存在某个元素aij满足：aij是第ij列中的最大值，则称该元素为矩阵A的一个鞍点。试编写一个算法，找出A中的所有鞍点。中的最大值，是则打印出，接着处理下一行。矩阵A用一个二维数组表示。 /*m,n是矩阵A的行和列{intfor {for(j=1;j<n;if(A[i][j]<min /*找第I行最小值for(j=0j<n; if(A[I][j]==min if(p>=m)printf(＂%d,%d,%d\n＂,i}/*if}/*for}算法的时间性能为O(m*(n+m*n))对称３６４７８６２８４２４８１６９７４６０５８２９５７对称矩阵的特点是：在一个n阶方阵中，有aij=aji1≤i,j≤n5.5所示是元，当n３６４７８６２８４２４８１６９７４６０５８２９５７３６２４８１７４６０８２９５７5.55阶对称方阵及它的压缩题是要找到k与i、j n(n+1)/2-……a1

第2 第3 第n5.6一般对称矩阵的压缩角中的元素aij，其特点是：i≥j且1≤i≤n，到SA中后，根据原则，它前面有i-1列顺序中，aij是第i*(i-1)/2+j个元素，因此它在SA中的下标k与i、j的关系为： 若i<j，则aij是上三角中的元素，因为aij=aji，这样，上三角中的元素aij时则去SA 式子综合起来得到：k=I*(I-1)/2+J-1。三角形如图5.7的矩阵称为三角矩阵，其c为某个常数。其5.7(a)为下三角矩阵：主队３c３cccc３4810６２cccc2946４８１cccc１57７４６０cccc08８２９５７cccc7 (b)上三角矩5.7三角矩方的常量，因为是同一个常数，所以存一个即可，这样一共了n*(n+1)+1个元素，aji

k=k=

……ac1第2 第3 第n5.8下三角矩阵后对角线下方的常量。对于第1行，n个元素，第2行n-1个元素，…，第p行(n-p+1)个元素，aij的前面有i-1行，共：i (np)p

个元素，而aij是它所在的行中要的第（j-i+1）个；所以，它是上三角sak与aji(i-1)*(2n-i+2)/2+j-当 ……a…cn第1 第25.9上三角矩阵带状nAm，满足当∣i-j∣≥m时，aij=0，这′数组B5.10(b)w时，先存放非零元素后补零。那么aij映射为bi′j′ 当 元素，如图5.10(c)所示，按其压缩规律，找到相应的映象函数。0000000000000 0w=3的5阶带状矩 (b)压缩为5*3的矩 5.10带状矩阵及设m*ntt<<m*n，这样的矩阵称为稀疏矩阵。很多科学管理（i,j,v稀疏矩阵的三元组表元组表，采用顺序方法该表。如图5.11稀疏矩阵对应的三元组表为图5.12。 123 000-060000000000000000000 123 000-060000000000000000000634675163467515.12defineSMAX1024/*一个足够大的数 {int datatype int SPNode }SPMatrix;/*三元组表 设SPMatrixA;表示一m*nB则是一个n*m的稀疏矩阵，因此也有SPMatrixB;由A求B需要：A的行、列转化成B的列、行将A.data中每一三元组的行列交换后转化到B.data1单元用起。①A的行、列转化成B的列、 00 —5.13A的转置567 voidTransM1(SPMatrix intp,q,col;B=malloc(sizeof(SPMatrix));/*申请空间

图 B的三元组B->mu=A- ifB for(col=1;col<=(A->nu); /*A的列序转换for(p=1;p<=(A->tu); return 算法5.1稀疏矩阵转分析该算法，其时间主要耗费在col和p的二重循环上，所以时间复杂性为O(n*t)，(设m、n是原矩阵的行、列，t是稀疏矩阵的非零元素个数)，显然当非零元素的个数t和扫描一遍A.data即可。cpot［col中的第col列的第一个非零元素在B.data中的位置。于是cpot的初始值为： 5.11矩阵A的num和cpot 5.15AnumcpotSPMatrix*TransM2(SPMatrix intnum[n+1],cpot[n+1];B->mu=A- ifB for(i=1;i<=A /*A中每一列非零元素的个数}cpot[1]=1;/*A中每一列第一个非零元素在B.data中的位置for(i=2;i<=A->nu;i++)fori=1;iA->tu {j=A->data[i].j;/*当前三元组的列号*/ /*当前三元组在B.data中的位置*/B->data[k].i=A->data[i].j;}/*fori return 算法5.2稀疏矩阵转置的改进算O（n+t已知稀疏矩阵A(m1×n1)和B(m2×n2)，求乘积C(m1×n2)30070003007000-0200

B. C.5.16稀疏矩阵A、B、C及对应的三元n A(i,k)*B(k,k后得到c11，A的第一行再与B的第二列对应相乘累加后得到c12，…，因为现在按三元组素是很费时的，因此改变一下求值的顺序，以求c11和c12为例，因为：a12只与B2行元素a13只与B3行元素

即a11只有可能和B1行的非零元素相乘，a12只有可能和B2行的非零元素相乘，…，而同一行的非零元是相邻存放的，所以求c11和c12同时进行：求a11*b11累加到c11，求a11*b12累加到c12，再求a12*b21累加到c11，再求a12*b22累加到c22，…，当然只有aik和bkj(列号与行号相等)且均不为零（三元组存在）时才相乘，并且累加到cij当中去。为了运算方便，设一个累加器：datatypetemp[n+1]cij的值，当前行中所有元素全部算出之后，再存放到C.data中去。和rpot两个向量。num[k]表示矩阵B中第k行的非零元素的个数；rpot[k]表示第k行的第一个非零元素在B.data中的位置。于是有 Bnum和rpot5.171234202013355.17矩阵Bnumrpot⑵求B的SPMatrix*MulSMatrix(SPMatrix*A,SPMatrix/*稀疏矩阵A(m1×n1)和B(m2×n2)用三元组表，求A×B SPMatrix*C;/*乘积矩阵的指针intp,q,i,j,k,r;if(A->nu!=B->mu)returnNULL/*AB的行不相等C=malloc(sizeof(SPMatrix));/*申请C矩阵 {C->tu=0;return for(i=1;i<=B- num[i]=0;/*B中每一行非零元素的个数for(k=1;k<=B-}for(i=2;i<=B- /*当前C中非零元素的个数p=1;/*指示A.data中当前非零元素的位置for(i=1;i<=A->mu; temp[j]=0;/*cij的累加器初始化while(A->data[p].i==i ./*求第i行的 k=A->data[p].j;/*A中当前非零元的列号if(k<B- elset=B->tu+1;/*确定B中第k行的非零元素在B.data中的下限位置for(q=rpot[k];q<t /*B中第k行的每一个非零元素 temp[j]+=A->data[p].v*B-}/*whileif(temp[j]){} returnC;}/*MulSMatrix算法5.3稀疏矩阵的乘tu)（2mu)（3）nu)（4）的所有非零元素的时间复杂度为O(A->tu*B->tu/B->mu)（5）压缩时间复杂度为O(A->mu*B->nu)；所以总的时间复杂度为O(A->mu*B->nu+(A->tu*B->tu)/B->nu)个域组成，其结构如图5.19表示，其中：row域非零元素的行号，col域非零元素的列号，v域本元素的值，right，down是两个指针域。v5.19十字链表的jijwlntwlvttii每行列将列的结们来因点值所i行（列）的头结点，…，形成一个循环表。这个循环表又有一个头结点，这就是最后的总头结点，指针HA指向它。总头结点的row和col域原矩阵的行数和列数。来表示；改进后的结点结构如图5.20所示。5.20十字链表中非零元素和表头共用的结点结 { row, } ，n（A，r（i，j，aij，到第ij个列链表中去。在算法中将利用一个辅助数组MNode*hd[s+1];s=max(mn),hd[i]指向第i行(第i列)链MLinkCreatMLink(/*返回十字链表的头指针｛MLinkinti,j,m,n,t;datatypev; for(i=1;i<S; p=malloc(sizeof(MNode));/*i个头结点p->row=0;p-}hd[S]->v_next.next=H;/*将头结点们形成循环链表forscanfd,%d,%d”,&i,&j,&v);/*/*以下是将*p插入到第i行链表中去，且按列号有序 /*以下是将*p插入到第j行链表中去，且按行号有序 ) q->downreturnH; 算法5.4建立稀疏矩阵的十字链已知两个稀疏矩阵A和B，分别采用十字链表，计算C=A+B，C也采用十字链表方式，并且在A的基础上形成C。由矩阵的加则知，只有A和B行列对应相等，二者才能相加。C中的非零元素cijaij+bijaij(bij=0)，或者是bij(aij=0)，因此当B加到AA十字链表的当前结点来说，对应下列四种情况：或者改变结点的值（aij+bij（bij＝０（aij＝０＝０。整个运算从矩阵的第一行起逐行进行。对每一行都从行表的头结点出发，分别找到和pb分别指向A和B的十字链表中行号相同的两个结点，４种情况如下：若pa->col=pb->col且pa->v+pb->v≠0aij+bij的值改写pa所指结点的值若pa->colpb->col或pa->col＝0（即是表头结点A的十字链表中插入一个pb所指结点。分析的4种情况利用了这些信息来判断是否为表头结点。MLinkAddMatHa,Hb)MLinkHa,Hb; if(Ha->row!=Hb->row||Ha->col!=Hb->col)returnca=Ha->v_next.next;/*ca初始指向A矩阵中第一行表头结点*/cb=Hb->v_next.next;/*cbB矩阵中第一行表头结点*/do{pa=ca->right;/*pa指向A矩阵当前行中第一个结点*/qa=ca;/*qa是pa的前驱pb=cb->right;/*pb指向B矩阵当前行中第一个结点 { (pa->col<pb->col&&pa->col!=0)/*第三种情况{}p->right=pa;qa->right=p/*新结点插入*pa的前面*/q=Find_JH(Ha,p->col);/*从列链表的头结点找起p->down=q->down/*插在*q的后面}/*ifelse/*第一、二种情况if(x==0)/*第二种情况*/ /*还要从列链中删除，找*pa的列前驱结点q=Find_JHHa,pa->col/*从列链表的头结点找起while(q->down->row<pa->row)(pa);}/*if(x==0)*/else/*第一种情况*/}}} /*ca指向A中下一行的表头结点 /*cb指向B中下一行的表头结点 }算法 为了保持算法的层次，在上面的算法，用到了一个函数findjH函数MlinkFind_JH(MLinkH,intj)H中第j列链表的头称的表List的区别。广义表的定义（，广义表（GeneralizedLists）是n（n≥0）个数据元素a1，a2，…，ai，…，an的有序序列，ls＝（a1，a2…，ai…，an）其中：ls是广义表的名称，n是它的长度。每个ai（1≤i≤n）是ls的成员，它可以是（head（tailABC＝（a（b，c，d）DE其自身的子表。例如表E就是一个递归的表。A、表B、表C是表D广义表有两个重要的基本操作，即取头操作（Head）和取尾操作（TailHead（B）＝ （C）＝a Tail（C）＝（bc，d）Head（D）＝A Head（E）＝a Tail（E）＝（E）Head（F）＝（）连接、、遍历等。 IsEmpty(ls)：若广义表ls空，则返回True；否则返回FalseDepth(ls)：求广义表ls的深度Locate(ls，x)：在广义表ls中查找数据元素x。Merge(ls1，ls2)：以ls1为头、ls2为尾建立广义表。CopyGList(ls1，ls2)：广义表，即按ls1建立广义表ls2。Head(ls)：返回广义表ls的头部。Tail(ls)：返回广义表的尾广义表的typedefenumATOMLIST Elemtag datatype /*data是元素结点的值域struct /*ptr是表结点的指针域，ptrhp和ptr.tp分别 521头尾表示法的结点结构如图5.22所示。F1^1^^图5.22广义表的头尾表示法结构示的层次。例如，在广义表D中，单元素a和e在同一层次上，而单元素b、c、d在同一层次上且比a和e低一层，子表B和C在同一层次上。另外，最的表结点的个数即为广义表的长度。例如，在广义表D的最有三个表结点，其广义表的长度为3。typedefenumATOMLIST GLENodeElemtag datatype structGLENode structGLENode 图5.23孩子兄弟表示法的结点形式方式，其结构如图5.24所示。1^^A1^^0e0e^0d^ 1^1^^图5.24广义表的孩子兄弟表示法结构示从图5.24的结构示例中可以看出，采用孩子兄弟表示法时，表达式中的左括“（”对应表示中的tag=1的结点，且最结点的tp域必为NULL。 广义表基本操作的实GListHead(GList{ifls->tag==1 p=ls->hp; }算法{ifls->tag==1 p=ls->tp; }算法 { ifStrEmpty(S)*ls=NULL;else{if(!(*ls=(GList)malloc(sizeof(GLNode))))return if(StrLength(S)==1){(*ls)->tag=0;(*ls)->data=}p=*ls;do{q=p;ifif(!(p= }q->ptr.tp=NULL;}}return}算法 { i=1;k=0;for(i=1,k=0;i<=n||k!=0;{if(ch=='(')++k;elseif(ch== }if(i<={hstr=SubStr(str,1,i-2);str=SubStr(str,i,n-}}} Merge(GListls1,GListls2,Glist{if(!(*ls= *ls->tag=*ls->hp=return1;}算法intDepth(GList{ifreturn /*if(ls->tag==return /*for(max=0,p=ls;p;p=p->ptr.tp) /*求以p->ptrhp尾头指针的子表深度if(dep> max=}return /*非空表的深度是各元素的深度的最大值加} CopyGList(GListls1,GList{if(!ls1)*ls2= /*空表if(!(*ls2=(Glist)malloc(sizeof(Glnode))))return /*单元素 /*广义表ls1->ptrhp的一个副本 /*广义表ls1->ptr.tp的一个副本}}return}算法第六定义与性二叉树的基本概二叉图6.1所示。 6.1二叉树的五种的父结点（1≤i<k）,就把n1,n2,…,nk称为一条由n1至nk的路径。这条路径的长度是k-1。的祖先，而N称为M的子孙的层数加1。（7(a)一棵满二叉树 (b)一棵非满二叉树图6.2满二叉树和非满二叉树示意图 (a)一棵完全二叉树 (b)一棵非完全二叉树图6.3完全二叉树和非完全二叉树示意图二叉树的主要性x（1≤i≤k i-1＝2k- n0＝n2＋1证明设n，n11 4具有n个结点的完全二叉树的深度k为[log2n]+1数为n时，有2k－1－1<n≤2k- 叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点，有：如果i>1，则序号为ii/2(“/”表示整除)；如果＝1，则序号为i为i的结点无左孩子。1>n，则序号为i的结点无右孩子。基本操作与实二叉树的顺序结6.46.3(a)所示的完全二叉树的顺序示意。图6.5给出了一棵一般二叉树改造后的完全二叉树形态和其顺序状态示意图。显然，这深度为k的右单支树，只有k个结点，却需分配2k－1个单元。ABCDEFGHIJ数组下标 图6.4完全二叉树的顺序示意(a)一棵二叉 (b)改造后的完全二叉ABC∧DE∧∧∧F∧∧G(c)改造后完全二叉树顺序状态图6.5一般二叉树及其顺序示意图(a)一棵右单支二叉 (b)改造后的右单支树对应的完全二叉A∧B∧∧∧C∧∧∧∧∧∧∧D图6.6右单支二叉树及其顺序示意#defineMAXNODE typedefelemtypeSqBiTree[MAXNODE]/*0号单元存放根结点*/SqBiTreebt;链式结子的指针，当左孩子或右孩子不存在时，相应指针域值为空（用符号∧或NULL二叉链表也可以结点的方式存放，如图6.7(b)所示。DCBA头结点指针DCBA头结点指针D∧C∧BA∧E∧∧F∧∧E∧∧F∧∧E∧∧F∧∧G∧∧G∧(a)指针的二叉链表 (b)结点的二叉链表图6.7图6.3(b)所示二叉树的二叉链表表示示意图其中，data、lchild以及rchild域的意义同二叉链表结构；parent指向该结点双C C DBAE，序二树式链typedefstructBiTNode{elemtypedata;structBiTNode 二叉树的基本二叉树的基本操InsertL（bt，x，parent）将数据域信息为x的结点插入到二叉树bt中作为结点结点作为结点x的左孩子结点。结点作为结点x的右孩子结点。Search（bt，x）在二叉树bt中查找数据元素x算法的实Initiate（bt）初始建立二叉树bt，并使bt指向头结点。在二叉树根结点前建立 {/*初始化建立二叉树*bt的头结点return0;return1;}算法{/*生成一棵以xlbt和rbt为左右子树的二叉树BiTreereturnp;}算法{/*在二叉树btparent的左子树插入结点数据元素 ifreturn}else{p->lchild=parent->lchild;}return}算法（3 {/*bt中删除结点parent的左子树 return}(p);/*当 return}算法略。操作Search（bt，x）Traverse（bt）的特例，关于二叉树的遍历二叉树的遍此，只要依次遍历这三部分，就可以遍历整个二叉树。若以D、L、R分别表示根结为先序遍历、LDR（称为中序遍历）LRD（称为后序遍历。先序遍历（1）根结点voidPreOrder（BiTreebt）if(bt==NULL)return; /*递归调用的结束条件*/ /*结点的数据域*/ /*先序递归遍历bt的左子树*/PreOrder（bt- /*先序递归遍历bt的右子树*/}算法ABDGCE中序遍历（2）根结点（3）中序遍历根结点的右子树。voidInOrder（BiTreebt）if(bt==NULL)return; /*中序递归遍历bt的左子树*/ /*结点的数据域*/ /*中序递归遍历bt的右子树*/}算法DGBAEC后序遍历if(bt==NULL)return; /*递归调用的结束条件*/ /*后序递归遍历bt的左子树*/ /*后序递归遍历bt的右子树*/ }算法GDBEFC在图ABCDEF（1）该元素所指结点以实现队列，变量front和rear分别表示当前对首元素和队尾元素在数组中的位置。intfront,rear;if(bt==NULL) /*队首结点的数据域if(queue[front {}if(queue[front {}}}算法如图6.3(b)所示的二叉树，对其进行先序、中序和后序遍历都是从根结点A开始的，△⊕△A*△⊕△A* △⊕ △⊕ * △△*G * 6.96.3(b)的路线示意量top用来表示当前栈顶的位置。inttop;{ /*结点的数据域if(top<MAXNODE-1)/*将当前指针p}elseprintf(“栈溢出”)；} /*p}if(top<=0 else{top-- /*从栈出栈顶元素 /*指针指向p的右孩子结点}}}算法化情况以及树中各结点的次序如表6.1所示。6.1二叉树先序非递归遍历过指针栈stackA空1BAA2DB3∧D4G5∧G6∧7∧A8C空9ECC∧E∧CF空∧FF∧空移到p=stack[topp=p->rchild{1第一次出{flag＝ 义为指针和标志flag合并的结构体类型。定义如下： 栈的结构，指针变量p指向当前要处理的结点，整型变量top用来表示当前栈顶的位置，整型变量sign为结点p的标志量。 BiTreep;intif(bt==NULL) if {top++; }else{p=stack[top].link;if } /*该结点数据域值}}}}算法由遍历序列恢复二叉ABCDEFGHBCAEDGHF续分解下去，最后得到如图6.10(c)的整棵二叉树。II 6.10一棵二叉树的恢复过程示数组preod[]与inod[]中，并假设二叉树各结点的数据值均不相同。/*n为二叉树的结点个数，root为二叉树根结点的地址{if(n≤0)}算法while(inod[m]!=preod[i])m++;if(m==k)*t->lchild=NULLif(m==h)*t->rchild=NULL}算法需要说明的是，数组preod和inod的元素类型可根据实际需要来设定，这里设为字符不用栈的二叉树遍历的非递归方对二叉树采用三叉链表存放，即在二叉树的每个结点中增加一个双亲域parent这的其n个结点的二叉树中的叶子结点和一度结点线索线索二叉树的（thread线索二叉树的一个具有n个结点的二叉树若采用二叉链表结构，在2n个指针域中只有n－1个线索二叉树分别如图6.11(a)、(b)、(c)所示。图中实线表示指针，虚线表示线索。 lchild lchild指向结点的前驱结{ rchild{1rchild指向结点的后继结 (a)先序线索二叉 (b)中序线索二叉(c)后序线索二叉树6.11线索二叉图6.12线索树中序线索二叉树的示线索二叉树的基本操作实typedefcharelemtype;unsignedltag:1;unsigned建立一棵中序线索二叉为指向前驱结点或后继结点的线索。为实现这一过程，设指针pre始终指向刚刚过的结点，即若指针p指向当前结点，则pre指向它的前驱，以便增设线索。{/*T，并将其中序线索化，*head指向头结点。if(!(*headBiThrNodeType*)malloc(sizeof(BiThrNodeType))))return0; ifT*head)->lchild pre= pre->rchild=*head;pre->rtag=1; }return}算法if(p){ {p- }ifpre } }}算法在中序线索二叉树上查找任意结点的中序前驱结0，表明该结点有左孩子，根据中序遍历的定义，它的下查找，当某结点的右标志为1时，它就是所要找的前驱结点。{/*在中序线索二叉树上寻找结点p的中序前驱结点if(p-}算法在中序线索二叉树上查找任意结点的中序后继结0，表明该结点有右孩子，根据中序遍历的定义，它的下查找，当某结点的左标志为1时，它就是所要找的后继结点。{/*在中序线索二叉树上寻找结点p的中序后继结点if(p->rtag!=1)}算法在中序线索二叉树上查找任意结点在先序下的后②若p->rchild不是头结点，则p结点一定是以p->rchild结点为根的左子树中在时，若p->rchild结点有右子树，则所找结点在先序下的后继结点的地址为{/*在中序线索二叉树上寻找结点p的先序的后继结点,head为线索树的头结点else{post=p;}}算法在中序线索二叉树上查找任意结点在后序下的前②若p->lchild不是头结点，则p结点一定是以p->lchild结点为根的右子树中在p->lchild{/*在中序线索二叉树上寻找结点p的先序的后继结点，head为线索树的头结点else{pre=p;}}算法在中序线索二叉树上查找值为x问结点的操作具体写为那结点的值与x比较的语句。下面给出其算法：{/*在以head为头结点的中序线索二叉树中查找值为x的结点BiThrTreep;while(p->ltag==0&&p!=head)p=p->lchild;if(p==head)}else}算法在中序线索二叉树上的更的情况，即在中序线索二叉树中插入一个结点p，使它成为结点s的右孩子。若s的右子树为空，如6.13(a)p之后成为6.13(b)所示的情形。在这种情况中，s的后继将成为p的中序后继，s成为p的中序前驱，而p成为s的pps成为p的中序