数据结构双向链表-学生管理系统

数据结构实验报告数学与计算机学院实 验 报 告（ 2011 / 2012 学年 第 1 学期）课程名称数据结构课程代码6014279实验时间年月日指导单位软件工程系指导教师周立章学生姓名吴超年 级10级学 号312010080611402专 业软件工程实验成绩实验名称学生成绩管理系统指导教师周立章实验类型设计实验学时2+10实验时间一、 实验目的和要求（1）掌握线性表的顺序存储结构，在顺序存储结构基础上进行的插入、删除、查找等算法的思想和实现；（2）掌握线性表的链式存储结构。掌握线性表的链式存储结构的建立。在链表中插入、删除和查找算法的思想和算法实现。（3）掌握线性表在顺序存储、链式存储结构的基础进行的各种应用。（4）掌握链表的定义和基础知识以及链表的存储和链式存储结构及其应用。（5）掌握队列的基础知识，循环顺序队列、链队列及其应用。（6）会用结构体正确描述每一条学生记录的信息，掌握链表结构存储所处理的数据。（7）设计友好的人机交互菜单，通过相应的流程控制语句的正确使用，使得在主函数中体现对各功能模块的调用，从而实现一个完整的小型管理系统。 要求：课内实验学时2学时，课后学时要求为10学时。二、实验环境(实验设备) 硬件: 微型计算机P4软件: Windows XP+Microsoft Visual C+6.0三、实验原理及内容实验题目 利用链式存储结构存储学生的成绩信息，设计一个学生成绩管理系统，具有以下功能：（1）定义学生结构体类型struct Student，每个学生包括学号、姓名、3门功课（课程名自己定义）、总分。（2）建立双向循环链表：输入若干学生的信息（当输入学生的学号为0000时结束，要求自动计算总分），并按输入的顺序建立双向循环链表；（3）输出学生成绩信息：遍历双向循环链表，输出所有学生的完整信息到屏幕；（4）查找指定学号的学生信息。如果查找成功，输出所有学生信息，否则输出失败。（5）插入学生信息：以队列的方式将新学生成绩信息插入到链表中；（6）删除学生信息：给出学生姓名，删除链表所有相同姓名的学生的信息（即姓名相同的结点）；（7）修改学生信息：给出学生学号，修改该生的三门课程成绩信息；（8）按总分排序：在原来的双向循环链基础上按总分降序进行就地排列。即不能增加额外的空间开销；实验前准备：完成上述(1)-(4)算法，并要求上机验证通过。实验时完成(5)-(6)。实验后，完成算法（7），(8) ,并要求上机验证通过。实验解答：1) 画出主函数的流程图 2）数据类型定义 （1）学生成绩信息结构体类型的定义struct Studentint num;char name20;int math;int chinese;int english;int sum;struct Student *prior,*next; ;（2）双向链表结点的定义。是否将结点的数据类型定义为学生成绩信息结构体类型？是的；3）为了能够完成链表的各项操作，你给出的测试数据有哪些？主要用于测试哪些方面？1 菜单函数测试：2输入函数测试3 查询函数测试4 插入函数测试5 删除函数测试6 输出函数测试7 修改函数测试8 排序函数测试实 验 报 告4)你是否在实验前完成了算法（1）-（4）？如果完成了难点在哪儿？。如果没有完成，理由是什么？答：是；难点在于双向循环链表的创建，在最后需要把最后一个结点指向头结点，否则会出现一系列问题；5）建立双向循环链表，你采用的是后插法还是前插法？写出C+语言代码。答：前插法，代码如下：void RDLink:Create()Student *p,*s; int x;if(head=new Student)=NULL)cout分配内存失败.prior=NULL;head-next=NULL;p=head;cout开始输入学生信息，输入时结束。endl;while(1)if(s=new Student)=NULL)cout分配内存失败.next=s;coutx;if(x=0000)break;elses-num=x;couts-name;couts-math;couts-chinese;couts-english;s-sum=s-math+s-chinese+s-english;s-prior=p;s-next=NULL;p=s;s-next=head;head-prior=s;cout储存成功！next;用while(p!=head)来控制循环；循环一次p再指向下一结点：p=p-next;void RDLink:DispList()Student *p=head-next; while (p!=head) cout学生的学号：numendl; cout学生的姓名：nameendl; cout学生的数学成绩：mathendl; cout学生的语文成绩：chineseendl; cout学生的英语成绩：englishendl; cout个学生的总成绩：sumnext; coutnext; 8）插入算法：当按队列的方式进行插入运算时，新学生信息是插入到什么位置？写出算法。答：插到末尾void RDLink:InsElem() Student *s; s=new Student; Student *p=head; couts-num;couts-name;couts-math;couts-chinese;couts-english;s-sum=s-math+s-chinese+s-english;head-prior-next=s;s-prior=head-prior;head-prior=s;s-next=head;cout插入成功！next,*s;s=new Student; s-data=x;if(i=1)head-prior=s;head-next=s; s-prior=head; s-next=head; else while (jnext;j+; s-next=p-next; s-prior=p; if (p-next!=head) p-next-prior=s; p-next=s; return 1; 时间复杂度为：0(n)10）删除操作：在该删除中，时间开销主要用在什么地方？写出删除算法的代码，给出时间复杂度。它与顺序表中同样的删除上有什么不同？你是如何保证删除了所有姓名相同的结点的？答：用在遍历链表上；时间复杂度为：O(n)顺序表没有链表中前后指针，不用让前后指针指来指去；遍历整个双线循环链表，只要姓名相同，则执行删除操作；int RDLink:DelElem() Student *p=head-next,*q;coutm;int j=1,x=0;while (p!=head) if(strcmp(p-next-name,m)=0) q=p-next; p-next=q-next; if (q-next!=head) q-next-prior=p; delete q; cout删除成功next; j+; if(x=0)cout查找失败！endl; return 0;11）写出修改学生成绩的代码。void RDLink:Modify()int x,a,b,c,d;cout请输入需要修改的学生学号x;Student *p=head-next; while (p!=head) if(p-num=x)coutd;p-num=d;cout语文成绩a;p-chinese=a;cout英语成绩b;p-english=b;cout数学成绩c;p-math=c;p-sum=a+b+c;cout修改成功！next;12）按总分排序时，你是否增加了空间？写出该算法的代码。答：没有增加。void RDLink:Rank()Student *p=head-next;Student *q=head-next-next; while(p!=head) while(q!=head) if(p-sumsum) p-prior-next=q; q-next-prior=p; q-prior=p-prior; p-next=q-next; q-next=p; p-prior=q; q=q-next; p=p-next; cout排序成功！endl;实 验 报 告四、实验小结（包括问题和解决方法、心得体会、意见与建议等）1在使用链表存储学生信息进行编程时，你所遇到的主要问题是什么，如何解决的？ 由于本人对链表的操作并不是特别熟练，特别是像这种双向循环链表，刚开始做的时候真的是完全靠照搬老师代码，但是在拼凑的过程中一次次的出错，比如一进行插入操作和删除操作就意外停止，通过自己不断的调试，并查找资料，自己画图理解，修改代码，终于把问题搞定了！2链栈的进栈操作需什么条件？栈操作的特点是什么？ 答：需要栈未满；特点是只能从顶部进栈，比较简单。3队列操作的特点是什么？如果Q表示是循环顺序队列，则表示Q为空的条件和满的条件是什么？答：特点：队头出队，队尾入队。队满的条件：（rear+1)%MaxSize=front（此时，循环队列中能装入的元素的个数为MaxSize）队空的条件：rear=front 4在删除算法中，你准备的测试数据是什么？是否都按算法姓名相同的都删除？答： 准备了两个姓名相同的数据，不存在的一个姓名，存在的姓名。经过测试，姓名相同的结点均被删除。 5.对学生的成绩信息进行相关操作，你认为使用链式存储结构合理吗？说明理由。答：合理，虽然使用链式存储太过复杂，需要指针不断的变化来达到目的，非常容易出错，但是它不需要不断的移动元素，并且指针的变化不需要位置的连续，还可以节省空间。 五、指导教师评语成 绩批阅人日 期17