数据结构实验指导书

《数据结构与算法》

试验指导书

2022年8月

目录

试验一C语言编程复习1

试验二线形表基本操作的实现5

试验三栈和队列基本操作的实现及应用14

试验四二叉树算法的实现24

试验五图的算法的实现36

试验六查找算法的实现52

试验七排序算法的实现62

试验一C语言编程复习

一、试验目的

1.熟识C语言的上机环境，进一步把握C语言的结构特点。

2.理解指针与应用的区分。

3.把握结构体的使用。

4.把握简洁排序方法。

二、试验内容

(1)输入一行字符，计算该行字符中包含多少个单词，单词之间用空格

分隔开。

(2)采用add函数求两个复数2+3i和4+5i的和。(要求用结构体来定义

复数)

(3)一个班上有30名同学，每个同学的数据作为一个纪录，每个纪录包

括学号、姓名、三门课程的成果和三门课程平均成果。从键盘输入

同学的学号、姓名及三门课的成果。要求打印三门课程平均成果最

高分的同学纪录。

三、试验步骤

(1)用数组或字符串猎取字符，遇到空格即表示新单词的开头。

(2)要求用结构体来定义复数，包括实部和虚部。

(3)定义一个Student的结构体类型，包含学号、姓名、成果等成员。

四、实现提示

structstudent

{charnum[6];

stringname;

floatscore[3];

floataver;

);

五、思索与提高

思索为何voidSwap1(Student,Student)这个函数无法实现两个同学的交

换？

六、完整参考程序

1、

#include<iostream>

#include<string>

usingnamespacestd;

voidmainO

(

cout。〃输入n个单词，单词之间用空格隔开〃<lndl;

stringstr;

getline(cin,str);

intnum=0;

intlen=str.size();

if(len!=0)num=l;

for(inti=0;i<len;i++)

if(str[i]=='')

(

num++;

)

)

cout<<〃单词个数为：〃〈<num〈〈6ndl;

)

也可使用数组实现：

^include<iostream>

usingnamespacestd;

voidmainO

(

cout<<〃输入n个单词，单词之间用空格隔开〃Gendl;

charstr[100];

cin>>str;

intnum=0;

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

(

if(str[i]=,f)

(

num++;

)

}

cout<〈〃单词个数为：〃《num<<endl;

)

2、

#include<iostream>

usingnamespacestd;

structcomplex

{

floatreal;

floatimag;

};一

complexadd(complexxl,complexx2)

(

complexsum;

sum.real=xl.real+x2.real;

sum.imag=xl.imag+x2.imag;

returnsum;

voidmain()

(

complexx1={2,3},x2={4,5},sum;

complexadd(complexxl,complexx2);

sum=add(xl,x2);

cout«ux1="«xl.real«"+,,«xl.imag«nin«n

n«nx2=n«x2.real«',+',«x2.imag«,,i',«endl;

cout«nx1+x2=',«sum.real«n4-,,«sum.imag«',i,,«endl;

)

3、

#include<iostream>

#include<string>

#include<iomanip>

usingnamespacestd;

constintn=3;

structstudent

{charnum[6];

stringname;

floatscore[3];

floataver;

);

intmain()

{intij,maxi,max,sum;

floataverage;

studentstudfn];

for(i=0;i<n;i++)〃输入同学和成果信息

{cout«"inputscoresofstudentn«i+l«endl;

cout«"number:H;

cin»stud[i].num;

cout«"name:";

cin»stud[i].name;

for(j=O；j<3;j++)

{cout«nscoren«j+l«n:n;

cin»stud[i].score[j];

)

cout«endl;

)〃输入同学和成果信息

average=0;

max=0;

maxi=0;

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

{sum=0;

for(j=0;j<3;j++)〃计算每个同学总成果

sum+=stud[i].score[j];

studfi].aver=sum/3.0;//计算每个同学平均成果

if(sum>max)〃将某同学平均成果与目前的最高平均成果进行比较

选择高的那个为最新最高平均成果

{max=sum;

maxi=i;

cout«"score1score2score3average"«endl;

for(i=0;i<n;i++)〃输出全部同学成果信息

{cout«setw(8)«stud[i].num«H"«setw(10)«stud[i].name«n”；

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

cout<vsetw(3)«stud[i].score[jkv"”；

cout«stud[i].aver«endl;}〃输出全部同学成果信息

cout«nThehighestscoreis:n«stud[maxi].num«n,K«stud[maxi].name«n,

n«nTheaverageis:"«stud[maxi].aver;

cout«",threescores:n;〃输出最高平均成果的同学信息

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

cout«stud[maxi].score[j]«nn;

cout«endl;

return0;

试验二线形表基本操作的实现

一、试验目的

1.熟识C语言的上机环境，进一步把握C语言的结构特点。

2.把握线性表的挨次存储结构的定义及C语言实现。

3.把握线性表的链式存储结构——单链表的定义及C语言实现。

4.把握线性表在挨次存储结构即挨次表中的各种基本操作。

5.把握线性表在链式存储结构——单链表中的各种基本操作。

二、试验内容

1.挨次线性表的建立、插入及删除。

2.链式线性表的建立、插入及删除。

三、试验步骤

1.建立含n个数据元素的挨次表并输出该表中各元素的值及挨次表的长

度。

2.采用前面的试验先建立一个挨次表L=[21,23,14,5,56,17,31},

然后在第i个位置插入元素68o

3.建立一个带头结点的单链表，结点的值域为整型数据。栗求将用户输入

的数据按尾插入法来建立相应单链表。

四、实现提示

1.由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就

是挨次结构。因此，可用C语言的一维数组实现线性表的挨次存储。

在此，我们采用C语言的结构体类型定义挨次表：

#defineMAXSIZE1024

typedefintelemtype;/*线性表中存放整型元素*/

typedefstruct

{elemtypevecfMAXSIZE];

intlen;/*挨次表的长度*/

}sequenlist;

将此结构定义放在一个头文件sqlist.h里，可避开在后面的参考程序中代

码重复书写，此外在该头文件里给出挨次表的建立及常量的定义。

2.留意如何取到第i个元素，在插入过程中留意溢出状况以及数组的下

标与位序（挨次表中元素的次序）的区分。

3.单链表的结点结构除数据域外，还含有一个指针域。用C语言描述结

点结构如下：

typedefintelemtype;

typedefstructnode

{elemtypedata;〃数据域

structnode*next;〃指针域

}linklist;

留意结点的建立方法及构造新结点时指针的变化。构造一个结点需用到C

语言的标准函数malloc(),如给指针变量p安排一个结点的地址：

p=(linklist*)malloc(siz60f(linklist));该语句的功能是申请安排一个类型为

linklist的结点的地址空间，并将首地址存入指针变量p中。当结点不需要时

可以用标准函数free(p)释放结点存储空间，这时p为空值(NULL)。

五、思索与提高

1.假如按由表尾至表头的次序输入数据元素，应如何建立挨次表。

2.在main函数里假如去掉L二&a语句，会消失什么结果？

六、完整参考程序

#include<stdio.h>

#include<conio.h>

#defineMAX30〃定义线性表的最大长度

enumBOOL{False,True);〃定义BOOL型

typedefstruct{

charelem[MAX];〃线性表

intlast;//last指示当前线性表的长度

Jsqlist;

voidinitial(sqlist&);〃初始化线性表

BOOLinsert(sqlist&,int,char);〃在线性表中插入元素

BOOLdel(sqlist&Jnt,char&);//在线性表中删除元素

intlocate(sqlist,char);〃在线性表中定位元素

voidprint(sqlist);〃显示线性表中全部元素

voidmain()

{sqlistS;//S为一线性表

intloc,flag=l;

charj,ch;

BOOLtemp;

printff本程序用来实现挨次结构的线性表。\nn);

printf("可以实现查找、插入、删除等操作。\n")；

initial(S);〃初始化线性表

while(flag)

{printf("请选择:\n");

printf("1.显示全部元素5”)；

printf(”2.插入一个元素\n")；

printf("3.删除一个元素\n")；

printf("4.查找一个元素曲”)；

printf("5.退出程序\nn);

scanf(M%c'\&j);

switch(j)

{case*r：print(S);break;//显示全部元素

case2:{printf(”请输入要插入的元素(一个字符)和插入位置:\n")；

printf(”格式:字符，位置;例如:a,2\n");

scanf("%c,%dH,&ch,&loc);〃输入要插入的元素和插入的位置

temp=insert(S,loc,ch);〃插入

if(temp==False)printf("插入失败八n")；〃插入失败

else{printf("插入胜利!\n");print(S);}〃插入胜利

break;

)

case3:{printf("请输入要删除元素的位置蜜

scanf("%d",&loc);〃输入要删除的元素的位置

temp=del(S,loc,ch);〃删J除

if(temp==True)printf(”删除了一个元素:％c\n”,ch);//删除胜利

elseprintf(“该元素不存在!\n")；〃删除失败

print(S);

break;

)

case'4':{printf("请输入要查找的元素:")；

scanf("%c",&ch);〃输入要查找的元素

loc=locate(S,ch);//定位

if(loc!=-l)printf("该元素所在位置:％d\n",loc+l);//显示该元素位置

elseprintf("%c不存在!\n",ch);〃当前元素不存在

break;

)

default:flag=O;printf("程序结束,按任意键退出!\n")；

)

)

getch();

voidinitial(sqlist&v)

{〃初始化线性表

inti;

printf(”请输入初始线性表长度：n=)〃输入线性表初始化时的长度

scanf(u%d",&v.last);

printf(”请输入从1到％(1的各元素(字符)，例如:abcdefgW”,v.last);

getchar();

for(i=0;i<v.last;i++)scanf(H%cn,&v.elem[i]);//输入线性表的各元素

}

BOOLinsert(sqlist&v,intloc,charch)

{//插入一个元素，胜利返回True,失败返回False

inti;

if((loc<l)||(loc>v.last+1))

{printf("插入位置不合理!\n")；〃位置不合理

returnFalse;

)

elseif(v.last>=MAX)〃线性表已满

{printf("线性表已满!\n");

returnFalse;

)

else{for(i=v.last-l;i>=loc-l;i—)v.elem[i+1J=v.elem[iJ;〃其后元素依次后移

v.elem[loc-l]=ch;〃插入元素

v.last++;〃线性表长度加一

returnTrue;

)

)

BOOLdel(sqlist&v,intloc,char&ch)

{//删除一个元素，胜利返回True,并用ch返回该元素值，失败返回False

intj;

if(loc<l||loc>v.last)〃删除位置不合理

returnFalse;

else{ch=v.elem[loc-l];//ch取得该元素值

for(j=loc-1;j<v.last-l;j++)v.elem[jj=v.elem[j+1];〃其后元素依次前移

v.last—;〃线性表长度减一

returnTrue;

)

)

intlocate(sqlistv,charch)

{〃在线性表中查找ch的位置，胜利返回其位置，失败返回-I

inti=0;

while(i<v.last&&v.elem[i]!=ch)i++;〃当前位置后移，直到找到为止

if(v.elem[i]==ch)//找到当前元素

returni;

elsereturn(-l);

)

voidprint(sqlistv)〃显示当前线性表全部元素

{inti;

for(i=0;i<v.last;i++)printf(n%cn,v.elem[i]);

printf(,'\n,');

)

2.链式线性表的建立、插入及删除。

#include<conio.h>

#include<stdio.h>

#include<stdlib.h>

#defineLENsizeof(LNode)//定义LEN为一个节点的长度

enumBOOL{False,True};〃定义BOOL型

typedefstructnode

{chardata;〃数据域

structnode*next;〃指向下一个节点的指针

}LNode,*LinkList;

voidCreatList(LinkList&,int);〃生成一个单链表

BOOLListInsert(LinkList&,int,char);//在单链表中插入一个元素

BOOLListDelete(LinkList&,int,char&);〃在单链表中删除一个元素

BOOLListFind_keyword(LinkList,char,int&);//按关键字查找一个元素

BOOLListFind__order(LinkList,char&,int);〃按序号查找一个元素

voidListPrint(LinkList);//显示单链表全部元素

voidmain()

{LinkListL;

BOOLtemp;

intnum,loc,flag=l;

charj,ch;

printf("本程序实现链式结构的线性表的操作。\nn);

printf("可以进行插入，删除，定位，查找等操作。\n")；

printf(”请输入初始时链表长度:");//输入生成单链表时的元素个数

scanf("%d",&num);

CreatList(L,num);〃生成单链表

ListPrint(L);

while(flag)

{printf("请选择:\n)

printf("l.显示全部元素\n");〃显示链表元素

printf("2.插入一个元素\n");〃插入链表元素

printf("3.删除一个元素\n")；〃删除链表元素

printf("4.按关键字查找元素\n")；//按关键字查找

printf(”5.按序号查找元素\n");//按序号查找

printf("6.退出程序\n")；〃退出

scanf(n%c”,&j);

switch(j)

{case'r：ListPrint(L);break;

case2:{printf("请输入元素(一个字符)和要插入的位置:\n”)；

printf(”格式:字符,位置；例如:a,3\n");

scanf("%c,%d",&ch,&loc);〃输入要插入的元素和耍插入的位置

temp=ListInsert(L,loc,ch);//插入

if(temp==False)printf("插入失败!\n");〃插入失败

elseprintf("插入胜利!\n");//胜利插入

ListPrint(L);

break;

)

case3:printf("请输入要删除的元素所在位置

scanf(n%d",&loc);〃输入要删除的节点的位置

temp=ListDelete(L,loc,ch);〃删除

if(temp==False)printf("删除失败!\n)〃删除失败

elseprintf("胜利删除了一个元素:％c\n”,ch);〃删除胜利，显示该元素

ListPrint(L);

break;

case,4,:if(L->next==NULL)〃链表为空

printf("链表为空!\n");

else{printf("请输入要查找的元素(一个字符):")；

scanf(n%c",&ch);〃输入要查找的元素

temp=ListFind_keyword(L,ch,loc);//按关键字查找

if(temp==False)printf("没有找到该元素!\n");〃查找失败

elseprintf("该元素在链表的第％(1个位置。\n'\loc);

//胜利查找，显示该元素位置

)

break;

case,5,:if(L->next==NULL)〃链表为空

primf("链表为空!\n”);

else{primf("请输入要查找的位置

scanf("%d",&loc);〃输入要查找的元素的位置

temp=ListFind_order(L,ch,loc);〃按序号查找

if(temp==False)printf("该位置不存在!\n");〃查找失败

elseprintf("第％d个元素是：%c\nH,loc,ch);

//胜利查找，显示该元素

break;

default:flag=O;printf("程序结束,按任意键退出!\n");

)

}

getch();

}

voidCreatList(LinkList&v,intn)

{〃生成一个带头结点的有n个元素的单链表

inti;

LinkListp;

v二(LinkLisl)malloc(LEN);〃生成头结点

v->next=NULL;

printf("请输入％d个字符：例如：abcdefg\n",n);

getchar();

for(i=n;i>0;-i)

{p=(LinkList)malloc(LEN);〃生成新结点

scanf(n%cn,&p->data);

p->next=v->next;

v->next=p;

}

)

BOOLListInsert(LinkList&v,inti,chare)

{//在单链表的第i各位置插入元素e,胜利返回True,失败返回False

LinkListp,s;

intj=O;

p=v;

while(p&&j<i-l){p=p->next;++j;)〃查找第i-1个元素的位置

if(!plU>i-l)returnFalse;〃没有找到

s=(LinkList)malloc(LEN);〃生成一个新结点

s->data=e;

s->next=p->next;〃将新结点插入到单链表中

p->next=s;

returnTrue;

)

BOOLListDelete(LinkList&v,inti,char&e)

{〃在单链表中删除第i个元素,胜利删除返回True,并用e返回该元素值，失败返回False

LinkListp,q;

intj=O;

p=v;

while(p->next&&j<i-1)//查找第i-1个元素位置

{p=p->next;++j;}

if(!(p->next)||j>i-l)returnFalse;〃查找失败

q=p->next;p->next=q->next;〃删除该元素

e=q->data;//e取得该元素值

free(q);〃释放该元素空间

returnTrue;

)

BOOLListFind_keyword(LinkListv,chare,int&i)

{〃在单链表中查找关键字为e的元素，胜利返回True,并用i返回该元素位置,

〃失败返回False

i=l；

LinkListp;

p=v->next;

while((p->data!=e)&&(p->next!=NULL))//p指针指向下一个,直到

{p=p->next;i++;}〃找到或到链表尾为止

if(p->data!=e)〃该元素在链表中不存在

returnFalse;

elsereturnTrue;

)

BOOLListFind_order(LinkListv,char&e,inti)

{〃在单链表中查找第i个元素，胜利返回True,并用e返回该元素值，

〃失败返回False

LinkListp;

intj=0;

P=v;

while(p->next&&j<i)//移动指针，直到找到第i个元素

{p=p->next;++j;}

if(j!=i)returnFalse;〃查找失败

else{e=p->data;〃查找胜利，用e取得该元素值

returnTrue;

}

)

voidListPrint(LinkListv)

{〃显示链表全部元素

LinkListq;

q=v->next;

printf("链表全部元素

while(q!=NULL)

{printf("%c,\q->data);q=q->next;}

printf(n\n");

试验三栈和队列基本操作的实现及应用

一、试验目的

1.把握栈的挨次表示和实现

2.把握队列的链式表示和实现

二、试验内容

1.编写一个程序实现挨次栈的各种基本运算。

2.实现队列的链式表示和实现。

三、试验步骤

1.初始化挨次栈

2.插入元素

3.删除栈顶元素

4.取栈顶元素

5.遍历挨次栈

6.置空挨次栈

7.初始化并建立链队列

8.入链队列

9.出链队列

10.遍历链队列

四、实现提示

1./*定义挨次栈的存储结构*/

typedefstruct{

ElemTypestack[MAXNUM];

inttop;

}SqStack;

/*初始化挨次栈函数列

voidInitStack(SqStack*p)

{q=(SqStack*)manoc(sizeof(SqStack)/*申请空间*/)

/*入栈函数号

voidPush(SqStack*p,ElemTypex)

{if(p->top<MAXNUM-l)

{p->top=p->top+1;/*栈顶+1*/

p->stackfp->top]=x;}/*数据入栈*/

)

/*出栈函数*/

ElemTypePop(SqStack*p)

{x=p->stack[p->top];/*将栈顶元素赋给x*/

p->top=p->top-l;}/*栈顶-1*/

/*猎取栈顶元素函数刃

ElemTypeGetTop(SqStack*p)

{x=p->stackfp->top];}

/*遍历挨次栈函数刃

voidOutStack(SqStack*p)

{for(i=p->top;i>=0;i-)

printf("第％d个数据元素是：%6d\nn,i,p->stack[i]);}

/*置空挨次栈函数*/

voidsetEmpty(SqStack*p)

{p->top=-l;}

2./*定义链队列*/

typedefstructQnode

{ElemTypedata;

structQnode*next;

JQnodetype;

typedefstruct

{Qnodetype*front;

Qnodetype*rear;

JLqueue;

/*初始化并建立链队列函数*/

voidcreat(Lqueue*q)

{h=(Qnodetype*)malloc(sizeof(Qnodetype));/*初始化申请空间*/

h->next=NULL;

q->front=h;

q->rear=h;

for(i=l;i<=n;i++)*采用循环快速输入数据*/

{scanf("%dn,&x);

Lappend(q,x);}/*采用入链队列函数快速输入数据*/

)

/*入链队列函数*/

voidLappend(Lqueue*q,intx)

{s->data=x;

s->next=NULL;

q->rear->next=s;

q->rear=s;}

/*出链队列函数*/

ElemTypeLdelete(Lqueue*q)

{p=q->front->next;

q->front->next=p->next;

if(p->next==NULL)

q->rear=q->front;

x=p->data;

free(p);}/*释放空间*/

/*遍历链队列函数*/

voiddisplay(Lqueue*q)

{while(p!=NULL)/*采用条件推断是否到队尾*/

{printf(n%d—>",p->data);

p=p->next;

)

)

五、思索与提高

1.读栈顶元素的算法与退栈顶元素的算法有何区分？

2.假如一个程序中要用到两个栈，为了不发生上溢错误，就必需给每个

栈预先安排一个足够大的存储空间。若每个栈都预安排过大的存储空间，势

必会造成系统空间紧急。如何解决这个问题？

(1)链栈只有一个top指针，对于链队列，为什么要设计一个头指针和

一个尾指针？

(2)一个程序中假如要用到两个栈时，可通过两个栈共享一维数组来实

现。即双向栈共享邻接空间。假如一个程序中要用到两个队列，能否实现？

如何实现？

六、完整参考程序

1.栈的挨次表示和实现

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

#defineTRUE1

#defineFALSE0

#defineOK1

#defineERROR0

#defineINFEASIBLE-1

#defineOVERFLOW-2

typedefintStatus;

typedefintSElemType;

//---栈的挨次存储表示—-

#defineSTACKJNIT.SIZE100

#defineSTACKINCREMENT10

typedefstruct{

SElemType*base;

SElemType*top;

intstacksize;

}SqStack;

StatusInitStack(SqStack&S);

StatusDestroyStack(SqStack&S);

StatusStackDisplay(SqStack&S);

StatusGetTop(SqStackS,SElemType&e);

StatusPush(SqStack&S,SElemTypee);

StatusPop(SqStack&S,SElemType&e);

StatusStackEmpty(SqStackS);

StatusInitStack(SqStack&S){〃构造一个空栈S

S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));

if(!S.base)exit(OVERFLOW);〃存储安排失效

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

returnOK;

}//InitStack

StatusDestroyStack(SqStack&S){〃销毁栈S

if(S.base)free(S.base);

S.top=S.base=NULL;

returnOK;

}//InitStack

StatusStackDisplay(SqStack&S){〃显示栈S

SElemType*p=S.base;

inti=0;

if(S.base==S.top){

printf(”堆栈已空!\n")；

returnOK;

)

while(p<S.top)

printf("[%d:%d]",++i,*p++);

printf("\n”)；

returnOK;

}//StackDisplay

StatusGetTop(SqStackS,SElemType&e){

〃若栈不空，则用e返回S的栈顶元素，

〃并返回OK;否则返回ERROR

if(S.top==S.base)returnERROR;

e=*(S.top-l);

returnOK;

}//GetTop

StatusPush(SqStack&S,SElemTypee){〃插入元素e为新的栈顶元素

if(S.top-S.base>=S.stacksize){〃栈满，追加存储空间

S.base=(SElemType*)realloc(S.base,

(S.stacksize+STACKINCREMENT)*sizeof(SElemType));

if(!S.base)exit(OVERFLOW);〃存储安*非失贝攵

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

)

*S.top++=e;

returnOK;

}//Push

StatusPop(SqStack&S,SElemType&e){

〃若栈不为空，则删除S的栈顶元素，

〃用e返回其值，并返回OK;否则返回ERROR

if(S.top==S.base)returnERROR;

e=*—S.top;

returnOK;

}//Pop

StatusStackEmpty(SqStackS){

〃若S为空栈，则返回TRUE,否则返回FALSE。

if(S.top==S.base)returnTRUE;

elsereturnFALSE;

)//StackEmpty

voidmain(){

SqStackSt;

Statustemp;

intflag=I,ch;

inte;

printf("本程序实现挨次结构的堆栈的操作。\nu);

printf("可以进行入栈，出栈，取栈顶元素等操作。\nn);

InitStack(St);〃初始化堆栈St

while(flag){

printf("请选择:\n");

printf("l.显示栈中全部元素W");

printf(”2.入栈\n");

printf("3.出栈

printf(”4.取栈顶元素W”)；

printf(”5.退出程序

scanf("％d”,&ch);

switch(ch){

case1:

StackDisplay(St);

break;

case2:

printf(”请输入要入栈的元素(一个整数):")；

scanf(u%d",&e);〃输入要入栈的元素

temp=Push(St,e);〃入栈

if(temp!=OK)printf("堆栈已满!入栈失败!\n”)；

else{

printf("胜利入栈!\n)〃胜利入栈

StackDisplay(St);

)

break;

case3:

temp=Pop(St,e);〃出栈

if(temp==ERROR)printf("堆栈巳空!\nu);

else{

printf("胜利出栈一个元素:％d\n”,e);〃胜利出栈

StackDisplay(St);

}

break;

case4:

temp二GetTop(St,e);〃取得栈顶元素

if(temp==ERROR)printf(”堆栈已空!\nH);

elseprinlf("栈顶元素是:％d\n”,e);〃显示栈顶元素

break;

default:

flag=O;

printf("程序结束，按任意键退出!\n");

getch();

DestroyStack(St);

2.队列的链式表示和实现

#include<conio.h>

#include<stdio.h>

#include<stdlib.h>

#defineTRUE1

#defineFALSE0

#defineOK1

#defineERROR0

#defineINFEASIBLE-1

#defineOVERFLOW-2

//Status是函数的类型，其值是函数结果状态代码

typedefintStatus;

//ElemType是挨次表数据元素类型,此程序定义为int型

typedefintQElemType;

//—-单链队列-队列的链式存储结构--

typedefstructQNode{〃定义结点结构

QElemTypedata;〃数据域

structQNode*next;//指针域

}QNode,*QueuePlr;

typedefstructlinkqueue{〃定义队列结构

QueuePtrfront;〃队头指针

QueuePtrrear;〃队尾指针

)LinkQueue;

StatusInitLinkQueue(LinkQueue&);〃初始化一个队列

StatusDestroyLinkQueue(LinkQueue&);〃销毁一个队列

intLinkQueueLength(LinkQueue&Q);〃队列的长度

StatusEnLinkQueue(LinkQueue&,QElemType);〃将一个元素入队列

StatusDeLinkQueue(LinkQueue&,QElemType&);〃将一个元素出队列

StatusDisplayLinkQueue(LinkQueue);〃显示队列中全部元素

voidmain(){

LinkQueueLQ;

QElemTypee;

intflag=l,ch,len;

Statustemp;

printfC,本程序实现链式结构队列的操作。\nn);

printf("可以进行入队列、出队列等操作。\nM);

InitLinkQueue(LQ);〃初始化队列

while(flag){

printf("请选择:\n");

printf(M1.显示队列全部元素\n”)；

printf(”2.入队列\n");

printf(”3.出队列\n");

printf(”4.求队列的长度\n”);

printf(”5.退出程序\n");

scanf("％d”,&ch);

switch(ch){

case1:DisplayLinkQueue(LQ);〃显示队列中全部元素

break;

case2:prinlf("请输入要人队的元素(一个整数):")；

scanf("%dn,&e);〃输入要入队列的字符

EnLinkQueue(LQ,e);〃入队列

DisplayLinkQueue(LQ);

break;

case3:temp=DeLinkQueue(LQ,e);〃出队列

if(temp==OK){

printf(”出队一个元素:％d\n”,e);

DisplayLinkQueue(LQ);

)

elseprintf("队列为空!\n")；

break;

case4:len=LinkQueueLength(LQ);

printf("队列的长度为:%d\nn,len);

break;

default:flag=O;

printf("程序运行结束，按任意键退出!\n)

getch();

StatusInitLinkQueue(LinkQueue&Q){〃队列初始化

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));〃生成一个头结点，并把首尾

指针指向头结点

Q.front->next=NULL;

returnOK;

}

StatusDestroyLinkQueue(LinkQueue&Q){〃销毁一个队列

QueuePtrp;

QElemTypee;

while(Q.front!=Q.rear)

DeLinkQueue(Q,e);

free(Q.front);

Q.front=Q.rear=NULL;

returnOK;

)

intLinkQueueLength(LinkQueue&Q){〃队列的长度

inti=0;

QueuePtrp=Q.front;

while(p!=Q.rear){

++i；

p=p->next;

)

returni;

)

StatusEnLinkQueue(LinkQueue&Q,QElemTypee){〃入队列

QueuePtrp;

p=(QueuePtr)malloc(sizeof(QNode));〃生成一个新结点

p->data=e;//赋值

p->next=NULL;

Q.rear->next=p;〃插入至队列尾

Q.rear=p;〃修改队尾指针

returnOK;

StatusDeLinkQueue(LinkQueue&Q,QElemType&e){〃出队歹“

QueuePtrp;

if(Q.front==Q.rear)returnERROR;〃推断队列是否已空，已空返回ERROR

p=Q.front->next;〃p指向队列中第一个元素

e=p->data;//取得该元素值

Q.front->next=p->next;〃修改队首指针

if(Q.rear==p)Q.rear=Q.front;〃若队列已空，把队尾指针指向头结点

returnOK;〃胜利出队列，返回0K

StatusDisplayLinkQueue(LinkQueueQ){〃显示队列中全部元素

QueuePtrp;

inti=0;

p=Q.front->next;

if(p==NULL)printf("队列为空队列为空

else{

while(p){〃否则显示队列中全部元素

printf(,'[%d:%d]*',++i,p->data);

p=p->next;

)

printf(n\n");

)

returnOK;

)

试验四二叉树算法的实现

一、试验目的

1.通过试验，把握二叉树的建立与存储

2.通过试验，把握二叉树的遍历方法

二、试验内容

1.练习二叉树的建立与存储

2.练习二叉树的遍历

三、试验步骤

1.建立自己的头文件BT.H,内容包括二叉链表的结构描述、二叉树的

建立、二叉树的先序、中序与后序遍历算法。

2.建立二叉树,并通过调用函数,，输出先序遍历、中序遍历与后序遍历

的结果。

四、实现提示

建立二叉树的代码如下：

BTCHINALR*createbt()

{BTCHINALR*q;

structnodel*s[30];

intj,i,x;

printf("建立二叉树,输入结点对应的编号和值,编号和值之间用逗号

隔开\n\n”);

printf("i,x=");

scanf("%d,%c",&i,&x);

while(i!=0&&x!='$')

{q=(BTCHINALR*)malloc(sizeof(BTCHINALR));/*建立一个

新结点q*/

q->data=x;q->lchild=NULL;q->rchild=NULL;

s[i]=q;/*q新结点地址存入s指针数组中*/

if(i!=1)/*i=l,对应的结点是根结点*/

{j=i/2;/*求双亲结点的编号j*/

if(i%2==0)s[j]->lchild=q;/*q结点编号为偶数则挂在双亲结

点j的左边*/

elses[j]->rchild=q;}/*q结点编号为奇数则挂在双亲结点j

的右边*/

printf("i,x=");

scanf("%d,%c",&i,&x);}

returns[l];/*返回根结点地址*/

)

五、思索与提高

1.如何用孩子兄弟表示法存储树？

2.熟识及难赫夫曼树。

六、完整参考程序

1.二叉树的建立、存储与遍历

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<dos.h>

#include<conio.h>

#defineTRUE1

#defineFALSE0

#defineOK1

#defineERROR0

#defineINFEASIBLE-1

#defineOVERFLOW-2

//Status是函数的类型，其值是函数结果状态代码

typedefintStatus;

//TElemType是二叉树数据元素类型,此程序定义为char型

typedefcharTElemType;

//----二叉树的二叉链表存储表示--一

typedefstructBiTNode{//定义二叉树结点结构

TElemTypedata;〃数据域

structBiTNode*lchild,*rchild;〃左右孩子指针域

}BiTNode,*BiTree;

StatusCreateBiTree(BiTree&T);〃生成一个二叉树(可用两种方法输入)

StatusCreateBiTreeInPreOrderResult(BiTree&T);〃生成一个二叉树(先序遍历

结果输入)

StatusCreateBiTreeInBracket(BiTree&T);〃生成一个二叉树(嵌套括号法输入)

StatusPrintElement(BiTreet);

StatusPreOrderTraverse(BiTreeT,Status(*Visit)(BiTreet));〃先序递归遍历二叉

树

StatusInOrderTraverse(BiTreeT,Status(*Visit)(BiTreet));〃中序递归遍历二

叉树

StatusPostOrderTraverse(BiTreeT,Status(*Visit)(BiTree。);〃后序递归遍历二

叉树

char*pstr;

StatusCreateBiTree(BiTree&T){〃生成一个二叉树(可用两种方法输入)

inti,len,choice=0;

charstr[200];

printf("请选择建立二叉树的方法:\n");

printf("l.按先序遍历的结果输入二叉树\n");

printf("2.按嵌套括号表示法输入二叉树\n");

do{

gets(str);

choice=atoi(str);

}while(choice<l||choice>2);

if(choice==l){

printf("请输入先序遍历二叉树的结果，程序据此建立二叉树。\n");

printf("对于叶子结点以空格表示。\n");

printf("例如:abc_de_g_f__(回车)，建立如下二叉树：\n");

printf("a\n");

printf("/\n");

printf("b\n");

printf("/\\\n");

printf("cd\n");

printf("/\\\n");

printf("ef\n");

printf("\\\n");

printf("g\n");

pstr=gets(str);

len=strlen(str);

for(i=len;i<180;++i)

str[i]='

strfi]=O;

CreateBiTreelnPreOrderResult(T);//初始化二叉树

else{

printf("请输入嵌套括号表示法表示的二叉树，程序据此建立二叉树。\nM);

printf("例如:(a(b(c,d(e(,g),f))))(回车),建立如下二叉树:\nn);

printf("a\n");

printf("/\n")；

printf("b\n");

printf("/\\\n");

printf("cd\n");

printf("/\\\n");

printf("ef\n");

printf("\\\n");

printf("g'n")；

pstr=gets(str);

CreateBiTreelnBracket(T);//初始化二叉树

returnOK;

)

StatusCreateBiTreeInPreOrderResult(BiTree&T){

〃依据存放在字符串*str中的光序遍历二叉树的结果，生成链接存储的二叉树。

〃(若某结点无左孩子或右孩子，则以空格表示其“孩子

if(!(*pstr)||*pstr=-*){

T=NULL;

pstr++;

}

else{

T=(BiTNode*)malloc(sizeof(BiTNode));〃生成一个新结点

if(!T)exit(OVERFLOW);

T->data=*(pstr++)；

CreateBiTreeInPreOrderResult(T->lchild);〃生成左子树

CreateBiTreeInPreOrderResult(T->rchild);//生成右子树

)

returnOK;

)

StatusCreateBiTreeInBracket(BiTree&T){

〃依据嵌套括号表示法的字符串*str生成链接存储的二叉树

//例如:*pstr="(a(b(c),d(e(,f),g)))”

BiTreestackfl00],p;

inttop=0,k;//top为栈指针,k指定是左还是右孩子；

T=NULL;

while(*pstr){

switch(*pstr){

caseV:stack[top++]=p;k=