数据结构课程设计

沈阳理工大学课程设计专用纸No.沈阳理工大学沈阳理工大学课程设计专用纸沈阳理工大学目录题目：普里姆算法求最小生成树、排序子系统（2） 1一、课程设计的目的 1二、课程设计的内容和要求 1三、题目一设计过程 2四、题目二设计过程 10五、设计总结 15六、参考文献 15沈阳理工大学课程设计专用纸No.PAGE15沈阳理工大学课程设计专用纸No.PAGE10题目：普里姆算法求最小生成树、排序子系统（2）一、课程设计的目的本学期我们对《数据结构》这门课程进行了学习。这门课程是一门实践性非常强的课程，为了让大家更好地理解与运用所学知识，提高动手能力，我们进行了此次课程设计实习。这次课程设计不但要求学生掌握《数据结构》中的各方面知识，还要求学生具备一定的C语言基础和编程能力。（1）题目一的目的：1.掌握图的存储方法2.掌握普里姆算法求解最小生成树（2）题目二的目的：掌握排序方法的基本思想通过实验加深理解各种排序算法了解各种排序方法的优缺点及适用范围二、课程设计的内容和要求（1）题目一的内容和要求：对教材174页7.16的a图建立它的邻接表。普里姆算法求其最小生成树，依次输出顶点集合和边集合。（2）题目二的内容和要求：1.设计一个选择式菜单。排序子系统*******************************************************1……直接插入排序**2……希尔排序**0……返回*******************************************************请选择菜单号（0…2）：2.编写直接插入排序程序。3.编写希尔排序程序。三、题目一设计过程1、题目分析在本次试验中，定义了多种的struct结构，分别存储加权无向图的结点信息，及相连的结点位置及结点信息加边上的权值。通过邻接矩阵的建立，可以将任意两点的权值存入其中，便于进行各边的权值的比较修改，在ALG（）函数中，无向图的邻接矩阵定义为二维数组的形式，通过函数的转换，转换成邻接表并输出。在普利姆算法中，为实现这个算法需附设一个辅助数组closedge，以记录从U到V-U具有最小代价的边，对每个顶点vi∈V-U,在辅助数组中存在一个相应分量closedge[i-1]，他包括两个域，其中lowcost存储该边上的权值。显然，closedge[i-1].lowcost=Min{cost(u,vi)|u∈U}从算法可以看出每加入一个顶点到U中，closedge数组都会发生相应的变化。程序模块之间的调用：在主函数中调用主界面函数，通过选择菜单选择邻接表的输出或者普利姆算法求最小生成树。然后再分别调用邻接矩阵的初始化函数，邻接矩阵的生成函数，ALG（）函数，PRIM算法的函数，图的构造函数，输出函数。邻接矩阵的生成函数主要解决的是边的信息存储问题，而PRIM算法的函数是解决计算出最小生成树的功能。2、算法描述（1）关于带权网络的存储形式要实现对于任意给定带权网络和顶点，输出邻接表和运用PRIM基本算法思想求解所有的最小生成树的运算。在这里我们首先要明确所选用的数据结构，即选用何种数据结构存储来存储带权网络，这是必选首先解决的问题，所以我们选择了图的邻接矩阵存储方式来存储带权网络，建图时采用邻接矩阵的结构，定义邻接矩阵用到了一维数组和二维数组，分别存储顶点信息和边的权值。由于该算法对图中的边的权值频繁比较，所以采用邻接矩阵比较方便，并在此基础上实现带权网络的建立以及输出显示。（2）关于普利姆算法的基本思想Prim算法求最小生成树的主要思想此算法是普利姆与1957年提出的一种构造最小生成树的算法，主要思想是：假设N=（V，{E}）是连通网，TE是N上最小生成树中边的集合。算法从U={u0}(u0∈V),TE={}开始，重复执行下述操作：在所有u∈U,v∈V-U的边（u,v）∈E中找一条代价最小的边（u0,v0）并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有n-1条边，则T=（V，{E}）为N的最小生成树。对于最小生成树问题最小生成树是指在所有生成树中，边上权值之和最小的生成树，另外最小生成树也可能是多个，他们之间的权值之和相等。3、源代码#include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<string.h>#include<limits.h>#defineMAX_VERTEX_NUM20#defineMAX_NAME3#defineMAX_INFO20#defineINFINITYINT_MAXtypedefintVRType;typedefcharInfoType;typedefcharVertexType[MAX_NAME];typedefintInfotype;#defineMAXV100typedefstruct{ intno; Infotypeinfo;}Vertextype;typedefstruct{ intedges[MAXV][MAXV]; intvexnum,arcnum; Vertextypevexs[MAXV];}Graph;typedefstructANode{ intadjvex; structANode*nextarc; Infotypeinfo;}ArcNode;typedefintVertex;typedefstructVnode{ Vertexdata; ArcNode*firstarc;}VNode;typedefVNodeAdjList[MAXV];typedefstruct{ AdjListadjlist; intn,e;}ALGraph;#defineINF32767typedefstruct{ VRTypeadj; InfoType*info;}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{ VertexTypevexs[MAX_VERTEX_NUM]; AdjMatrixarcs; intvexnum, arcnum; }MGraph;typedefstruct{ VertexTypeadjvex; VRTypelowcost;}minside[MAX_VERTEX_NUM];intLocateVex(MGraphG,VertexTypeu){ inti; for(i=0;i<G.vexnum;++i) if(strcmp(u,G.vexs[i])==0) returni; return-1;}intCreateAN(MGraph*G){ inti,j,k,w,IncInfo; chars[MAX_INFO],*info; VertexTypeva,vb; printf("请输入无向网G的顶点数,边数,边是否含其它信息(是:1,否:0):(空格区分)"); scanf("%d%d%d%*c",&(*G).vexnum,&(*G).arcnum,&IncInfo); printf("请输入%d个顶点的值(<%d个字符):\n",(*G).vexnum,MAX_NAME); for(i=0;i<(*G).vexnum;++i) scanf("%s",(*G).vexs[i]); for(i=0;i<(*G).vexnum;++i) for(j=0;j<(*G).vexnum;++j) { (*G).arcs[i][j].adj=INFINITY; (*G).arcs[i][j].info=NULL; } printf("请输入%d条边的顶点1顶点2权值(以空格作为间隔):\n",(*G).arcnum); for(k=0;k<(*G).arcnum;++k) { scanf("%s%s%d%*c",va,vb,&w); i=LocateVex(*G,va); j=LocateVex(*G,vb); (*G).arcs[i][j].adj=(*G).arcs[j][i].adj=w; if(IncInfo) { printf("请输入该边的相关信息(<%d个字符):",MAX_INFO); gets(s); w=strlen(s); if(w) { info=(char*)malloc((w+1)*sizeof(char)); strcpy(info,s); (*G).arcs[i][j].info=(*G).arcs[j][i].info=info; } } } return1;}intminimum(minsideSZ,MGraphG){ inti=0,j,k,min; while(!SZ[i].lowcost) i++; min=SZ[i].lowcost; k=i; for(j=i+1;j<G.vexnum;j++) if(SZ[j].lowcost>0) if(min>SZ[j].lowcost) { min=SZ[j].lowcost; k=j; } returnk;}voidMiniSpanTree_PRIM(MGraphG,VertexTypeu){ inti,j,k; minsideclosedge; k=LocateVex(G,u); for(j=0;j<G.vexnum;++j) { if(j!=k) { strcpy(closedge[j].adjvex,u); closedge[j].lowcost=G.arcs[k][j].adj; } } closedge[k].lowcost=0; printf("最小代价生成树的各条边为:\n"); for(i=1;i<G.vexnum;++i) { k=minimum(closedge,G); printf("(%s-%s)\n",closedge[k].adjvex,G.vexs[k]); closedge[k].lowcost=0; for(j=0;j<G.vexnum;++j) if(G.arcs[k][j].adj<closedge[j].lowcost) { strcpy(closedge[j].adjvex,G.vexs[k]); closedge[j].lowcost=G.arcs[k][j].adj; } }}intprim(){ MGraphG; CreateAN(&G); MiniSpanTree_PRIM(G,G.vexs[0]); system("pause"); return0;}voidMatToList(Graphg,ALGraph*&G){ inti,j,n=g.vexnum; ArcNode*p; G=(ALGraph*)malloc(sizeof(ALGraph)); for(i=0;i<n;i++) G->adjlist[i].firstarc=NULL; for(i=0;i<n;i++) for(j=n-1;j>=0;j--) if(g.edges[i][j]!=0) { p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j; p->info=g.edges[i][j]; p->nextarc=G->adjlist[i].firstarc; G->adjlist[i].firstarc=p; } G->n=n; G->e=g.arcnum;}voidDispMat(Graphg){ inti,j; for(i=0;i<g.vexnum;i++) { for(j=0;j<g.vexnum;j++) if(g.edges[i][j]==INF) printf("%3s","∞"); else printf("%3d",g.edges[i][j]); printf("\n"); }}voidDispAdj(ALGraph*G){ inti; ArcNode*p; for(i=0;i<G->n;i++) { p=G->adjlist[i].firstarc; if(p!=NULL) printf("%3d:",i); while(p!=NULL) { printf("%3d",p->adjvex); p=p->nextarc; } printf("\n"); }}voidALG(){ inti,j; Graphg; ALGraph*G; intA[MAXV][6]={ {0,6,1,5,0,0},{6,0,5,0,3,0},{1,5,0,5,6,4},{5,0,5,0,0,2},{0,3,6,0,0,6},{0,0,4,2,6,0}}; g.vexnum=6;g.arcnum=10; for(i=0;i<g.vexnum;i++) for(j=0;j<g.vexnum;j++) g.edges[i][j]=A[i][j]; printf("邻接矩阵G:\n"); printf("\n"); DispMat(g); G=(ALGraph*)malloc(sizeof(ALGraph)); printf("图G的邻接图矩阵转换成邻接表:\n"); MatToList(g,G); DispAdj(G); printf("\n");}voidshow(){ printf("\n"); printf("\t****************主菜单****************\n\n\n\n"); printf("\t*☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆*\n\n\n"); printf("\t^^^^^^^^^^^^^[1]建立174页图的邻接表^^^^^^^^^^^^^\n\n"); printf("\t^^^^^^^^^^^^^[2]普里姆算法求最小生成树^^^^^^^^^^^^^\n\n"); printf("\t^^^^^^^^^^^^^[0]退出^^^^^^^^^^^^^\n\n\n"); printf("\t*★★★★★★★★★★★★★★★★★★★★★★★*\n");}voidback(){ printf("\t===>按Enter键返回主菜单\n");}voidmain(){ intchoose=0; while(true) { show(); printf("\t\t====>请选择："); scanf("%d",&choose); system("cls"); switch(choose) { case1:ALG(); back(); break; case2:prim(); back(); break; case0:exit(0); break; default: break; } fflush(stdin); getchar(); system("cls"); }}4、运行结果输入无向网G的顶点数,边数，顶点1顶点2权值可以得到图的最小生成树的边和节点，如下图所示。四、题目二设计过程1、题目分析在本次试验中，采用了一维数组存放待排序的数组元素，输入完数据之后即可进入主界面选择菜单选择排序的方法，通过调用子函数实现排序功能，其中insert_sort（）为直接排序的功能函数，shell_sort（）为希尔排序的功能函数。直接插入排序是由两层嵌套循环组成的，外层循环标识并决定待比较的数，内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。希尔算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。2、算法描述(1).直接插入排序：每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。第一趟比较前两个数,然后把第二个数按大小插入到有序表中;第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。(2).希尔排序基本思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。3、源代码#include<stdio.h>#include<stdlib.h>voidinsert_sort(int*x,intn){ inti,j,t; printf("直接插入排序:\n在排序前，数组为："); for(i=0;i<n;i++) { printf("%d",x[i]); } for(i=1;i<n;i++) { t=*(x+i); for(j=i-1;j>=0&&t<*(x+j);j--) { *(x+j+1)=*(x+j); } *(x+j+1)=t; } printf("\n在排序后，数组变为："); for(i=0;i<n;i++) { printf("%d",x[i]); } printf("\n\n");}voidshell_sort(int*x,intn){ inth,j,k,t,i; printf("希尔排序\n在排序前，数组为："); for(i=0;i<n;i++) { printf("%d",x[i]); } for(h=n/2;h>0;h=h/2) { for(j=h;j<n;j++) { t=*(x+j); for(k=j-h;(k>=0&&t<*(x+k));k-=h) { *(x+k+h)=*(x+k); } *(x+k+h)=t; } } printf("\n在排序后，数组变为："); for(i=0;i<n;i++) { printf("%d",x[i]); } printf("\n\n");}voidshow(){ printf("\n"); printf("\t排序子系统\n\n"); printf("\t***********************************************\n\n"); printf("\t*[1]……直接插入排序*\n\n"); printf("\t*[2]……希尔排序*\n\n"); printf("\t*[0]……返回*\n\n"); printf("\t***********************************************\n\n");}voidback(){ printf("\t===>按Enter键返回主菜单\n");}voidmain(){ inti,n,p=0,arr[100],x[100]; printf("请输入数组的大小:\n"); scanf("%d",&n); printf("请输入%d个数组元素：\n",n); for(i=0;i<n;i++) { scanf("%d",&arr[i]); } system("cls"); while(p!=i) { x[p]=arr[p]; p++; } intchoose=0; while(true) { show(); printf("\t\t请选择菜单号（0…2）："); scanf("%d",&choose); system("cls"); switch(choose) { case1:insert_sort(x,n); back(); break; case2:shell_sort(arr,n); back(); break; case0:main(); break; default: break; } fflush(stdin); getchar(); system("cls"); } }4、运行结果五、设计总结数据结构程序设计就此结束了，两周的课程设计收获很多。课程设计是对本门学科综合知识的应用，如果一个知识点没有掌握好就会导致程序整体的质量。所以在开始编写程序前，先分析题目中涉及的知识点，并一一列出来。然后返回课本以及通过图书馆或者网络查找资料，把所需的知识点一一弄明白。这样用起来就会得心应手，不会因为一个知识点的不熟悉而终止程序的编写。把相同的工作统一起来会节省很多时间，提高学习的效率。在程序设计中遇到很多问题，编程出了问题反映了自己在学习过程中存在的问题，对以后的学习有很大的帮助。比如：在对程序的调试过程中多次出现了错误，无法运行，后来发现原因并改正，运行成功后却发现选择菜单无法使用，原因在于scanf（）输入后没有清空输入缓冲区，通过上网查阅资料，加入了fflush（stdin）；语句，完美解决问题；运行成功后结果却不正确，通过排查发现输出的是指针的地址而不是数据，更正后解决问题。基础知识的不扎实在课程实际中完全体现了出来，比如对一些