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

数学与计算机学院实验报告〔2011/2012学年第1学期〕课程名称数据结构课程代码6014279实验时间年月日指导单位软件工程系指导教师周立章学生姓名吴超年级10级学号专业软件工程实验成绩

实验名称学生成绩管理系统指导教师周立章实验类型设计实验学时2+10实验时间实验目的和要求〔1〕掌握线性表的顺序存储结构，在顺序存储结构根底上进行的插入、删除、查找等算法的思想和实现；〔2〕掌握线性表的链式存储结构。掌握线性表的链式存储结构的建立。在链表中插入、删除和查找算法的思想和算法实现。〔3〕掌握线性表在顺序存储、链式存储结构的根底进行的各种应用。〔4〕掌握链表的定义和根底知识以及链表的存储和链式存储结构及其应用。〔5〕掌握队列的根底知识，循环顺序队列、链队列及其应用。〔6〕会用结构体正确描述每一条学生记录的信息，掌握链表结构存储所处理的数据。〔7〕设计友好的人机交互菜单，通过相应的流程控制语句的正确使用，使得在主函数中表达对各功能模块的调用，从而实现一个完整的小型管理系统。要求：课内实验学时2学时，课后学时要求为10学时。二、实验环境(实验设备)硬件:微型计算机P4软件:WindowsXP+MicrosoftVisualC++6.0三、实验原理及内容实验题目利用链式存储结构存储学生的成绩信息，设计一个学生成绩管理系统，具有以下功能：〔1〕定义学生结构体类型structStudent，每个学生包括学号、姓名、3门功课〔课程名自己定义〕、总分。〔2〕建立双向循环链表：输入假设干学生的信息〔当输入学生的学号为0000时结束，要求自动计算总分〕，并按输入的顺序建立双向循环链表；〔3〕输出学生成绩信息：遍历双向循环链表，输出所有学生的完整信息到屏幕；〔4〕查找指定学号的学生信息。如果查找成功，输出所有学生信息，否那么输出失败。〔5〕插入学生信息：以队列的方式将新学生成绩信息插入到链表中；〔6〕删除学生信息：给出学生姓名，删除链表所有相同姓名的学生的信息〔即姓名相同的结点〕；〔7〕修改学生信息：给出学生学号，修改该生的三门课程成绩信息；〔8〕按总分排序：在原来的双向循环链根底上按总分降序进行就地排列。即不能增加额外的空间开销；实验前准备：完成上述(1)-(4)算法，并要求上机验证通过。实验时完成(5)-(6)。实验后，完成算法〔7〕，(8),并要求上机验证通过。实验解答：1)画出主函数的流程图2〕数据类型定义〔1〕学生成绩信息结构体类型的定义structStudent{ intnum; charname[20]; intmath; intchinese; intenglish; intsum; structStudent*prior,*next;};〔2〕双向链表结点的定义。是否将结点的数据类型定义为学生成绩信息结构体类型？是的；3〕为了能够完成链表的各项操作，你给出的测试数据有哪些？主要用于测试哪些方面？1菜单函数测试：2输入函数测试3查询函数测试4插入函数测试5删除函数测试6输出函数测试7修改函数测试8排序函数测试实验报告4)你是否在实验前完成了算法〔1〕-〔4〕？如果完成了难点在哪儿？。如果没有完成，理由是什么？答：是；难点在于双向循环链表的创立，在最后需要把最后一个结点指向头结点，否那么会出现一系列问题；5〕建立双向循环链表，你采用的是后插法还是前插法？写出C++语言代码。答：前插法，代码如下：voidRDLink::Create(){Student*p,*s;intx;if((head=newStudent)==NULL){cout<<"分配内存失败..."<<endl;}head->prior=NULL;head->next=NULL;p=head;cout<<"开始输入学生信息，输入时结束。"<<endl;while(1){if((s=newStudent)==NULL){cout<<"分配内存失败..."<<endl;}p->next=s;cout<<"请输入学生的学号：";cin>>x;if(x==0000)break;else{s->num=x;cout<<"请输入学生的姓名：";cin>>s->name;cout<<"请输入学生的数学成绩：";cin>>s->math;cout<<"请输入学生的语文成绩：";cin>>s->chinese;cout<<"请输入学生的英语成绩：";cin>>s->english;s->sum=s->math+s->chinese+s->english;s->prior=p;s->next=NULL;p=s;}}s->next=head;head->prior=s;cout<<"储存成功！"<<endl;}实验报告6〕在遍历双向循环链表时，你是如何判断遍历结束的？如何控制对结点的访问？给出算法的代码。答：从头结点出发，当再次到达头结点时，那么遍历结束；首先创立结点p：Student*p=head->next;用while(p!=head)来控制循环；循环一次p再指向下一结点：p=p->next;voidRDLink::DispList() { Student*p=head->next;while(p!=head) { cout<<"学生的学号："<<p->num<<endl; cout<<"学生的姓名："<<p->name<<endl; cout<<"学生的数学成绩："<<p->math<<endl; cout<<"学生的语文成绩："<<p->chinese<<endl; cout<<"学生的英语成绩："<<p->english<<endl; cout<<"个学生的总成绩："<<p->sum<<endl; p=p->next;}cout<<endl;}7〕在循环双向链表中，有几种方法可以取链表中的首元结点？写出表达式。Student*p=head->next;8〕插入算法：当按队列的方式进行插入运算时，新学生信息是插入到什么位置？写出算法。答：插到末尾voidRDLink::InsElem(){Student*s;s=newStudent;Student*p=head;cout<<"请输入学生的学号：";cin>>s->num;cout<<"请输入学生的姓名：";cin>>s->name;cout<<"请输入学生的数学成绩：";cin>>s->math;cout<<"请输入学生的语文成绩：";cin>>s->chinese;cout<<"请输入学生的英语成绩：";cin>>s->english;s->sum=s->math+s->chinese+s->english;head->prior->next=s;s->prior=head->prior;head->prior=s;s->next=head;cout<<"插入成功！"<<endl;}9〕如果要求将新学生信息插入到链表中指定的i位置，写出插入算法的代码，并给出时间复杂度。intRDLink::InsElem(inti) {intj=1;Student*p=head->next,*s;s=newStudent; s->data=x; if(i==1) {head->prior=s; head->next=s;s->prior=head;s->next=head;}else{while(j<i) { p=p->next;j++; } s->next=p->next; s->prior=p; if(p->next!=head) p->next->prior=s;p->next=s; return1;}}时间复杂度为：0(n)10〕删除操作：在该删除中，时间开销主要用在什么地方？写出删除算法的代码，给出时间复杂度。它与顺序表中同样的删除上有什么不同？你是如何保证删除了所有姓名相同的结点的？答：用在遍历链表上；时间复杂度为：O(n)顺序表没有链表中前后指针，不用让前后指针指来指去；遍历整个双线循环链表，只要姓名相同，那么执行删除操作；intRDLink::DelElem() {Student*p=head->next,*q;cout<<"请输入需要删除的学生姓名：";charm[20];cin>>m;intj=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;deleteq; cout<<"删除成功"<<endl; x++;return1; break;} p=p->next;j++;}if(x==0)cout<<"查找失败！"<<endl;return0;}11〕写出修改学生成绩的代码。voidRDLink::Modify(){ intx,a,b,c,d; cout<<"请输入需要修改的学生学号"<<endl; cin>>x; Student*p=head->next;while(p!=head) { if(p->num==x) { cout<<"请输入学生的学号：";cin>>d; p->num=d; cout<<"语文成绩"<<endl; cin>>a; p->chinese=a; cout<<"英语成绩"<<endl; cin>>b; p->english=b; cout<<"数学成绩"<<endl; cin>>c; p->math=c; p->sum=a+b+c; cout<<"修改成功！"<<endl; break; } p=p->next; }}12〕按总分排序时，你是否增加了空间？写出该算法的代码。答：没有增加。voidRDLink::Rank(){ Student*p=head->next; Student*q=head->next->next; while(p!=head){while(q!=head) {if(p->sum<q->sum) {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=fron