数据结构实验指导书(C语言版)

——信息管理系

《数据结构》实验指导书

《DATASTRUCTURES》

西南大学信息管理系

Iinformationdept.SouthwestUniversity

January24,2010

写在上机实习之需

上机实践是学生对本门课程所学知识的一种全面、综合的能力训练，是与课堂听

讲、自学和练习相辅相成的必不可少的一个教学环节，也是对课堂教学与实践教学效

果的一种检验。通常，实习题中的问题比平时的习题复杂得多，也更接近实际。实习

着眼于原理与应用的结合，使学生学会如何把书上学到的知识运用于解决实际问题的

过程中去，培养从事软件开发设计工作所必需的基本技能；另一方面，能使书上的知

识变“活”，起到深化理解和灵活掌握教学内容的目的。平时的练习较偏重于如何编

写功能单一的“小”算法，而实习题是软件设计的综合训练，包括问题分析，总体结

构设计，用户界面设计，程序设计基本技能和技巧，多人合作，以至一整套软件工程

规范的训练和科学作风的培养。此外，还有很重要的一点是：机器是比任何教师都严

厉的主考者。

为了达到上述目的，本篇安排了7个主实习单元，各单元的训练重点在于基本的

数据结构，而不强调面面俱到。各实习单元与教科书的各章具有紧密的对应关系，在

个别实习单元中安排有难度差别不等的多个实习题，以便学生选做。

此外，每个实习题采取了统一的格式，实验目的、实验内容、实验要求、程序

实现、程序运行情况和源程序清单等5个部分组成。

在每个实习单元都提供了一个完整的实现代码，仅供同学们参考，绝大多数的同

学在上机实习时千万不要机械的照抄本附录所提供的范文。而是应该自己独立的思考

和设计你的算法和程序，并争取在规定的时间内如期完成上机工作任务。对于个别成

绩较差的同学，实在是没法完成任务的建议你不妨抄一遍附录中的样题，以增强你的

感性认识，强化你的实践基础，提高你的实践能力。本附录样题全部用c语言编写，

并全部上机调试通过，但由于时间比较仓促，样题中提供的算法和程序并不是最好的

算法和程序，相信不少的同学一定有能力设计出更好的算法和程序。随着计算机学科

的不断发展，可以使用的语言工具越来越丰富，在本篇中的实习示例还只是应用面向

过程的语言进行设计和编写的程序，同样的实习题，读者也可以用面向对象的语言来

实现。我们希望实习报告示例能起到一个抛砖引玉的作用，在经过同学们的努力学习

和积极使用以后，更多更优良的设计范例能不断涌现，

文中存在的不妥之处，敬请各位不吝赐教!

目录

《数据结构》实验大纲.............................................................4

实验一、线性表操作...............................................................2

实验二、栈和队列的应用...........................................................6

实验三、多维数组和串............................................................12

实验四、树和二叉树的操作........................................................17

实验五、图的操作................................................................23

实验六、各种查找操作............................................................30

实验七、各种排序操作............................................................37

《DataStructuresandAlgorithm》

实验一、线性表操作

一、实验目的

1.掌握用C语言调拭程序的基本方法。

2.掌握线性表的基本运算，如插入、删除等。

二、实验内容

1.线性表在顺序存储结构上的插入元素，删除元素运算

2.线性表在链式存储结构上的建链表，插入结点，删除结点运算

三、实验要求

1.1.C++/C完成算法设计和程序设计并上机调试通过。

2.2.撰写实验报告，提供实验结果和数据。

3.3.分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并

简要给出算法设计小结和心得。

四、程序实现

写出每个操作的算法(操作过程)

五、程序运行情况

写出输入数据及运行结果

六、源程序清单。

程序1：顺序存储的线性表和运算

#include<stdio.h>

SdefineMAXSIZE100

intlist[MAXSIZE];

intn;

/♦insertinaseqlist*/

intsq_insert(intlist[],int*p_n,inti,intx)

{intj;

if(i<0||i>*p_n)return(1);

if(*p_n==MAXSIZE)return(2);

for(j=*p_n+l;j>i;j—)

list[j]=list[j-l];

list[i]=x;

(*p_n)++;

return(0);

}

/♦deleteinaseqlist*/

intsqdelete(intlist[],int*pn,inti)

{intj;

if(i<()||i>=*p_n)return(1);

for(j=i+1;j<=*p_n;j++)

list[j-l]=list[j];

(*p_n)—;

return(0);

}

voidmain()

{inti,x,temp;

西南大学信息管理系第2页

《DataStructuresandAlgorithm》

printf(z，pleaseinputthenumberforn\n");

printf(〃n=〃)；

scanf&n);

for(i=0;i<=n;i++)

{printfClist[%d]=",i);

scanfst[i]);}

printf("Th。listbeforeinsertionis'n");

for(i=0;i<=n;i++)printfC%d",list[i]);

printf(〃\n〃)；

printfC'pleaseinputthepositionwhereyouwanttoinsertavalue\npositior=，");

scanf(飞d",&i);

printf("pleaseinputthevalueyouwanttoinsert.\nx=*);

scanf&x);

temp=sq_insert(lisl,&n,i,x);

switch(temp)

{case0:printf(wTheinsertionissuccessful!\n");

printf("Thelistisafterinsertionis\n");

for(i=0;i<=n;i++)printf("刎",list[i：);

printf("\n");

printf(飞d\n”,n);

break;

case1:

case2:printf("Theinsertionisnotsuccessful!\n");break;}

/♦deleting*/

printf(?，Thelistbeforedeletingis'n");

for(i=0;i<=n;i++)printf(^dlist[i]);

printf(〃\n");

printf("pleaseinputthepositionwhereyouwanttodeleteavalue\npositior=/z);

scanf(〃机T,&i);

temp=sq_delete(list,&n,i);

switch(temp)

{case0:printf(wThedeletingissuccessful!\nz，);

printf(^The1istisafterdeletingis\n");

for(i=0;i<=n;i++)printf(*%d*,list[il);

printf("\n");

printfn);

break;

case1:printf("Thedeletingisnotsuccessful!");break;}

)

程序2链式存储的线性表和运算

#include<stdio.h>

#include<malloc.h>

structnode{

chardata;

structnode*next;

)；

typedefstructnodeNODE;

/♦Thisfunctioncreatesalink_listwithNnodes.*/

NODE*create_link_list(intn)

{inti;

西南大学信息管理系第3页

《DataStructuresandAlgorithm》

NODE*head,*p,*q;

if(n==0)returnNULL;

head=(NODE*)malloc(sizeof(NODE));

p=head;

printf("Pleaseinput%dcharsforthelinklist'n",n);

for(i=0;i<n;i++)

{scanf(*%c",&(p->data)):

q=(NODE*)malloc(sizeof(NODE));

printf(，?test3\n，/);

p->next=q;

P=q；}

scanf(，?%c，z,&(p->data));

getchar();

p->next=NULL;

return(head);)

/♦Thisfunctioninsertsanodewhosevalueisb*/

/♦beforethenodewhosevalueisa,ifthenodeisnotexist,*/

/♦theninsertitattheendofthelist*/

voidinsert(NODE**p_head,chara,charb)

{NODE*p,*q;

q=(NODE*)mal1oc(sizeof(NODE));

q->data=b;

q->next二NULL;

if(*phead==NULL)*phead=q;

else

{p=(NODE*)malloc(sizeof(NODE));

p=*p_head;

while(p->data!=a&&p->next!=NULL)

p=p->next;

q->next-p->next;

p->next=q;)

)

/*Thefunctiondeletesthenodewhosevalueisa,*/

/*ifsuccess,return0,orreturn1*/

intdeletenode(NODE**p_head,chara)

{NODE*p,*q；

q=*p_head;

if(q==NULL)return(1);

if(q->data==a)

{*phead=q->next;

free(q);

return(0);}

else

{while(q->data!=a&&q->next!=NULL)

(p=q；

q=q->next;}

if(q->data==a)

{p->next=q->next;

free(q);

return(0);)

elseietuin(1),}

西南大学信息管理系第4页

《DataStructuresandAlgorithm》

)

voidmain()

{NODE*my_head,*p;

/*createalinklistwithmnodes*/

intm;

charch_a,ch_b;

printf("pleaseinputthenumberofnodesforthelink_list\nm=*);

scanf(飞d",&m);

getchar();

printf；

my_head=(NODE*)ma11oc(sizeof(NODE));

my_head=create_link_list(m);

/♦Outputthelinklist*/

printf(?，Thelinklistislike:\n?，);

p=my_head;

while(p!=NULL)

{printf(“枇"，p->data);

p=p->next;

)

printf("\n");

/♦insertanodewhosevalueisbbeforea*/

printf("Pleaseinputthepositionfora\nch_a=");

getchar();

scanf&ch_a);

getchar();

printf(,zPleaseinputthevaluethatyouwanttoinsert\nch_b=");

scanf("枇"，&ch_b);

getchar();

insert(Smyhead,ch_a,ch_b);

printfC'Thelinklistafterinsertionislike:\n，z);

p=my_head;

while(p!=NULL)

{printf(飞c”,p->data);

p=p->next;

)

printf('\n");

/♦deleteanodewhosevalueisa*/

printf("Pleaseinputthepositionforaa=*);

scanf&cha);

getchar();

de1etenode(&my_head,ch_a);

printf("Thelinklistafterdeletingislike:\n〃)；

p=myhead;

while(p!=NULL)

{printf(*%c",p->data);

p=p->next;

)

printf('\n");

)

西南大学信息管理系第5页

《DataStructuresandAlgorithm》

实验二、栈和队列的应用

一、实验目的

1、掌握枝的特点(先进后出FILO)及基本操作,如入栈、出梭等，栈的顺序存储结构和钻式存

储结构，以便在实际问题背景卜.灵活应用。

2、掌握队列的特点(先进先出FIFO)及基本操作，如入队、出队等，队列顺序存储结构、链式

存储结构和循环队列的实现，以便在实际问题背景下灵。

二、实验内容

1.顺序栈的实现和运算

2.链栈的实现和运算

3.顺序队列的实现和运算

4.链式队列的实现和运算

5.循环队列的实现和运算

三、实验要求

1.用C++/C完成算法设计和程序设计并上机调试通过。

2.撰写实验报告，提供实验结果和数据。

3.分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要

给出算法设计小结和心得。

四、程序实现

写出每个操作的算法(操作过程)

程序运行情况

五、写出输入数据及运行结果

六、源程序清单。

程序1：顺序栈的实现和运算

#include<stdio.h>

#defineMAXN26

charstack[MAXN];

inttop=0;

intpush(charx)

{if(top>=MAXN)

return(1);

stack[top++]=x;

return(0);

}

intpop(char*p_y)

{if(top--0)

return(1);

*p_y=stack[-top];

return(0);

}

voidmain()

{inti;

charch_x,ch_y;

printf(z，inputthecharyouwanttopush'd');

scanf&ch_x);

西南大学信息管理系第6页

《DataStructuresandAlgorithm》

while(ch_x!:'()')

if(push(ch_x)==l)printf("failure!\n");

else

(printf("success!\n");

printf("inputacharforch_xtopush\nch_x=");

getchar();

scanf&ch_x);}

i=0;

while(stack[i]!='\D')

{printf(*%c",stack[i]);

i++;}

if(pop(&ch_y)==l)printf(^failure!Xn^);

else

{prinlf("success!"");

printf(，?Thepopcharis%c\nz，,ch_y);}

for(i=top-l;i>=0;i­)

printf(^c”,stack[i]);

}

程序2：链栈的实现和运算

^include<stdio.h>

#include<malloc.h>

structnode{chardata;

structnode*1ink;

}；

typedefstructnodeNODE;

NODE*top=NULL;

voidpush_l(charx)

{NODE*p;

p-(NODE+)iiialli)c(sizcof(NODE));

p->data=x;

p->link=top;

top=p;

}

intpopl(char*p_y)

{NODE*p;

if(top==NULL)

return(1);

*p_y-top->data;

P-top；

top=top->link;

free(p);

return(0);

}

voidmainO

{NODE*p;

charch_x,ch_y;

printf(?，inputthecharyouwanttopush'd');

西南大学信息管理系第7页

《DataStructuresandAlgorithm》

scanf("/c",&ch_x);

while(ch_x!=，O')

{push_l(ch_x);

getchar();

scanf(飞c",&ch_x);}

p=(NODE*)mal1oc(sizeof(NODE));

P=top;

while(p!=NULL)

{printf(*%c",p->data);

p=p->link;}

printf("\n");

if(pop_l(&ch_y)==l)printf("failure!\n");

else

{printf("success!\n");

，，

printf("Thepopcharis%c\n>ch_y);}

p=(NODE*)malloc(sizeof(NODE));

P=top;

while(p!-NULL)

{printfC"%c”,p->data);

p=p->link;}

printf(〃\n");

}

程序3：顺序队列的实现和运算

#include<stdio.h>

defineMAXN26

charq[MAXN];

inthead--1,tail--1;

intcn_quoue(charx)

{if(tail==MAXN-1)

return(1);

q[++tail]=x;

return(0);

)

intdequeue(char*p_y)

{if(head==tail)

rcturn(l);

*p_y=q[++head];

return(0);

}

voidmain()

{inti;

charch_x,ch_y;

printf("inputthecharyouwanttocnqucuc\n");

scanf&ch_x);

while(ch_x!=，O')

西南大学信息管理系第8页

《DataStructuresandAlgorithm》

if(en_queue(ch_x)==1)printf(z/failure!\n，/);

else

{printf("success!\n");

printf("inputacharforch_xtoenqueue\nch_x=*);

getchar();

scanf(,z%c*.&ch_x);}

i=l；

while(q[i]!='\0')

{printf(*%cq[i])；

i++；}

if(de_queue(&ch_y)==1)printf(^failure!Xn^);

else

{printf("success!\n");

printf("Thedequeuecharis%c\n”,ch_y);}

for(i=head+l;i<=tail;i++)

printfC%c”,q[i]);

}

程序4：链式队列的实现和运算

#include<stdio.h>

#includc<malloc.h>"

structnode{chardata;

structnode*link;

}；

typedefstructnodeNODE;

NODE*hcad,*tail;

voidenqueue1(charx)

{NODE*p；

p=(NODE*)mal1oc(sizeof(NODE));

p->data=x;

p->link=NULL;

if(head=NULL)

head=p;

else

tai1->1ink=p;

tail=p;

)

intdequouel(char*p_y)

{NODE*p；

if(head=NULL)

ieluiu(1),

*p_y=head->data;

p=head;

head=head->link;

free(p);

return(0);

)

voidmain()

{NODE*p;

charch_x,ch_y;

西南大学信息管理系第9页

《DataStructuresandAlgorithm》

printf(z，inputthecharyouwanttoenqueue'n");

scanf("睨",&ch_x);

while(ch_x!=，0')

{en_queue_l(ch_x);

getchar();

scanf("枇"，&ch_x);}

p=(N0DE*)malloc(sizcof(NODE));

p=head;

while(p!=NULL)

{printf(*%c”,p->data);

p=p->link;)

printfC\n*)；

if(de_queue_l(&ch_y)==l)printf("failure!\n");

else

{printf("success!\n");

printf("Thedequeuecharis%c\n”,ch_y);}

p=(NODE*)malloc(sizcof(NODE));

p=head;

while(p!=NULL)

(printfC%c”,p->data);

p=p->link;)

printf(〃\n");

}

程序5：循环队列的实现和运算

#include<stdio.h>

#include<string.h>

#defineMAXN26

charq[MAXN];

inthead=0,tail=0;

inten_c_q(charx)

{tail=(tail+1)%MAXN;

if(tail==head)

{if(tail==0)tail=MAXN-1;

elsetail—;

return(1);}

q[tail]=x;

return(0);

)

intde_c_q(char*p_y)

{if(head=tail)

return(l);

head=(head+1)%MAXN;

*p_y=q[head];

return(0);}

voidmain()

{inti;

charchx,chy;

西南大学信息管理系第10页

《DataStructuresandAlgorithm》

printf(z，inputthecharyouwanttoenqueue'n");

scanf(“枇"，&ch_x);

while(ch_x!=，0')

if(en_c_q(ch_x)==l)printf("failure!\n");

else

{printf("success!\n〃)；

printf(^inputacharforch_xtoenqueue\nch_x=");

getchar();

scanf&ch_x);}

i=l；

while(q[i]!=，\0*)

{printfC%cq[i]);

i++；}

if(de_c_q(&ch_y)=1)printf("failure!\n");

else

{printf("success!\n");

，，

printf("Thedequeuecharis%c\n>ch_y);)

for(i=head+1;i<=tail;i++)

printf(*%c”,q[i]);

)

西南大学信息管理系第11页

《DataStructuresandAlgorithm》

实验三、多维数组和串

一、实验目的

1.掌握稀疏矩阵的特点（三元组存储方法）。

2.掌握串的运算（赋值，比较，联结，插入子串，模式匹配……等）。

二、实验内容

1-稀疏矩阵的存储及转置运算

2.串的基本操作

三、实验要求

1.用C++/C完成算法设计和程序设计并上机调试通过。

2.撰写实验报告，提供实验结果和数据。

3.分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要

给出算法设计小结和心得。

四、程序实现

写出每个操作的算法（操作过程）

程序运行情况

五、写出输入数据及运行结果

六、源程序清单。

程序1：稀疏矩阵的存储及转置运算

Sinclude<stdio.h>

typedefstruct{

introw

intcol

intval

}THA;

^defineMAX20

main()

{inti,j,count=l;

intcol,row,val;

THAs[MAX];

THAt[MAX];

printf(z，inputthenumberofrow,colandelements:");

scanf(*%d,%d,$d”,row,&s[0].col,&s[0].val);

if(s[0].val==0)return;

val=s[0].val;

for(i=l;i<=val;i++);

scanf("%d,%d,%d”,&s[i].row,&s[i].col,&s[i].val);

row=s[0].row;

col=s[0].col;

count=l;

for(i=l;i<=col;i++)

for(j=l;j<=val;j++)

if(s[j].col==i)

t[count],row=s[j].col;

t[count],col=s[j].row;

t[count++].val=s[j].val;

西南大学信息管理系第12页

《DataStructuresandAlgorithm》

t[0].row=CO1；

t[0].col=row；

t[0].val=val;

for(i=0;i<=val;i++)

printf("%d,%d,%d\n*,t[i].row,t[i].col,t[i].val);

}

程序2：串的实现和运算

#include<stdio.h>

#defineMAXN128

typedefenum{fail,success)status;

typedefenurn{false,true}boolean;

main()

{intstrlenO;

voidstrass();

booleanstrcmpO;

statusstrcat();

statusstrins();

voidpatmatch();

intt,n,i;

booleanb;

statusst;

chars[MAXN],si[JfAXN],s2[MAXN];

printf(z，\nl.Thelengthofstring'n");

printfC2.Theassignmentofslring\n〃)；

printf("3.Astringcomparewithanotherstring:\n，z);

printfC4.Astringconnectwithanotherstring:\n/z);

printfC5.Astringtoboinsertedintoanotherstring\n，z)

printf(z，6.Thepatternmatchofstring:'')；

printf(z，Pleaseinputaopertation：z，);

scanf(飞d",&t);

switch(t)

(case1:

printf(vpleaseinputastring:\n");

getcharO;

gets(s);

n=strlen(s);

printf("thelengthis:%d”,n);

break;

case2:

piiiitr(*pleabeinputthefirststring:\n");

getchar();

gets(sl);

printf("pleaseinputthesecondstring:\nz，);

getchar();

gets(s2);

strass(sl,s2);

break;

case3:

printf("pleaseinputthefirststring:\nz，);

gctchar0;

西南大学信息管理系第13页

《DataStructuresandAlgorithm》

gets(sl)；

printf(^pleaseinputthesecondstring:\n");

gets(s2);

b=strcmp(sl,s2);

if(b==true)

printf(^equal\n，z);

else

printf(*notequal\n");

break;

case4:

printf('pleaseinputthefirststring:Xn^);

getcharO;

gets(si);

printf("pleaseinputthesecondstring:\nw);

gets(s2);

st=strcat(si,s2);

if(st==success)

printf("answeris%s\n',si);

else

printf("error!\n");

break;

case5:

printf('pleaseinputthefirststring:\n，/);

getcharO；

gets(si);

printf('pleaseinputthesecondstring:\n，/);

gets(s2);

printf('pleaseinputi:〃)；

scanf(飞d",&i);

st=strins(sl,i,s2);

if(st==success)

printf("answeris%s\n〃，si)；

elseprintf(，，error!\n/，);

break;

case6:

patmatch();

break;

default:printf("Thereisn*tthisoperation!");

)

)

intstrlen(s)

chars[];

{inti;

for(i=0;s[i]!=\0';i++);

return(i);

}

voidstrass(si,s2)

charsi[],s2[];

{inti=0;

while(sl[i]!='\0')

{s2[i]=sl[i];

西南大学信息管理系第14页

《DataStructuresandAlgorithm》

i++；

)

s2[i]=，\0\

printf(*s2is%s”,s2);

)

boo1eanstrcmp(s1,s2)

charsi[],s2[];

{inti=0;

whi1e(si[i]==s2[i]&&sl[i]!='\0'&&s2[i]!=>\0*)

i++;

if(si[i]==，\0J&&s2[i]==>\0*)

return(true);

else

return(false);

)

statusstrcat(si,s2)

charsi[],s2[];

{inti,j,k;

i=strlen(sl);

j=strlcn(s2);

if((i+j)>=MAXN)

return(fail);

for(k=0;k<=j;k++)

si[i+k]=s2[k];

return(success);

}

statusstrins(sl,i,s2)

charsi[],s2[];

inti;

{intm,n,k;

m=strlen(sl);

n=strlen(s2);

if(i<0||i>m||(m+n)>MAXN)

return(fail);

for(k=m;k>=i;k­)

si[k+n]=sl[k];

for(k=0;k<n;k-H-)

si[i+k]=s2[k];

return(success);

}

intsniatch(ch,n,pat,m)

charch[],pat[];

intn,m;

{ints,p,k;

for(s=0;s<=n-m;s++)

(

for(p=0,k=s;p<m&&ch[k]==pat[p];k++,p++);

if(p==m)return(s+l);

)

return(-1);

西南大学信息管理系第15页

《DataStructuresandAlgorithm》

voidpatmatch()

{charch[MAXN],pat[MAKN];

intn,m,result;

printf('，\ninputtheprimarystring:Xn^);

scanfch);

printf(*inputthepatternstring:\n,z);

scanf(“%s",pat);

n=strlen(ch);

m=strlen(pat);

result=smatch(ch,n,pat,m);

if(result==-l)printfC*XnNomatchedfound!");

elseif(result>=0)printf('AnMatchedsubstringfoundinposition%d，/,result);

)

西南大学信息管理系第16页

《DataStructuresandAlgorithm》

实验四、树和二叉树的操作

一、实验目的

1.进一步掌握树的结构及非线性特点，递归特点和动态性。

2.进一步巩固对指针的使用和二叉树的三种遍历方法、建立方法及用广义表进行输入输出。

二、实验内容

1.二叉树的实现和运算

2.线索二叉树的实现

3.哈夫曼树的实现

三、实验要求

1.用C++/C完成算法设计和程序设计并上机调试通过。

2.撰写实验报告，提供实验结果和数据。

3.分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要

给出算法设计小结和心得。

四、程序实现

写出每个操作的算法（操作过程）

程序运行情况

五、写出输入数据及运行结果

六、源程序清单。

程序1：二叉树的实现和运算

#include<stdio.h>

#include<stdlib.h>

#include<malloc.h>

typedefstructbinode

{chardata;/"supposethedatafield'stypeischar*/

structbtnode*lchild;/*leftpointerfield*/

structbtnode*rchild:/*rightpointerfield*/

}N0DE;

voidmain()

{NODE*root,*q,n;

NODE*create(NODE*p);

voidpreorder(NODE*root);

voidinorder(NODE*root);

voidpostorder(NODE*root);

intt;

q=&n;

root=create(q);

printf(z，Atthefirst,wecreateatree'n");

printf(''Pleaseinputnodesoftree\n,/);

if(root==NULL)printf("It'sanemptytree!\nw);

else

printfCAni.Thepreordetraverse\n〃)；

printfC2.Theinordertraverse'n");

printfC3.Thepostordertraverse'n");

printfCPleasechooseakindoforder'n");

scanf("/d",&t);

西南大学信息管理系第17页

《DataStructuresandAlgorithm》

switch(t)

{

case1:preorder(root);break;

case2:inorder(root);break;

case3:postorder(root);break;

default:printfTheerror!");

)

}

}

NODE*create(NODE*p>/*createthestructureofbinarytree*/

{charch;

NODE*t;

scanf&ch);

if(ch==，')p=NULL;

else

(p->data=ch;

t=(NODE*)malloc(sizcof(NODE));

p->lchild=create(t);

t=(NODE*)maHoc(sizeof(NODE));

p->rchild=create(t);

}

returnp;

)

voidpreorder(NODE*root)/*travelthetreeusingpreorder*/

{if(root!=NULL)

(printf("%c*.root->data);

preordor(root->lchild);

preorder(root->rchiId);

)

return;

)

voidinorder(NODE*root)/*travelthetreeusinginorder*/

if(root!=NULL)

{inorder(root->lchiId);

printfC%c”,root->data);

inorder(root->rchiId);

)

return;

)

voidpoblurdei(NODE+iuol)/*liavelthetieeusingpusloider*/

{if(root!=NULL)

(postorder(root->lchiId);

postorder(root->rchiId);

printfC%c”,root->data);

)

return;

)

程序2：线索二叉树的实现和运算

^include<stdio.h>

#includc<stdlib.h>

西南大学信息管理系第18页

《DataStructuresandAlgorithm》

#include<ma11oc.h>

structbtnode

{chardata;Adatafield*/

intIbit;/*leftflagfield*/

intrbit;/*rightflagfield*/

structbinode*lchiId;/*leftpointerfield*/

structbtnode*rchild;/*rightpointerfieldd**/

｝；

typedefstructbtnodeNODE;

NODE*pre;

voidmain()

{NODE*create(NODE*p);

voidinthread(NODE*root);

NODE*q,*root;

q=(NODE*)malloc(sizcof(NODE));

printf(^XnAtfirst,wecreateatree!\n");

printf("Pleaseinputthedataofthetree!\n^);

root二create(q);

inthread(root);

)

NODE*create(NODE*p)/*createastructureofbinarytree*/

{charch;

NODE*t;/*supposethetypeofthedataisint*/

scanf&ch);

if(ch=='')

p=NULL;

else

{p->data=ch;

p->lbit=0;

t=(NODE*)malloc(sizeof(NODE));

p->lchild=create(t);

t=(NODE*)malloc(sizeof(NODE));

p->rchild=create(t);

}

returnp;

)

voidinthread(NODE*root)

{voidinthreading(NODE**p);

voidinvodth(NODE**h);

NODE*t;

t=((NODE*)malloc(sizeof(NODE)));

t->lbit=O;t->rbit=l;

t->rchild=t;

if(root==NULL)

t->lchild=t;

else

{pre=t;

inthreading(&root);/"producethethreadtreeusinginorder*/

t->lchild=root;/*thelastnodeformthethread*/

pre->rchild=t;

pie->rbit=l,

西南大学信息管理系第19页

《DataStructuresandAlgorithm》

t->rchild=pre;

}

invodth(&t);

}

voidinthreading(NODE**p)

if((*p)!=NULL)

{inthreading(&((*p)->lchiId));/*leftsubtreeformthethread*/

if(((*p)->lchild)==NULL)

{(*p)->lbit=l;

(*p)->lchild=pre;

)

if(pre->rchild==NULL)

{pre->rbit=l;

pre->rchild=*p;

}

pre=*p;

inthreading(&((*p)->rchiId));Arightsubtreeformthethread*/

)

)

voidinvodth(NODE**h)/*travclthebinarytreeusingtheino