[工学]数据结构课程设计实验报告.doc

数据结构课程设计实验报告目录1. 单位员工通讯录管理系统（线性表的应用）* 2. 停车场管理（栈和队列的应用）*3. 哈夫曼编码/译码系统（树应用）*4. 教学计划编制问题（图的应用）*5. 药店的药品销售统计系统（排序应用*6. 综合排序 （*）*7. 迷宫求解*8. 总结*9. 源代码*一 单位员工通讯录管理系统（线性表的应用）1.设计题目：单位员工通讯录管理系统（线性表的应用）2.问题描述：为某个单位建立一个员工通讯录管理系统，可以方便查询每一个员工的办公室电话、手机号。其功能包括通讯录链表的建立、员工通讯信息的查询、修改、插入与删除、以及整个通讯录表的输出。3.需求分析：随着社会的发展，越来越多的工厂建立。为了便于管理单位员工和方便员工之间的交流，员工的各项信息的统计，查询和修改，删除等显得很重要。基于上面的种种原因，在学习过数据结构课程和其他编程语言的基础上编成了一个单位员工通讯录管理系统，便于单位对员工的管理和员工间的交流。4.算法设计：本程序使用的数据结构中的线性表中的知识，在C语言的基础上编的。首先，应该建立一个单链表，链表的节点信息表存的有单位员工的编号，姓名，手机号码和办公室电话，然后我们就可以添加员工的各项信息了。在建立好员工信息的表后我们还可以进行员工信息的查询操作，在进行查询时我们首先要信息删除操作，此操作首先要找到要删除的员工信息，然后将此节点的前一节点的后续指针直接指向要删除的结点的后续指针，并且释放要删除的结点空间即可。员工信息修改，首先找到要修改的员工，然后输入要修改的员工信息，将输入信息直接覆盖在原有信息上即可。员工信息输出，遍历整个链表并输出。初始化函数：LinkList Creat() 查找函数：void Search(staff *l)删除函数：void Delete(staff *l)修改函数：void Change(staff *l)利用头插法插入函数void Insert(staff *l) staff *p; printf(*插入通讯录记录*n); p=(staff *)malloc(sizeof(staff); printf(n请输入员工信息:n); printf(员工编号:); scanf(%d,&p-num); printf(员工姓名:); scanf(%s,p-name); printf(手机号码:); scanf(%d,&p-phone); printf(电话号码:); scanf(%d,&p-call); p-next=l-next;/头插法 l-next=p; printf(*插入成功!*n); 五测试结果测试数据：编号 姓名 手机 电话 01 苏 12345 123 02 王 23456 234 03 胡 34567 3451.界面2.新建通讯录3.查询4.插入5.修改6.删除二、停车场管理（栈和队列的应用）1设计题目：停车场管理（栈和队列的应用）2问题描述设停车场是一个可以停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次有北向南排列（大门在最南端，最先到达的第一车停放在车场的最北端），若车场内已停满n辆车，那么后来的车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。3.需求分析：由于现在车辆越来越多，基本上所有的公共场所都有停车场，便于人们的出行。当车辆过多的时候，仅仅需要人工指挥是不可能的，所以就必须有更加完善的停车管理系统来保障车辆的正常停放。因此开发出了这一个相对来说更完善的管理系统。4算法思想和算法设计本系统是在C+语言的基础上，结合数据结构中的栈和队列的应用编程的。以栈模拟停车场，以队列模拟车场外的便道。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停车不收费）。首先定义栈的顺序存储结构和队列的链表结构同时定义栈顶指针top以及栈底指针base。然后初始化栈，同时定义在停车时停车时间time和所需费用money的关系。当车A进入的时候栈顶元素加1，当车B进入的时候栈顶元素加1，但是由于空间不足，当车C进入的时候则显示停车场已满，进入便道！同时输入车辆的信息，只有当A,B两辆车中有一量出站的时候C方能进入。当便道上的车辆进入的时候同时队列元素减1.停车实现函数：void tingche(SqStack &S,LinkQueue &L)int time1;char mingz10;if(S.top-S.base4)cout请输入车辆信息endl;coutmingz;strcpy(S.top-name,mingz);couttime1;S.top-time=time1;S.top-money=S.top-time*5;S.top+;elseL.rear-next=new QNode;cout停车场已满，请进入通道等待。endl;cout请输入进入车辆的信息endl;coutmingz;strcpy(L.rear-next-car,mingz);L.rear=L.rear-next;L.rear-next=NULL;出车函数实现：void chuche(SqStack &S,SqStack &q,LinkQueue &L)char chu10;q.base=q.top=q.stop;coutchu;S.top-;while(strcmp(S.top-name,chu)*(q.top)=*(S.top);q.top+;S.top-;cout停车时间：timeendl;cout停车费用：money=0)*(S.top)=*(q.top);S.top+;q.top-;if(L.front-next!=NULL)int time2;cout便道车辆向停车场转移；endl;cout转移的车辆为：next-carendl;couttime2;strcpy(S.top-name,L.front-next-car);S.top-time=time2;S.top-money=S.top-time*5;S.top+;L.front-next=L.front-next-next;五测试结果测试数据：车牌号A23 时间 5 车牌号B56 时间 10车牌号T12 时间 10 三、哈夫曼编码/译码系统（树应用）1设计题目：哈夫曼编码/译码系统（树应用） 2问题描述：现在要求编写一程序模拟传输过程，实现在发送前将要发送的字符信息进行编码，然后进行发送，接收后将传来的数据进行译码，即将信息还原成发送前的字符信息。3.需求分析：由于通讯信息的简洁性和保密性，就需要对传输的内容进行处理，然后到达接受者的手中之后再进行必要的解码。哈弗曼编码译码系统就是这样一个处理并翻译信息的系统。利用利用哈夫曼编码进行通信,可以压缩通信的数据量,提高传输效率,缩短信 息的传输时间,还有一定的保密性。4.算法思想和算法设计本程序是用最优二叉树即哈夫曼树来实现哈夫曼编码译码器的功能。假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长度为(W1*L1)+(W2*L2)+(Wi*Li)。若将此对应到二叉树上，Wi为叶结点，Li为根结点到叶结点的路径长度。那么，(W1*L1)+(W2*L2)+(Wi*Li)恰好为二叉树上带权路径长度。因此，设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权，构造一棵哈夫曼树，此构造过程称为哈夫曼编码该系统将实现以下几大功能：从文件中读取字符串，建立哈夫曼树，哈弗曼编码以及哈夫曼译码等。从硬盘读取字符串的函数：void Open(char s) char name10;FILE *fp;int i=0;printf(请输入要打开的文件名：);gets(name); if(fp=fopen(name,rt)=NULL)printf(打开失败！n); exit(1);si+=fgetc(fp);while(si-1!=EOF)si+=fgetc(fp);si=0; fclose(fp);保存函数：void Save(char s) char name10;FILE *fp;printf(请输入要保存的文件名：);gets(name);if(fp=fopen(name,wt)=NULL)printf(存储失败！);exit(1);fputs(s,fp);printf(n保存成功，文件名为:%s。n,name);printf(n按回车键继续.);getchar();fclose(fp);编码函数：void HFMCode(HFMTree HT,CodeNode HC,char str) int i;HFMTree q,p=HT;for(i=0;in;i+) HCi.ch=stri;HCi.coden-1=0;for(i=0;iParent;q=q-Parent) if(q=q-Parent-LChild)HCi.code-HCi.start=0;elseHCi.code-HCi.start=1;p=p-next; 译码函数：void DeCoding(char code,HFMTree HT,char str,char s) int i,j,k=0;HFMTree root,p,q;for(root=HT;root-Parent;root=root-Parent); for(i=0,p=root;codei;i+) if(codei=0)p=p-LChild;elsep=p-RChild;if(p-LChild=NULL&p-RChild=NULL) for(j=0,q=HT;q!=p;q=q-next,j+);sk+=strj;p=root; sk=0; 五测试结果程序界面编码及保存译码及保存四教学计划编制问题（图的应用）1设计题目：教学计划编制问题（图的应用）2问题描述：大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。在这样的前提下设计一个教学计划编制程序。3.需求分析：随着素质教育的实施，大学里开设的课程也越来越多。每个课程并不是单独的，他们之间都有着不同的联系。教学计划编制也就成了一个难题，不仅要求课程的排列适合课程的需要，也应该考虑学生的接受能力和时间的安排。运用数据结构中图的应用可以很快的解决这个问题。4.算法思想和算法设计通过有向图的定义和图的基本性质，进行设计。我们可以将所以的课程编制成一张图，然后遍历图。由于课程有前续后继的关系，所以用AOV网是最合适。对AOV网进行拓扑排序即可以得出结果。对AOV网进行拓扑排序有两种情况：广度优先和深度优先。首先确定学期数和每学期的学分总数上限，不能一学期将很多课全部学完。然后根据输入的计划课程树和输入的拓扑排序所形成的课程先修关系建立拓扑图。有向图G采用邻接表存储结构。若G无回路,则输出G的顶点的一个拓扑序列并返回OK，否则返回ERROR。5测试结果 五药店的药品销售统计系统（排序应用）1设计题目：药店的药品销售统计系统（排序应用）2问题描述：设计一系统，实现医药公司定期对销售各药品的记录进行统计，可按药品的编号、单价、销售量或销售额做出排名。在本设计中，首先从数据文件中读出各药品的信息记录，存储在顺序表中。各药品的信息包括：药品编号、药名、药品单价、销出数量、销售额。药品编号共4位，采用字母和数字混合编号，如：A125，前一位为大写字母，后三位为数字，按药品编号进行排序时，可采用基数排序法。对各药品的单价、销售量或销售额进行排序时，可采用多种排序方法，如直接插入排序、冒泡排序、快速排序，直接选择排序等方法。在本设计中，对单价的排序采用冒泡排序法，对销售量的排序采用快速排序法，对销售额的排序采用堆排序法3.需求分析：药品销售系统可以实时记录药品销售的数目，单价以及按照药品的编号，销售量的排序，更加方便了药品的管理。4.算法思想和算法设计：首先从txt文件中读取数据信息并保存，本次试验采用了5中排序方法。其中编号排序是按照基数排序，采用多关键字进行排序。对单价的排序采用了直接插入排序和冒泡排序，直接插入排序就是首先将第一个元素看成是一个有序的，然后第二个元素和第一个比较，若大于第一个则放在其后面否则放前面，依次直至最后一个。冒泡排序就是采用两个循环，即将第一个元素和第二个比较若第一个大于第二个则交换，否则不变，然后第二个和第三个比较，同上。第一趟可将最大的一个放在最后，依次可得排序。销售量是快速排序，快速排序就是首先设置一个关键字，然后让最后一个和其比较，直至找到一个比关键字小的，然后和其交换，接下来让第一个和其比较，直至找到一个比其大的，然后交换，在找到的位置分别做标记，依次执行即可。单价冒泡排序：void BubbleSort(SequenList &L)int i,j;DataType temp;for(i=0;iL.length-1;i+)for (j=1;jL.rj+1.price)temp=L.rj;L.rj=L.rj+1;L.rj+1=temp; cout按单价排序后的结果是：endl;for (i=1;iL.length;i+)coutL.ri.numtL. tL.ri.pricetL.ri.counttL.ri.saleendl;销售量快速排序int Partition(SequenList &L,int low,int high)int pri;L.r0=L.rlow;pri=L.rlow.count;while (lowhigh)while (low=pri) -high;L.rlow=L.rhigh;while(lowhigh&L.rlow.count=pri) +low;L.rhigh=L.rlow;L.rlow=L.r0;return low;void Qsort(SequenList &L,int low,int high)int p;if(lowhigh)p=Partition(L,low,high);Qsort(L,low,p-1);Qsort(L,p+1,high);void QuickSort(SequenList &L)Qsort(L,1,L.length-1);cout按销售量排序后的结果是：endl;for(int i=1;iL.length;i+)coutL.ri.numtL. tL.ri.pricetL.ri.counttL.ri.saleendl;5.测试结果：六排序综合（*）1设计题目：排序综合（*）2问题描述：利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。（1）至少采用三种方法（希尔排序、快速排序、堆排序）实现上述问题求解；（2）统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法；（3）统计每种算法所用的比较次数和交换次数，最后列表显示；3.需求分析：利用随机产生的整数，通过数据结构中的排序知识进行排序，并统计每种方法的所用的时间。找出最快的两种方法。4.算法思想和算法设计首先利用随机数发生器的初始化函数随机产生两千个整数。然后分别以直接插入排序，直接选择排序，冒泡排序，快速排序，堆排序对随机产生的2000整数进行排序。排序的同时记录所需的时间。冒泡排序算法void BubbleSort(int a,int p) /*冒泡排序算法*/ int i,j,temp; for (i=0;ii;j-) /*比较,找出本趟最小关键字的记录*/ if (ajaj-1) temp=aj; /*进行交换,将最小关键字记录前移*/ aj=aj-1; aj-1=temp; 堆排序算法void creatheap(int a,int i,int n) /创建堆int j; int t;t=ai;j=2*(i+1)-1;while(j=n)if(jn)&(ajaj+1)j+;if(t=0;i-)creatheap(a,i,n-1);for(i=n-1;i=1;i-)t=a0;a0=ai;ai=t;creatheap(a,0,i-1);void quicksort(int a,int n,int p) int i,j,low,high,temp,top=-1; struct node int low,high; stN; top+; sttop.low=0;sttop.high=n-1; while(top-1) low=sttop.low;high=sttop.high; top-; i=low;j=high; if(lowhigh) temp=alow; while(i!=j) while(itemp)j-; if(ij)ai=aj;i+; while(ij&aitemp)i+; if(ij)aj=ai;j-; ai=temp; top+;sttop.low=low;sttop.high=i-1; top+;sttop.low=i+1;sttop.high=high; 5.测试结果：8、迷宫求解（*）1设计题目：迷宫求解（*）2问题描述：以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。3.算法思想和算法设计若当前位置可通，则纳入当前路径，并继续朝下一个位置探索，即切换下一位置为当前位置，如此重复直至到达出口；若当前位置不可通，则应顺着来向退回到前一通道块，然后朝着除来向之外的其他方向继续探索；若该通道块的四周4个方块均不可通，则应从当前路径上删除该通道块。设以栈记录当前路径，则栈顶中存放的是当前路径上最后一个通道块。由此，纳入路径的操作即为当前位置入栈；从当前路径上删除前一通道块的才操作即为出栈。设顶当前位置的初值为入口位置；利用二维数组建立迷宫initMaze(int Maze98) int i; for (i=0;i=8;i+) Maze0i=1; for (i=0;i=9;i+) Mazei0=1; for (i=0;i=8;i+) Maze9i=1; for (i=0;in,sumN,i,j); if(i=Exportsi&j=Exportsj) printf(!OKn);return 0; else if(Mazeij+1=0) j=j+1;Push(p,i,j);Mazeij-1=1;Mazeij=1; else if(Mazei+1j=0) i=i+1;Push(p,i,j);Mazei-1j=1;Mazeij=1; else if(Mazeij-1=0) j=j-1;Push(p,i,j);Mazeij+1=1;Mazeij=1; else if(Mazei-1j=0) i=i-1;Push(p,i,j);Mazei+1j=1;Mazeij=1; else Pop(p,readij); i=readij0; j=readij1; if(p-top=p-base) printf(找不到出口n);return 0; 四实现界面 课设总结及体会三个周的课程设计就这样结束了，在这次课程设计中我学到了很多的知识。基本上是把数据结构中所学的知识都重新学习了一遍，也对数据结构这一门课有了更深的了解。通过本次数据结构的课程设计，我学习了很多在上课没懂的知识，更巩固了课堂中学习的知识， 此次设计让自己对数据结构的了解更深入，可以把它同实际相结合，同时，又让我们学会了如何更好的从网上查找资料，还有同班上同学的交流。虽然我对数据结构有了一定的掌握，但是到了真正使用，做课设的时候还是遇到了许多的问题。 在仔细研究过课设要求和功能需求后，我有了初步的想法。 在整个设计过程中，通过对程序的分析，锻炼了对事情的分析能力，通过怎样解决过程中出现的问题，培养了解决问题的能力。刚开始做课程设计的时候真的是一点头绪都没有，不知道怎样把课本中所学的知识运营到实际中去，不知道怎样下手去编写一个程序。不过还好有老师和同学的指导和帮助。当我们看见一个程序课题的时候，应该首先分析他所要实现的功能，从而结合所学的知识和阅历找到实现他所用的知识。然后慢慢地去把他所要实现的功能一步一步的分割，一点一点的编写程序，最后把它结合起来。最后在这个基础上完善系统。课程设计主要是培养我们的动手实践能力和我们对知识的理解和运用能力。使我们巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。 而且还培养了我们选用参考书，查阅手册及文献资料的能力和培养独立思考，深入研究，分析问题、解决问题的能力。总之，通过这次的课程设计我收获了很多在课本上学习不到的知识和能力。也感觉自己的发现问题，解决问题的能力有了很大的提高，最重要的是学会了如何把实践和理论相结合，学会了如何用所学到的只是去解决实际问题。这次课程设计真的是受益匪浅。源代码通讯录44#include #include #include #define NULL 0 typedef struct staff int num;/员工编号 char name8;/员工姓名 int phone; /手机号码 int call;/电话号码 struct staff *next; staff,*LinkList; /建立链表 LinkList Creat() int i,n; staff *p; LinkList L; L=(LinkList)malloc(sizeof(staff); L-next=NULL; printf(请输入员工数:); scanf(%d,&n); printf(*建立通讯录*n); for(i=0;inum); printf(员工姓名:); scanf(%s,p-name); printf(手机号码:); scanf(%d,&p-phone); printf(电话号码:); scanf(%d,&p-call); p-next=L-next; L-next=p; printf(*输入成功!*n); return L; /查找 void Search(staff *l) int m; staff *p; p=l-next; printf(*查询通讯录记录*n); printf(n请选择查询方式:n); printf(1编号 n); printf(2姓名 n); printf(3手机 n); printf(4电话 n); printf(请选择:); scanf(%d,&m); while(m!=1&m!=2&m!=3&m!=4) printf(输入错误!请重新选择:); scanf(%d,&m); ; if(m=1)/按编号查询 int t; printf(n请输入想查询的编号:); scanf(%d,&t); while(p&(p-num)!=t) p=p-next; if(p=NULL) printf(无此人!n); else printf(*员工信息*n); printf(员工编号: %dn,p-num); printf(员工姓名: %sn,p-name); printf(手机电话: %dn,p-phone); printf(电话号码: %dn,p-call); ; if(m=2)/按姓名查找 char s8; printf(n请输入想查询的姓名:); scanf(%s,s); while(strcmp(p-name,s)!=0&(p!=0) p=p-next; if(strcmp(p-name,s)=0) printf(*员工信息*n); printf(员工编号: %dn,p-num); printf(员工姓名: %sn,p-name); printf(手机号码: %dn,p-phone); printf(电话号码: %dn,p-call); else printf(无此人!n); ; if(m=3)/按手机号码查找 int t; printf(n请输入想查询的手机号码:); scanf(%d,&t); while(p&(p-phone)!=t) p=p-next; if(p!=0) printf(*员工信息*n); printf(员工编号: %dn,p-num); printf(员工姓名: %sn,p-name); printf(手机号码: %dn,p-phone); printf(电话号码: %dn,p-call); else printf(无此人!n); ; if(m=4)/按电话号码查找 int t; printf(n请输入想查询的电话号码:); scanf(t%d,&t); while(p&p-call!=t) p=p-next; if(p!=0) printf(*员工信息*n); printf(员工编号: %dn,p-num); printf(员工姓名: %sn,p-name); printf(手机号码: %dn,p-phone); printf(电话号码: %dn,p-call); else printf(无此人!n); ; /删除 void Delete(staff *l) int m; staff *p,*s; p=l; printf(*删除通讯录记录*n); printf(请选择删除方式:n); printf(1编号 n); printf(2姓名 n); printf(3手机 n); printf(4电话 n); printf(请选择:); scanf(%d,&m); while(m!=1&m!=2&m!=3&m!=4) printf(输入错误，请重新选择:); scanf(%d,&m); ; if(m=1)/按编号删除 int t; printf(请输入想删除的编号:); scanf(%d,&t); while(p-next&p-next-num!=t) p=p-next; if(p-next) s=p-next; p-next=s-next; free(s); printf(*删除成功!*); else printf(未找到，请重新选择！n); ; if(m=2)/按姓名删除 char ss8; printf(n请输入想删除的姓名:); scanf(%s,ss); while(p-next&(strcmp(p-next-name,ss)!=0) p=p-next; if(p-next) s=p-next;p-next=s-next; free(s); printf(*删除成功!*); else printf(未找到，请重新选择！n!); ; if(m=3)/按手机号码删除 int t; printf(n请输入想删除的手机号码:); scanf(%d,&t); while(p-next&p-next-phone!=t) p=p-next; if(p-next) s=p-next; p-next=s-next; free(s); printf(*删除成功!*); else printf(未找到，请重新选择！n); ; if(m=4)/按电话号码删除 int t; printf(n请输入想删除的电话号码:); scanf(%d,&t); while(p-next&p-next-call!=t) p=p-next; if(p-next) s=p-next; p-next=s-next; free(s); printf(*删除成功!*n); else printf(未找到，请重新选择！n); ; /插入 void Insert(staff *l) staff *p; printf(*插入通讯录记录*n); p=(staff *)malloc(sizeof(staff); printf(n请输入员工信息:n); printf(员工编号:); scanf(%d,&p-num); printf(员工姓名:); scanf(%s,p-name); printf(手机号码:); scanf(%d,&p-phone); printf(电话号码:); scanf(%d