校园导航系统数据结构课程设计

校园导航系统数据结构课程设计第一篇：校园导航系统数据结构课程设计校园导航系统数据结构课程设计1引言本概要设计说明书基于之前建立的软件需求设计基础上，对“蚌埠学院校园导航系统”做出概要分析。主要解决了实现该系统需求的程序模块设计问题。包括如何把该系统划分成若干个模块、决定各个模块之间的接口、模块之间传递的信息，以及数据结构、模块结构的设计等。在以下的概要设计报告中将对在本阶段中对系统所做的所有概要设计进行详细的说明。2程序设计2.1设计时间2015-06-01—2015-06-152.2设计目的1.加深对《数据结构》这门课程的进一步理解与巩固2.通过课程设计，培养自己的编程能力以及团队协作能力3.加强自己对实际问题的分析能力，以及如何更好的将一些经典的算法应用于实际2.3设计任务该导航系统为参观者提供校园主要建筑的基本信息及各建筑间的距离，同时通过该系统计算出所在位置到目的地的最短路径。2.4需求分析1.程序体现的功能：(1)main()——主函数(2)navigate()——导航函数(3)pri()——打印校园平面图函数(4)visit()——递归查找路线函数2.正确输入与输出形式：如：执行建筑查询功能：①输入为：sod输出为：该建筑所在的坐标为78种有花草和一些艺术标记物②输入为：ld输出为：该位置没有找到你找的建筑没有找到执行导航功能：输入为：请输入你所在位置：gym输入你要的目的地：sod输出为：打印并给出所有可能走通的线路，计算出两地间的最短路径（距离）执行显示最短路径功能：输入为：请输入你所在位置：sod输入你要的目的地：office输出为：其中最短路径为：平面图中包含最短线路图，其行走的距离为450米2.5概要设计2.5.1.设计思路和主要步骤按照需求分析，首先我们先要把学校的整体布局给设计出来，即用一个二维数组chararr[17][22]表示学校的整体布局，并将每个建筑物用特殊的符号表示：/*2为墙壁■A办公楼▤c教学区●g草坪▣p操场▓0路b图书馆★M门□m食堂○h为宿舍☆T为体育馆▢l为实验室╳*/，然后要打印出学校的整体布局,设计一个pri（char，int）打印出学校的整体布局。在学校里，最重要的是校园的导航系统，这样可以使人耳目一新的知道某个地方的某个地方的路径，所以设计校园导航函数是必须的，因此我们设计voidnavigate(intx)函数，在图的应用中，一个最重要的知识就是求最短路径，我们并没有用迪杰斯特拉的算法和弗洛伊德算法来实现这个功能，而是利用了迷宫求解问题中的递归意义来实现求最短路径的功能voidvisit(intqiX,intqiY,intzhX,intzhY,intx)用于查找某地点到某地点的所有路径，然后进行比较，将最短路径用函数voidfuzhi(将最短路径存放在一个数组中)。2.5.2程序流程图2.6详细设计按照需求分析中的需求，和概要设计中的各流程图的模块，进行详细设计，完善各流程的代码，详细设计如下：2.6.1学校整体局部chararr[17][22]={/*2为墙壁■A办公楼▤c教学区●g草坪▣p操场▓0路b图书馆★M门□m食堂○h为宿舍☆T为体育馆▢l为实验室╳*///0123456789101112131415161718192021{'2','2','2','2','2','2','2','2','2','2','2','2','2','M','2','2','2','2','2','2','2','2'},{'2','A','A','A','0','c','c','c','c','c','c','c','c','0','2','p','p','p','p','p','p','2'},{'2','A','A','A','0','c','c','c','c','c','c','c','c','0','2','p','p','p','p','p','p','2'},{'2','A','A','A','0','c','c','c','c','c','c','c','c','0','2','p','p','p','p','p','p','2'},{'2','A','A','A','0','0','0','0','0','0','0','0','0','0','2','p','p','p','p','p','p','2'},{'2','A','A','A','0','g','g','g','g','g','g','g','g','0','2','2','2','0','2','2','2','2'},{'M','0','0','0','0','g','g','g','g','g','g','g','g','0','0','0','0','0','0','0','m','2'},{'2','l','l','l','0','0','0','0','0','0','0','0','0','0','h','h','h','h','h','0','m','2'},{'2','l','l','l','0','b','b','b','b','b','b','b','b','0','h','h','h','h','h','0','m','2'},{'2','l','l','l','0','b','b','b','b','b','b','b','b','0','0','0','0','0','0','0','m','2'},{'2','l','l','l','0','b','b','b','b','b','b','b','b','0','h','h','h','h','h','0','0','2'},{'2','0','0','0','0','b','b','b','b','b','b','b','b','0','h','h','h','h','h','0','m','2'},{'2','T','T','T','0','b','b','b','b','b','b','b','b','0','0','0','0','0','0','0','m','2'},{'2','T','T','T','0','b','b','b','b','b','b','b','b','0','h','h','h','h','h','0','m','2'},{'2','T','T','T','0','b','b','b','b','b','b','b','b','0','h','h','h','h','h','0','m','2'},{'2','T','T','T','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','M'},{'2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2'},};4.3.2：校园建筑信息structConstructconstruct[]={{3,4,“office”，“------n|一层为经管系办公室|n|二层为外语系办公室|n|三层为文教系办公室|n|四层为计算机科学与技术系办公室|n|五楼为数理系办公室|n------n”}，//办公室{4,8,“classroom”,“学生上课的主要区域”},//教学楼A{1,13,“northDoor”,“是学生经常出入的门，人流量较大”},//北门{5,17,“playground”,“体育课上课的场所，学生健身的去处。”},//操场{6,1,“westDoor”,“是学校的正门,前方有一个面具很多的停车区”},//西门{7,8,“sod”,“种有花草和一些艺术标记物”},//草坪{9,4,“lab”,“学生动手实践的教室”},//实验室{9,7,“library”,“开放时间为：每天的8:00~21:00n是老师和学生学习的好去处”},//图书馆{9,16,“Whostel”,“女生宿舍楼”},//宿舍楼A{7,19,“SdiningRoom”,“靠近女生宿舍的食堂,饭菜口味比较可口n人流量较大,但只在供餐时间较短”},//食堂A{12,16,“Mhostel”,“男生宿舍楼”},//宿舍楼B{15,16,“Thostel”,“教师公寓楼”},//宿舍楼C{13,19,“TdiningRoom”,“靠近男生宿舍楼,供餐时间较长,随时去随时有饭”},//食堂B{14,4,“gym”,“内部体育设施齐全,在里面可以打篮球、打排球、打羽毛球等等”},//体育馆{15,20,“eastDoor”,“学校正门，老师班车出入。”},//东门{-1,-1,“Nofound”,“你找的建筑没有找到”},};2.6.2打印图voidpri(chara[17][22],intbushu){inti,j;for(i=0;i<17;i++){for(j=0;j<22;j++){switch(a[i][j]){case'2':printf(“■”);break;case'A':printf(“▤”);break;case'c':printf(“●”);break;case'g':printf(“▣”);break;case'p':printf(“▓”);break;case'0':printf(“”);break;case'b':printf(“★”);break;case'M':printf(“□”);break;case'm':printf(“○”);break;case'h':printf(“☆”);break;case'T':printf(“▢”);break;case'l':printf(“╳”);break;case'1':printf(“╬”);break;}}printf(“n”);}if(bushu>0){printf(“其行走的距离为%d米n”,bushu*50);}printf(“备注:n■为墙壁,▤办公楼,●为教学区,▣为草坪,▓为操场,n”);printf(“★为图书馆,□为门,○为食堂,▤为宿舍,▢为体育馆n╳为实验室n”);}2.6.3导航函数voidnavigate(intx){shortbushu=1000;/*用于记录最短步数*/structConstruct*qi;structConstruct*zh;intqiX,qiY,zhX,zhY;intc;inti=1;while(i==1){printf(“请输入你所在位置:”);qi=selectName(15);if((-1)==qi->x){printf(“是否重新输入你所在地:(1/0)n”);scanf(“%d”,&c);if(c==1){i=1;}else{return;}}elsei=0;};i=1;while(i==1){printf(“输入你要的目的地:”);zh=selectName(15);if((-1)==zh->x){printf(“是否重新输入你的目的地:(1/0)n”);scanf(“%d”,&c);if(c==1){i=1;}else{return;}}elsei=0;}qiX=qi->x;qiY=qi->y;zhX=zh->x;zhY=zh->y;num=1;visit(qiX,qiY,zhX,zhY,x);printf(“其中最短路径为:n”);pri(jilu,shortbushu);}2.6.4查找路径voidvisit(intqiX,intqiY,intzhX,intzhY,intx){//x为标志，用于控制要不要显示所有的路径当其非0是显示所有的路径charn=arr[qiX][qiY];arr[qiX][qiY]='1';bushu++;if(qiX==zhX&&qiY==zhY){if(x){printf(“第%d条线路n”,(num++));pri(arr,bushu);}if(shortbushu>bushu){shortbushu=bushu;fuzhi();}}if(arr[qiX][qiY+1]=='0')visit(qiX,qiY+1,zhX,zhY,x);if(arr[qiX+1][qiY]=='0')visit(qiX+1,qiY,zhX,zhY,x);if(arr[qiX][qiY-1]=='0')visit(qiX,qiY-1,zhX,zhY,x);if(arr[qiX-1][qiY]=='0')visit(qiX-1,qiY,zhX,zhY,x);arr[qiX][qiY]=n;bushu--;}2.6.5记录最短路径voidfuzhi(){inti,j;for(i=0;i<17;i++){for(j=0;j<22;j++){jilu[i][j]=arr[i][j];}}}3调试分析4附录程序源代码：#include#include#includecharjilu[17][22];/*用于记录最短路径*/voidfuzhi();/*用于给最短路径赋值*/intshortbushu=1000;/*用于记录最短步数*/intnum=1;/*记录多少条路*/intbushu=0;/*记录走了多远*/structConstructselectName(int*a,intn);/*根据名字查询位置*/voidnavigate(intx);/*导航*/voidpri(char[][22],int);//打印图voidadd();//增加建筑信息voidvisit(int,int,int,int,int);//递归查找路线chararr[17][22]={/*2为墙壁■A办公楼▤c教学区●g草坪▣p操场▓0路b图书馆★M门□m食堂○h为宿舍☆T为体育馆▢l为实验室╳*///071112131415161718192021{'2','2','2','2','2','2','2','2','2','2','2','2','2','M','2','2','2','2','2','2','2','2'},{'2','A','A','A','0','c','c','c','c','c','c','c','c','0','2','p','p','p','p','p','p','2'},{'2','A','A','A','0','c','c','c','c','c','c','c','c','0','2','p','p','p','p','p','p','2'},{'2','A','A','A','0','c','c','c','c','c','c','c','c','0','2','p','p','p','p','p','p','2'},{'2','A','A','A','0','0','0','0','0','0','0','0','0','0','2','p','p','p','p','p','p','2'},{'2','A','A','A','0','g','g','g','g','g','g','g','g','0','2','2','2','0','2','2','2','2'},{'M','0','0','0','0','g','g','g','g','g','g','g','g','0','0','0','0','0','0','0','m','2'},{'2','l','l','l','0','0','0','0','0','0','0','0','0','0','h','h','h','h','h','0','m','2'},{'2','l','l','l','0','b','b','b','b','b','b','b','b','0','h','h','h','h','h','0','m','2'},{'2','l','l','l','0','b','b','b','b','b','b','b','b','0','0','0','0','0','0','0','m','2'},{'2','l','l','l','0','b','b','b','b','b','b','b','b','0','h','h','h','h','h','0','0','2'},{'2','0','0','0','0','b','b','b','b','b','b','b','b','0','h','h','h','h','h','0','m','2'},{'2','T','T','T','0','b','b','b','b','b','b','b','b','0','0','0','0','0','0','0','m','2'},{'2','T','T','T','0','b','b','b','b','b','b','b','b','0','h','h','h','h','h','0','m','2'},{'2','T','T','T','0','b','b','b','b','b','b','b','b','0','h','h','h','h','h','0','m','2'},{'2','T','T','T','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','M'},{'2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2'},};structConstruct{intx;inty;charname[25];charmiaoshu[10000];};structConstructconstruct[]={{3,4,“office”，“------n|一层为经管系办公室|n|二层为外语系办公室|n|三层为文教系办公室|n|四层为计算机科学与技术系办公室|n|五楼为数理系办公室|n------n”}，//办公室{4,8,“classroom”,“学生上课的主要区域”},//教学楼A{1,13,“northDoor”,“是学生经常出入的门，人流量较大”},//北门{5,17,“playground”,“体育课上课的场所，学生健身的去处。”},//操场{6,1,“westDoor”,“是学校的正门,前方有一个面具很多的停车区”},//西门{7,8,“sod”,“种有花草和一些艺术标记物”},//草坪{9,4,“lab”,“学生动手实践的教室”},//实验室{9,7,“library”,“开放时间为：每天的8:00~21:00n是老师和学生学习的好去处”},//图书馆{9,16,“Whostel”,“女生宿舍楼”},//宿舍楼A{7,19,“SdiningRoom”,“靠近女生宿舍的食堂,饭菜口味比较可口n人流量较大,但只在供餐时间较短”},//食堂A{12,16,“Mhostel”,“男生宿舍楼”},//宿舍楼B{15,16,“Thostel”,“教师公寓楼”},//宿舍楼C{13,19,“TdiningRoom”,“靠近男生宿舍楼,供餐时间较长,随时去随时有饭”},//食堂B{14,4,“gym”,“内部体育设施齐全,在里面可以打篮球、打排球、打羽毛球等等”},//体育馆{15,20,“eastDoor”,“学校正门，老师班车出入。”},//东门{-1,-1,“Nofound”,“你找的建筑没有找到”},};voidar(){intm,n;for(m=0;m<17;m++){for(n=0;n<22;n++){printf(“%c”,arr[m][n]);}printf(“n”);}}structConstruct*selectName(intn)/*根据名字查询位置*/{inti;charname[15];scanf(“%s”,&name);for(i=0;iif(strcmp(construct[i].name,name)==0){return&construct[i];}}printf(“给位置没有找到n”);return&construct[15];}intmain(){inti;intn=15;structConstruct*jianzhu;while(1){printf(“欢迎来到蚌埠学院,我们将为你提供贴心的导航服务n”);printf(“*********************************************n”);printf(“1.学校整体布局n”);printf(“2.建筑查询n”);printf(“3.导航n”);printf(“4.显示最短路径n”);printf(“5.退出n”);printf(“*********************************************n”);scanf(“%d”,&i);switch(i){case1:printf(“查询位置n”);pri(arr,0);break;case2:printf(“请输入查询建筑的名称:n”);jianzhu=selectName(n);if(-1!=jianzhu->x)printf(“该建筑所在的坐标为%d%dn”,jianzhu->x,jianzhu->y);printf(“%sn”,jianzhu->miaoshu);break;case3:printf(“导航n”);navigate(1);break;case4:printf(“其中最短路径为:n”);navigate(0);//pri(jilu,shortbushu);break;case5:printf(“退出”);exit(0);break;}};return0;}voidnavigate(intx){shortbushu=1000;/*用于记录最短步数*/structConstruct*qi;structConstruct*zh;intqiX,qiY,zhX,zhY;intc;inti=1;while(i==1){printf(“请输入你所在位置:”);qi=selectName(15);if((-1)==qi->x){printf(“是否重新输入你所在地:(1/0)n”);scanf(“%d”,&c);if(c==1){i=1;}else{return;}}elsei=0;};i=1;while(i==1){printf(“输入你要的目的地:”);zh=selectName(15);if((-1)==zh->x){printf(“是否重新输入你的目的地:(1/0)n”);scanf(“%d”,&c);if(c==1){i=1;}else{return;}}elsei=0;}qiX=qi->x;qiY=qi->y;zhX=zh->x;zhY=zh->y;num=1;visit(qiX,qiY,zhX,zhY,x);printf(“其中最短路径为:n”);pri(jilu,shortbushu);}/*2为墙壁■A办公楼▤c教学区●g草坪▣p操场▓0路b图书馆★M门□m食堂○h为宿舍▤T为体育馆▢*/voidpri(chara[17][22],intbushu){inti,j;for(i=0;i<17;i++){for(j=0;j<22;j++){switch(a[i][j]){case'2':printf(“■”);break;case'A':printf(“▤”);break;case'c':printf(“●”);break;case'g':printf(“▣”);break;case'p':printf(“▓”);break;case'0':printf(“”);break;case'b':printf(“★”);break;case'M':printf(“□”);break;case'm':printf(“○”);break;case'h':printf(“☆”);break;case'T':printf(“▢”);break;case'l':printf(“╳”);break;case'1':printf(“╬”);break;}}printf(“n”);}if(bushu>0){printf(“其行走的距离为%d米n”,bushu*50);}printf(“备注:n■为墙壁,▤办公楼,●为教学区,▣为草坪,▓为操场,n”);printf(“★为图书馆,□为门,○为食堂,▤为宿舍,▢为体育馆n╳为实验室n”);}voidvisit(intqiX,intqiY,intzhX,intzhY,intx){//x为标志，用于控制要不要显示所有的路径当其非0是显示所有的路径charn=arr[qiX][qiY];arr[qiX][qiY]='1';bushu++;if(qiX==zhX&&qiY==zhY){if(x){printf(“第%d条线路n”,(num++));pri(arr,bushu);}if(shortbushu>bushu){shortbushu=bushu;fuzhi();}}if(arr[qiX][qiY+1]=='0')visit(qiX,qiY+1,zhX,zhY,x);if(arr[qiX+1][qiY]=='0')visit(qiX+1,qiY,zhX,zhY,x);if(arr[qiX][qiY-1]=='0')visit(qiX,qiY-1,zhX,zhY,x);if(arr[qiX-1][qiY]=='0')visit(qiX-1,qiY,zhX,zhY,x);arr[qiX][qiY]=n;bushu--;}voidfuzhi(){inti,j;for(i=0;i<17;i++){for(j=0;j<22;j++){jilu[i][j]=arr[i][j];}}}总结此次课程设计相对于我来说，难度较大，相对于这个学期写的那些小算法来说，这个课程设计能充分发挥出学习数据结构后的能力；而相对于之前做的设计性实验，又有了实际的应用，现实应用度增加。从接触C语言编程到现在，我就觉得：编程不是简简单单的写出程序，更多的是处理出现的语法和逻辑错误。在这次课程设计中，我深刻的体会到编程不是一种简单的事，编程不但需要耐心，更需要细心。编出大体的程序架构，花费了我的时间并不多，但我很多时间是用在调试和测试数据上！有些现在看着简单的语法错误，一时竟然无从下手。我想，这和我C语言基础薄弱有很大关系，以后要加强认识。总的来说，这次课程设计，让我学了很多，总结了很多！参考文献[1]严蔚敏，吴伟民.数据结构（C语言版）[M].北京清华大学出版社，2007[2]谭浩强.C程序设计（第三版）[M].北京清华大学出版社，2007[3]谭浩强.C程序设计题解与上机指导（第三版）[M].北京清华大学出版社，2007[4]严蔚敏，吴伟民，米宁.数据结构题集（C语言版）[M].北京清华大学出版社，2007[5]互联网的相关信息和内容第二篇：2012数据结构课程设计数据结构课程设计报告题目：一元多项式计算专业：信息管理与信息系统班级：2012级普本班学号：201201011367姓名：左帅帅指导老师：郝慎学时间：一、课程设计题目分析本课程设计要求利用C语言或C++编写，本程序实现了一元多项式的加法、减法、乘法、除法运算等功能。二、设计思路本程序采用C语言来完成课程设计。1、首先，利用顺序存储结构来构造两个存储多项式A(x)和B(x)的结构。2、然后把输入，加，减，乘，除运算分成五个主要的模块：实现多项式输入模块、实现加法的模块、实现减法的模块、实现乘法的模块、实现除法的模块。3、然后各个模块里面还要分成若干种情况来考虑并通过函数的嵌套调用来实现其功能，尽量减少程序运行时错误的出现。4、最后编写main()主函数以实现对多项式输入输出以及加、减、乘、除，调试程序并将不足的地方加以修改。三、设计算法分析1、相关函数说明：(1)定义数据结构类型为线性表的链式存储结构类型变量typedefstructPolynomial{}(2)其他功能函数插入函数voidInsert(Polynp,Polynh)比较函数intcompare(Polyna,Polynb)建立一元多项式函数PolynCreate(Polynhead,intm)求解并建立多项式a+b，PolynAdd(Polynpa,Polynpb)求解并建立多项式a-b，PolynSubtract(Polynpa,Polynpb)2求解并建立多项式a*b，PolynMultiply(Polynpa,Polynpb)求解并建立多项式a/b，voidDevice(Polynpa,Polynpb)输出函数输出多项式，voidPrint(PolynP)销毁多项式函数释放内存，voidDestroy(Polynp)主函数，voidmain（）2、主程序的流程基函数调用说明(1)typedefstructPolynomial{floatcoef;intexpn;structPolynomial*next;}*Polyn,Polynomial;在这个结构体变量中coef表示每一项前的系数，expn表示每一项的指数，polyn为结点指针类型，属于抽象数据类型通常由用户自行定义，Polynomial表示的是结构体中的数据对象名。(2)当用户输入两个一元多项式的系数和指数后，建立链表，存储这两个多项式，主要说明如下：PolynCreatePolyn(Polynhead,intm)建立一个头指针为head、项数为m的一元多项式p=head=(Polyn)malloc(sizeof(structPolynomial));为输入的多项式申请足够的存储空间p=(Polyn)malloc(sizeof(structPolynomial));建立新结点以接收数据Insert(p,head);调用Insert函数插入结点这就建立一元多项式的关键步骤(3)由于多项式的系数和指数都是随即输入的，所以根据要求需要对多项式按指数进行降幂排序。在这个程序模块中，使用链表，根据对指数大小的比较，对各种情况进行处理，此处由于反复使用指针对各个结点进行定位，找到合适的位置再利用voidInsert(Polynp,Polynh)进行插入操作。(4)加、减、乘、除、的算法实现：在该程序中，最关键的一步是实现四则运算和输出，由于加减算法原则是一样，减法可通过系数为负的加法实现；对于乘除算法的大致流程都是：首先建立多项式a*b，a/b，然后使用链表存储所求出的乘积，商和余数。这就实现了多项式计算模块的主要功能。(5)另一个子函数是输出函数PrintPolyn（）；输出最终的结果，算法是将最后计算合并的链表逐个结点依次输出，便得到整链表，也就是最后的计算式计算结果。由于考虑各个结点的指数情况不同，分别进行了判断处理。四、程序新点通过多次写程序，发现在程序在控制台运行时总是黑色的，本次写程序就想着改变一下，于是经过查资料利用system(“ColorE0”);可以函数解决，这里“E0，”E是控制台背景颜色，0是控制台输出字体颜色。五、设计中遇到的问题及解决办法首先是，由于此次课程设计里使用指针使用比较多，自己在指针多的时候易脑子混乱出错，对于此问题我是采取比较笨的办法在稿纸上写明白后开始进行4代码编写。其次是，在写除法模块时比较复杂，自己通过查资料最后成功写出除法模块功能。最后是，前期分析不足开始急于写代码，中途出现各种问题，算是给自己以后设计时的一个经验吧。六、测试（程序截图）1.数据输入及主菜单2.加法和减法模块3.乘法和除法模块七、总结通过本次应用C语言设计一元多项式基本计算程序，使我更加巩固了C语言程序设计的知识，以前对指针这一点使用是比较模糊，现在通过此次课程设计对指针理解的比较深刻了。而且对于数据结构的相关算法和函数的调用方面知识的加深。本次的课程设计，一方面提高了自己独立思考处理问题的能力；另一方面使自己再设计开发程序方面有了一定的小经验和想法，对自己以后学习其他语言程序设计奠定了一定的基础。八、指导老师评语及成绩附录：（课程设计代码）#include#include#includetypedefstructPolynomial{floatcoef;6intexpn;structPolynomial*next;}*Polyn,Polynomial;//Polyn为结点指针类型voidInsert(Polynp,Polynh){if(p->coef==0)free(p);//系数为0的话释放结点else{Polynq1,q2;q1=h;q2=h->next;while(q2&&p->expnexpn)//查找插入位置{q1=q2;q2=q2->next;}if(q2&&p->expn==q2->expn)//将指数相同相合并{q2->coef+=p->coef;free(p);if(!q2->coef)//系数为0的话释放结点{q1->next=q2->next;free(q2);}}else{p->next=q2;q1->next=p;}//指数为新时将结点插入}7}//建立一个头指针为head、项数为m的一元多项式PolynCreate(Polynhead,intm){inti;Polynp;p=head=(Polyn)malloc(sizeof(structPolynomial));head->next=NULL;for(i=0;i{p=(Polyn)malloc(sizeof(structPolynomial));//建立新结点以接收数据printf(“请输入第%d项的系数与指数:”,i+1);scanf(“%f%d”,&p->coef,&p->expn);Insert(p,head);//调用Insert函数插入结点}returnhead;}//销毁多项式pvoidDestroy(Polynp){Polynq1,q2;q1=p->next;8q2=q1->next;while(q1->next){free(q1);q1=q2;//指针后移q2=q2->next;}}//输出多项式pintPrint(PolynP){Polynq=P->next;intflag=1;//项数计数器if(!q)//若多项式为空，输出0{putchar('0');printf(“n”);return;}while(q){if(q->coef>0&&flag!=1)putchar('+');//系数大于0且不是第一项9if(q->coef!=1&&q->coef!=-1)//系数非1或-1的普通情况{printf(“%g”,q->coef);if(q->expn==1)putchar('X');elseif(q->expn)printf(“X^%d”,q->expn);}else{if(q->coef==1){if(!q->expn)putchar('1');elseif(q->expn==1)putchar('X');elseprintf(“X^%d”,q->expn);}if(q->coef==-1){if(!q->expn)printf(“-1”);elseif(q->expn==1)printf(“-X”);elseprintf(“-X^%d”,q->expn);}}q=q->next;flag++;}printf(“n”);}intcompare(Polyna,Polynb){if(a&&b){if(!b||a->expn>b->expn)return1;elseif(!a||a->expnexpn)return-1;elsereturn0;}elseif(!a&&b)return-1;//a多项式已空，但b多项式非空elsereturn1;//b多项式已空，但a多项式非空}//求解并建立多项式a+b，返回其头指针PolynAdd(Polynpa,Polynpb){Polynqa=pa->next;Polynqb=pb->next;Polynheadc,hc,qc;hc=(Polyn)malloc(sizeof(structPolynomial));//建立头结点11hc->next=NULL;headc=hc;while(qa||qb){qc=(Polyn)malloc(sizeof(structPolynomial));switch(compare(qa,qb)){case1:qc->coef=qa->coef;qc->expn=qa->expn;qa=qa->next;break;case0:qc->coef=qa->coef+qb->coef;qc->expn=qa->expn;qa=qa->next;qb=qb->next;break;case-1:qc->coef=qb->coef;qc->expn=qb->expn;qb=qb->next;break;12}if(qc->coef!=0){qc->next=hc->next;hc->next=qc;hc=qc;}elsefree(qc);//当相加系数为0时，释放该结点}returnheadc;}//求解并建立多项式a-b，返回其头指针PolynSubtract(Polynpa,Polynpb){Polynh=pb;Polynp=pb->next;Polynpd;while(p)//将pb的系数取反{p->coef*=-1;p=p->next;}pd=Add(pa,h);for(p=h->next;p;p=p->next)//恢复pb的系数p->coef*=-1;13returnpd;}//求解并建立多项式a*b，返回其头指针PolynMultiply(Polynpa,Polynpb){Polynhf,pf;Polynqa=pa->next;Polynqb=pb->next;hf=(Polyn)malloc(sizeof(structPolynomial));//建立头结点hf->next=NULL;for(;qa;qa=qa->next){for(qb=pb->next;qb;qb=qb->next){pf=(Polyn)malloc(sizeof(structPolynomial));pf->coef=qa->coef*qb->coef;pf->expn=qa->expn+qb->expn;Insert(pf,hf);//调用Insert函数以合并指数相同的项}}returnhf;}//求解并建立多项式a/b，返回其头指针voidDevice(Polynpa,Polynpb){Polynhf,pf,temp1,temp2;Polynqa=pa->next;Polynqb=pb->next;hf=(Polyn)malloc(sizeof(structPolynomial));//建立头结点,存储商hf->next=NULL;pf=(Polyn)malloc(sizeof(structPolynomial));//建立头结点，存储余数pf->next=NULL;temp1=(Polyn)malloc(sizeof(structPolynomial));temp1->next=NULL;temp2=(Polyn)malloc(sizeof(structPolynomial));temp2->next=NULL;temp1=Add(temp1,pa);while(qa!=NULL&&qa->expn>=qb->expn){temp2->next=(Polyn)malloc(sizeof(structPolynomial));temp2->next->coef=(qa->coef)/(qb->coef);temp2->next->expn=(qa->expn)-(qb->expn);Insert(temp2->next,hf);pa=Subtract(pa,Multiply(pb,temp2));15qa=pa->next;temp2->next=NULL;}pf=Subtract(temp1,Multiply(hf,pb));pb=temp1;printf(“商是:”);Print(hf);printf(“余数是:”);Print(pf);}voidmain(){intchoose=1;intm,n,flag=0;system(“ColorE0”);Polynpa=0,pb=0,pc,pd,pf;//定义各式的头指针，pa与pb在使用前付初值NULLprintf(“请输入A(x)的项数:”);scanf(“%d”,&m);printf(“n”);pa=Create(pa,m);//建立多项式Aprintf(“n”);printf(“请输入B(x)的项数:”);16scanf(“%d”,&n);printf(“n”);pb=Create(pb,n);//建立多项式Bprintf(“n”);printf(“**********************************************n”);printf(“*多项式操作菜单printf(”**********************************************n“);printf(”tt1.输出操作n“);printf(”tt2.加法操作n“);printf(”tt3.减法操作n“);printf(”tt4.乘法操作n“);printf(”tt5.除法操作n“);printf(”tt6.退出操作n“);printf(”**********************************************n“);while(choose){printf(”执行操作:“);scanf(”%d“,&flag);switch(flag){case1:printf(”多项式A(x):“);Print(pa);*n”);printf(“多项式B(x):”);Print(pb);break;case2:pc=Add(pa,pb);printf(“多项式A(x)+B(x):”);Print(pc);Destroy(pc);break;case3:pd=Subtract(pa,pb);printf(“多项式A(x)-B(x):”);Print(pd);Destroy(pd);break;case4:pf=Multiply(pa,pb);printf(“多项式A(x)*B(x):”);Print(pf);Destroy(pf);break;case5:Device(pa,pb);18break;case6:exit(0);break;}}Destroy(pa);Destroy(pb);}第三篇：数据结构课程设计数据结构课程设计1.赫夫曼编码器设计一个利用赫夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。要求：1)将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中)2)初始化：键盘输入字符集大小26、26个字符和26个权值（统计一篇英文文章中26个字母），建立哈夫曼树；3)编码：利用建好的哈夫曼树生成哈夫曼编码；4)输出编码（首先实现屏幕输出，然后实现文件输出）；5)界面优化设计。代码如下：#include#include#include#include#defineN200typedefstructHTNode//结构体{intWeight;charch;intParent,Lchild,Rchild;}HTNode;typedefchar**HCode;voidSave(intn,HTNode*HT)//把权值保存到文件{FILE*fp;inti;if((fp=fopen(“data.txt”,“wb”))==NULL){printf(“cannotopenfilen”);return;}for(i=0;iif(fwrite(&HT[i].Weight,sizeof(structHTNode),1,fp)!=1)printf(“filewriteerrorn”);fclose(fp);system(“cls”);printf(“保存成功！”);}voidCreate_H(intn,intm,HTNode*HT)//建立赫夫曼树，进行编码{intw,k,j;charc;for(k=1;k<=m;k++){if(k<=n){printf(“n请输入权值和字符(用空格隔开):”);scanf(“%d”,&w);scanf(“%c”,&c);HT[k].ch=c;HT[k].Weight=w;}elseHT[k].Weight=0;HT[k].Parent=HT[k].Lchild=HT[k].Rchild=0;}intp1,p2,w1,w2;for(k=n+1;k<=m;k++){p1=0;p2=0;w1=32767;w2=32767;for(j=1;j<=k-1;j++){if(HT[j].Parent==0){if(HT[j].Weight{w2=w1;p2=p1;w1=HT[j].Weight;p1=j;}elseif(HT[j].Weight{w2=HT[j].Weight;p2=j;}}}HT[k].Lchild=p1;HT[k].Rchild=p2;HT[k].Weight=HT[p1].Weight+HT[p2].Weight;HT[p1].Parent=k;HT[p2].Parent=k;}printf(“输入成功！”);}voidCoding_H(intn,HTNode*HT)//对结点进行译码{intk,sp,fp,p;char*cd;HCodeHC;HC=(HCode)malloc((n+1)*sizeof(char*));cd=(char*)malloc(n*sizeof(char));cd[n-1]='';printf(“************************n”);printf(“CharCodingn”);for(k=1;k<=n;k++){sp=n-1;p=k;fp=HT[k].Parent;for(;fp!=0;p=fp,fp=HT[fp].Parent)if(HT[fp].Lchild==p)cd[--sp]='0';elsecd[--sp]='1';HC[k]=(char*)malloc((n-sp)*sizeof(char));strcpy(HC[k],&cd[sp]);printf(“%c%sn”,HT[k].ch,HC[k]);}printf(“************************n”);free(cd);}voidRead(intn,HTNode*HT)//从文件中读出数据{inti;FILE*fp;if((fp=fopen(“data.txt”,“rb”))==NULL){printf(“cannotopenfilen”);exit(0);}for(i=0;ifread(&HT[i].Weight,sizeof(structHTNode),1,fp);//printf(“%dn”,HT[i].Weight);}Coding_H(n,HT);fclose(fp);}voidPrint_H(intm,HTNode*HT)//输出赫夫曼造树过程{intk;printf(“************************n”);printf(“NumWeightParLChRChn”);for(k=1;k<=m;k++){printf(“%d”,k);printf(“%d”,HT[k].Weight);printf(“%d”,HT[k].Parent);printf(“%d”,HT[k].Lchild);printf(“%dn”,HT[k].Rchild);}printf(“************************n”);}voidDecode(intm,HTNode*HT)//对输入的电文进行译码{inti,j=0;chara[10];charendflag='2';i=m;printf(“输入发送的编码，以‘2’结束:”);scanf(“%s”,&a);printf(“译码后的字符：”);while(a[j]!='2'){if(a[j]=='0')i=HT[i].Lchild;elsei=HT[i].Rchild;if(HT[i].Lchild==0)//HT[i]是叶结点{printf(“%c”,HT[i].ch);i=m;//回到根结点}j++;}printf(“n”);if(HT[i].Lchild!=0&&a[j]!='2')printf(“ERROR”);}intmain()//主函数{intn,m,c;HTNodeHT[N];do{system(“color2f”);//运行环境背景颜色.printf(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”);printf(“nttt赫夫曼编译码系统ttt”);printf(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”);printf(“nttt1.输入权值、字母nttt2.把数据写入文件nttt3.输出赫夫曼编码表nttt”);printf(“4.输出赫夫曼译码表nttt5.输入编码并译码.nttt6.从文件中读出数据nttt7.退出”);printf(“nnttt请选择:”);scanf(“%d”,&c);switch(c){case1:system(“cls”);printf(“输入多少结点:”);scanf(“%d”,&n);m=2*n-1;Create_H(n,m,HT);break;case2:system(“cls”);Save(n,HT);break;case3:system(“cls”);Print_H(m,HT);break;case4:system(“cls”);Coding_H(n,HT);break;case5:system(“cls”);Decode(m,HT);break;case6:system(“cls”);Read(n,HT);break;case7:system(“cls”);exit(0);}}while(1);return0;}运行界面如下：2.学生成绩管理（链表实现）要求：实现如下功能：增加、查找、删除、输出、退出。代码如下：#include#include#includetypedefstructscore//定义成绩信息结构体{charNumber[20];charName[20];charChinese[20];charEnglish[20];charMath[20];}score;typedefstructnode_score//定义成绩信息链表结点，包括数据域和指针域{scoredata;structnode_score*next;}node_score,*p_node_score;p_node_scoreheadScore;//定义链表的头指针为全局变量voidPrintScore(scores)//输出信息函数{printf(“%10s”,s.Number);printf(“|%-6s”,s.Name);printf(“|%-3s”,s.Chinese);printf(“|%-3s”,s.English);printf(“|%-3sn”,s.Math);}voidView()//输出函数{p_node_scorepNodeScore;pNodeScore=headScore;printf(“学号|姓名|语文成绩|英语成绩|高数成绩n”);while(pNodeScore!=NULL){PrintScore(pNodeScore->data);//输出学生信息和成绩信息pNodeScore=pNodeScore->next;}}voidAdd(){p_node_scorepNodeScore;//定义一个节点pNodeScore=(p_node_score)malloc(sizeof(node_score));//为节点分配存储空间printf(“请输入学号：”);scanf(“%s”,pNodeScore->data.Number);printf(“请输入姓名：”);scanf(“%s”,pNodeScore->data.Name);printf(“请输入语文成绩：”);scanf(“%s”,pNodeScore->data.Chinese);printf(“请输入英语成绩：”);scanf(“%s”,pNodeScore->data.English);printf(“请输入高数成绩：”);scanf(“%s”,pNodeScore->data.Math);if(headScore==NULL){//如果头结点为空headScore=pNodeScore;pNodeScore->next=NULL;}else{//如果头结点不为空pNodeScore->next=headScore;headScore=pNodeScore;//将头结点新结点}}voidInput(){intn,i;printf(“输入几个学生的数据：”);scanf(“%d”,&n);for(i=0;iAdd();printf(“输入成功！”);}intDelete(){p_node_scorepNodeScore,p1;//p1为pNodeScore的前驱p1=headScore;if(p1==NULL){printf(“成绩表中没有数据！请先添加数据！n”);return0;}charDeleteNumber[20];printf(“请数入要删除的学生学号:”);scanf(“%s”,DeleteNumber);if(strcmp(p1->data.Number,DeleteNumber)==0){//如果要删除的结点在第一个headScore=p1->next;pNodeScore=p1;printf(“学号为%s的学生信息已经删除！n”,DeleteNumber);return0;}else{pNodeScore=p1->next;while(pNodeScore!=NULL){if(strcmp(pNodeScore->data.Number,DeleteNumber)==0){p1->next=pNodeScore->next;printf(“学号为%s的学生信息已经删除！n”,DeleteNumber);return0;}else{//否则，结点向下一个，p1仍为pNodeScore的前驱p1=pNodeScore;pNodeScore=pNodeScore->next;}}}printf(“没有此学号的学生！”);}intChange(){p_node_scorepNodeScore;pNodeScore=headScore;if(pNodeScore==NULL){printf(“成绩表中没有数据！请先添加数据！n”);return0;}charEditNumber[20];printf(“请输入你要修改的学生学号：”);scanf(“%s”,EditNumber);while(pNodeScore!=NULL){if(strcmp(pNodeScore->data.Number,EditNumber)==0){//用strcmp比较两字符串是否相等，相等则返回0printf(“原来的学生成绩信息如下：n”);//输出原来的成绩信息printf(“学号|姓名|语文成绩|英语成绩|高数成绩n”);PrintScore(pNodeScore->data);printf(“语文新成绩:”);scanf(“%s”,pNodeScore->data.Chinese);printf(“英语新成绩:”);scanf(“%s”,pNodeScore->data.English);printf(“高数新成绩:”);scanf(“%s”,pNodeScore->data.Math);printf(“成绩已经修改！”);return0;}pNodeScore=pNodeScore->next;//如果不相等，pNodeScore则指向下一个结点}printf(“没有此学号的学生！n”);//如果找到最后都没有，则输出没有此学号的学生}intFind(){p_node_scorepNodeScore;pNodeScore=headScore;if(pNodeScore==NULL){printf(“成绩表中没有数据！请先添加数据！n”);return0;}charFindNumber[20];printf(“请输入你要查找的学生学号：”);scanf(“%s”,FindNumber);while(pNodeScore!=NULL){if(strcmp(pNodeScore->data.Number,FindNumber)==0){printf(“你要查找的学生成绩信息如下：n”);printf(“学号|姓名|语文成绩|英语成绩|高数成绩n”);PrintScore(pNodeScore->data);return0;}pNodeScore=pNodeScore->next;}printf(“没有此学号的学生！n”);}intmain()//主函数{intchoice=0;headScore=NULL;intc;do{system(“color2f”);//运行环境背景颜色.printf(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”);printf(“nttt学生成绩管理系统ttt”);printf(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”);printf(“nttt1.输入成绩信息nttt2.输出成绩信息nttt3.添加成绩信息nttt”);printf(“4.修改成绩信息nttt5.删除成绩信息nttt6.查询成绩信息nttt7.退出”);printf(“nnttt请选择:”);scanf(“%d”,&c);switch(c){case1:system(“cls”);Input();break;case2:system(“cls”);View();break;case3:system(“cls”);Add();break;case4:system(“cls”);Change();break;case5:system(“cls”);Delete();break;case6:system(“cls”);Find();break;case7:system(“cls”);exit(0);}}while(1);return0;}运行界面如下：第四篇：课程设计(数据结构)课程设计题目1、运动会分数统计任务：参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m=10,w=8,n=15）功能要求：1).可以输入各个项目的前三名或前五名的成绩；2).能统计各学校总分（用链表）；3).可以按学校编号、学校总分、男女团体总分排序输出（快速、基数）；4).可按学校编号查询学校某个项目的情况；可按项目编号查询取得前三或前五名的学校。界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。测试数据：要求使用1、全部合法数据；2、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；2、迷宫求解任务：可以读入一个任意大小的迷宫数据，分别用广度和深度搜索的方法求出一条走出迷宫的路径，并将路径输出（最佳路径）；要求：以较为直观的方式显示结果3、Huffman编码任务：对一篇英文文章，统计各字符出现的次数，实现Huffman编码；要求：输出每个字符出现的次数和编码，其中求最小权值要求用堆实现；4、营业窗口队列模拟任务：实现具有n（n=3）个窗口的现实队列模拟，统计每人的等待时间。要求：1).随机产生顾客的到达时间和服务时间存盘。2).利用存盘数据实现队列的插入和删除。2).当有顾客离开时，根据队列长度调整队尾。3).考虑顾客中途离队的情况。4).考虑顾客具有优先级的情况。5、公交线路提示任务：建立南京主要公交线路图。要求：输入任意两站点，给出最佳的乘车线路和转车地点。6、家谱管理系统任务：实现具有下列功能的家谱管理系统功能要求：1).输入文件以存放最初家谱中各成员的信息，成员的信息中均应包含以下内容：姓名、出生日期、婚否、地址、健在否、死亡日期（若其已死亡），也可附加其它信息、但不是必需的。2).实现数据的存盘和读盘。3).以图形方式显示家谱。4).显示第n代所有人的信息。5).按照姓名查询，输出成员信息（包括其本人、父亲、孩子的信息）。6).按照出生日期查询成员名单。7).输入两人姓名，确定其关系。8).某成员添加孩子。9).删除某成员（若其还有后代，则一并删除）。10).修改某成员信息。11).按出生日期对家谱中所有人排序。12).打开一家谱时，提示当天生日的健在成员。要求：建立至少30个成员的数据，以较为直观的方式显示结果，并提供文稿形式以便检查。界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计，但是要求相关数据要存储在数据文件中。测试数据：要求使用1、全部合法数据；2、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；7、排序算法比较设计要求：利用随机函数产生10个样本，每个样本有50000随机整数，利用直接插入排序、折半插入排序，表插入排序，希尔排序，起泡排序、快速排序、选择排序、堆排序，归并排序，基数排序十种排序方法进行排序（结果为由小到大的顺序），并统计每一种排序所耗费的平均时间（统计为图表坐标形式）。8、算术表达式求值[问题描述]一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。[基本要求]（1）从键盘读入一个合法的算术表达式，输出正确的结果。（2）显示输入序列和栈的变化过程。9、电子