还剩75页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
《数据结构与算法》试验指导书2022年8月目录试验一C语言编程复习1试验二线形表基本操作的实现5试验三栈和队列基本操作的实现及应用14试验四二叉树算法的实现24试验五图的算法的实现36试验六查找算法的实现52试验七排序算法的实现62试验一C语言编程复习
一、试验目的.熟识C语言的上机环境,进一步把握C语言的结构特点.理解指针与应用的区分.把握结构体的使用.把握简洁排序方法
二、试验内容1输入一行字符,计算该行字符中包含多少个单词,单词之间用空格分隔开elsereturn-l;}voidprintsqlistv〃显示当前线性表全部元素{inti;fori=0;iv.last;i++printfM%cnv.elem[i];printfH\nn;}
2.链式线性表的建立、插入及删除#includeconio.h#includestdio.h#includestdlib.h#defineLENsizeofLNode//定义LEN为一个节点的长度enumBOOL{FalseTrue};//定义BOOL型typedefstructnode{chardata;〃数据域structnode*next;〃指向下一个节点的指针}LNode*LinkList;voidCreatListLinkListint;〃生成一个单链表BOOLListInsertLinkListintchar;//在单链表中插入一个元素BOOLListDeleteLinkListintchar;//在单链表中删除一个元素BOOLListFind_keywordLinkListcharint;//按关键字查找一个元素BOOLListFind_orderLinkListcharint;〃按序号查找一个元素voidListPrintLinkList;〃显示单链表全部元素voidmain{LinkListL;BOOLtemp;intnumlocflag=l;charjch;printf本程序实现链式结构的线性表的操作\n;printf可以进行插入,删除,定位,查找等操作\n;printf”请输入初始时链表长度:;//输入生成单链表时的元素个数scanfH%dnnum;CreatListLnum;〃生成单链表ListPrintL;whilcflag{printf请选择:\n;printfL显示全部元素\n;〃显示链表元素printf
2.插入一个元素\n;〃插入链表元素printf
3.删除一个元素\n;//删除链表元素printf
4.按关键字查找元素\n〃按关键字查找printf
5.按序号查找元素\n;//按序号查找printf
6.退出程序\nn;〃退出scanfn%c;j;switchj{case*r ListPrintL;break;case2:{printf请输入元素一个字符和要插入的位置:\n;printf格式:字符,位置;例如:a3\n;scanfn%c%d\chloc;〃输入要插入的元素和要插入的位置temp=List!nsertLlocch;〃插入iftemp==Falseprintf插入失败!\n;〃插入失败elseprintf插入胜利!\n”;//胜利插入ListPrintL;break;case3:printf请输入要删除的元素所在位置:;scanf%dloc;〃输入要删除的节点的位置temp=ListDeleteLlocch;〃删除iftemp==Falseprintf删除失败!\n;〃删除失败elseprintf胜利删除了一个元素:%c\n”ch;//删除胜利,显示该元素ListPrintL;break;case4:ifL-next==NULL〃链表为空printf链表为空!\n;else{printf请输入要查找的元素一个字符scanfn%cnch;//输入要查找的元素temp=ListFind_keywordLchloc;//按关键字查找iftemp==Falseprintf没有找到该元素!\n;〃查找失败elseprintf该元素在链表的第%1个位置\ntloc;//胜利查找,显示该元素位置break;case5:ifL-next==NULL〃链表为空printf链表为空!\nelse{printf请输入要查找的位置scanfn%d;loc;〃输入要查找的元素的位置temp=ListFind_orderLchloc;//按序号查找iftemp==Falseprintf该位置不存在!\n;//查找失败elseprintf第%d个元素是%c\nJocch;〃胜利查找,显示该元素break;default:flag=O;printf程序结束按任意键退出!\n;getch;}voidCreatListLinkListv9intn{〃生成一个带头结点的有n个元素的单链表inti;LinkListp;v=LinkListmallocLEN;〃生成头结点v-next=NULL;printf请输入%d个字符例如abcdefg\nf\n;getchar;fori=n;i0;—i{p=LinkListmallocLEN;//生成新结点scanfn%c\p-data;p-next=v-next;v-next=p;BOOLListInsertLinkListvintichare{〃在单链表的第i各位置插入元素e胜利返回True失败返回FalseLinkListps;intj=0;P=v;whilepji-l{p=p-next;++j;}〃查找第i-1个元素的位置if!p||ji-lreturnFalse;〃没有找到s=LinkListmallocLEN;〃生成一个新结点s-data=e;s-next=p-next;//将新结点插入到单链表中p-next=s;returnTrue;BOOLListDclctcLinkListvinticharc{〃在单链表中删除第i个元素胜利删除返回True并用e返回该元素值失败返回FalseLinkListpq;intj=0;P=v;whilep-nextji-1〃查找第i-1个元素位置{p=p-next;++j;}if!p-next||ji-1returnFalse;〃查找失败q=p-next;p-next=q-next;Ol除该元素e=q-data;//e取得该元素值freeq;〃释放该元素空间returnTrue;}BOOLListFind_keywordLinkListv9chareinti{//在单链表中查找关键字为e的元素,胜利返回True并用i返回该元素位置〃失败返回Falsei=l;LinkListp;p=v-next;whilep-data!=ep-next!=NULL//p指针指向下一个,直到{p=p-next;i++;}〃找到或到链表尾为止ifp-data!=e〃该元素在链表中不存在returnFalse;elsereturnTrue;BOOLListFind_orderLinkListvchareinti{〃在单链表中查找第i个元素,胜利返回True并用e返回该元素值,〃失败返回FalseLinkListp;intj=0;P=v;whilep-nextji〃移动指针,直到找到第i个元素{p=p-next;++j;}ifj!=ireturnFalse;//查找失败else{e=p-data;〃查找胜利,用e取得该元素值returnTrue;voidListPrintLinkListv{〃显示链表全部元素LinkListq;q=v-next;printf链表全部元素whileq!=NULL{printfn%cHq-data;q=q-next;}printfn\nn;试验三栈和队列基本操作的实现及应用
一、试验目的.把握栈的挨次表示和实现.把握队列的链式表示和实现
二、试验内容.编写一个程序实现挨次栈的各种基本运算.实现队列的链式表示和实现
三、试验步骤.初始化挨次栈.插入元素.删除栈顶元素.取栈顶元素.遍历挨次栈6置空挨次栈.初始化并建立链队列.入链队列.出链队列.遍历链队列
四、实现提示./*定义挨次栈的存储结构*/typedefstruct{ElemTypestack[MAXNUM];inttop;JSqStack;/*初始化挨次栈函数*/voidInitStackSqStack*p{q=SqStack*manocsizeofSqStack/*申请空间*//*入栈函数*/voidPushSqStack*pElemTypex{ifp-topMAXNUM-1{p-top=p-top+l;/*栈顶+1*/p-stack[p-top]=x;}/*数据入栈*//*出栈函数*/ElemTypePopSqStack*p{x=p-stack[p-top];/*将栈顶元素赋给x*/p-top=p-top-l;}/*栈顶-1*//*猎取栈顶元素函数*/ElemTypeGetTopSqStack*p{x=p-stack[p-top];}/*遍历挨次栈函数*/voidOutStackSqStack*p{fori=p-top;i=0;iprintf第%d个数据元素是:%6d\nip-stack[i];}/*置空挨次栈函数*/voidsetEmptySqStack*p{p-top=-l;}./*定义链队列*/typedefstructQnode{ElemTypedata;structQnode*next;JQnodetype;typedefstruct{Qnodetype*front;Qnodetype*rear;JLqueue;/*初始化并建立链队列函数*/voidcreatLqueue*q{h=Qnodetype*maUocsizeofQnodetype;/*初4台化申请空间*/h-next=NULL;q-front=h;q-rear=h;fori=l;i=n;i++*采用循环快速输入数据*/{scanf%dx;Lappendqx;}/*采用入链队列函数快速输入数据*//*入链队列函数*/voidLappendLqueue*qintx{s-data=x;s-next=NULL;q-rear-next=s;q-rear=s;}/*出链队列函数*/ElemTypeLdeleteLqueue*q{p=q-front-next;q-front-next=p-next;ifp-next==NULLq-rear=q-front;x=p-data;freep;}/*释放空间*//*遍历链队列函数*/voiddisplayLqueue*q{whilep!=NULL/*采用条件推断是否到队尾*/{printf%d—p-data;p=p-next;
五、思索与提高.读栈顶元素的算法与退栈顶元素的算法有何区分?.假如一个程序中要用到两个栈,为了不发生上溢错误,就必需给每个栈预先安排一个足够大的存储空间若每个栈都预安排过大的存储空间,势必会造成系统空间紧急如何解决这个问题?1链栈只有一个top指针,对于链队列,为什么要设计一个头指针和一个尾指针?2一个程序中假如要用到两个栈时,可通过两个栈共享一维数组来实现即双向栈共享邻接空间假如一个程序中要用到两个队列,能否实现?如何实现?
六、完整参考程序
1.栈的挨次表示和实现#includestdio.h#includestdlib.h#includeconio.hdefineTRUE1defineFALSE0defineOK1defineERROR0defineINFEASIBLE-1#defineOVERFLOW-2typedefintStatus;typedefintSElemType;II—-栈的挨次存储表示-一#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;StatusInitStackSqStackS;StatusDestroyStackSqStackS;StatusStackDisplaySqStackS;StatusGetTopSqStackSSElemTypee;StatusPushSqStackSSElemTypee;StatusPopSqStackSSElemTypee;StatusStackEmptySqStackS;StatuslnitStackSqStackS{〃构造一个空栈SS上ase=SElemType*mallocSTACK_INIT_SIZE*sizeofSElemType;ifSbaseexitOVERFLOW;〃存储安排失效S.top二S.base;S.stacksize:STACKINITSIZE;returnOK;}//InitStackStatusDestroyStackSqStackS{〃销毁栈SifS上asefreeS.base;S.top=S.base=NULL;returnOK;}//InitStackStatusStackDisplaySqStackS{〃显示栈SSElemType*p=S.base;inti=0;ifS.base==S.top{printf堆栈已空!\n;returnOK;whilepS.topprintfT%d:%d—++i*p++;printfn\nn;returnOK;}//StackDisplayStatusGetTopSqStackSSElemTypee{〃若栈不空,则用e返回S的栈顶元素,〃并返回OK;否则返回ERRORifS.top==S上asereturnERROR;e=*S.top-l;returnOK;}//GetTopStatusPushSqStackSSElemTypee{〃插入元素e为新的栈顶元素ifS.top-S.base=S.stacksize{/^^追加存储空间S.base=SElemType*reallocS.baseS.stacksize+STACKINCREMENT*sizeofSElemType;if!S.baseexitOVERFLOW;〃存储安排失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top++二e;returnOK;}//PushStatusPopSqStackSSElemTypee{〃若栈不为空,则删除S的栈顶元素,〃用e返回其值,并返回OK;否则返回ERRORifS.top==S.basereturnERROR;e=*—S.top;returnOK;}//PopStatusStackEmptySqStackS{〃若S为空栈,则返回TRUE否则返回FALSEifS.top==S.basereturnTRUE;elsereturnFALSE;}//StackEmptyvoidmain{SqStackSt;Statustemp;intflag=lch;inte;printf本程序实现挨次结构的堆栈的操作\n”;printf可以进行入栈,出栈,取栈顶元素等操作\nn;InitStackSt;〃初始化堆栈Stwhileflag{2采用add函数求两个复数2+3i和4+5i的和要求用结构体来定义复数3一个班上有30名同学,每个同学的数据作为一个纪录,每个纪录包括学号、姓名、三门课程的成果和三门课程平均成果从键盘输入同学的学号、姓名及三门课的成果要求打印三门课程平均成果】高分的同学纪录
三、试验步骤1用数组或字符串猎取字符,遇到空格即表示新单词的开头2要求用结构体来定义复数,包括实部和虚部3定义一个Student的结构体类型,包含学号、姓名、成果等成员
四、实现提示structstudent{charnum
[6];stringname;floatscore
[3];floataver;;
五、思索与提高思索为何voidSwap1StudentStudent这个函数无法实现两个同学的交换?
六、完整参考程序
1、#includeiostream#includestringusingnamespacestd;voidmaincout«〃输入n个单词,单词之间用空格隔开〃《endl;stringstr;getlinecinstr;intnum=0;intlen=str.size;iflen!=0num=l;forinti=0;ilen;i++printf”请选择:\nprintfCl.显示栈中全部元素\nprintf
2.入栈printf”
3.出栈printf”
4.取栈顶元素printf”
5.退出程序scanfn%dnch;switchch{StackDisplaySt;break;printf”请输入要入栈的元素一个整数scanfn%dHe;〃输入要入栈的元素temp=PushSte;〃入栈iftemp!=OKprintf堆栈已满!入栈失败!\n;else{printfC胜利入栈!\n〃胜利入栈StackDisplaySt;break;temp=PopSte;〃出栈iftemp==ERRORprintf堆栈已空!\nH;else{printf胜利出栈一个元素:%d\n”e;〃胜利出栈StackDisplaySt;break;temp=GetTopSte;〃取得栈顶元素iftemp==ERRORprintf堆栈已空!\nn;elseprintf栈顶元素是:%1\11”©;〃显示栈顶元素break;default:flag=O;printf程序结束,按任意键退出!\ngetch;DestroyStackSt;
2.队列的链式表示和实现#includeconio.h#includestdio.h#includestdlib.h#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2//Status是函数的类型,其值是函数结果状态代码typedefintStatus;//ElemType是挨次表数据元素类型此程序定义为int型typedefintQElemType;〃——一单链队列一一队列的链式存储结构一一一typedefstructQNode{QElemTypedata;structQNode*next;}QNode*QueuePtr;typedefstructlinkqueue{QueuePtrfront;QueuePtrrear;〃定义结点结构〃数据域//指针域〃定义队列结构〃队头指针〃队尾指针}LinkQueue;StatusInitLinkQueueLinkQueue;StatusDestroyLinkQueueLinkQueue;intLinkQueueLengthLinkQueueQ;〃初始化一个队列〃销毁一个队列〃队列的长度StatusEnLinkQueueLinkQueueQElemType;〃将一个元素入队列StatusDeLinkQueueLinkQueueQElemType;〃将一个元素出队列StatusDisplayLinkQueueLinkQueue;〃显示队列中全部元素voidmain{LinkQueueLQ;QElemTypee;intflag=lchlcn;Statustemp;printf本程序实现链式结构队列的操作\n”;printf可以进行入队列、出队列等操作\n”;InitLinkQueueLQ;whileflag{〃初始化队列printf请选择:\n;printfI.显示队列全部元素\n”;printf”
2.入队列\n;printf”
3.出队列\nprintf”
4.求队列的长度\n”;printf”
5.退出程序\n;scanfn%dnch;switchch{case1:DisplayLinkQueueLQ;〃显示队列中全部元素break;case2:printf”请输入要人队的元素一个整数:;scanfH%dne;〃输入要入队列的字符EnLinkQueueLQe;〃入队列DisplayLinkQueueLQ;break;case3:temp=DeLinkQueueLQe;〃出队列iftemp==OK{printf”出队一个元素:%d\n”e;DisplayLinkQueueLQ;elseprintfM队列为空!\nn;break;case4:len=LinkQueueLengthLQ;printf队列的长度为:%d\n\len;break;default:flag=O;printf程序运行结束,按任意键退出!\ngetch;StatusInitLinkQueueLinkQueueQ{〃队女]初也台化Q.front=Q.rear=QueuePtrmallocsizeofQNode;〃生成一个头结点,并把首尾指针指向头结点Q.front-ncxt=NULL;returnOK;StatusDestroyLinkQueueLinkQueueQ{〃销毁^队列QueuePtrp;QElemTypee;whileQ.front!=Q.rearDeLinkQueueQe;freeQ.front;Q.front=Q.rear=NULL;returnOK;intLinkQueueLengthLinkQueueQ{〃队列的长度inti=0;QueuePtrp=Q.front;whilep!=Q.rear{++i;p=p-next;returni;StatusEnLinkQueueLinkQueueQQElemTypee{〃入队歹4QueuePtrp;p二QueuePtrmallocsizeofQNode;〃生成一个新结点p-data=e;〃赋值p-next=NULL;Q.rear-next=p;〃插入至队列尾Q.rear=p;//修改队尾指针returnOK;StatusDeLinkQueueLinkQueueQQElemTypee{〃出队歹UQueuePtrp;ifQ.front==Q.rearreturnERROR;〃推断队列是否已空,已空返回ERRORp=Q.front-next;//p指向队列中第一个元素e=p-data;〃取得该元素值Q.front-next=p-next;〃修改队首指针ifQ.rear-pQ.rear=Q.front;〃若队歹“已空,把队尾指针指向头结点returnOK;〃胜利出队列,返回0KStatusDisplayLinkQueueLinkQueueQ{〃显示队列中全部元素QueuePtrp;inti=0;p=Q.front-next;ifp==NULLprintf队列为空!\n;〃队列为空else{printfn[%d:%d]n++ip-data;p=p-next;printfH\nn;returnOK;试验四二叉树算法的实现
一、试验目的.通过试验,把握二叉树的建立与存储.通过试验,把握二叉树的遍历方法
二、试验内容.练习二叉树的建立与存储.练习二叉树的遍历
三、试验步骤.建立自己的头文件BT.H内容包括二叉链表的结构描述、二叉树的建立、二叉树的先序、中序与后序遍历算法.建立二叉树并通过调用函数,输出先序遍历、中序遍历与后序遍历的结果
四、实现提示建立二叉树的代码如下BTCHINALR*createbt{BTCHINALR*q;structnodel*s
[30];intjix;printf建立二叉树,输入结点对应的编号和值编号和值之间用逗号printfix=;scanf%d%cix;whilei!=0x!=${q=BTCHINALR*mallocsizeofBTCHINALR;/*建立一个新结点q*/q-data=x;q-lchild=NULL;q-rchild=NULL;s[i]=q;/*q新结点地址存入s指针数组中*/ifi!=1/*i=l对应的结点是根结点*/{j=i/2;/*求双亲结点的编号j*/ifi%2==0s[j]-lchild=q;/*q结点编号为偶数则挂在双亲结点j的左边*/elses[j]-rchild=q;}/*q结点编号为奇数则挂在双亲结点j的右边*/printfix=;scanf%d%cix;}returns[l];/*返回根结点地址*/
五、思索与提高.如何用孩子兄弟表示法存储树?.熟识及难赫夫曼树
六、完整参考程序
1.二叉树的建立、存储与遍历#includestdio.h#includestdlib.h#includestring.h#includedos.h#includeconio.hdefineTRUE1defineFALSE0defineOK1defineERROR0defineINFEASIBLE-1defineOVERFLOW-2//Status是函数的类型,其值是函数结果状态代码typedefintStatus;//TElemType是二叉树数据元素类型此程序定义为char型typedefcharTElemType;//--二叉树的二叉链表存储表示-----typedefstructBiTNode{〃定义二叉才对结点结构TElemTypedata;//数据域structBiTNode*lchild*rchild;〃左右孩子指针域}BiTNode*BiTree;StatusCreateBiTreeBiTreeT;〃生成一个二叉树可用两种方法输入StatusCreateBiTreeInPreOrderResultBiTreeT;〃生成一个二叉树先序遍历结果输入StatusCreateBiTreeInBracketBiTreeT;〃生成一^个二叉树嵌套括号法输入StatusPrintElementBiTreet;StatusPreOrderTraverseBiTreeTStatus*VisitBiTreet;〃先序递归遍历二叉树StatusInOrderTraverseBiTreeTStatus*VisitBiTreet;〃中序递归遍历二叉树StatusPostOrderTraverseBiTreeTStatus*VisitBiTreet;〃后序递归遍历二叉树char*pstr;StatusCreateBiTreeBiTreeT{〃生成一^个二叉树可用两种方法输入intilenchoice=0;charstr
[200];printf(请选择建立二叉树的方法:\n”);printf(l.按先序遍历的结果输入二叉树\n);printf(
2.按嵌套括号表示法输入二叉树\n);do{getsstr;choice=atoistr;}whilechoicel||choice2;ifchoice==l{printf请输入先序遍历二叉树的结果,程序据此建立二叉树\n;printf对于叶子结点以空格表示\n;printf例如:abc_de_g_f回车,建立如下二叉树\n;printfa\n;printf/\n;printfb\n;printf/\\\n;printfcd\n;printf/\\\n;printfef\n;printf\\\n;printfg\n;pstr=getsstr;len=strlenstr;fori=len;i180;++istr[i]=O;CreateBiTreelnPreOrderResultT;〃初始化二叉树else{printf,请输入嵌套括号表示法表示的二叉树,程序据此建立二叉树\n;printf例如:abcdegf回车,建立如下二叉树\nH;returnOK;StatusCreateBiTreeInPreOrderResultBiTreeT{〃依据存放在字符串*str中的先序遍历二叉树的结果,生成链接存储的二叉树〃若某结点无左孩子或右孩子,则以空格表示其“孩子if!*pstr||*pstr—{T=NULL;pstr++;else{T=BiTNode*mallocsizeofBiTNode;//生成一个新结点if!TexitOVERFLOW;T-data=*pstr++;CreateBiTreeInPreOrderResultT-lchild;//生成左子树CreateBiTreeInPreOrderResultT-rchild;〃生成右子树returnOK;StatusCreateBiTreeInBracketBiTreeT{//依据嵌套括号表示法的字符串*str生成链接存储的二叉树〃例如:*pstr=abcdefgBiTreestack
[100]p;inttop=0k;//top为栈指针k指定是左还是右孩子;T=NULL;while*pstr{switch*pstr{caseV-stack[top++]=p;k=1;break;//左结点,其父结点为*pcasey top;break;case:k=2;break;〃右结点其父结点为*pcasebreak;default:p=BiTreemallocsizeofBiTNode;p_〉data=*pstr;p-lchild=p-rchild=NULL;if!TT=p;〃根结点ifstr[i]==,{num++;cout〈〈〃单词个数为〃nuniendl;也可使用数组实现ttincludeiostreamusingnamespacestd;voidmain{cout〃输入n个单词,单词之间用空格隔开〃《endl;charstr
[100];cinstr;intnum=0;forinti=0;str[i]!=\0;i++ifstr[i]=,{num++;}cout〈〃单词个数为〃〈〈num〈〈endl;
2、#includeiostreamusingnamespacestd;structcomplexfloatreal;floatimag;;complexaddcomplexxlcomplexx2complexsum;sum.real二xl.real+x
2.real;sum.imag=xl.imag+x
2.imag;returnsum;;switchk{case1:stack[top-l]-lchild=p;break;case2:stack[top-l]-rchild=p;break;pstr++;returnOK;StatusDestroyBiTreeBiTreeT{ifT{ifT-lchildDestroyBiTreeT-lchild;//销毁左子树ifT-rchildDestroyBiTreeT-rchild;〃销毁右子树freeT;〃销毁根结点T=NULL;returnOK;elsereturnOK;StatusPrintElementBiTreet{printf%ct-data;〃显示结点数据域returnOK;StatusPreOrderTraverseBiTreeTStatus*VisitBiTreet{〃先序if*VisitT〃1方问结点ifPreOrderTraverseT-lchildVisit//遍历左子树ifPreOrderTraverseT-rchildVisit//遍历右子树returnOK;returnERROR;elsereturnOK;StatusInOrderTraverseBiTreeTStatus*VisitBiTreet{//中序ifT{ifInOrderTraverseT-lchildVisit〃遍历左子树if*VisitT〃访■问结点ifInOrderTraverseT-rchildVisit〃遍历右子树returnOK;returnERROR;elsereturnOK;StatusPostOrderTraverseBiTreeTStatus*VisitBiTreee{〃后序ifT{ifPostOrderTraverseT-lchildPrintElement〃遍历左子树ifPostOrderTraverseT-rchildPrintElement〃遍历右子树if*VisitT〃1方问结点returnOK;returnERROR;elsereturnOK;StatusDisplayBiTreeInConcaveBiTreeT{〃以凹入表示法输出一棵二叉树BiTreestack
[100]p;intlevel[l00]
[2]topniwidth=4;charchildtype
[3]={LRD;constintMaxWidth=30;ifT{top=0;stack[top]=T;〃根结点入栈level[top]
[0]=width;level[top][l]=2;//2表示是根whiletop=0{p=stack[top];〃退栈并凹入显示该结点值n=level[top]
[0];fori=l;i=n;i++printf”;〃其中n为显示场宽,字符以右对齐显示printf%c%cp-datachildtype[level[top][l]];fori=n+l;i=MaxWidth;i+=2printf一;printf\n;top-;ifp-rchild{〃将右子树根结点入栈top++;stack[top]=p-rchild;level[top]⑼=n+width;〃显示场宽增widthlevel[top][l]=l;//I表示是右子树ifp-lchild{〃将左子树根结点入栈top++;stack[top]=p-lchild;level[top][O]=n+width;〃显示场宽增widthlevel[top][l]=0;//0表示是左子树}}elseprintf该二叉树是一棵空二叉树!\n”;returnOK;StatusDisplayBiTreeInBracketBiTreeT{〃以嵌套括号表示法输出一棵二叉树ifT{printf%cT-data;ifT-lchild||T-rchild{printf;ifT-lchildDisplayBiTreeInBracketT-lchild;〃递归处理左子树ifT-rchildprintf;ifT-rchildDisplayBiTreeInBracketT-rchild;〃递归处理右子树printf;}elseprintf该二叉树是一棵空二叉树!;returnOK;voidmain(){BiTreeT;charchj;charstr
[200];intchoiceflag=1leni;Statustemp;printf(本程序实现二叉树的操作:\n”);printf(可以进行建立二叉树,递归先序、中序、后序遍历等操作\n);CreateBiTree(T);while(flag){printf(请选择:\n);printf(l.递归先序遍历如);printf(”
2.递归中序遍历\n);printf(
3.递归后序遍历\rT);printf(
4.凹入表示法输出二叉树\n”);printf(
5.嵌套括号表示法输出二叉树\n);printf(
6.重新构建二叉树\n);printf(”
7.退出程序\n”);scanf(%dchoice);switch(choice){if(T){printf(先序遍历二叉树:);PreOrderTraverseOPrintElement);〃先序递归遍历二叉树printf(\n);printf二叉树为空!\nbreak;ifT{printf中序遍历二叉树:;InOrderTraverseTPrintElement;〃中序递归遍历二叉树printf\n;elseprintf二叉树为空!\n”;break;ifT{printf后序遍历二叉树:;PostOrderTraverseTPrintElement;〃后序递归遍历二叉树printf\n;elseprintf二叉树为空!\n”;break;DisplayBiTreelnConcaveT;break;printf;DisplayBiTreelnBracketT;printfn\nn;break;DestroyBiTreeT;CreateBiTreeT;break;default:flag=0;printf程序运行结束,按任意键退出!\n;getch;DestroyBiTreeT;试验五图的算法的实现
一、试验目的.把握图的基本存储方法;.把握有关图的操作算法并用高级语言实现;.娴熟把握图的两种搜寻路径的遍历方法
二、试验内容假设以一个带权有向图表示某一区域的公交线路网,图中顶点代表一些区域中的重要场所,弧代表已有的公交线路,弧上的权表示该线路上的票价或搭乘所需时间,试设计一个交通指南系统,指导前来询问者以最低的票价或最少的时间从区域中的某一场所到达另一场所
三、试验步骤.定义结点结构,定义图结构.存储图信息;.定义求任意两点最短路径函数;.写出主函数
四、实现提示typedefstructnodeintno;floatwgt;structnode*next;edgenode;typedefstructcharvtx;edgenode*link;}vexnode;typedefvexnodeGraph[n];voidFloydGraphGfloatA[n][n]intp[n][n]intijk;fori=0;in;i++forj=0;jn;j++A[i][j]=G[i][j];P[i][j]=-1;fork=0;kn;k++fori=0;in;i++forj=0;jn;j++ifA[i][k]+A[k]U]A[i][j]P[i][j]=k;A[i]U]=A[i][k]+A[k][j];
五、思索与提高.推断两点是否可达.如何对程序进行修改,找一条人最少的公交线路?.练习图的拓扑排序
六、完整参考程序.图的建立与遍历#includeconio.h#includestdio.h#includestdlib.h#includestring.h#defineMAX_VERTEX_NUM20〃图的最大顶点数#defineMAXQSIZE30〃队歹4的最大容量enumBOOL{FalseTrue};typedefstructArcNode{intadjvex;〃该弧所指向的顶点的位置structArcNode*nextarc;〃指向下一条弧的指针}ArcNode;〃弧结点typedefstruct{ArcNode*AdjList[MAX_VERTEX_NUM];〃指向第一条依附该顶点的弧的指针intvexnumarcnum;〃图的当前顶点和弧数intGraphKind;〃图的种类,0—无向图,1—有向图}Graph;typedefstruct//队列结构{intelem[MAXQSIZE];〃数据域intfront;〃队头指针intrear;//队尾指针JSqQueue;BOOLvisited[MAX_VERTEX_NUM];〃全局变量——访问标志数组voidCreateGraphGraph;〃生成图的邻接表voidDFSTraverseGraph;〃深度优先搜寻遍历图voidDFSGraphint;voidBFSTraverseGraph;〃广度优先搜寻遍历图voidInitialSqQueue;〃初始化一个队列BOOLQueueEmptySqQueue;〃推断队列是否空BOOLEnQueueSqQueueint;〃将一个元素入队列BOOLDeQueueSqQueueint;〃将一^元素出队列intFirstAdjVexGraphint;〃求图中某一点的第一^个邻接顶点intNextAdjVexGraphintint;//求某一顶点的下一个邻接顶点voidmain{GraphG;〃采纳邻接表结构的图charj=y;printf本程序将演示生成一个图,并对它进行遍历.\n;printf首先输入要生成的图的种类An;printf”O—无向图,1一有向图\11;printf之后输入图的顶点数和弧数\n格式顶点数,弧数;例如:43\n;printf接着输入各边弧尾,弧头.\n例如:\nl2\nl3\n24\n”;printf程序会生成一个图,并对它进行深度和广度遍历An;printf深度遍历1-2-4-3\n广度遍历1-2-3-4\n;whilej!=Nj!=nvoidmaincomplexx1={23}x2={45}sum;complexaddcomplexxlcomplexx2;sum=addxlx2;cout«xl=«xl.real«+«xl.imag«i«x2=«x
2.real«+«x
2.imag«i«endl;cout«nxl+x2=n«sum.real«n+n«sum.imag«nin«endl;
3、#includeiostream#includestring#includeiomanipusingnamespacestd;constintn=3;structstudent{charnum
[6];stringname;floatscore
[3];floataver;;intmainQ{intijmaximaxsum;floataverage;studentstud[n];fori=0;in;i++〃输入同学和成果信息{cout«ninputscoresofstudentn«i+l«endl;cout«nnumber:n;cin»stud[i].num;cout«nname:n;cin»stud[i].name;forj=0;j3;j++{cout«nscoren«j+l«n:n;cin»stud[i].scorefj];cout«endl;}〃输入同学和成果信息average=0;max=0;maxi=0;{printf请输入要生成的图的种类0/1:”;scanf”%d”G.GraphKind;〃输入图的种类printf请输入顶点数和弧数;scanf%d%dG.vexnumG.arcnum;〃输入图的顶点数和弧数CreateGraphG;〃生成邻接表结构的图DFSTraverseG;//深度优先搜寻遍历图BFSTraverseG;〃广度优先搜寻遍历图printf图遍历完毕,连续进行吗Y/N”;scanf%cj;voidCreateGraphGraphG{〃构造邻接表结构的图Ginti;intstartend;ArcNode*s;fori=l;i=G.vexnum;i++G.AdjList[i]=NULL;〃初始化指针数组fori=1;i=G.arcnum;i++{scanf%d%d”startend;〃输入弧的起点、和终点s=ArcNode*mallocsizeofArcNode;//生成~~~^个弧结点s-nextarc=G.AdjList[start];〃插入到邻接表中s-adjvex=end;G.AdjList[start]=s;ifG.GraphKind==O〃若是无向图,再插入到终点的弧链中{s=ArcNode*mallocsizeofArcNode;s-nextarc=G.AdjList[end];s-adjvex=start;G.AdjList[end]=s;voidDFSTraverseGraphG{〃深度优先遍历图Ginti;printfDFSTraverse:;fori=1;i=G.vexnum;i++visited[i]=False;//访问标志数组初始化fori=l;i=G.vexnum;i++if!visited[i]DFSGi;〃对尚未访问的顶点调用DFSprintf\b\b\n;voidDFSGraphGinti{〃从第i个顶点动身递归地深度遍历图Gintw;visited[i]=True;//访问第i个顶点printf%d-i;forw=FirstAdjVexGi;w;w=NextAdjVexGiwif!visited[w]DFSGw;〃对尚未访问的邻接顶点w调用DFSvoidBFSTraverseGraphG{〃按广度优先非递归的遍历图G使用帮助队列Q和访问标志数组visitedintiuw;SqQueueQ;printfBFSTreverse:;fori=l;i=G.vexnum;i++visited[i]=False;//访问标志数组初始化InitialQ;〃初始化队列fori=l;i=G.vexnum;i++if!visited[i]{visited[i]=True;〃访问顶点iprintf%d-i;EnQueueQi;〃将序号i入队列while!QueueEmptyQ〃若队列不空,连续{DeQueueQu;〃将队头元素出队列并置为uforw=FirstAdjVexGu;w;w=NextAdjVexGuwif!visited[w]〃对u的尚未访问的邻接顶点w进行访问并入队列{visited[w]=True;printf%d-w;EnQueueQw;printf\b\b\n;intFirstAdjVexGraphGintv{〃在图G中查找第v个顶点的第一个邻接顶点if!G.AdjList[v]return0;elsereturnG.AdjList[v]-adjvex;intNextAdjVexGraphGintvintu{〃在图G中查找第v个顶点的相对于u的下一个邻接顶点ArcNode*p;p=G.AdjList[v];whilep-adjvex!=up=p-nextarc;〃在顶点v的弧链中找至I顶点uifp-nextarc==NULLreturn0;〃若已是最终一个顶点,返回0elsereturnp-nextarc-adjvex;〃返回下一个邻接顶点的序号voidInitialSqQueueQ{〃队列初始化Q.front=Q.rear=0;BOOLQueueEmptySqQueueQ{〃推断队列是否已空,若空返回True否则返回FalseifQ.front==Q.rearreturnTrue;elsereturnFalse;BOOLEnQueueSqQueueQintch{〃入队列,胜利返回True失败返回FalseifQ.rear+1%MAXQSIZE==Q.frontreturnFalse;Q.elem[Q.rear]=ch;Q.rear=Q.rear+1%MAXQSIZE;returnTrue;BOOLDeQueueSqQueueQintch{〃出队列,胜利返回True并用ch返回该元素值,失败返回FalseifQ.front==Q.rearreturnFalse;ch=Q.elem[Q.front];Q.front=Q.front+1%MAXQSIZE;returnTrue;〃胜利出队列,返回True
2.最短路径-迪杰斯特拉算法#includeconio.h#includestdio.h#includestdlib.h#includestring.h#defineINFINITY30000〃定义一个权值的最大值#defineMAX_VERTEX_NUM20〃图的最大顶点数enumBOOL{FalseTrue};typedefstruct{intarcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];〃邻接矩阵intvexnumarcnum;〃图的当前顶点和边数}Graph;voidCreateGraphGraph;//生成图的邻接矩阵voidShortestPath_DiJGraphintint[][MAX_VERTEX_NUM]int[];〃用迪杰斯特拉算法求从某一源点到其余顶点的最短路径voidPrint_ShortestPathGraphintint[][MAX_VERTEX_NUM]int[];//显示最短路径voidmain{GraphG;〃采纳邻接矩阵结构的图charj=V;intu;intP[MAX_VERTEX_NUM][MAX_VERTEX_NUM];〃存放从源点到各顶点的最短路径intD[MAX_VERTEX_NUM];〃存放从源点到各顶点的最短路径的距离printf本程序将演示采用迪杰斯特拉算法求\n从图的一点到其余顶点的最短路径.\n;printf首先输入图的顶点数和弧数An格式:顶点数弧数;例如:57\n;printf然后输入各弧和权值.\n格式弧尾,弧头,权值;例^:\nl210\nl318\n245\n325\n432\n452\n532\n;printf再输入从哪个顶点动身,例如printf程序将会找出从1到其余顶点的最短路径An;printf10l-2\nl7l-2-4-3\nl5l-2-4\nl71-2-4-5\n;whilej!=Nj!=n{CreateGraphG;〃生成邻接矩阵结构的图printf从哪个顶点动身:;scanf%du;〃输入迪杰斯特拉算法中的起始顶点ShortestPath_DiJGuPD;〃采用迪杰斯特拉算法求最短路径Print_ShortestPathGuPD;〃显示最短路径printf最短路径演示完毕,连续进行吗?Y/N”;scanf%cj;voidCreateGraphGraphG{〃构造邻接矩阵结构的图Gintij;intstartendweight;printf请输入图的顶点数和弧数顶点数,弧数:;scanf%d%dG.vexnumG.arcnum;〃输入图的顶点数和边数fori=l;i=G.vexnum;i++forj=l;j=G.vexnum;j++G.arcs[i][j]=INFINITY;//初始化邻接矩阵printf输入各弧和权值,格式弧尾,弧头,权值\n;fori=1;i=G.arcnum;i++{scanf%d%d%d”startendweight;〃输入边的起点和终点及权值G.arcs[start][end]二weight;voidShortestPath_DiJGraphGintvOintP[][MAX_VERTEX_NUM]intD[]{〃用迪杰斯特拉算法求有向网G的vO顶点到其余顶点v的最短路径P[v]及其带权路径长度D[v]〃若P[v]
[0]于0表明从源点动身存在一条到顶点v的最短路径,该路径存放在P[v]中//finalM为True则表明已经找到从vO到v的最短路径intijwv;intmin;BOOLfinal[MAX_VERTEX_NUM];forv=l;v=G.vexnum;v++〃初」台化{final[v]=False;D[v]=G.arcs[vO][v];fori=0;i=G.vexnum;i++P[v][i]=0;〃设空路径//ifD[v]INFINITYP[v]
[0]=v0;//若从vO到v有直达路径D[v0]=0;final[vO]=True;〃初始时,vO属于S集〃开头主循环,每次求得vO到某个顶点v的最短路径,并加v至IS集fori=l;i=G.vexnum;i++〃查找其余Gvexnum-1个顶点{v=0;min=INFINITY;forw=1;w=G.vexnum;w++〃查找当前离vO最近的顶点vif!final[w]D[w]min{v=w;min=D[w];}if!vbreak;〃若v=0表明全部与vO有通路的顶点均已找到了最短路径,退出主循环final[v]=True;//将v加入S集forj=0;P[v][j]!=0;j++;P[v][j]=v;〃将路径P[v]延长到顶点vforw=l;w=G.vexnum;w++〃更新当前最短路径及距离if!final[w]min+G.arcs[v][w]D[w]{D[w]=min+G.arcs[v][w];forj=0;P[v][j]!=0;j++P[w][j]=P[v][j];voidPrint_ShortestPathGraphGintvOintP[][MAX_VERTEX_NUM]intD口{〃显示从顶点u到其余顶点的最短路径及距离intvj;printfTheshortestpathfromVertex%dtotheotherVertex:\n;forv=l;v=G.vexnum;v++{ifP[v]
[0]=0continue;〃表明顶点vO到顶点v没有通路printf%-4dD[v];printf%d-vO;forj=0;P[v][j]!=0;j++printf%d-P[v][j];printf\b\b\n;
3.最短路径-弗洛依德算法#includeconio.h#includestdio.h#includestdlib.h#includestring.h#defineINFINITY10000〃定义权值的最大值#defineMAX_NUM20//图的最大顶点数enumBOOL{FalseTrue};typedefstruct{intarcs[MAX_NUM][MAX_NUM];〃邻接矩阵intvexnumarcnum;〃图的当前顶点和边数}Graph;voidCreateGraphGraph;〃生成图的邻接矩阵voidShortestPath_FloydGraphBOOL[][MAX_NUM][MAX_NUM]int[][MAX_NUM];〃用弗洛依德算法求每对顶点之间的最短路径voidPrint_ShortestPathGraphBOOL[][MAX_NUM][MAX_NUM]int[][MAX_NUM];〃显示用弗洛依德算法所求得的最短路径voidPrint_OnePathintintintBOOL[][MAX_NUM][MAX_NUM];〃显示一对顶点之间的最短路径voidmainQ{GraphG;〃采纳邻接矩阵结构的图charj=y;intu;BOOLP[MAX_NUM][MAX_NUM][MAX_NUM];//存放每对顶点的最短路径intD[MAX_NUM][MAX_NUM];〃存放每对顶点的最短路径的距离printf本程序演示弗洛依德算法求图的每一对顶点之间的最短路径o\n;printf首先输入图的顶点和弧的数目\n例如35\n;printf接着输入弧ij和其权值\n例如\nl24\n2l6\nl3H\n3l3\n232\n;printf程序将会显示出每对顶点之间的最短路径值和所经过的路径\n;printf41-2\n61-2-3\n52-3-l\n22-3\n33-l\n73-l-2\n;whilej!-Nj!=n{CreateGraphG;〃生成邻接矩阵结构的图ShortestPath_FloydGPD;//采用弗洛依德算法求最短路径Print_ShortestPathGPD;//显示每对顶点之间的最短路径printf连续执行吗Y/N”;scanf%cj;printf程序运行结束,按任意键退出窗口!getch;voidCreateGraphGraphG{〃构造邻接矩阵结构的图Gintij;intstartendweight;printf请输入顶点和弧的数目格式顶点数,弧数\n;fori=0;in;i++{sum=0;forj=O;j3;j++〃计算每个同学总成果sum+=stud[i].score[j];stud[i].aver=sum/
3.0;〃计算每个同学平均成果ifsummax〃将某同学平均成果与目前的最高平均成果进行比较选择高的那个为最新最高平均成果{max=sum;maxi=i;cout«nnumber.namescore1score2score3averageH«endl;fori=0;in;i++〃输出全部同学成果信息{cout«setw8«stud[i].num«nn«setw10«stud[i].name«n”;forj=0;j3;j++coutsetw3«stud[i].score[j]«n”;cout«stud[i].aver«endl;}〃输出全部同学成果信息cout«nThehighestscoreis:n«stud[maxi].num«nn«stud[maxi].name«nn«nTheaverageis:n«stud[maxi].aver;cout«threescores:;〃输出最高平均成果的同学信息forj=0;j3;j++cout«stud[maxi].score[j]«nn;cout«endl;return0;试验二线形表基本操作的实现
一、试验目的.熟识C语言的上机环境,进一步把握C语言的结构特点.把握线性表的挨次存储结构的定义及C语言实现.把握线性表的链式存储结构——单链表的定义及C语言实现.把握线性表在挨次存储结构即挨次表中的各种基本操作.把握线性表在链式存储结构——单链表中的各种基本操作
二、试验内容scanf%d%dG.vexnumG.arcnum;〃输入图的顶点数和边数fori=l;i=G.vexnum;i++forj=l;j=G.vexnum;j++G.arcs[i][j]=INFINITY;//初始化邻接矩阵printf请输入各条弧和其权值,格式弧尾,弧头,权值\n;fori=l;i=G.arcnum;i++{scanf%d%d%dstartendweight;//输入边的起点和终点及权值Gares[start][end]=weight;voidShortestPath_FloydGraphGBOOLP[][MAX_NUM][MAX_NUM]intD[][MAX_NUM]{〃用弗洛依德算法求有向网G的每对顶点v和w之间的最短路径P[v][w]〃及其带权路径长度D[v][w]〃若P[v][w][u]为True表明u是从v到w当前求得最短路径上的顶点intuvwi;forv=l;v=G.vexnum;v++〃各对顶点之间的初始已知路径及距离forw=l;w=G.vexnum;w++{D[v][w]=G.arcs[v][w];foru=1;u=G.vexnum;u++P[v][w][u]=False;ifD[v][w]INFINITY〃从v到w有直接路径{P[v][w][v]=True;P[v][w][w]=True;}foru=1;u=G.vexnum;u++forv=l;v=G.vexnum;v++forw=1;w=G.vexnum;w++ifD[v][u]+D[u][w]D[v][w]v!=w//从v经u到w的一条路径更短{D[v][w]=D[v][u]+D[u][w];fori=1;i=G.vexnum;i++ifP[v][u][i]||P[u][w][i]P[v][w][i]=True;voidPrint_ShortestPathGraphGBOOLP[][MAX_NUM][MAX_NUM]intD[][MAX_NUM]{〃显示每对顶点之间的最短路径及距离intvwj;printf最短路径:\n;forv=l;v=G.vexnum;v++forw=1;w=G.vexnum;w++ifD[v][w]INFINITY〃顶点v和w之间有通路{printf”%-5d”D[v][w];〃从v到w的最短距离Print_OnePathvwG.vexnumP;//显示从v到w的最短路径printf\n;voidPrint_OnePathintvintwintnumBOOLP[][MAX_NUM][MAX_NUM]{//显示从v到w的最短路径inti;fori=l;i=num;i++ifi!=vi!=wP[v][w][i]==Truebreak;ifinumprintf%d-%dvw;〃说明从v到w不需经过其它的顶点else{Print_OnePathvinumP;//否则从v到w需经过顶点i先显示从v到i的最短路径ifi10printfn\bn;〃掌握显示格式消退多余的“elseprintf\b\b;Print_OnePathiwnumP;//显示从i到w的最短路径试验六查找算法的实现
一、试验目的.把握查找的不同方法,并能用高级语言实现查找算法;.娴熟把握二叉排序树的构造和查找方法.娴熟把握静态查找表及哈希表查找方法
二、试验内容设计一个读入一串整数,然后构造二叉排序树,进行查找
三、试验步骤.从空的二叉树开头,每输入一个结点数据,就建立一个新结点插入到当前已生成的二叉排序树中.在二叉排序树中查找某一结点.用其它查找算法进行排序(课后自己做)
四、实现提示.定义结构typedefstructnode{intkey;intother;structnode*lchild*rchild;}bstnode;voidinordert{ift!=Null{inordert-Ichild;printf%4d”t-key;inordert-rchild;}}bstnode*insertbsttsbstnode*s*t;{bstnode*f*p;p=t;whilep!=Null{f=P;ifs—key==pTkeyreturnt;ifsTkeyvpTkeyp=pTIchild;elsep=pTrchild;ift==Nullreturns;ifsTkeyfTkeyfTlchild=s;elsef-rchild=s;returnt;}bstnode*creatord{bstnode*t*s;intkey;t=Null;scanf%cTkey;whilekey!=O{s=mallocsizeofbitree;sTkey二key;s—lchild=Null;s-rchild=Null;scanf“%d”,data;sTother=data;t=insertbstts;scanf%d”key;returnt;
五、思索与提高.用其它的查找方法完成该算法.比较各种算法的时间及空间简单度
六、完整参考程序
1.折半查找#includeconio.h#includestdio.h#defineMAX30〃定义有序查找表的最大长度typedefstruct{charelem[MAX];〃有序查找表intlength;//length指示当前有序查找表的长度}SSTable;voidinitialSSTable;〃初始化有序查找表intsearchSSTableint;〃在有序查找表中查找元素voidprintSSTable;〃显示有序查找表中全部元素voidmain{SSTableST;//ST为一有序查找表intchlocflag=l;charj;initialST;〃初始化有序查找表whileflag{printf请选择\n;printfl.显示全部元素由;printf
2.查找一个元素\n;printf
3.退出\n;scanf%cj;switchj{caser printST;break;〃显示全部元素case2:{printf请输入要查找的元素;scanf%dch;〃输入要查找的元素的关键字loc=searchSTch;〃查找ifloc!=0printf该元素所在位置是%d\n”loc;//显示该元素位置elseprintf%d不存在!\n”ch;〃当前元素不存在break;default:flag=O;printf程序运行结束!按任意键退出!\n;voidinitialSSTablev{〃初始化有序查找表inti;printf请输入静态表的元素个数;//输入有序查找表初始化时的长度scanf%dv.length;printf请从小到大输入%d个元素整形数\nv.length;getchar;fori=l;i=v.length;i++scanf%d”v.elem[i];〃从下到大输入有序查找表的各元素intsearchSSTablevintch{〃在有序查找表中查找ch的位置,胜利返回其位置,失败返回0intlowhighmid;low=l;high=v.length;//置区间初值whilelow=high{mid=low+high/2;ifv.elem[mid]==chreturnmid;〃找到待查元素elseifv.elem[mid]chhigh=mid-1;〃连续在前半区间进行查找elselow=mid+l;〃连续在后半区间进行查找return0;〃找不到时,i为0voidprintSSTablev〃显示当前有序查找表全部元素{inti;fori=l;i=v.length;i++printf%dv.elem[i];printf\n;
2.二叉排序树的建立与查找#includeconio.h#includemath.h#includestdio.h#includestdlib.henumBOOL{FalseTrue};typedefstructBiTNode〃定义二叉树节点结构{chardata;〃为了便利,数据域只有关键字一项structBiTNode*lchild*rchild;〃左右孩子指针域}BiTNode*BiTree;BOOLSearchBSTBiTreecharBiTreeBiTree;//在二叉排序树中查找元素BOOLInsertBSTBiTreechar;〃在二叉排序树中插入元素BOOLDeleteBSTBiTreechar;〃在二叉排序树中删除元素voidDeleteBiTree;〃删除二叉排序树的根结点voidInorderBSTBiTree;〃中序遍历二叉排序树,即从小到大显示各元素voidmain{BiTreeTp;charchkeywordj=y;BOOLtemp;T=NULL;whilej!=n{printf
1.display\n;printf
2.search\n;printf
3.insert\n;printf
4.delete\n;printf
5.exit\n;scanf%c”ch;〃输入操作选项switchch{caseT:if!TprintfTheBSThasnoelemAn;else{InorderBSTT;printf\n;}break;case2:printfInputthekeywordofelemtobesearchedachar:;scanf%ckeyword;〃输入要查找元素的关键字temp=SearchBSTTkeywordNULLp;if!tempprintf%cisntexisted!\nkeyword;〃没有找至Uelseprintfn%chasbeenfound!\n”keyword;〃胜利找至1break;case3:printfInputthekeywordofelemtobeinsertedachar:;scanf%ckeyword;〃输入要插入元素的关键字temp=InsertBSTTkeyword;if!tempprintfn%chasbeenexisted!\nkeyword;//该元素已经存在elseprintfnSucesstoinert%c!\n”keyword;〃胜利插入break;case4:printfnInputthekeywordofelemtobedeletedachar:;scanf%c”keyword;〃输入要删除元素的关键字temp=DeleteBSTTkeyword;if!tempprintfn%cisntexisted!\rTkeyword;//该元素不存在elseprintfnSucesstodelete%c\n\keyword;〃月生利册[除break;default:j=n;printfnTheprogramisover!\nPressanykeytoshutoffthewindow!\nn;getchar;getchar;voidInorderBSTBiTreeT{〃以中序方式遍历二叉排序树T即从小到大显示二叉排序树的全部元素ifT-lchildInorderBSTT-lchild;printf%2cT-data;ifT-rchildInorderBSTT-rchild;BOOLSearchBSTBiTreeTcharkeyBiTreefBiTreep{〃在根指针T所指二叉排序树中递归的查找其关键字等于key的元素,若查找胜利〃则指针p指向该数据元素,并返回True否则指针指向查找路径上访问的最终一〃个结点并返回False指针f指向T的双亲,其初始调用值为NULLBOOLtmpltmp2;tmp1=tmp2=False;if!T{p=f;retumFalse;〃查找不胜利elseifkey==T-data{p=T;returnTrue;}〃查找胜利elseifkeyT-datatmp1=SearchBSTT-lchildkeyTp;//在左子树中连续查找elsetmp2=SearchBSTT-rchildkeyTp;〃在右子才对中连续查找iftmpl||tmp2returnTrue;〃若在子树中查找胜利,向上级返回TrueelsereturnFalse;〃否则返回FalseBOOLInsertBSTBiTreeTchare{〃当二叉排序树T中不存在元素e时,插入e并返回True否则返回FalseBiTreeps;if!SearchBSTTeNULLp〃查找不胜利.挨次线性表的建立、插入及删除.链式线性表的建立、插入及删除
三、试验步骤.建立含n个数据元素的挨次表并输出该表中各元素的值及挨次表的长度.采用前面的试验先建立一个挨次表L={2123145561731}然后在第i个位置插入元素68o.建立一个带头结点的单链表,结点的值域为整型数据要求将用户输入的数据按尾插入法来建立相应单链表
四、实现提示.由于C语言的数组类型也有随机存取的特点,一维数组的机内表示就是挨次结构因此,可用C语言的一维数组实现线性表的挨次存储在此,我们采用C语言的结构体类型定义挨次表#defineMAXSIZE1024typedefintelemtype;/*线性表中存放整型元素*/typedefstruct{elemtypevec[MAXSIZE];intlen;/*挨次表的长度*/Jsequenlist;将此结构定义放在一个头文件sqlist.h里可避开在后面的参考程序中代码重复书写,此外在该头文件里给出挨次表的建立及常量的定义.留意如何取到第i个元素,在插入过程中留意溢出状况以及数组的下标与位序(挨次表中元素的次序)的区分.单链表的结点结构除数据域外,还含有一个指针域用C语言描述结点结构如下typedefintelemtype;typedefstructnode{s=BiTreemallocsizeofBiTNode;s-data=e;s-lchild=s-rchild=NULL;if!pT=s;〃被插结点*s为新的根结点elseifep-datap-lchild=s;〃被插结点*s为左孩子elsep-rchild=s;〃被插结点*s为右孩子returnTrue;//胜利插入}elsereturnFalse;〃树中已存在关键字为e的数据元素BOOLDeleteBSTBiTreeTcharkey{//若二叉排序树T中存在关键字等于key的数据元素时,则删除该数据元素结点〃并返回True否则返回FalseBOOLtmpltmp2;tmp1=tmp2二False;if!TreturnFalse;〃不存在关键字等于key的数据元素else{ifkey==T-data{DeleteT;returnTrue;}〃找到关键字等于key的数据元素并删除它elseifkeyT-datatmp1=DeleteBSTT-lchildkey;〃连续在左子树中删除elsetmp2=DeleteBSTT-rchildkey;//连续在右子树中删除iftmpl||tmp2returnTrue;〃在子树中删除胜利,返回TrueelsereturnFalse;〃不存在该元素voidDeleteBiTreep{//在二叉排序树中删除结点P并重接它的左或右子树BiTreesq;if!p-rchild〃右子树空,只需重接它的左子树{q=p;p=p-lchild;freeq;elseif!p-lchild〃左子树空,只需重接它的右子树{q=p;p=p-rchild;freeq;else〃左右子树均不空{q=p;s=p-lchild;whiles-rchild{q=s;s=s-rchild;}〃转左,然后向右走到终点p-data=s-data;//s指向被删结点的“前驱”ifq!=pq-〉rchild=s-rchild;〃重接*q的右子树elseq-lchild=s-lchild;//重接*q的左子树frees;试验七排序算法的实现
一、试验目的.把握常用的排序方法,并把握用高级语言实现排序算法的方法;.深刻理解排序的定义和各种排序方法的特点,并能加以敏捷应用;.了解各种方法的排序过程及其时间简单度的分析方法
二、试验内容统计成果给出n个同学的考试成果表,每条信息由姓名和分数组成,试设计一个算法1按分数凹凸次序,打印出每个同学在考试中获得的名次,分数相同的为同一名次;2按名次列出每个同学的姓名与分数
三、试验步骤.定义结构体.定义结构体数组.定出主程序,对数据进行排序
四、实现提示#definen30typedefstructstudent{charname
[8];intscore;}studentR[n];main{intnumijmaxtemp;printf\n请输入同学成果:\n;fori=0;in;i++{printf姓名scanf“%s”stu[i].name;scanf%4d”stu[i].score;}num二1;fori=0;in;i++{max=i;forG=i+1;jn;j++ifR[jl.scoreRfmax]scoremax=j;ifmax!=i{temp=R[max];R[maxl=R[i];R[i]=temp;ifi0R[i].scoreR[i-l].scorenum=num+l;printf%4d%s%4d”numR[i].nameR[i].score;}}
五、思索与提高.快速排序算法解决本问题.较各种排序算法的优缺点及.使用其它排序算法实现该问题直接插入排序、希尔排序、简洁选择排序、堆排序等
六、完整参考程序
1.直接插入排序#includeconio.h#includemath.h#includestdio.h#includestdlib.h#defineMAXSIZE20〃排序表的最大容量typedefstruct〃定义排序表的结构{intelemword[MAXSIZE];//数据元素关键字intcount;〃表中当前元素的个数}SqList;voidInitialSqListSqList;〃初始化排序表voidInsertSortSqList;//直接插入排序voidPrintSqListSqList;〃显示表中的全部元素voidmain{SqListL;〃声明表Lcharj=y;printf”本程序将演示直接插入排序的操作\nH;whilej!=nj!=N{InitialSqListL;InsertSortL;PrintSqListL;printf连续进行下一次排序吗Y/N”;scanfn%c\j;printf,程序运行结束!\n按任意键关闭窗口!\n”;getchar;getchar;voidInitialSqListSqListL{〃表初始化inti;printf请输入待排序的纪录的个数:;scanfH%dnLcount;printf请输入待排序的纪录的关键字整型数:\n“;fori=l;i=Lcount;i++scanfn%dnLelemword[i];voidInsertSortSqListL{intij;fori=2;i=L.count;i++ifL.elemword[i]L.elemword[i-l]〃,需将L.elemword[i]插入有序子表{L.elemword
[0]=L.elemword[i];〃复制为哨兵forj=i-1;L.elemword
[0]L.elemword[j];—jL.elemword[j+l]=L.elemword[j];〃纪录后移L.elemword[j+1]=L.elemword
[0];〃插入到正确的位置}voidPrintSqListSqListL{〃显示表全部元素inti;printf已排好序的序列如下:\nn;fori=l;i=L.count;i++printfn%4dML.elemword[i];printfn\nH;
2.希尔排序#includeconio.h#includemath.h#includestdio.h#includestdlib.h#defineMAXSIZE20〃排序表的最大容量typedefstruct〃定义排序表的结构{intelemword[MAXSIZE];//数据元素关键字intcount;〃表中当前元素的个数}SqList;voidInitialSqListSqList;〃初始化排序表voidShellSortSqListint口int;〃希尔排序voidShellInsertSqListint;〃一趟希尔排序voidPrintSqListSqList;〃显示表中的全部元素voidmain{SqListL;〃声明表Lchar尸y;intdlta
[3]={53/};〃希尔排序增量序列,本程序采纳531序列intt=3;〃希尔排序增量序列中增量的个数printf”本程序将演示希尔排序的操作\n增量序列为531\nn;while!=nj!=N{InitialSqListL;//待排序列初始化ShellSortL41tat;〃希尔排序PrintSqListL;〃显示希尔排序结果printf连续进行下一次排序吗Y/N”;scanfn%cHj;printf程序运行结束!\n按任意键关闭窗口!\ngetchar;getchar;voidInitialSqListSqListL{〃表初始化inti;printf请输入待排序的纪录的个数scanfn%dnL.count;printff请输入待排序的纪录的关键字整型数:\n“;fori=1;i=L.count;i++scanfn%dnLelemword[i];}voidShellSortSqListLintdlta[]intt{〃按增量序列对挨次表L作希尔排序forintk=O;kt;++kSheHInsertLdlta[k];〃一趟增量为dlta[k]的插入排序}voidShellInsertSqListLintdk{〃对挨次表L做一趟希尔插入排序本算法是和一趟直接插入排序相比,作了以下修改://I.前后纪录的增量是dk而不是1〃
2.0号单元只是暂存单元,不是哨兵当jv=0时,插入位置已找到intij;fori=dk+l;i=L.count;i++ifL.elemword[i]L.elemword[i-dk]//,需将L.elemword[i]插入有序子表{L.elemword
[0]=L.elemword[i];〃暂存在0号单元forj=i-dk;j0L.elemword
[0]L.elemword|j];j-dkL.elemword[j+dk]=L.elemword[j];〃纪录后移,查找插入位置L.elemword[j+dk]=L.elemword
[0];〃插入到正确的位置voidPrintSqListSqListL{〃显示表全部元素inti;printf,已排好序的序列如下\n”;fori=l;i=L.count;i++printfn%4dnL.elemword[i];printfn\nn;
3.快速排序#includeconio.h#includemath.h#includestdio.h#includestdlib.h#defineMAXSIZE20〃排序表的最大容量typedefstruct〃定义排序表的结构{intelemword[MAXSIZE];〃数据元素关键字intcount;〃表中当前元素的个数{SqListL;〃声明表Lcharj=y;printf”本程序将演示快速排序的操作\nn;while!=nj!=N{InitialSqListL;〃待排序列初始化QuickSortL;〃,快速才非序PrintSqListL;//显示排序结果printf连续进行下一次排序吗Y/N”;scanfn%c”j;printf程序运行结束!\n按任意键关闭窗口!\ngetchar;getchar;voidInitialSqListSqListL{〃表初始化inti;printf请输入待排序的纪录的个数:;scanfH%dnLcount;printf请输入待排序的纪录的关键字整型数:\nfori=1;i=L.count;i++scanfH%dnLelemword[i];}voidQuickSortSqListL{〃对挨次表L做快速排序QSortL1Lcount;}{elemtypedata;〃数据域structnode*next;〃指针域}linklist;留意结点的建立方法及构造新结点时指针的变化构造一个结点需用到C语言的标准函数mallocQ如给指针变量p安排一个结点的地址p=linklist*mallocsizeoflinklist;该语句的功能是申请安排一类型为linklist的结点的地址空间,并将首地址存入指针变量p中当结点不需要时可以用标准函数freep释放结点存储空间,这时p为空值NULL
五、思索与提高.假如按由表尾至表头的次序输入数据元素,应如何建立挨次表.在main函数里假如去掉L=a语句,会消失什么结果?
六、完整参考程序#includestdio.h#includeconio.h#defineMAX30〃定义线性表的最大长度enumBOOL{FalseTrue};//定义BOOL型typedefstruct{charelem[MAX];〃线性表intlast;//last指示当前线性表的长度Jsqlist;voidinitialsqlist;〃初始化线性表BOOLinsertsqlistintchar;〃在线性表中插入元素BOOLdelsqlistintchar;〃在线性表中删除元素intlocatesqlistchar;〃在线性表中定位元素voidprintsqlist;〃显示线性表中全部元素voidmain{sqlistS;//S为一线性表intlocflag=l;charjch;BOOLtemp;printf本程序用来实现挨次结构的线性表\n;printf可以实现查找、插入、删除等操作\n;initialS;〃初始化线性表whileflag{〃对挨次表中的子序列1巾0\¥.・出811]作快速排序intpivotloc;iflowhigh〃长度大于1{pivotloc=PartitionLlowhigh;//#L.elemword[kw..high]一分为二QSortLJowpivotloc-1;//对低子表递归排序pivotloc是枢轴位置QSortLpivotloc+1high;〃对高子表递归排序}intPartitionSqListLintlowinthigh{〃交换挨次表L中子表r[low..high]的纪录,枢轴纪录到位,并返回其所在位置,此时〃在它之前后的纪录均不大小于它intpivotkey;pivotkey=L.elemword[low];〃用子表的第一个纪录作枢轴纪录whilelowhigh〃从表的两端交替地向中间扫描{whilelowhighL.elemword[high]=pivotkey-high;L.elemword[low]=L.elemword[high];〃将比枢轴纪录小的纪录移到低端whilelowhighL.elemword[low]=pivotkey++low;L.elemword[high]=L.elemword[low];〃将比枢轴纪录大的纪录移到高端L.elemword[low]=pivotkey;〃才区山纪录到位returnlow;〃返回枢轴纪录}voidPrintSqListSqListL{〃显示表中全部元素inti;printf,已排好序的序列如下\n;fbri=1;i=L.count;i++printfH%4dHL.elemword[i];printfn\nn;{printf请选择:\n;printf”
1.显示全部元素素printf
2.插入一个元素\n;printf3删除一个元素\n;printf
4.查找一个元素\n;printf”
5.退出程序\nn;scanfH%c\j;switchj{caseT:printS;break;//显示全部元素case2:{printf请输入要插入的元素一个字符和插入位置:\n;printf格式字符,位置;例如:a2\n;scanfn%c%d”chloc;〃输入要插入的元素和插入的位置temp=insertSlocch;〃插入iftemp==Falseprintf插入失败!\n“;〃插入失败else{printf插入胜利!\n”;printS;}〃插入胜利break;case3:{printf”请输入要删除元素的位置:;scanf%dloc;〃输入要删除的元素的位置temp=delSlocch;〃删除iftemp==Trueprintf”删除了一个元素:%c\n”ch;//删除胜利elseprintf该元素不存在!\rT;//删除失败printS;break;case4:{printf请输入要查找的元素scanfn%c”ch;//输入要查找的元素loc=locateSch;〃定位ifloc!=-lprintf”该元素所在位置:%d\n”loc+l;//显示该元素位置elseprintfn%c不存在!\n”ch;〃当前元素不存在break;default:flag=O;printf程序结束,按任意键退出!\n;getch;}voidinitialsqlistv{〃初始化线性表inti;printff请输入初始线性表长度n=//输入线性表初始化时的长度scanfn%dnv.last;printf”请输入从1到%1的各元素字符例如:abcdefgn”v.last;getchar;fori=0;iv.last;i++scanf”%c”v.elem[i];//输入线性表的各元素}BOOLinsertsqlistvintloccharch{〃插入一个元素,胜利返回True失败返回Falseinti;ifloc1||locv.last+1{printf插入位置不合理!\n”;〃位置不合理returnFalse;elseifv.last=MAX〃线性表已满{printf线性表已满!\nreturnFalse;else{fori=v.last-l;i=loc-l;i—v.elem[i+l]=v.elem[i];〃其后元素依次后移v.elem[loc-l]=ch;〃插入元素v.last++;〃线性表长度加一returnTrue;BOOLdelsqlistvintloccharch{〃删除一个元素,胜利返回True并用ch返回该元素值,失败返回Falseintj;iflocl||locv.last//删除位置不合理returnFalse;else{ch=v.elem[loc-l];//ch取得该元素值forj=loc-1;jv.last-1;j++v.elem[j]=v.elem[j+1];〃其后元素依次前移v.last-;〃线性表长度减一returnTrue;intlocatcsqlistvcharch{〃在线性表中查找ch的位置,胜利返回其位置,失败返回-1inti=0;whileiv.lastv.elem[i]!=chi++;〃当前位置后移,直到找到为止ifv.elem[i]==ch//找到当前元素returni;printfa\n;printf/\n;printfb\n;printf/\\\n;printfcd\n;printf/\\\n;printfef\n;printf\\\n;printfg\n;pstr=getsstr;CreateBiTreelnBracketT;〃初始化二叉树。