数据结构课程设计

PAGEPAGE2景德镇陶瓷学院课程设计报告课程名称：数据结构课程设计设计题目：1、通讯录管理9、扑克牌游戏14、拓扑排序班级：计算机科学与技术1班学生姓名:游君学号:202110510114起止日期:2021年6月23日~2021年6月30日指导教师:李娟徐星题目1、通讯录管理1、问题描述通讯录管理是一个比较实用的小型管理系统，该系统用于对通讯人员的姓名、号码的管理。该设计采用菜单作为应用程序的主要界面，用控制语句来改变程序执行的顺序，控制语句是实现结构化程序设计的基础。该设计的任务是利用一个简单实用的菜单，通过菜单项进行选择，实现和完成通讯录管理中常用的几个不同的功能。2、要求功能要求：建立通讯录的链表；插入通讯录信息；查询通讯录信息；删除通讯录信息；输出通讯录信息。规定：输入通讯录的信息：编号、姓名、性别、、地址界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：利用单链表存储通讯录信息，同时要求将通讯信息相关数据存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明。系统分析与概要设计根据问题描述和要求，系统要求能够按姓名查找、增加、删除和保存各学生的信息。确定程序应该具备如下功能：“查询学生信息”、“增加学生信息”、“修改学生信息”“删除学生信息”、“数据存盘”基本模块。系统可以将学生信息数据保存到磁盘文件student.txt，从而可以通过磁盘文件读出学生数据信息，为了便于统计在生成学生信息时同时生成学生编号，这样每输入一个学生信息编号顺序加1，这样也方便了管理员查询学生信息。详细设计和编码数据类型定义根据系统要求，可以将姓名和和联系通讯地址定义为字符型。各模块算法描述查询学生信息：Que_name()输入要查询的学生姓名，比较名字与保存的信息是否相同，若相同则查找到，否则，没查找到。增加学生信息：Add()输入要添加的学生信息并保存。删除学生信息：Del()输入要删除的学生姓名，若与数据相同则删除，否则输出查找不到该信息。修改学生信息：Mod()输入要修改的学生姓名，输入要修改的信息，并确认。数据存盘：Sav()创建文件，将信息写入文件。程序关键算法流程图主函数流程（2)某操作算法流程Student::Add()(3)Student::Del()（4)Student::Mod()(5)Student::Que_name()Student::Sav()(7)Student::Load()三、调试结果运行界面录入信息界面查询信息界面修改信息界面源代码：#include<iostream>#include<string.h>#include<windows.h>usingnamespacestd;structstudent{charnum[20];charname[20];charaddress[50];charsex[20];chartelphone[20];}student[2021];//定义学生类结构体voidMenu();//声明菜单函数voidInput();//声明录入函数voidSav(int);//声明保存函数intLoad();//声明信息导入函数voidQue_name();//声明按姓名查找函数voidDel();//声明删除函数voidMod();//声明修改函数voidScan();//声明浏览函信息数voidAdd();//声明添加函数voidMenu()//菜单函数{cout<<"\t*******欢迎来到景德镇陶瓷学院学生通讯录信息管理系统!*******"<<endl;cout<<"\t**请按要求正确录入学生的通讯录信息**"<<endl;cout<<"\t**1.录入相关学生通讯录信息**"<<endl;cout<<"\t**2.保存相关学生通讯录信息**"<<endl;cout<<"\t**3.按姓名查找相关学生通讯录信息**"<<endl;cout<<"\t**4.修改相关学生通讯录信息**"<<endl;cout<<"\t**5.删除相关学生通讯录信息**"<<endl;cout<<"\t**6.添加相关学生通讯录信息**"<<endl;cout<<"\t**7.退出该学生通讯录信息系统**"<<endl;cout<<"\t*****************欢迎您的光临**************************"<<endl;}voidmain()//主函数的实现{intn;loop: Menu();//调用菜单函数 cout<<"请输入您所要进行的操作过程的序号（1-7）:"; cin>>n; system("cls");switch(n) { case1:cout<<"请输入相关学生通讯信息:"<<endl;Input();system("cls");gotoloop; case2:cout<<"请保存相关学生通讯信息:"<<endl;Sav(n);gotoloop; case3:cout<<"按姓名查找相关学生通讯信息:"<<endl;Que_name();gotoloop; case4:cout<<"修改相关学生通讯信息:"<<endl;Mod();gotoloop; case5:cout<<"删除相关学生通讯信息:"<<endl;Del();gotoloop; case6:cout<<"添加相关学生通讯信息:"<<endl;Add();gotoloop;//用goto语句调至指定行 default:break; }cout<<"\t\t\t*********欢迎您的使用!**********"<<endl;}voidInput()//学生通讯信息录入函数{inti,m;cout<<"请输入您所要输入的学生通讯信息的个数(1-2021):";cin>>m;for(i=0;i<m;i++){ cout<<"请输入学生的编号："<<endl; cin>>student[i].num; cout<<"请输入通讯录中学生的姓名："<<endl; cin>>student[i].name; cout<<"请输入通讯录中学生的性别："<<endl; cin>>student[i].sex; cout<<"请输入通讯录中学生的号码："<<endl; cin>>student[i].telphone; cout<<"请输入通讯录学生的地址(格式如***省**市**县**乡)："<<endl; cin>>student[i].address; cout<<"该学生的通讯信息已经输入完毕，请继续输入下一个学生通讯信息!"<<endl;}}voidSav(intm)//如何写入信息？保存通讯录文件函数{inti;FILE*fp;if((fp=fopen("E:\\student.dat","wb"))==NULL)//创建文件并判断是否能打开{cout<<"该文件打开失败。"<<endl;exit(0);}for(i=0;i<m;i++) //将内存中学生通讯信息输入到磁盘里去if(fwrite(&student[i],sizeof(structstudent),1,fp)!=1)//申请空间，写入学生信息，为何有个1???{ cout<<"信息写入失败！"<<endl;fclose(fp);}}voidQue_name()//按姓名查找函数{charname1[10];inti,m;m=Load();cout<<"请输入您要查询学生通讯信息的名字"<<endl;cin>>name1;for(i=0;i<m;i++)if(strcmp(name1,student[i].name)==0) { cout<<"查找到该学生的通讯信息如下："<<endl; Scan(); break; }else{ cout<<"抱歉，查无此人！"<<endl; return;}}voidScan(){inti,m;m=Load();//不明白这个，把函数赋给m吗？cout<<"输出学生通讯信息如下："<<endl;for(i=0;i<m;i++)cout<<"编号:"<<student[i].num<<""<<"姓名："<<student[i].name<<""<<"性别："<<student[i].sex<<""<<"联系:"<<student[i].telphone<<""<<"通讯地址："<<student[i].address<<""<<endl;}intLoad()//导入函数{FILE*fp;inti=0;if((fp=fopen("E:\\student.dat","rb"))==NULL){ cout<<"文件打开失败！"<<endl; exit(0);}else{ do { fread(&student[i],sizeof(structstudent),1,fp); i++; }while(feof(fp)==0);} return(i); fclose(fp);}voidDel()//删除函数{intm;inti,j,n,t,f;charname1[10]; m=Load();cout<<"查看学生的通讯信息如下："<<endl;Scan();//调用浏览函数cout<<"请输入您想删除的通讯信息的名字："<<endl; cin>>name1;for(f=1,i=0;f&&i<m;i++){ if(strcmp(student[i].name,name1)==0) { cout<<"查找到该学生的通讯信息如下："<<endl; Scan(); cout<<"如果要删除该生信息，请按1，否则按0"<<endl; cin>>n; if(n==1)//如果删除，则其他的信息都向前移一行 { for(j=i;j<m-1;j++) { student[j]=student[j+1]; } f=0; } } }if(!f)m=m-1;//??? elsecout<<"抱歉！未找到该生信息。"<<endl; cout<<"输出其他学生通讯信息如下："<<endl; Scan();//调用浏览函数 Sav(m);//调用保存函数 cout<<"如果您想继续删除通讯信息，请按1，否则按0。"<<endl; cin>>t; switch(t) { case1:Del();break; case0:break; default:break; };}voidMod()//修改函数{ charnum[20],tel[20],sex[20]; charname[20]; charaddress[50]; intb,c,i,n,t,f; intm=Load();//导入文件内的信息 cout<<"该学生先前的通讯信息为："<<endl; Scan();//调用浏览函数 cout<<"请输入您想要修改通讯信息的名字："<<endl; cin>>name; for(f=1,i=0;f&&i<m;i++) { if(strcmp(student[i].name,name)==0) { cout<<"查找到该学生的通讯信息如下："<<endl; Scan(); cout<<"确实要修改该生通讯信息请按1，否则按0"<<endl; cin>>n; if(n==1) { cout<<"请输入您要修改的项目（1-编号2-姓名3-性别4-联系5-通讯地址）:"<<endl; cin>>c; if(c>6||c<1) cout<<"抱歉，您的输入有误，请从新输入。"<<endl; } f=0; } } if(f==1)cout<<"抱歉，未找到此人！"<<endl; do { switch(c)//因为当找到第i个学生时,for语句后i自加了1,所以下面的应该把改后的信息赋值给第i-1个人 { case1:cout<<"将该生的编号改为："; cin>>num; strcpy(student[i].num,num); break; case2:cout<<"将该生的姓名改为："; cin>>name; strcpy(student[i].name,name); break; case3:cout<<"将该生的性别改为："; cin>>sex; strcpy(student[i].sex,sex); break; case4:cout<<"将该生的联系改为："; cin>>tel; strcpy(student[i].telphone,tel); break; case5:cout<<"将该生的通讯地址改为："; cin>>address; strcpy(student[i].address,address); break; } cout<<endl; cout<<"确认您所修改的信息请按1，从新修改请按0："<<endl; cin>>b; }while(b==0);Sav(m); cout<<"修改后所有信息如下;"<<endl; Scan(); cout<<"如果您想继续修改请按1，否则按0："<<endl; cin>>t; switch(t) { case1:Mod();break; case0:break; default:break; }}voidAdd()//添加函数{ intn=Load(); inti,m; cout<<"请输入您要添加的学生通讯信息的个数："<<endl; cin>>m; for(i=n;i<m+n;i++) { cout<<"请输入该生的编号："; cin>>student[i].num; cout<<endl;; cout<<"请输入该生的姓名："; cin>>student[i].name; cout<<endl; cout<<"请输入该生的性别："; cin>>student[i].sex; cout<<endl; cout<<"请输入该生的联系："; cin>>student[i].telphone; cout<<endl; cout<<"请输入该生的通讯地址："; cin>>student[i].address; cout<<endl; system("cls"); cout<<"该生的通讯信息添加完毕，请输入您要添加的下一位学生的通讯信息！"<<endl; } Sav(m+n); cout<<"学生通讯信息添加完毕，查看信息如下："<<endl; Scan();}题目9、扑克牌游戏需求分析1.1课程设计题目纸牌游戏：[问题描述]编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后…从第4张开始，以4为基数，是4的倍数的牌翻一次，直到最后一张牌；...再依次5的倍数的牌翻一次，6的，7的直到以52为基数的翻过，输出：这时正面向上的牌有哪些？1.2课程设计目的及其任务1.2.1目的熟练掌握数据结构这门课程，掌握经性表、栈、队列、串、数组、广义表、树和二叉树以及图等基本类型的数据结构及其应用。进一步熟悉抽象数据类型的定义和实现、如何利用数组的动态分酚实现顺序结构、继承的实现方式。学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、想念结构及基相应的算法并初步掌握算法的时间分析和空间分析的技术。基本掌握程序设计的基本思路和方法。利用所学的基本知识和技能，解决简单的程序设计问题各算法描述培养我们的数据抽象能力。1.2.2任务1、课程设计题目每组一题，每个学生必须独立完成；2、对课题进行功能分析，选择合适的数据结构，并定义数据结构的结构体；3、根据程序所要完成的基本要求，设计出完整的算法；4、编程简练，程序功能齐全，能够正确的运行；5、每人提交一份报告，并按照报告有固定的模板和要求书写报告。在课程设计过程中要求重视课程设计环节，用严谨、科学、踏实的工作态度对待课程设计的每一项任务，按照课程设计的题目要求，独立的完成各项任务，按时到机房上机，认真编写课程设计报告。1.3课程设计思想首先必须确定实现这个课程设计的主算法是使用链式存储结构还是栈又或是数组和广义表。根据题目要求需要实现的功能有：1、数据录入：输入各种数据；此处即创建链表的过程，调用一个成员函数负值。在此处还有一个方法实现，即先输入数据，然后再调用构造实现。2、数据统计：存储方式的选择，是使用链式存储结构还是栈又或是数组和广义表；遵守先定义后调用的原则；数组定义时注意下标的起始值和上限；链表定义时注意结点中的项；准确运用结点。3、数据输出：按要求的格式打印调用do循环和for循环4、查找,修改,删除：这三个功能的核心是寻找成员，先遍历链表，然后寻找对应的ID号来找到结点，然后再对结点实行删除，修改操作。1.4软件运行环境及开发工具软件运行的环境是WindowsXP开发工具是MicrosoftVisualC++6.0概要设计2.所用方法及其原理说明1.当每个号码每次遇到是某个数的倍数时，都会相应的翻一次，这样，每张牌会翻的次数就各不一样，可能很多次，也可能只有一两次，结果就只是要输出在经过各个不同次数的翻牌后，正面向上的牌都有哪几个。将所有的牌建立一个数组，运用for的循环嵌套执行以下操作：把52张牌初始化成正面朝上、控制基数和翻牌次数，判断最终的纸牌朝向并打印出结果，具体实现算法参看详细设计。详细设计3.详细设计方案源代码：#include<stdio.h>voidmain(){ inti,j,a[52]; for(i=2;i<=52;i++) for(j=i-1;j<52;j+=i) a[j]=!a[j];printf("正面向上的牌有:"); for(i=0;i<52;i++) if(a[i]) printf("%4d",i+1);}第四章调试和操作说明4.调试运行后的菜单展示图2调试图第五章总结与体会5.1本文的主要工作1．这题的时间复杂度是T（n）=O（n2）。2．虽然本次程序的题目难度与其他问题相比不是很高，但仍有很多问题我们是很容易忽视的，其一：在理解题目的要求时，注意翻牌的次数可能有多次；其二：for循环的嵌套使用在书写时很容易漏掉大括弧。3．运用更多的基础算法，使得程序和算法思想得到更好的表现。5.2心得体会这个学期是我第一次接触“课程设计”，在完成设计的过程中，我遇到了一系列的问题，能明显感觉到自己在很多方面的不足，但另一方面，问题是要分析解决的，找出问题以便为完善学习计划，改变学习内容与方法提供实践依据。通过这次课程设计，加强了我们的动手、思考和解决问题的能力。在设计过程中，经常会遇到这样那样的情况，总觉得思路对着，可是就是行不通，所以耗费时间比较多。在做课程设计的同时，我对课本知识也得到了巩固和加强，由于课本上的东西太多，平时课间的学习并不能很好的理解和运用各个知识点的功能，而且考试内容有限，所以在这次课程设计过程中，我们了解了很多知识点的功能，并且对数据结构有了更多的了解。在平时看课本的过程中，有些问题老是弄不明白，做完课程设计，有些问题就迎刃而解了。而且还可以记住很多东西。通过动手实践让我们映象深刻，知识来源于实践。实践是认识的动力和最终目的，也是检验真理的唯一标准。所以这次课程设计对我们的帮助很大。题目14拓扑排序1、问题描述拓扑排序可判断AOV网络中是否存在回路，使的所有活动可排成一个线性序列，使用每个活动的所有前驱活动都排在该活动的前面。2、要求（1）在有向图中选一个没有前驱的顶点，输出；（2）从有向图中删除该顶点及其该顶点出发的所有边；（3）重复以上两个步骤，直至全部顶点输出；注：输出所有拓扑排序可加分。3、实验内容：拓扑排序。任意给定一个有向图，设计一个算法，对它进行拓扑排序。拓扑排序算法思想：a.在有向图中任选一个没有前趋的顶点输出；b.从图中删除该顶点和所有以它为尾的弧；c.重复上述a、b，直到全部顶点都已输出，此时，顶点输出序列即为一个拓朴有序序列；或者直到图中没有无前趋的顶点为止，此情形表明有向图中存在环。试验分析：在拓扑排序的过程之中，输入入度为零（即没有前趋）的顶点，同时将该顶点的直接后继的入度减1。、查邻接表中入度为零的顶点，并进栈。（2）、当栈为空时，进行拓扑排序。（a）、退栈，输出栈顶元素V。（b）、在邻接表中查找Vj的直接后继Vk，将Vk的入度减一，并令入度减至零的顶点进栈。、若栈空时输出的顶点数不是N个则说明有向回路，否则拓扑排序结束。为建立存放入度为零的顶点的栈，不需要另分配存储单元，即可借入入度为零的数据域。一方面，入度为零的顶点序号即为表头结点的序号，另一方面，借用入度为零的数据域存放带链栈的指针域（下一个入度的顶点号）。源程序：#include<iostream>#include<stack>usingnamespacestd;#defineMAXV50stack<int>mystack;intindegree[MAXV];structnode{intadjvex;node*next;}AdjList[MAXV];voidCreate(nodeAdjList[],intn,intm)//邻接表建表函数，n代表顶点数，m代表边数{inti;node*p;for(i=0;i<=n-1;i++){AdjList[i].adjvex=i;AdjList[i].next=NULL;}for(i=0;i<=m-1;i++){cout<<"请输入第"<<i<<"条边:";intu,v;cin>>u>>v;p=newnode;p->adjvex=v;p->next=AdjList[u].next;AdjList[u].next=p;}}voidprint(intn)//邻接表打印函数{inti;node*p;for(i=0;i<=n-1;i++){p=&AdjList[i];while(p!=NULL){cout<<p->adjvex<<'';p=p->next;}cout<<endl;}}voidTopSort(nodeAdjList[],intn){inti;node*p;memset(indegree,0,sizeof(indegree));for(i=0;i<=n-1;i++){p=AdjList[i].next;while(p!=NULL){indegree[p->adjvex]++;p=p->next;}}for(i=0;i<=n-1;i++){if(indegree[i]==0)mystack.push(i);}intcount=0;while(mystack.size()!=0){i=mystack.top();mystack.pop();cout<<i<<'';count++;for