线性表的基本操作(西华大学数据结构)

1、数学与计算机学院实验报告2011/ 2012学年第1学期）实验时间2011年11月16日指导单位软件牛工程系指导教师周立章课程名称数据结构课程代码6014279学生姓名年级10学 号专业Web与移动平台技术实验成绩数据结构实验报告实验名称学生成绩管理系统指导教师周立章实验类型设计实验学时2+10实验时间实验目的和要求（1）掌握线性表的顺序存储结构，在顺序存储结构基础上进行的插入、删除、查找等算法的思 想和实现；（2）掌握线性表的链式存储结构。掌握线性表的链式存储结构的建立。在链表中插入、删除和 查找算法的思想和算法实现。（3 ）掌握线性表在顺序存储、链式存储结构的基础进行的各种应用。（4 ）掌

2、握链表的定义和基础知识以及链表的存储和链式存储结构及其应用。（5）掌握队列的基础知识，循环顺序队列、链队列及其应用。(6)(7)会用结构体正确描述每一条学生记录的信息，掌握链表结构存储所处理的数据。设计友好的人机交互菜单，通过相应的流程控制语句的正确使用，使得在主函数中体现对各功能模块的调用，从而实现一个完整的小型管理系统。要求：课内实验学时 2学时，课后学时要求为 10学时。二、实验环境（实验设备）硬件：微型计算机P4软件：Win dows XP+Microsoft Visual C+6.0三、实验原理及内容实验题目 利用链式存储结构存储学生的成绩信息，设计一个学生成绩管理系统， 具有以下功

3、能：（1）定义学生结构体类型struct Student，每个学生包括学号、姓名、3门功课（课 程名自己定义）、总分。（2）建立双向循环链表：输入若干学生的信息（当输入学生的学号为0000时结束， 要求自动计算总分），并按输入的顺序建立双向循环链表；（3）输出学生成绩信息：遍历双向循环链表，输出所有学生的完整信息到屏幕；（4）查找指定学号的学生信息。如果查找成功，输出所有学生信息，否则输出失 败。（5）插入学生信息：以队列的方式将新学生成绩信息插入到链表中；数据结构实验报告（6）删除学生信息：给出学生姓名，删除链表所有相同姓名的学生的信息（即姓名 相同的结点）；（7）修改学生信息：给出学生学号

4、，修改该生的三门课程成绩信息；（8）按总分排序：在原来的双向循环链基础上按总分降序进行就地排列。即不能增 加额外的空间开销；实验前准备：完成上述（1）-（4）算法，并要求上机验证通过。 实验时完成-（6）。实验后，完成算法（7），（8）,并要求上机验证通过。实验解答：1）画出主函数的流程图2 ）数据类型定义（1）学生成绩信息结构体类型的定义typ edef struct Stude ntint ID;char n ame10;int zongs;int score3;struct Stude nt *p rior,* next;DNode;（2）双向链表结点的定义。是否将结点的数据类型定义为学

5、生成绩信息结构体类型?是。3 ）为了能够完成链表的各项操作，你给出的测试数据有哪些？主要用于测试哪些方 面？测试链表的建立 测试链表的建立I. ID=101, name=z,score0=11,score1=11,score2=11/2.ID=102, name=x,score0=22,score1=22,score2=22/ 3.ID=-999/测试输入完成4.i=1/菜单选项测试增加学生信息ID=103 ,n ame=c,score0=33,score1=33,score2=33/5.i=2/菜单选项测试修改学生信息一一成功ID=101,score0=12,score1=12,score2

6、=12/6.i=2/菜单选项ID=100/测试修改学生信息一一错误7.i=3/菜单选项ID=101/测试查找学生信息一一成功8.i=3/菜单选项ID=100/测试查找学生信息一一错误9.i=4/菜单选项ID=c/测试删除学生信息一一成功10.i=4/菜单选项ID=100/测试删除学生信息一一错误II. i=5/菜单选项/测试显示学生信息一一成功12.i=6菜单选项/测试学生信息排序一一成功13.i=7退出系统成功实验报告4）你是否在实验前完成了算法（1）-（4）?如果完成了难点在哪儿？。如果没有完 成，理由是什么？是之前完成的。之前在完成的时候，没有编写测试代码，进行初步的程序测试，导致在后期

7、的调试过程 中出现了大量的错误。花费大量的经历在调试程序上。我觉得这个实验的难点在于自己对双向链表的理解以及把握上。只要自己对双向链表的 理解以及把握能够进一步提高，那么我相信自己在编写这个程序的时候一定会得心应手 的。5）建立双向循环链表，你采用的是后插法还是前插法？写出C+语言代码。后插法。void Stude ntLi nk:CreatLi nk()head=new DNode;head->p rior=head->n ext=head;DNode *s,* p;s=new DNode;coutvv"请依次输入学号、姓名、语数外三科成绩(学号为-999是结束)：&q

8、uot;<<endl;cin> >s->ID;p=head;docin> >s->n ame>>s->score0>>s->score1>>s->score2;s->z on gs=s->score0+s->score1+s->score2;s->p rior =p;p->n ext=s;s->n ext =head;head->p rior=s ;p=s;coutvv"请依次输入学号、姓名、语数外三科成绩(学号为-999是结束):&q

9、uot;<<endl; s=new DNode;cin> >s->ID;while(s->ID!=-999);coutvv"学生信息录入完毕！ "vvendl;106）、遍历双向循环链表时，你是如何判断遍历结束的？如何控制对结点的访问？给 出算法的代码。遍历结束的标志是指针指导了头节点。void Stude ntLi nk:Show()/DNode *p;p=head->n ext;docoutvv"学号："<<p->IDvvendl;"vvp->n amevve ndl;cou

10、tvv"姓名 coutvv"语文："wp->score0vvendl; coutvv"数学："vvp->score1vvendl; coutvv"英语"vvp->score2vvendl; coutvv"总分"vvp->zongsvvendl; p=p->n ext;while( p!=head); coutvv"信息显示完毕！ "vvendl;7）在循环双向链表中，有几种方法可以取链表中的首元结点？写出表达式。我知道的一共有2中取链表中首元结点的方法:P

11、=head->n extp=head->n ext- >n ext- >p iror;8 ）插入算法：当按队列的方式进行插入运算时，新学生信息是插入到什么位置？写 出算法。链表末尾。void Stude ntLi nk:Add()DNode *s,* p;s=new DNode;coutvv"请依次输入学号、姓名、语数外三科成绩："vvendl; cin> >s->ID>>s->n ame>>s->score0>>s->score1>>s->score2; s-

12、>z on gs=s->score0+s->score1+s->score2;p=head->p rior;s->p rior =p;p->n ext=s;s->n ext =head;head->p rior=s; coutvv"增加完毕"vvendl;9）如果要求将新学生信息插入到链表中指定的 i位置，写出插入算法的代码，并 给出时间复杂度。这个之前没有做。10）删除操作：在该删除中，时间开销主要用在什么地方？写出删除算法的代码，给出时间复杂度。它与顺序表中同样的删除上有什么不同？你是如何保证删除了所有姓名 相同的结

13、点的？在这个算法中，花费时间最多的在于查找这个人的时间花费上。 为了保证所有相同姓名的人都删除掉， 到一个就删除掉，然后有继续查找。我在设计的时候是一边找，一边删除。即找void Stude ntLi nk:Delete(char a10)/ DNode *p;p=head->n ext;while( p!=head)if (strcm p(p->n ame, a)=0)p->pnor->n ext=p->n ext; p->n ext- >p rior= p->p rior; coutvv"删除成功！ "<<en

14、dl; p=p->n ext; coutvv"删除后："vvendl;Show();删除学生信息11）写出修改学生成绩的代码void Stude ntLi nk:Modify(i nt x)/DNode *s; s=head->n ext; while(s->ID!=x&&s-> next!=head) s=s->n ext; if(s->ID=x) coutvv"你要修改的学生的信息：修改学生信息"vvs->IDvve ndl;coutvv"请依次输入修改后的语数外三科成绩："

15、;<<endl;cin> >s->score0>>s->score1>>s->score2;s->z on gs=s->score0+s->score1+s->score2;coutvv"修改成功！ "<<endl;elseoutw"没有这个人！ "wendl;12)按总分排序时，你是否增加了空间？写出该算法的代码。 没有。void Stude ntLin k:Sort()DNode *p ,*q;for(p=head->n ext; p->

16、n ext!=head ;p=p->n ext)for(q=p->n ext;q!=head;q=q->n ext)if(p->zon gsvq->z on gs)if(p->n ext!=q)DNode *p2二p->n ext,* p1二p->p rior; p->pnor->n ext=q; p->n ext- >p rior=q; p->p rior=q->p rior; p->n ext=q->n ext; q->p rior- >n ext=p; q->n ext- &

17、gt;pnor=p;q->n ext=p2; q->pnor=p1;p=q; else p->pnor->n ext=q; q->n ext- >pnor=p; p->n ext=q->n ext; q->pnor=p->p rior; p->p rior=q; q->n ext=p; p=q;Show();实验报告四、实验小结（包括问题和解决方法、心得体会、意见与建议等）1.在使用链表存储学生信息进行编程时，你所遇到的主要问题是什么，如何解决的?在增加算法时，总是把原来的东西覆盖；查找、删除算法是又老是没有办法查找到 第

18、一个数据。当时忙了很久才发现原来是链表指针出现了问题，所以就一个操作就显示 一次，这样就很清晰明了的发现了问题的锁子啊，知道是什么原因了，就可以有的放矢 的解决这一系列问题了。2.链栈的进栈操作需什么条件？栈操作的特点是什么?条件：操作前需验满，栈满就不能够进行进栈操作。 特点：先出后进3.队列操作的特点是什么？如果 Q表示是循环顺序队列，则表示Q为空的条件和满 的条件是什么？队列操作的特点是先进先出。如果Q表示循环顺序队列，top=-1时表示栈空，如果top=MAX则表示栈满。4 .在删除算法中，你准备的测试数据是什么？是否都按算法姓名相同的都删除?数据是：1.ID=101, name=z,sco