数据结构课程设计指导书

数据结构课程设计

指导书2014.9一、实验目的通过训练，实现以下三方面目标：使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。使学生初步掌握查阅参考资料的方法，提高学生进行程序设计等综合的应用能力。二、涉及的基本理论数据结构中关于“线性表、栈和队列、树和二叉树、图、查找和排序”等基本理论。三、基本要求巩固和加深对数据结构基本知识的理解，提高综合运用课程知识的能力。培养学生自学参考书籍，查阅手册、图表和文献资料的能力。通过训练，使学生初步掌握简单软件的分析方法和设计方法。了解与课程有关的工程技术规范，能正确解释和分析实验结果。题目具有足够的工作量。课程中各任务的设计和调试要求独立完成，遇到问题可以讨论，但不可以拷贝。做好上机准备：每次上机前，要事先编制好准备调试的程序，认真想好调试步骤和有关环境的设置方法，准备好有关的文件。趣味题除外，按照课程设计的具体要求建立的功能模块，每个模块要求按照如下几个内容认真完成；其中包括：a）需求分析：在该部分中叙述，每个模块的功能要求b）概要设计在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义。c）详细设计各个算法实现的源程序，对每个题目要有相应的源程序（可■以是一组源程序，每个功能模块采用不同的函数实现）源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。d）调试分析测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。课程设计总结：（保存在word文档中）总结可以包括：课程设计过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对《数据结构》课程的认识等内容；每组实现的结果必须进行检查和演示；程序源代码和程序的说明文件必须上交，作为考核内容的一部分；（上交时每人交一份，文件夹的取名规则为：“学号姓名”，如“200413498高魁”。该文件夹下至少包括：“源代码”、“课程设计报告”、“可执行文件”。由学习委员收集刻盘按规定时间统一上交)。课程设计报告可以附原代码，也可以只对对重点函数及结构进行说明。报告格式参照数据结构习题集或下面设计报告样例。报告提交(要求见大纲)。四、训练内容：(每人完成3类题目中的各一道题即可)•-详见大纲三类题目：第一类：趣味问题(如汉诺塔、约瑟夫环、八皇后问题、串的模式匹配等问题)；第二类如下：内部排序演示【问题描述】设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数。【基本要求】⑴对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较；(可■以选3种)待排序的元素的关键字为整数。其中的数据要用伪随机产生程序产生(如10000个)，至少用5组不同的输入数据做比较，再使用各种算法对其进行排序，记录其排序时间，再汇总比较。演示程序以人机对话的形式进行。界面友好，易与操作。采用菜单方式进行选择。校园导游咨询【问题描述】设计一个校园导游程序，为来访的客人提供各种信息查询服务。【基本要求】设计本校的校园平面图，所含景点不少于6个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。为来访客人提供图中任意景点相关信息的查询。为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。可以拓展。建通讯录【问题描述】设计散列表实现通讯录查找系统。【基本要求】设每个记录有下列数据项：电话号码、用户名、地址；从键盘输入各记录，分别以电话号码为关键字建立散列表；采用线性探测再散列法解决冲突；查找并显示给定电话号码的记录；通讯录信息文件保存；要求人机界面友好，使用菜单方式进行选择。【实现提示】主函数：根据选单的选项调用各函数，并完成相应的功能。Menu()的功能：显示英文提示选单。Quit。的功能：退出选单。CreateQ的功能：创建新的通讯录。Append。的功能：在通讯录的末尾写入新的信息，并返回选单。Find（）：查询某人的信息，如果找到了，则显示该人的信息，如果没有则提示通讯录中没有此人的信息，并返回选单。Alter。的功能：修改某人的信息，如果未找到要修改的人，则提示通讯录中没有此人的信息，并返回选单。DeleteQ的功能：删除某人的信息，如果未找到要删除的人，则提示通讯录中没有此人的信息，并返回选单。List。的功能：显示通讯录中的所有记录。Save（）的功能：保存通讯录中的所有记录到指定文件中。Load（）的功能：从指定文件中读取通讯录中的记录。哈夫曼编码/译码器【问题描述】设计一个哈夫曼编码/译码系统，对一个文本文件中的字符进行哈夫曼编码，生成编码文件（压缩文件，后缀名.cod）；反过来，可将一个压缩文件译码还原为一个文本文件（.txt）。【基本要求】（1）输入一个待压缩的文本文件名，统计文本文件中各字符的个数作为权值，生成哈夫曼树；（2）将文本文件利用哈夫曼树进行编码，生成压缩文件（后缀名cod）,（3）输入一个待解压的压缩文件名称,并利用相应的哈夫曼树将编码序列译码；（4）显示指定的压缩文件和文本文件；（5）界面友好，易与操作。采用菜单方式进行选择。计算器【问题描述】利用栈设计一个简单的计算器，可以做加、减、乘、除等基本运算。第三类题目如下：学生成绩管理系统【基本要求】（1）按学期、按班级完成对学生成绩的录入、修改；（2）按班级统计学生的成绩；（3）求学生的总分及平均分；（4）根据学生的平均成绩进行排序，能查询学生成绩，不及格科目及学生名单：（5）按班级输出学生的成绩单。影碟出租管理系统【基本要求】（1）影碟信息包括如下内容：影碟编号、电影名称和在架情况（出租或在架）。（2）增加、删除、修改影碟条目的功能。（3）程序启动时从文件中读取所有影碟条目，程序退出时保存所有条目。餐饮管理系统的菜谱管理子系统【基本要求】功能（1）实现菜谱（文字）的录入（菜谱有分类）能够进行菜谱的浏览能够进行菜谱排序(按照价格)查询菜谱功能按类别输出菜谱人事档案管理系统【基本要求】实现员工信息的录入、修改；统计各科室的员工的人数；能按员工的姓名、所在科室查询员工的档案信息。五、设计报告样例题目一：约瑟夫问题自述题目：这是17世纪的法国数学家加斯帕在《数目的游戏问题》中讲的一个故事：15个教徒和15个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。程序说明与注释：#iiiclude<stdio.h>structnode{intnextp;/*指向下一个人的指针*7mtno_out;/*标记是否被扔下海。*/)lnik[31];/*建立一个顺序表*/intmaui()(intpnntf("Theongmalciicleis(+:pag}oiiK@:cluistian):\ii");fbr(i=l;i<=30;i-H-)filuik[i].nextp=i+l;luik[i].no_out=l;/*标志置为1,表示人都在船上*/}luik[30].nextp=1;/*第30个人的指针指向第一个人以构成环*/J=30;fbr(i=0;i<15;i++)fifor(k=0;;)/*k:决定哪个人被扔下海的计数器*/if(k<15)fij=luik[j].iiextp;k^=luik[j].no_out;}elsebreak;/*计数到15则停止计数*/liiik[j].no_out=0;}fbr(i=l;i<=30;i-H-)pnntf(H%cHJink[i].no_out?);/*+:被扔下海的非教徒，@留在船上活命的教徒*/printf(n\nM);}运行结果Theoriginalcirele+：pagendom,0：christian〉:问题引申：有N个小孩围成一圈并依次编号，教师指定从第S个小孩开始报数，报到第D个小孩即令其出列。然后从卜.一个孩子继续报数，数到第D个小孩又令其出列，如此直到所有的孩子都出列。求小孩出列的先后顺序。程序说明与注释：iiiclude<stdio.h>iiiclude<malloc.h>typedefstmetNode(intdata;smictNode*next;JLNode/LnikList;voidmam(void){ints,n.d,i,count;LuikListp,q;priiitf(^pleaseinputn:H);scaiif(M%d”,&n);priiitf(^pleaseinputn:H);scaiif(M%d",&s);priiitf(^pleaseinputn:H);scaiif(M%d”,&d);if((n<l)||(s<l)||(s>n)||(d<l)){printf(n'jilnputparaenor!\nH);return;}/*建立一个无头结点的循环单链表*/p=malloc(sizeof(LNode));p->data=l;p->next=p;fbr(i=n;i>l;i—){q=malloc(sizeoRLNode));q->data=i;q->next=p->next;p->next=q;}/*查找报数的起始结点*/{q=p;p=p->next;/*p指向其实报数的结点，q指向p的上一个结点*//*开始报数*/printf(n\iiTheturnofoutcircleis:\n”)；while(p->data!=NULL){count=l;/*设置计数器初值为1*/wlule(count!=d)(count++;q=p;p=p・>next;if(p->data==NULL)(q=P；p=q->next;}}printf(n%dH,p->data);if(p!=q){q->next=p->next;free(p);p=q->next;}elsefree(p);p=NULL;}}}运行结果如下：theturnoutofthecireleis：546231题目二校园导游咨询.问题描述以我校为例，设计一个校园导游程序，主要为来访的客人提供信息查询。需求分析提供至少5个景点的校园导游咨询（包括景点介绍、景点间距离等）。本程序的目的是为来客提供路径咨询和景点查询（根据用户指定的始点和终点输出相应最短简单路径或者输出用户指定景点的详细信息）：系统管理员又可根据实际情况对导游图进行修改，删除路径或景点。选取九个大家熟悉的景点，抽象成一张带权无向图（如图所示）。以图中顶点表示景点，存放景点名称、代号等信息：以边表示路径，边上的权值表示两地的距离，为此图选择适当的数据结构:本演示程序采用c语言编写，完成了无向图的建立和其他操作：输入的形式和输入值的范闱：主函数中调用图表建立函数之后，通过输入1到6不同的阿拉伯数字进行功能选择：在查找景点详细信息操作时需要输入景点的的序号；在求路径函数中，也是输入对应景点序号值：在删除路线函数里，输入构成边的两个景点的序号对;。在所有输入操作中，输入的值都是整数输出的形式：菜单函数，输出功能菜单目录；查找函数信息操作，输出景点序号，名称，还有详细介绍；求最短路径函数，输出路线经过的顶点和路线的长度！删除函数，当删除成功后会输出删除成功；求删除操作后显示删除的元素的值。程序所能达到的功能：完成无向带权图的生成（通过建立顶点数组和领结矩阵）、通过选择菜单进行不同操作，查看景点信息、求景点间最短路径、删除景点或路线。测试数据：查看景点详细信息操作中输入3查询最短路径操作中输入3,5删除操作中先后输入1（删除景点），2）（删除边）删除景点操作中输入1删除边操作中输入1,5查看一个景点到其他景点所有路线输入1概要设计1）为了实现上述程序功能，需要定义一个抽象的无向图数据类型：数据对象：6={1,2,3,4,5,6.7,8,9}/*1,2,3,4,5,6,7,8,9是景点的对应序号写数据关系:R={<1,3,100><1,4,200><1,5,100><2,5,200><2,3,50><3,7,600><3,8,500><4,9,200><6,7,100><6,8,100><6,9,600><7,8,100><8,9,600>}基本操作：初始条件：图的邻接矩阵和顶点表己经存在；（l）Createmgragh（）操作结果：建立了一个无向带权图，由邻接矩阵和顶点表组成⑵Display.allQ初始条件：图的邻接矩阵和顶点表己经存在；操作结果：将校园所有景点名称和对应序号输出。⑶Display.oneQ初始条件：图的邻接矩阵和顶点表己经存在；操作结果：将指定的某个景点名称和其详细信息输出。

Delete()初始条件：图的邻接矩阵和顶点表己经存在操作结果：删除无向图中的一些点或边，deletePQ初始条件：图的邻接矩阵和顶点表己经存在操作结果：删除点deleteLQ初始条件：图的邻接矩阵和顶点表己经存在操作结果：删除边Ashortestpath()初始条件：图的邻接矩阵和顶点表己经存在操作结果：显示从该节点出发的所有路线和相应距离LShoilestPath()初始条件：图的邻接矩阵和顶点表己经存在操作结果：显示两点间最短路径和最短距离⑼MenuQ操作结果：在屏幕上显示操作菜单.)本程序包含7个函数：主函数niam()初始化图函数CieatemgiaghO显示操作菜单函数Menu。显示单个景点内容函数Display_one()显示所有景点内容函数Display_all()删除景点或路线函数Delete()删除景点元素函数deletePO删除路线函数deleteL()查看一个景点所有路线函数AshortestpathQ查询两点间最短距离函数LshonestPatliO3)各函数间关系如下：typedefmtedgetype;mainDisplay.allCreatemgraghdeleteLAshortestpaMenudeleteP4.详细设计1)mainDisplay.allCreatemgraghdeleteLAshortestpaMenudeleteP4.详细设计1)结点类型和指针类型typedefstmct{charnaine[30];intnum;Jveitextype;typedefstmct{veitextypevexs[10];/*顶点表*/edgetypeedges[10][10];/*边表*/mtn.e;/*顶点数和边数*/Jmgragh;mgraghg；2）对无向图的操作：（DCieatemgraghQ函数算法程序（mtij;G->n=9;G->e=13;for（i=l;i<=G->n;i++）G->vexs[i].num=i;strcpy（G->vexs[l].name,,r大学校门"）;strcpy（G->vexs⑵.name,”商业街”）；strcpy（G->vexs[3].name,H男生宿舍”）；strcpy（G->vexs[4].name/校医务室”）；strcpy（G->vexs[5].name,H北苑食堂&超市”）;strcpy（G->vexs[6].name/体育馆”）；sticpy（G->vexs[7].name,,r东方学院"）;strcpy（G->vexs[8].name,H主教楼"）；strcpy（G->vexs[9].name,H42栋女生宿舍”）；for（i=l;i<=G->n;i++）fbr（j=l;jv=G->nJ++）G->edges[i][j]=Far;G->edges[l][3]=100;G->edges[l][4]=200;G->edges[1][5]=100;G->edges[2][5]=200;G->edges[2][3]=50;G->edges[3][7]=600;G->edges[3][8]=500;G->edges[4][9]=200;G->edges[6][7]=100;G->edges[6][8]=100;G->edges[6][9]=600;G->edges[7][8]=100;G->edges[8][9]=600;for（i=l;i<=G->n;i++）fbr（j=l;j<=G->n;j++）G->edges[j][i]=G->edges[i][j];Display_allQ函数算法程序(mti;pnntf(”对应序号和名称\n”)；for(i=1;i<=G->n;i-H-)priiitf("%d%s",G->vexs[i].num.G->vexs[i].name);}Display_one。函数算法程序(mti,b=l;while(b)fipnntf("请选择对应序号(1—9):”)；scanf(”％d”,&i);switch(i)ficasel:prmtfC'<l>.学校大门\n学校刚健不久的新大门，非常雄伟，进出学生络绎不绝，出门不远就是38路公交站\n");break;case2:prmtfC'<2>.商业街\n学校最热闹的地方，地处人多的男女生宿舍区，提供各种服务\ii");break;case3:prmtf("<3>,北苑男生宿舍\n学校最大的宿舍区，对面是1号女生宿舍区\nH);break;case4:pnntf(”v4>.校医务室也学校的卫生室，只能解决同学健康方面的小问题，且药价比学校外面高\n”);break;case5:pnntf(”〈5>.北苑食堂和超市山分八角餐厅和主餐厅，主餐厅有两层下层为普通食堂，上层为供应多种类型的食品\nH);break;case6:prmtfC'<6>.体育馆\n学生上体育课及运动的场地，设有田径场、足球场、篮球场，台球室,乒乓馆等。\nH);break;case7:prmtf("<7>.东方学院\n学校的本三学院，具有独立的管理体系\ii");break;case8:pimtf("<8>.主教楼\n学校的主教学楼之一，10层学校的主教学楼之一，是中德学院与外语学院的教学楼\n-);break;case9:pnntf(”<9>.42栋女生宿舍\n学校新建的女生宿舍，环境不错，靠近财经学院\iT);break;}pnntf(”是否继续？继续1,结束0”)；scanf("%d",&b);}}⑷Delete。函数算法程序(inti,b=l;while(b)fIpnntf(”请选择(删除景点按1,删除路线按2)：-);scanf(”％d”,&i);switch(i)case1:deleteP(&g);break;case2:deleteL(&g);break;}prmtf(”是否继续删除任务(是1否0):”)；scanf(”％d”,&b);}}deletePQ函数算法程序(mta,i;mtb=l,j,k;while(b)pnntff输入要删除的结点:”)；scanff%d”,&a);fbr(j=aj<=G->n-lJ++)(strcpy(G->vexs[j].name,G->vexs[j+1].name);fbr(k=l;k<=G->n-l;k++)G->edges[k]|j]=G->edges[k]|j+l]；}fbr(j=aj<=G->n-lJ++)fbr(k=l;k<=G->n-l;k++)G->edges[j][k]=G->edges[j+l][k];G->n-;G->e=0;fbr(i=l;i<=G->n;i++)fbr(j=l;j<=G->nJ++)if(G->edges[i][j]!=Far)G->e++;G->e=G->e/2;b=0;pnntf(”删除成功!\n”)；if(b!=0)pnntf(”输入错误!\n");b=0;}deleteL()函数算S'去程序(mtb=l,ij,a,d;for(i=l;i<=G->n;i++)fbr(j=l;j<=G->n;j++)if(G->edges[i][j]!=Far)printf(H%d-%d%s<—>%s*nH,iJ,G->vexs[i].name,G->vexs[j].name);wlule(b)pnntf(”输入要删除的边(eg：1,4):”);scanf(”％d,%d”,&a,&d);i=a；J=d;if(G->edges[i]U]!=Far)G->edges[i][j]=Far;G->edges[j][i]=Far;b=0;pnntf(”删除成功!\1T);G->e~;}if(b』O)pnntf(”输入错误!")；printf(”结束按0,继续按1scanf(”％d”.&b);}}Ashortestpath()函数算法程序{iiitv,wj,niaxj=0,x.flag=1,v0;mtfiiial[20],D[20],p[20][20];while(flag)pnntf(”请输入一个起始景点编号:”)；scanf(”％d”.&v0);if(v0vo||vO>G->n)prmtf(”景点编号不存在!请重新输入景点编号scanf(”％d”.&vO);}if(vO>=1&&vO<=G・>n)flag=O;}fbr(v=l;v〈=G・>n;v++)fiiial[v]=O;D[v]=G->edges[vO][v];fbr(w=l;w<=G->n;w++)p[v][w]=0;if(D[v]<Fai)p[v][vO]=l;p[v][v]=l;}D[vO]=O;final[vO]=l;for(i=l;i<G->n;i++)max=Fai;fbr(w=l;w<G->n;w++)if(!final[w])if(D[w]<max)(v=w;max=D[w];)fiiial[v]=l;fbr(w=l;wv=G・>n;w++)if(!final[w]&&(max+G->edges[v][w]<D[w]))D[w]=max+G->edges[v][w];fbr(x=1;x<=G-p[w][x]=p[v][x];p[w][w]=l;}}fbr(v=l;vv=G・>n;v++)if(vO!=v)print町％s”,G・>vexs[vO].name);fbr(w=l;wv=G・>n;w++)if(p[v][w]&&w»=vO)pnntf(M-->%s\G->vexs[w].name);t++;if(t>G->n-1&&vO!=vpnntf(”总路线长%dmW\D[v]);}}⑻LShoitestPathQ函数算法程序(mtij,b=l;wlule(b)printfC请输入起点和终点(如:1,4):”)；scanf(”％d,%d”,&i,&j);if(i>G->n||i<=0|[j>G->n||j<=0)(priiitf(^inputeioir?\ii\iiM);printf(”请输入起点和终点(如：1,4):”)；scanf(”％d,%d”,&i.&j);floyedQ;display_route(ij);pnntf(”是否继续？继续1,结束0”)；scanff%d”.&b);}⑼main。函数算法程序{mtchoice;createmgragh(&g);pnntf(”欢迎来到江苏技木师范学院地图网wlule(l){menu();scan«'%cT,&choice);getcharQ;switch(choice){case1:Display_all(&g);break;case2:Display_oneQ;break;case3:LShoitestPath(&g);break;case4:DeleteQ;break;case5:Ashortestpath(&g);case6:exit(0);}(10)floyed()函数算法程序{mtij,k;fbr(i=l;i<=g.n;i-H-)fbr(j=lj<=g.n;j++)(shoitest[i]|j]=g.edges[i]|j];path[i]|j]=O;}fbr(k=1;k<=g.n;k-H-)fbr(i=l;i<=g.n;i++)fbr(j=l;j<=g.nJ-H-)if(shortest[i][j]>(shortest[i][k]+shortest[k][j])){shortest"][j]=shortest[i][k]+shortest[k][j];path[i][j]=k;path[j][i]=k;}}0Ddisplay_routeO函数算法程序(inta,b;a=i；b=J；pnntf(”最短路径是：”)；if(slioilest[i][j]!=Far)(while(path[i][j]!=0)printfC'v-%d”,path[i][j]);j=path[i][j];elsei=path|j][i]；}pnntf(y%d”,a);pnntf(”\iT);prmtf(H%d<->%d最短距离是:%din\n\n,\a,b,shortest[a][b]);elsefprintf(”％d”,a);while(path[i][j]!=0)fpiintf(H->%dH,path[i][j])；j=path[i][j];elsei=path[j][i];}prmtf("->%dM,b);priiitf("(%d->%d)最短距离是:%dm\n\u",a,b,shoitest[a][b]);}}elsepriiitf("inputerror!notexist\nM);prmtf(M\ii");}调试分析在调试过程中，我主要遇到以下一些问题：1、在调运函数中，对把图指针的做为函数形参的定义和实参调用的用法不熟练，出现错误，通过看书复习指针后改正并掌握！2、对指向运算符“4”和用法区别不知道，通过调试时显示错误明白了并改正！3、对C语言库函数不十分了解，程序需要加的一些重要头文件，如#iiiclude<conio.h>,#mclude<process.h>,我并不知道要加，在函数最后调试时出现连接问题！4、程序调试结果正确后，经过多次调试修改使界面更加清楚，运行简单！使用说明程序名为校园导游图.cpp,运行环境为visualC++6.0集成开发环境。程序执行后显示：功能菜单1-->查看校所有景点2->S看景点详细信息3->2询最短路径4->删除景点或路线5-->查看一个景点所有路线6->退出

请选择（1-6）:在“请选择（1-6）:”后输入数字选择执行不同的功能。每执行一次功能，就会显示执行的结果。选择1：查看校所有景点信息选择2：查看某个景点的详细信息，要求输入某个景点的相应序号（l-9）o选择3：查询两景点间最短路径，要求输入两个景点的序号，如：1,4o选择4：删除景点或路线，输入1删除景点，输入2,删除边。选择5：查看一个景点到其他各景点的路线，输入一个景点序号后，显示到达其它所有景点的路线。选择6：退出程序7.测试结果查询学校景点和景点详细信息欢迎来到江苏技术师范学院地图网功能菜单1一＞查看督所壹景点2一〉查看景点详细信息功能菜单1一＞查看督所壹景点2一〉查看景点详细信息4—＞删除景点箴路线5—＞查看一个景点所有路线尹号和名称大