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

1、 printf(后序遍历二叉树:)；PostOrderTraverse(T,PrintElement);后序递归遍历二叉树printf(n)；elseprintfC二叉树为空!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

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

3、;typedefstructcharvtx;edgenode*link;vexnode;typedefvexnodeGraphn;voidFloyd(GraphG,floatAnn,intpnn)inti,j,k;for(i=0;in;i+)for(j=0;jn;j+)Aij=Gij;Pij=-1;for(k=0;kn;k+)for(i=0;in;i+)for(j=0;jn;j+)if(Aik+AkjAij)Pij=k;Aij=Aik+Akj;五、思考与提高判断两点是否可达。如何对程序进行修改，找一条人最少的公交线路？练习图的拓扑排序六、完整参考程序1.图的建立与遍历#include#incl

4、ude#include#include#defineMAX_VERTEX_NUM20/图的最大顶点数#defineMAXQSIZE30/队列的最大容量enumBOOLFalse,True;typedefstructArcNodeintadjvex;/该弧所指向的顶点的位置structArcNode*nextarc;/指向下一条弧的指针ArcNode;/弧结点typedefstructArcNode*AdjListMAX_VERTEX_NUM;/指向第一条依附该顶点的弧的指针intvexnum,arcnum;/intvexnum,arcnum;/图的当前顶点和弧数intGraphKind;/图的

5、种类，0无向图，1有向图Graph;typedefstruct/队列结构intelemMAXQSIZE;/数据域intfront;/队头指针intrear;/队尾指针SqQueue;BOOLvisitedMAX_VERTEX_NUM;/全局变量访问标志数组voidCreateGraph(Graph&);/生成图的邻接表voidDFSTraverse(Graph);/深度优先搜索遍历图voidDFS(Graph,int);voidBFSTraverse(Graph);/广度优先搜索遍历图voidInitial(SqQueue&);/初始化一个队列BOOLQueueEmpty(SqQueue);/

6、判断队列是否空BOOLEnQueue(SqQueue&,int);/将一个元素入队列BOOLDeQueue(SqQueue&,int&);/将一个元素出队列intFirstAdjVex(Graph,int);/求图中某一顶点的第一个邻接顶点intNextAdjVex(Graph,int,int);/求某一顶点的下一个邻接顶点voidmain()GraphG;/采用邻接表结构的图charj=y;printf(”本程序将演示生成一图，并对它进行遍历.n);printf(“首先输入要生成的图的种类.n);printf(0无向图，1-有向图n);printf(之后输入图的顶点数和弧数。n格式：顶点数，

7、弧数；例如:4,3n);printf(接着输入各边(弧尾，弧头).n例如:n1,2n1,3n2,4n);printf(程序会生成一个图，并对它进行深度和广度遍历An);printf(深度遍历:1-2-4-3n广度遍历:1-2-3-4n);while(j!=N&j!=n)printf(“请输入要生成的图的种类(0/1):)；scanf(%d,&G.GraphKind);/输入图的种类printf(请输入顶点数和弧数：)；scanf(%d,%d,&G.vexnum,&G.arcnum);/输入图的顶点数和弧数CreateGraph(G);/生成邻接表结构的图DFSTraverse(G);/深度优先

8、搜索遍历图BFSTraverse(G);/广度优先搜索遍历图printf(图遍历完毕，继续进行吗?(Y/N);scanf(%c,&j);voidCreateGraph(Graph&G)/构造邻接表结构的图Ginti;intstart,end;ArcNode*s;for(i=1;i=G.vexnum;i+)G.AdjListi=NULL;/初始化指针数组for(i=1;inextarc=G.AdjListstart;/插入到邻接表中s-adjvex=end;G.AdjListstart=s;if(G.GraphKind=0)/若是无向图，再插入到终点的弧链中s=(ArcNode*)malloc(

9、sizeof(ArcNode);s-nextarc=G.AdjListend;s-adjvex=start;G.AdjListend=s;voidDFSTraverse(GraphG)/深度优先遍历图Ginti;printf(DFSTraverse:);for(i=1;i=G.vexnum;i+)visitedi=False;/访问标志数组初始化for(i=1;i,i);for(w=FirstAdjVex(G,i);w;w=NextAdjVex(G,i,w)if(!visitedw)DFS(G,w);/对尚未访问的邻接顶点w调用DFSvoidBFSTraverse(GraphG)/按广度优先非

10、递归的遍历图G，使用辅助队列Q和访问标志数组visitedinti,u,w;SqQueueQ;printf(BFSTreverse:);for(i=1;i=G.vexnum;i+)visitedi=False;/访问标志数组初始化Initial(Q);/初始化队列for(i=1;i,i);EnQueue(Q,i);/将序号i入队列while(!QueueEmpty(Q)/若队列不空，继续DeQueue(Q,u);/将队头元素出队列并置为ufor(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w)if(!visitedw)/对u的尚未访问的邻接顶点w进行访问并入队列

11、visitedw=True;printf(%d-,w);EnQueue(Q,w);printf(bbn);intFirstAdjVex(GraphG,intv)/在图G中寻找第v个顶点的第一个邻接顶点if(!G.AdjListv)return0;elsereturn(G.AdjListv-adjvex);intNextAdjVex(GraphG,intv,intu)/在图G中寻找第v个顶点的相对于u的下一个邻接顶点ArcNode*p;p=G.AdjListv;while(p-adjvex!=u)p=p-nextarc;/在顶点v的弧链中找到顶点uif(p-nextarc=NULL)return

12、0;/若已是最后一个顶点，返回0elsereturn(p-nextarc-adjvex);/返回下一个邻接顶点的序号voidInitial(SqQueue&Q)/队列初始化Q.front=Q.rear=0;BOOLQueueEmpty(SqQueueQ)/判断队列是否已空，若空返回True，否则返回Falseif(Q.front=Q.rear)returnTrue;elsereturnFalse;BOOLEnQueue(SqQueue&Q，intch)/入队列，成功返回True，失败返回Falseif(Q.rear+1)%MAXQSIZE=Q.front)returnFalse;Q.elemQ

13、.rear=ch;Q.rear=(Q.rear+1)%MAXQSIZE;returnTrue;BOOLDeQueue(SqQueue&Q,int&ch)/出队列，成功返回True，并用ch返回该元素值，失败返回Falseif(Q.front=Q.rear)returnFalse;ch=Q.elemQ.front;Q.front=(Q.front+1)%MAXQSIZE;returnTrue;/成功出队列，返回True2.最短路径-迪杰斯特拉算法#include#include#include#include#defineINFINITY30000/定义一个权值的最大值#defineMAX_VE

14、RTEX_NUM20/图的最大顶点数enumBOOLFalse，True;typedefstructintarcsMAX_VERTEX_NUMMAX_VERTEX_NUM;/邻接矩阵intvexnum，arcnum;/图的当前顶点和边数Graph;voidCreateGraph(Graph&);/生成图的邻接矩阵voidShortestPath_DiJ(Graph，int，intMAX_VERTEX_NUM，int);/用迪杰斯特拉算法求从某一源点到其余顶点的最短路径voidPrint_ShortestPath（Graph,int,intMAX_VERTEX_NUM,int）;/显示最短路径v

15、oidmain（）GraphG;/采用邻接矩阵结构的图charj=y;intu;intPMAX_VERTEX_NUMMAX_VERTEX_NUM;/存放从源点到各顶点的最短路径intDMAX_VERTEX_NUM;/存放从源点到各顶点的最短路径的距离printf（“本程序将演示利用迪杰斯特拉算法求n从图的一点到其余顶点的最短路径An）;printf（首先输入图的顶点数和弧数.n格式：顶点数，弧数；例如:5,7n）;printf（然后输入各弧和权值.n格式：弧尾，弧头，权值；例如:nl,2,10nl,3,18n2,4,5n3,2,5n4,3,2n4,5,2n5,3,2n）;printf（再输入从

16、哪个顶点出发，例如:1n）;printf（程序将会找出从1到其余顶点的最短路径.n）;printf（101-2n171-2-4-3n151-2-4n171-2-4-5n）;while（j!=N&j!=n）CreateGraph（G）;/生成邻接矩阵结构的图printf（从哪个顶点出发:）;scanf(%d,&u);/输入迪杰斯特拉算法中的起始顶点ShortestPath_DiJ(G,u,P,D);/利用迪杰斯特拉算法求最短路径Print_ShortestPath(G,u,P,D);/显示最短路径printf(“最短路径演示完毕，继续进行吗?(Y/N);scanf(%c,&j);voidCrea

17、teGraph(Graph&G)/构造邻接矩阵结构的图Ginti,j;intstart,end,weight;printf(请输入图的顶点数和弧数(顶点数，弧数):)；scanf(%d,%d,&G.vexnum,&G.arcnum);/输入图的顶点数和边数for(i=1;i=G.vexnum;i+)for(j=1;j=G.vexnum;j+)G.arcsij=INFINITY;/初始化邻接矩阵printf(输入各弧和权值，格式：弧尾，弧头，权值n);for(i=1;i=G.arcnum;i+)scanf(%d,%d,%d,&start,&end,&weight);/输入边的起点和终点及权值G.

18、arcsstartend=weight;voidShortestPath_DiJ(GraphG,intv0,intPMAX_VERTEX_NUM,intD)/用迪杰斯特拉算法求有向网G的v0顶点到其余顶点v的最短路径Pv及其带权路径长度Dv若PvOO,表明从源点出发存在一条到顶点v的最短路径，该路径存放在Pv中finalv为True则表明已经找到从v0到v的最短路径inti,j,w,v;intmin;BOOLfinalMAX_VERTEX_NUM;for(v=1;v=G.vexnum;v+)/初始化finalv=False;Dv=G.arcsv0v;for(i=0;i=G.vexnum;i+)

19、Pvi=0;/设空路径if(DvvINFINITY)Pv0=v0;/若从v0到v有直达路径Dv0=0;finalvO=True;/初始时，vO属于S集开始主循环，每次求得v0到某个顶点v的最短路径，并加v到S集for(i=1;i=G.vexnum;i+)/寻找其余G.vexnum-1个顶点v=O;min=INFINITY;for(w=1;w=G.vexnum;w+)/寻找当前离v0最近的顶点vif(!finalw)&(Dwmin)v=w;min=Dw;if(!v)break;/若v=0表明所有与v0有通路的顶点均已找到了最短路径，退出主循环finalv=True;/将v加入S集for(j=0;

20、Pvj!=0;j+);Pvj=V；将路径Pv延伸到顶点Vfor(w=1;w=G.vexnum;w+)/更新当前最短路径及距离if(!finalw&(min+G.arcsvwDw)Dw=min+G.arcsvw；for(j=0；Pvj!=0；j+)Pwj=Pvj；voidPrint_ShortestPath(GraphG,intv0,intPMAX_VERTEX_NUM,intD)/显示从顶点u到其余顶点的最短路径及距离intv,j；printf(TheshortestpathfromVertex%dtotheotherVertex:n)；for(v=1；v,v0);for(j=0;Pvj!=0

21、;j+)printf(%d-,Pvj);printf(bbn);3.最短路径-弗洛依德算法#include#include#include#include#defineINFINITY10000/定义权值的最大值#defineMAX_NUM20/图的最大顶点数enumBOOLFalse,True;typedefstructintarcsMAX_NUMMAX_NUM;/邻接矩阵intvexnum,arcnum;/图的当前顶点和边数Graph;voidCreateGraph(Graph&);/生成图的邻接矩阵voidShortestPath_Floyd(Graph,BOOLMAX_NUMMAX_N

22、UM,intMAX_NUM);/用弗洛依德算法求每对顶点之间的最短路径voidPrint_ShortestPath(Graph,BOOLMAX_NUMMAX_NUM,intMAX_NUM);/显示用弗洛依德算法所求得的最短路径voidPrint_OnePath(int,int,int,BOOLMAX_NUMMAX_NUM);/显示一对顶点之间的最短路径voidmain()GraphG;/采用邻接矩阵结构的图charj=y;intu;BOOLPMAX_NUMMAX_NUMMAX_NUM;/存放每对顶点的最短路径intDMAX_NUMMAX_NUM;/存放每对顶点的最短路径的距离printf(本程

23、序演示弗洛依德算法求图的每一对顶点之间的最短路径n);printf(“首先输入图的顶点和弧的数目。n例如：3,5n);printf(接着输入弧(i,j)和其权值。n例如：n1,2,4n2,1,6n1,3,11n3,1,3n2,3,2n);printf(程序将会显示出每对顶点之间的最短路径值和所经过的路径：n);printf(41-2n61-2-3n52-3-1n22-3n33-1n73-1-2n);while(j!=N&j!=n)CreateGraph(G);/生成邻接矩阵结构的图ShortestPath_Floyd(G,P,D);/利用弗洛依德算法求最短路径Print_ShortestPat

24、h(G,P,D);/显示每对顶点之间的最短路径printf(“继续执行吗?(Y/N);scanf(%c,&j);printf(程序运行结束，按任意键退出窗口门；getch();voidCreateGraph(Graph&G)/构造邻接矩阵结构的图Ginti,j;intstart,end,weight;printf(请输入顶点和弧的数目，格式：顶点数，弧数n);scanf(%d,%d,&G.vexnum,&G.arcnum);/输入图的顶点数和边数for(i=1;i=G.vexnum;i+)for(j=1;j=G.vexnum;j+)G.arcsij=INFINITY;/初始化邻接矩阵print

25、f(请输入各条弧和其权值，格式：弧尾，弧头，权值：n);for(i=1;i=G.arcnum;i+)scanf(%d,%d,%d,&start,&end,&weight);/输入边的起点和终点及权值G.arcsstartend=weight;voidShortestPath_Floyd(GraphG,BOOLPMAX_NUMMAX_NUM,intDMAX_NUM)用弗洛依德算法求有向网G的每对顶点v和w之间的最短路径Pvw/及其带权路径长度Dvw,/若Pvwu为True,表明u是从v到w当前求得最短路径上的顶点intu,v,w,i;for(v=1;v=G.vexnum;v+)/各对顶点之间的初

26、始已知路径及距离for(w=1;w=G.vexnum;w+)Dvw=G.arcsvw;for(u=1;u=G.vexnum;u+)Pvwu=False;if(DvwvINFINITY)从v到w有直接路径Pvwv=True;Pvww=True;for(u=1;u=G.vexnum;u+)for(v=1;v=G.vexnum;v+)for(w=1;w=G.vexnum;w+)if(Dvu+DuwvDvw&v!=w)/从v经u到w的一条路径更短Dvw=Dvu+Duw;for(i=1;i=G.vexnum;i+)if(Pvui|Puwi)Pvwi=True;voidPrint_ShortestPath

27、(GraphG,BOOLPMAX_NUMMAX_NUM,intDMAX_NUM)/显示每对顶点之间的最短路径及距离intv,w,j;printf(”最短路径：n);for(v=1;v=G.vexnum;v+)for(w=1;w=G.vexnum;w+)if(DvwvINFINITY)顶点v和w之间有通路printf(%-5d,Dvw);从v到w的最短距离Print_OnePath(v,w,G.vexnum,P);/显示从v到w的最短路径printf(n);voidPrint_OnePath(intv,intw,intnum,BOOLPMAX_NUMMAX_NUM)/显示从v到w的最短路径int

28、i;for(i=1;inum)printf(%d-%d,v,w);/说明从v到w不需经过其它的顶点elsePrint_OnePath(v,i,num,P);/否则从v到w需经过顶点i，先显示从v到i的最短路径if(ielseprintf(bb);Print_OnePath(i,w,num,P);/显示从i到w的最短路径实验六查找算法的实现一、实验目的掌握查找的不同方法，并能用高级语言实现查找算法；熟练掌握二叉排序树的构造和查找方法。熟练掌握静态查找表及哈希表查找方法。二、实验内容设计一个读入一串整数，然后构造二叉排序树，进行查找。三、实验步骤从空的二叉树开始，每输入一个结点数据，就建立一个新结

29、点插入到当前已生成的二叉排序树中。在二叉排序树中查找某一结点。用其它查找算法进行排序（课后自己做）。四、实现提示1.定义结构typedefstructnodeintkey;intother;structnode*lchild,*rchild;bstnode;voidinorder(t)if(t!=Null)inorder(t-lchild);printf(“4d笃keyt；inorder(trchild);bstnode*insertbst(t,s)bstnode*s,*t;bstnode*f,*p;p=t;while(p!=Null)f=p;if(skey=pkey)returnt;if(s

30、keyvpkey)p=plchild;elsep=prchild;if(t=Null)returns;if(skeyvfkey)flchild=s;elsefrchild=s;returnt;bstnode*creatord()bstnode*t,*s;intkey;t=Null;scanf(“%d”,&key);while(key!=0)s=malloc(sizeof(bitree);skey=key;slchild=Null;srchild=Null;scanf(“%d”,&data);sother=data;t=insertbst(t,s);scanf(“%d”,&key);return

31、t;五、思考与提高1.用其它的查找方法完成该算法。2.比较各种算法的时间及空间复杂度。六、完整参考程序1.折半查找#include#include#defineMAX30/定义有序查找表的最大长度typedefstructcharelemMAX;/有序查找表intlength;/length指示当前有序查找表的长度SSTable;voidinitial(SSTable&);/初始化有序查找表intsearch(SSTable,int);/在有序查找表中查找元素voidprint(SSTable);/显示有序查找表中所有元素voidmain()SSTableST;/ST为一有序查找表intch,

32、loc,flag=1;charj;initial(ST);/初始化有序查找表while(flag)printf(“请选择：n);printf(l.显示所有元素n);printf(2.查找一个元素n);printf(3.退出n);scanf(%c,&j);switch(j)case1:print(ST);break;/显示所有元素case2:printf(请输入要查找的元素：)；scanf(%d,&ch);/输入要查找的元素的关键字loc=search(ST,ch)；/查找if(loc!=0)printf(该元素所在位置是：dn,loc);显示该元素位置elseprintf(%d不存在!n,ch

33、);当前元素不存在break;default:flag=0;printf(程序运行结束!按任意键退出!n);voidinitial(SSTable&v)/初始化有序查找表inti;printf(请输入静态表的元素个数：);输入有序查找表初始化时的长度scanf(%d,&v.length);printf(请从小到大输N%d个元素(整形数)：n,v.length);getchar();for(i=1;i=v.length;i+)scanf(%d,&v.elemi);/从下到大输入有序查找表的各元素intsearch(SSTablev,intch)/在有序查找表中查找ch的位置，成功返回其位置，失败

34、返回0intlow,high,mid;low=1;high=v.length;/置区间初值while(lowch)high=mid-1;/继续在前半区间进行查找elselow=mid+1;/继续在后半区间进行查找return0;找不到时，i为0voidprint(SSTablev)/显示当前有序查找表所有元素inti;for(i=1;i=v.length;i+)printf(%d,v.elemi);printf(n);2.二叉排序树的建立与查找#include#include#include#includeenumBOOLFalse,True;typedefstructBiTNode/定义二叉

35、树节点结构chardata;/为了方便，数据域只有关键字一项structBiTNode*lchild,*rchild;/左右孩子指针域BiTNode,*BiTree;BOOLSearchBST(BiTree,char,BiTree,BiTree&);/在二叉排序树中查找元素/在二叉排序树中插入元素/在二叉排序树中插入元素/在二叉排序树中删除元素/删除二叉排序树的根结点/中序遍历二叉排序树，即从小到大显示BOOLDeleteBST(BiTree&,char);voidDelete(BiTree&);voidInorderBST(BiTree);各元素voidmain()BiTreeT,p;cha

36、rch,keyword,j=y;BOOLtemp;T=NULL;while(j!=n)printf(1.displayn);printf(2.searchn);printf(3.insertn);printf(4.deleten);printf(5.exitn);scanf(%c,&ch);/输入操作选项switch(ch)case1:if(!T)printf(TheBSThasnoelem.n);elseInorderBST(T);printf(n);break;case2:printf(Inputthekeywordofelemtobesearched(achar):);scanf(%c,

37、&keyword);/输入要查找元素的关键字temp=SearchBST(T,keyword,NULL,p);if(!temp)printf(%cisntexisted!n,keyword);/没有找到elseprintf(%chasbeenfound!n,keyword);/成功找到break;case3:printf(Inputthekeywordofelemtobeinserted(achar):);scanf(%c,&keyword);/输入要插入元素的关键字temp=InsertBST(T,keyword);if(!temp)printf(%chasbeenexisted!n,key

38、word);/该元素已经存在elseprintf(Sucesstoinert%c!n,keyword);/成功插入break;case4:printf(Inputthekeywordofelemtobedeleted(achar):);scanf(%c,&keyword);/输入要删除元素的关键字temp=DeleteBST(T,keyword);if(!temp)printf(%cisntexisted!n,keyword);/该元素不存在elseprintf(Sucesstodelete%cn,keyword);/成功删除break;default:j=n;printf(Theprogra

39、misover!nPressanykeytoshutoffthewindow!n);getchar();getchar();voidInorderBST(BiTreeT)/以中序方式遍历二叉排序树T,即从小到大显示二叉排序树的所有元素if(T-lchild)InorderBST(T-lchild);printf(%2c,T-data);if(T-rchild)InorderBST(T-rchild);BOOLSearchBST(BiTreeT,charkey,BiTreef,BiTree&p)/在根指针T所指二叉排序树中递归的查找其关键字等于key的元素，若查找成功则指针p指向该数据元素，并返

40、回True，否则指针指向查找路径上访问的最后一个结点并返回False,指针f指向T的双亲，其初始调用值为NULLBOOLtmp1，tmp2;tmp1=tmp2=False;if(!T)p=f;returnFalse;/查找不成功elseif(key=T-data)p=T;returnTrue;/查找成功elseif(keydata)tmp1=SearchBST(T-lchild,key,T,p);/在左子树中继续查找elsetmp2=SearchBST(T-rchild,key,T,p);/在右子树中继续查找if(tmp1|tmp2)returnTrue;/若在子树中查找成功，向上级返回Tru

41、eelsereturnFalse;/否则返回FalseBOOLInsertBST(BiTree&T,chare)/当二叉排序树T中不存在元素e时，插入e并返回True,否则返回FalseBiTreep,s;if(!SearchBST(T,e,NULL,p)/查找不成功s=(BiTree)malloc(sizeof(BiTNode);s-data=e;s-lchild=s-rchild=NULL;if(!p)T=s;被插结点*s为新的根结点elseif(evp-data)p-lchild=s;被插结点*s为左孩子elsep-rchild=s;被插结点*s为右孩子returnTrue;/成功插入e

42、lsereturnFalse;/树中已存在关键字为e的数据元素BOOLDeleteBST(BiTree&T,charkey)/若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点并返回True,否则返回FalseBOOLtmpl,tmp2;tmp1=tmp2=False;if(!T)returnFalse;不存在关键字等于key的数据元素elseif(key=T-data)Delete(T);returnTrue;找到关键字等于key的数据元素并删除它elseif(keydata)tmpl=DeleteBST(T-lchild,key);/继续在左子树中删除elsetmp2=

43、DeleteBST(T-rchild,key);/继续在右子树中删除if(tmpl|tmp2)returnTrue;/在子树中删除成功，返回TrueelsereturnFalse;/不存在该元素voidDelete(BiTree&p)/在二叉排序树中删除结点P,并重接它的左或右子树BiTrees,q;if(!P-rchild)/右子树空，只需重接它的左子树q=P;P=P-lchild;free(q);elseif(!P-lchild)/左子树空，只需重接它的右子树q=P;P=P-rchild;free(q);else/左右子树均不空q=P;s=P-lchild;while(s-rchild)q

44、=s;s=s-rchild;/转左，然后向右走到尽头P-data=s-data;/s指向被删结点的“前驱”if(q!=p)q-rchild=s-rchild;重接*q的右子树elseq-lchild=s-lchild;重接*q的左子树free(s);实验七排序算法的实现一、实验目的掌握常用的排序方法，并掌握用高级语言实现排序算法的方法；深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用；了解各种方法的排序过程及其时间复杂度的分析方法。二、实验内容统计成绩给出n个学生的考试成绩表，每条信息由姓名和分数组成，试设计一个算法：（1）按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为

45、同一名次；（2）按名次列出每个学生的姓名与分数。三、实验步骤定义结构体。定义结构体数组。定出主程序，对数据进行排序。四、实现提示#definen30typedefstructstudentcharname8;intscore;studentRn;main()intnum,i,j,max,temp;printf(“n请输入学生成绩:n”);for(i=0;in;i+)printf(“姓名:”);scanf(“%s”,&);scanf(“%4d”,&stui.score);num=1;for(i=0;in;i+)max=i;for(j=i+1;jRmax.score)max=j;

46、if(max!=i)temp=Rmax;Rmax=Ri;Ri=temp;if(i0)&(Ri.scoreRi-1.score)num=num+1;printf(“%4d%s%4d”,num,R,Ri.score);五、思考与提高快速排序算法解决本问题。较各种排序算法的优缺点及。使用其它排序算法实现该问题(直接插入排序、希尔排序、简单选择排序、堆排序等)。六、完整参考程序1.直接插入排序#include#include#include#include#defineMAXSIZE20/排序表的最大容量typedefstruct/定义排序表的结构intelemwordMAXSIZE;/数

47、据元素关键字intcount;/表中当前元素的个数SqList;voidInitialSqList(SqList&);/初始化排序表voidInsertSort(SqList&);/直接插入排序voidPrintSqList(SqList);/显示表中的所有元素voidmain()SqListL;/声明表Lcharj=y;printf(本程序将演示直接插入排序的操作。n);while(j!=n&j!=N)InitialSqList(L);InsertSort(L);PrintSqList(L);printf(”继续进行下一次排序吗?(Y/N);scanf(%c,&j);printf(”程序运行

48、结束!n按任意键关闭窗口!n);getchar();getchar();voidInitialSqList(SqList&L)/表初始化inti;printf(”请输入待排序的记录的个数:”)；scanf(%d,&L.count);printf(”请输入待排序的记录的关键字(整型数):n);for(i=1;i=L.count;i+)scanf(%d,&L.elemwordi);voidInsertSort(SqList&L)inti,j;for(i=2;i=L.count;i+)if(L.elemwordivL.elemwordi-l)/,需将L.elemwordi插入有序子表L.elemwo

49、rd0=L.elemwordi;复制为哨兵for(j=i-l;L.elemword0L.elemwordj;-j)L.elemwordj+l=L.elemwordj;/记录后移L.elemwordj+l=L.elemword0;/插入到正确的位置voidPrintSqList(SqListL)/显示表所有元素inti;printf(已排好序的序列如下：n);for(i=l;i=L.count;i+)printf(%4d,L.elemwordi);printf(n);2.希尔排序#include#include#include#include#defineMAXSIZE20/排序表的最大容量ty

50、pedefstruct/typedefstruct/定义排序表的结构intelemwordMAXSIZE;/数据元素关键字intcount;/表中当前元素的个数SqList;voidInitialSqList(SqList&);/初始化排序表voidShellSort(SqList&,int,int);希尔排序voidShellInsert(SqList&,int);/一趟希尔排序voidPrintSqList(SqList);/显示表中的所有元素voidmain()SqListL;声明表Lcharj=y;intdlta3=5,3,1;/希尔排序增量序列，本程序采用5，3，1序列intt=3;

51、/希尔排序增量序列中增量的个数printf(本程序将演示希尔排序的操作。n增量序列为5,3,1on);while(j!=n&j!=N)InitialSqList(L);/待排序列初始化ShellSort(L,dlta,t);/希尔排序PrintSqList(L);/显示希尔排序结果printf(”继续进行下一次排序吗?(Y/N);scanf(%c,&j);printf(”程序运行结束!n按任意键关闭窗口!n);getchar();getchar();voidInitialSqList(SqList&L)/表初始化inti;printf(”请输入待排序的记录的个数:”)；scanf(%d,&L.

52、count);printf(请输入待排序的记录的关键字(整型数):n);for(i=1;i=L.count;i+)scanf(%d,&L.elemwordi);voidShellSort(SqList&L,intdlta,intt)/按增量序列dltaO.t-l对顺序表L作希尔排序for(intk=0;kt;+k)SheHInsert(L,dltak);一趟增量为dltak的插入排序voidShellInsert(SqList&L,intdk)/对顺序表L做一趟希尔插入排序。本算法是和一趟直接插入排序相比作了以下修改：/1.前后记录的增量是dk，而不是1/2.0号单元只是暂存单元，不是哨兵。当j=0时，插入位置已找到inti,j;for(i=dk+1;i=L.