数据结构与算法与实践数据结构实践实验指导书参考

《数据结构实践》实验指导书2013年8月目录TOC\o"1-1"\h\z\u实验一C语言编程复习 3实验二线形表基本操作的实现 5实验三栈和队列基本操作的实现及应用 14实验四二叉树算法的实现 26实验五图的算法的实现 40实验六查找算法的实现 57实验七排序算法的实现 67

实验一C语言编程复习一、实验目的1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。2.理解指针与应用的区别。3.掌握结构体的使用。4.掌握简单排序方法。二、实验内容1、使用指针和引用两种方式，完成两个学生的交换。2、写一函数，根据成绩，对包含有n个学生的数组进行排序。三、实验步骤1.定义一个Student的结构体类型，包含学号、姓名、成绩等成员。2.分别写Swap1(Student*s1,Student*s2)和Swap2(Student&s1,Student&s2)，完成两个学生的交换。3.写一排序函数SortStu(Student*s,intn)，使用冒泡或者简单选择排序算法根据成绩完成学生的排序。四、实现提示structStudent { charname[20]; //姓名 charnum[10]; //学号 floatscore; //成绩};voidSwap1(Student*,Student*);//交换两个结构体变量（指针）voidSwap2(Student&,Student&);//交换两个结构体变量（引用）voidSortStu(Student*,int);//按成绩（高到低）排序五、思考与提高思考为何voidSwap1(Student,Student)这个函数无法实现两个学生的交换？六、完整参考程序voidSwap1(Student*s1,Student*s2){ Studenttemp; temp=*s1; *s1=*s2; *s2=temp;}voidSwap2(Student&s1,Student&s2){ STUDENTtemp; temp=s1; s1=s2; s2=temp;}voidSortStu(StudentS[],intn){ Studenttemp; for(inti=0;i<n;i++) { intidx=i; for(intj=i+1;j<n;j++) { if(S[idx].score>S[j].score) idx=j; } if(idx!=i){ temp=S[idx]; S[idx]=S[i]; S[i]=temp;} }}实验二线形表基本操作的实现一、实验目的1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。2.掌握线性表的顺序存储结构的定义及C语言实现。3.掌握线性表的链式存储结构——单链表的定义及C语言实现。4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。5.掌握线性表在链式存储结构——单链表中的各种基本操作。二、实验内容1.顺序线性表的建立、插入及删除。2.链式线性表的建立、插入及删除。三、实验步骤1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。四、实现提示1.由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。在此，我们利用C语言的结构体类型定义顺序表：#defineMAXSIZE

1024typedef

int

elemtype;

/*

线性表中存放整型元素

*/typedefstruct{elemtypevec[MAXSIZE];

intlen;

/*

顺序表的长度

*/

}sequenlist;将此结构定义放在一个头文件sqlist.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出顺序表的建立及常量的定义。2.注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序（顺序表中元素的次序）的区别。3.单链表的结点结构除数据域外，还含有一个指针域。用C语言描述结点结构如下：

typedefintelemtype;typedefstructnode

{elemtypedata;

//数据域

structnode*next;//指针域

}linklist;

注意结点的建立方法及构造新结点时指针的变化。构造一个结点需用到C语言的标准函数malloc()，如给指针变量p分配一个结点的地址：p=(linklist*)malloc(sizeof(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指示当前线性表的长度}sqlist;voidinitial(sqlist&);//初始化线性表BOOLinsert(sqlist&,int,char);//在线性表中插入元素BOOLdel(sqlist&,int,char&);//在线性表中删除元素intlocate(sqlist,char);//在线性表中定位元素voidprint(sqlist);//显示线性表中所有元素voidmain(){sqlistS;//S为一线性表intloc,flag=1;charj,ch;BOOLtemp;printf("本程序用来实现顺序结构的线性表。\n");printf("可以实现查找、插入、删除等操作。\n");initial(S);//初始化线性表while(flag){printf("请选择:\n");printf("1.显示所有元素\n");printf("2.插入一个元素\n");printf("3.删除一个元素\n");printf("4.查找一个元素\n");printf("5.退出程序\n");scanf("%c",&j);switch(j) {case'1':print(S);break;//显示所有元素 case'2':{printf("请输入要插入的元素(一个字符)和插入位置:\n"); printf("格式：字符，位置；例如:a,2\n"); scanf("%c,%d",&ch,&loc);//输入要插入的元素和插入的位置 temp=insert(S,loc,ch);//插入 if(temp==False)printf("插入失败!\n");//插入失败else{printf("插入成功!\n");print(S);}//插入成功 break; } case'3':{printf("请输入要删除元素的位置:"); scanf("%d",&loc);//输入要删除的元素的位置 temp=del(S,loc,ch);//删除 if(temp==True)printf("删除了一个元素:%c\n",ch);//删除成功 elseprintf("该元素不存在!\n");//删除失败 print(S); break; } case'4':{printf("请输入要查找的元素:"); scanf("%c",&ch);//输入要查找的元素 loc=locate(S,ch);//定位 if(loc!=-1)printf("该元素所在位置:%d\n",loc+1);//显示该元素位置 elseprintf("%c不存在!\n",ch);//当前元素不存在 break; } default:flag=0;printf("程序结束，按任意键退出!\n"); }}getch();}voidinitial(sqlist&v){//初始化线性表inti;printf("请输入初始线性表长度：n=");//输入线性表初始化时的长度scanf("%d",&v.last);printf("请输入从1到%d的各元素(字符)，例如:abcdefg\n",v.last);getchar();for(i=0;i<v.last;i++)scanf("%c",&v.elem[i]);//输入线性表的各元素}BOOLinsert(sqlist&v,intloc,charch){//插入一个元素，成功返回True，失败返回Falseinti;if((loc<1)||(loc>v.last+1)){printf("插入位置不合理!\n");//位置不合理returnFalse;}elseif(v.last>=MAX)//线性表已满{printf("线性表已满!\n");returnFalse;}else{for(i=v.last-1;i>=loc-1;i--)v.elem[i+1]=v.elem[i];//其后元素依次后移v.elem[loc-1]=ch;//插入元素v.last++;//线性表长度加一returnTrue;}}BOOLdel(sqlist&v,intloc,char&ch){//删除一个元素，成功返回True，并用ch返回该元素值，失败返回Falseintj;if(loc<1||loc>v.last)//删除位置不合理returnFalse;else{ch=v.elem[loc-1];//ch取得该元素值for(j=loc-1;j<v.last-1;j++)v.elem[j]=v.elem[j+1];//其后元素依次前移v.last--;//线性表长度减一returnTrue;}}intlocate(sqlistv,charch){//在线性表中查找ch的位置，成功返回其位置，失败返回-1inti=0;while(i<v.last&&v.elem[i]!=ch)i++;//当前位置后移，直到找到为止if(v.elem[i]==ch)//找到当前元素returni;elsereturn(-1);}voidprint(sqlistv)//显示当前线性表所有元素{inti;for(i=0;i<v.last;i++)printf("%c",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=1;charj,ch;printf("本程序实现链式结构的线性表的操作。\n");printf("可以进行插入，删除，定位，查找等操作。\n");printf("请输入初始时链表长度:");//输入生成单链表时的元素个数scanf("%d",&num);CreatList(L,num);//生成单链表ListPrint(L);while(flag){printf("请选择:\n");printf("1.显示所有元素\n");//显示链表元素printf("2.插入一个元素\n");//插入链表元素printf("3.删除一个元素\n");//删除链表元素printf("4.按关键字查找元素\n");//按关键字查找printf("5.按序号查找元素\n");//按序号查找printf("6.退出程序\n");//退出scanf("%c",&j);switch(j) {case'1':ListPrint(L);break; case'2':{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; } case'3':printf("请输入要删除的元素所在位置:"); scanf("%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("%c",&ch);//输入要查找的元素 temp=ListFind_keyword(L,ch,loc);//按关键字查找 if(temp==False)printf("没有找到该元素!\n");//查找失败 elseprintf("该元素在链表的第%d个位置。\n",loc);//成功查找，显示该元素位置 } break; case'5':if(L->next==NULL)//链表为空 printf("链表为空!\n"); else{printf("请输入要查找的位置:"); scanf("%d",&loc);//输入要查找的元素的位置 temp=ListFind_order(L,ch,loc);//按序号查找 if(temp==False)printf("该位置不存在!\n");//查找失败 elseprintf("第%d个元素是：%c\n",loc,ch);//成功查找，显示该元素 } break; default:flag=0;printf("程序结束，按任意键退出!\n"); }}getch();}voidCreatList(LinkList&v,intn){//生成一个带头结点的有n个元素的单链表inti;LinkListp;v=(LinkList)malloc(LEN);//生成头结点v->next=NULL;printf("请输入%d个字符：例如：abcdefg\n",n);getchar();for(i=n;i>0;--i){p=(LinkList)malloc(LEN);//生成新结点scanf("%c",&p->data);p->next=v->next;v->next=p;}}BOOLListInsert(LinkList&v,inti,chare){//在单链表的第i各位置插入元素e，成功返回True，失败返回FalseLinkListp,s;intj=0;p=v;while(p&&j<i-1){p=p->next;++j;}//查找第i-1个元素的位置if(!p||j>i-1)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返回该元素值，失败返回FalseLinkListp,q;intj=0;p=v;while(p->next&&j<i-1)//查找第i-1个元素位置{p=p->next;++j;}if(!(p->next)||j>i-1)returnFalse;//查找失败q=p->next;p->next=q->next;//删除该元素e=q->data;//e取得该元素值free(q);//释放该元素空间returnTrue;}BOOLListFind_keyword(LinkListv,chare,int&i){//在单链表中查找关键字为e的元素，成功返回True,并用i返回该元素位置，//失败返回Falsei=1;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返回该元素值，//失败返回FalseLinkListp;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");}

实验三栈和队列基本操作的实现及应用一、实验目的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*)malloc(sizeof(SqStack)/*申请空间*/)/*入栈函数*/voidPush(SqStack*p,ElemTypex){if(p->top<MAXNUM-1)

{p->top=p->top+1;

/*栈顶+1*/

p->stack[p->top]=x;}

/*数据入栈*/}/*出栈函数*/ElemTypePop(SqStack*p){x=p->stack[p->top];/*将栈顶元素赋给x*/p->top=p->top-1;}/*栈顶-1*//*获取栈顶元素函数*/ElemTypeGetTop(SqStack*p){x=p->stack[p->top];}/*遍历顺序栈函数*/voidOutStack(SqStack*p){for(i=p->top;i>=0;i--)printf("第%d个数据元素是：%6d\n",i,p->stack[i]);}/*置空顺序栈函数*/voidsetEmpty(SqStack*p){p->top=-1;}2./*定义链队列*/typedefstructQnode{

ElemTypedata;

structQnode*next;}Qnodetype;typedefstruct{

Qnodetype*front;

Qnodetype*rear;}Lqueue;/*初始化并建立链队列函数*/voidcreat(Lqueue*q){

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

h->next=NULL;

q->front=h;

q->rear=h;for(i=1;i<=n;i++)*利用循环快速输入数据*/

{

scanf("%d",&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("%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-2typedefintStatus;typedefintSElemType;//栈的顺序存储表示#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefstruct{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;}//InitStackStatusDestroyStack(SqStack&S){//销毁栈S if(S.base)free(S.base); S.top=S.base=NULL; returnOK;}//InitStackStatusStackDisplay(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;}//StackDisplayStatusGetTop(SqStackS,SElemType&e){//若栈不空，则用e返回S的栈顶元素， //并返回OK；否则返回ERROR if(S.top==S.base)returnERROR; e=*(S.top-1); returnOK;}//GetTopStatusPush(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;}//PushStatusPop(SqStack&S,SElemType&e){ //若栈不为空，则删除S的栈顶元素， //用e返回其值，并返回OK；否则返回ERRORif(S.top==S.base)returnERROR;e=*--S.top;returnOK;}//PopStatusStackEmpty(SqStackS){ //若S为空栈，则返回TRUE，否则返回FALSE。 if(S.top==S.base)returnTRUE; elsereturnFALSE;}//StackEmptyvoidmain(){ SqStackSt; Statustemp; intflag=1,ch; inte; printf("本程序实现顺序结构的堆栈的操作。\n"); printf("可以进行入栈，出栈，取栈顶元素等操作。\n"); InitStack(St);//初始化堆栈St while(flag){ printf("请选择:\n"); printf("1.显示栈中所有元素\n"); printf("2.入栈\n"); printf("3.出栈\n"); printf("4.取栈顶元素\n"); printf("5.退出程序\n"); scanf("%d",&ch); switch(ch){ case1: StackDisplay(St); break; case2: printf("请输入要入栈的元素(一个整数):"); scanf("%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("堆栈已空!\n"); else{ printf("成功出栈一个元素:%d\n",e);//成功出栈 StackDisplay(St); } break; case4: temp=GetTop(St,e);//取得栈顶元素 if(temp==ERROR)printf("堆栈已空!\n"); elseprintf("栈顶元素是:%d\n",e);//显示栈顶元素 break; default: flag=0; 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,*QueuePtr;typedefstructlinkqueue{//定义队列结构 QueuePtrfront;//队头指针 QueuePtrrear;//队尾指针}LinkQueue;StatusInitLinkQueue(LinkQueue&);//初始化一个队列StatusDestroyLinkQueue(LinkQueue&);//销毁一个队列intLinkQueueLength(LinkQueue&Q);//队列的长度StatusEnLinkQueue(LinkQueue&,QElemType);//将一个元素入队列StatusDeLinkQueue(LinkQueue&,QElemType&);//将一个元素出队列StatusDisplayLinkQueue(LinkQueue);//显示队列中所有元素voidmain(){ LinkQueueLQ; QElemTypee; intflag=1,ch,len; Statustemp; printf("本程序实现链式结构队列的操作。\n"); printf("可以进行入队列、出队列等操作。\n"); InitLinkQueue(LQ);//初始化队列 while(flag){ printf("请选择:\n"); printf("1.显示队列所有元素\n"); printf("2.入队列\n"); printf("3.出队列\n"); printf("4.求队列的长度\n"); printf("5.退出程序\n"); scanf("%d",&ch); switch(ch){ case1:DisplayLinkQueue(LQ);//显示队列中所有元素 break; case2:printf("请输入要人队的元素(一个整数):"); scanf("%d",&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\n",len); break; default:flag=0; 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;//成功出队列，返回OK}StatusDisplayLinkQueue(LinkQueueQ){//显示队列中所有元素 QueuePtrp; inti=0; p=Q.front->next; if(p==NULL)printf("队列为空!\n");//队列为空 else{ while(p){//否则显示队列中所有元素 printf("[%d:%d]",++i,p->data); p=p->next; } printf("\n"); } returnOK;}

实验四二叉树算法的实现一、实验目的1.通过实验，掌握二叉树的建立与存储2.通过实验，掌握二叉树的遍历方法二、实验内容1.练习二叉树的建立与存储2.练习二叉树的遍历三、实验步骤1.建立自己的头文件BT.H，内容包括二叉链表的结构描述、二叉树的建立、二叉树的先序、中序与后序遍历算法。2.建立二叉树,并通过调用函数,，输出先序遍历、中序遍历与后序遍历的结果。四、实现提示建立二叉树的代码如下：BTCHINALR

*createbt(){

BTCHINALR*q;

structnode1*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=1，对应的结点是根结点*/

{j=i/2;

/*求双亲结点的编号j*/

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

else

s[j]->rchild=q;}

/*q结点编号为奇数则挂在双亲结点j的右边*/

printf("i,x=");

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

return

s[1];

/*返回根结点地址*/}五、思考与提高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)(BiTreet));//后序递归遍历二叉树char*pstr;StatusCreateBiTree(BiTree&T){//生成一个二叉树(可用两种方法输入)inti,len,choice=0;charstr[200];printf("请选择建立二叉树的方法:\n");printf("1.按先序遍历的结果输入二叉树\n");printf("2.按嵌套括号表示法输入二叉树\n");do{gets(str);choice=atoi(str);}while(choice<1||choice>2);if(choice==1){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]='';str[i]=0;CreateBiTreeInPreOrderResult(T);//初始化二叉树}else{printf("请输入嵌套括号表示法表示的二叉树,程序据此建立二叉树。\n");printf("例如:(a(b(c,d(e(,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);CreateBiTreeInBracket(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)))"BiTreestack[100],p;inttop=0,k;//top为栈指针,k指定是左还是右孩子;T=NULL;while(*pstr){switch(*pstr){case'(':stack[top++]=p;k=1;break;//左结点,其父结点为*pcase')':top--;break;case',':k=2;break;//右结点,其父结点为*pcase'':break;default: p=(BiTree)malloc(sizeof(BiTNode)); p->data=*pstr; p->lchild=p->rchild=NULL; if(!T)T=p;//根结点 else{ switch(k){ case1:stack[top-1]->lchild=p;break; case2:stack[top-1]->rchild=p;break; } }}pstr++;}returnOK;}StatusDestroyBiTree(BiTree&T){if(T){if(T->lchild)DestroyBiTree(T->lchild);//销毁左子树if(T->rchild)DestroyBiTree(T->rchild);//销毁右子树free(T);//销毁根结点T=NULL;returnOK;}elsereturnOK;}StatusPrintElement(BiTreet){printf("%c",t->data);//显示结点数据域returnOK;}StatusPreOrderTraverse(BiTreeT,Status(*Visit)(BiTreet)){//先序if(T){if((*Visit)(T))//访问结点 if(PreOrderTraverse(T->lchild,Visit))//遍历左子树 if(PreOrderTraverse(T->rchild,Visit))//遍历右子树 returnOK;returnERROR;}elsereturnOK;}StatusInOrderTraverse(BiTreeT,Status(*Visit)(BiTreet)){//中序if(T){if(InOrderTraverse(T->lchild,Visit))//遍历左子树 if((*Visit)(T))//访问结点 if(InOrderTraverse(T->rchild,Visit))//遍历右子树 returnOK;returnERROR;}elsereturnOK;}StatusPostOrderTraverse(BiTreeT,Status(*Visit)(BiTreee)){//后序if(T){if(PostOrderTraverse(T->lchild,PrintElement))//遍历左子树 if(PostOrderTraverse(T->rchild,PrintElement))//遍历右子树 if((*Visit)(T))//访问结点 returnOK;returnERROR;}elsereturnOK;}StatusDisplayBiTreeInConcave(BiTreeT){//以凹入表示法输出一棵二叉树BiTreestack[100],p;intlevel[100][2],top,n,i,width=4;charchildtype[3]={'L','R','D'};constintMaxWidth=30;if(T){top=0;stack[top]=T;//根结点入栈level[top][0]=width;level[top][1]=2;//2表示是根while(top>=0){p=stack[top];//退栈并凹入显示该结点值n=level[top][0];for(i=1;i<=n;i++)printf("");//其中n为显示场宽,字符以右对齐显示printf("%c(%c)",p->data,childtype[level[top][1]]);for(i=n+1;i<=MaxWidth;i+=2)printf("━");printf("\n");top--;if(p->rchild){//将右子树根结点入栈 top++; stack[top]=p->rchild; level[top][0]=n+width;//显示场宽增width level[top][1]=1;//1表示是右子树}if(p->lchild){//将左子树根结点入栈 top++; stack[top]=p->lchild; level[top][0]=n+width;//显示场宽增width level[top][1]=0;//0表示是左子树}}}elseprintf("该二叉树是一棵空二叉树!\n");returnOK;}StatusDisplayBiTreeInBracket(BiTreeT){//以嵌套括号表示法输出一棵二叉树if(T){printf("%c",T->data);if(T->lchild||T->rchild){printf("(");if(T->lchild)DisplayBiTreeInBracket(T->lchild);//递归处理左子树if(T->rchild)printf(",");if(T->rchild)DisplayBiTreeInBracket(T->rchild);//递归处理右子树printf(")");}}elseprintf("该二叉树是一棵空二叉树!");returnOK;}voidmain(){BiTreeT;charch,j;charstr[200];intchoice,flag=1,len,i;Statustemp;printf("本程序实现二叉树的操作:\n");printf("可以进行建立二叉树,递归先序、中序、后序遍历等操作。\n");CreateBiTree(T);while(flag){printf("请选择:\n");printf("1.递归先序遍历\n");printf("2.递归中序遍历\n");printf("3.递归后序遍历\n");printf("4.凹入表示法输出二叉树\n");printf("5.嵌套括号表示法输出二叉树\n");printf("6.重新构建二叉树\n");printf("7.退出程序\n");scanf("%d",&choice);switch(choice){case1: if(T){ printf("先序遍历二叉树:"); PreOrderTraverse(T,PrintElement);//先序递归遍历二叉树 printf("\n"); } else printf("二叉树为空!\n"); break;case2: if(T){ printf("中序遍历二叉树:"); InOrderTraverse(T,PrintElement);//中序递归遍历二叉树 printf("\n"); } else printf("二叉树为空!\n"); break;case3: if(T){ printf("后序遍历二叉树:"); PostOrderTraverse(T,PrintElement);//后序递归遍历二叉树 printf("\n"); } else printf("二叉树为空!\n"); break;case4: DisplayBiTreeInConcave(T); break;case5:printf("("); DisplayBiTreeInBracket(T);printf(")\n"); break;case6: DestroyBiTree(T); CreateBiTree(T); break;default: flag=0; printf("程序运行结束，按任意键退出!\n"); getch();}}DestroyBiTree(T);}

实验五图的算法的实现一、实验目的1.掌握图的基本存储方法；2.掌握有关图的操作算法并用高级语言实现；3.熟练掌握图的两种搜索路径的遍历方法。二、实验内容假设以一个带权有向图表示某一区域的公交线路网，图中顶点代表一些区域中的重要场所，弧代表已有的公交线路，弧上的权表示该线路上的票价（或搭乘所需时间），试设计一个交通指南系统，指导前来咨询者以最低的票价或最少的时间从区域中的某一场所到达另一场所。三、实验步骤1.定义结点结构，定义图结构。2.存储图信息；3.定义求任意两点最短路径函数；4.写出主函数。四、实现提示typedef

struct

node{

int

no;

float

wgt;

struct

node

*next;}edgenode;typedef

struct{

char

vtx;

edgenode

*link;

}vexnode;

typedef

vexnode

Graph[n];

void

Floyd(GraphG,floatA[n][n],intp[n][n]){

int

i,

j,

k;

for

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

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

{

A[i][j]=G[i][j];

P[i][j]=-1;

}

for

(k=0;k<n;k++)

for(i=0;i<n;

i++)

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

if(A[i][k]+A[k][j]<A[i][j])

{

P[i][j]=k;

A[i][j]=A[i][k]+A[k][j];

}

}五、思考与提高1.判断两点是否可达。2.如何对程序进行修改，找一条人最少的公交线路？3.练习图的拓扑排序六、完整参考程序1.图的建立与遍历#include<conio.h>#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMAX_VERTEX_NUM20//图的最大顶点数#defineMAXQSIZE30//队列的最大容量enumBOOL{False,True};typedefstructArcNode{intadjvex;//该弧所指向的顶点的位置structArcNode*nextarc;//指向下一条弧的指针}ArcNode;//弧结点typedefstruct{ArcNode*AdjList[MAX_VERTEX_NUM];//指向第一条依附该顶点的弧的指针intvexnum,arcnum;//图的当前顶点和弧数intGraphKind;//图的种类，0无向图，1有向图}Graph;typedefstruct//队列结构{intelem[MAXQSIZE];//数据域intfront;//队头指针intrear;//队尾指针}SqQueue;BOOLvisited[MAX_VERTEX_NUM];//全局变量——访问标志数组voidCreateGraph(Graph&);//生成图的邻接表voidDFSTraverse(Graph);//深度优先搜索遍历图voidDFS(Graph,int);voidBFSTraverse(Graph);//广度优先搜索遍历图voidInitial(SqQueue&);//初始化一个队列BOOLQueueEmpty(SqQueue);//判断队列是否空BOOLEnQueue(SqQueue&,int);//将一个元素入队列BOOLDeQueue(SqQueue&,int&);//将一个元素出队列intFirstAdjVex(Graph,int);//求图中某一顶点的第一个邻接顶