《2021年国家开放大学 数据结构 实验报告2 线性表的链式存储结构》由会员分享，可在线阅读，更多相关《2021年国家开放大学 数据结构 实验报告2 线性表的链式存储结构（8页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程实验报告学生姓名学号班级指导老师实验名称线性表的链式存储结构实验成绩实验报告实验概述实验目的：掌握线性表的链式存储结构及基本操作，深入了解顺序表的基本特性。实验要求：（1）建立一个评委打分的单向链表。（2）显示删除相关结点后的链表信息。（3）显示要求的结果。实验基本原理：用尾插法建立带头结点的单链表，逐次比较求最高分和最低分，用物理删除的方法累加求和，计算总分及平均分。实验内容实验设计思路、步骤和方法等：某项比赛中，评委们给某参赛者的评分信息存储在一个带头结点的单向链表中，编写程序：（1）显示在评分中给出最高分和最低分的评委的有关信息（姓名、年龄、所给分数等）。（2）在链表中删除一
2、个最高分和一个最低分的结点。（3）计算该参赛者去掉一个最高分和一个最低分后的平均成绩。实验过程（实验中涉及的记录、数据、分析）：（1）评委信息结点用结构变量存储，包含三个成员项，即姓名、年龄、评分。结构类型定义如下：/定义评委信息structpwcharname8;/姓名shortage;/年龄floatscore;/评分;(2) 用头插法或尾插法建立带头结点的单链表，本实验采用尾插法。(3) 遍历链表并逐次比较求最高分和最低分。(4) 在链表中物理删除，即实际删除最高分和最低分结点；也可以进行逻辑删除，即在被删结点的数据域设置一个删除标记，本实验采用物理删除的方法。(5) 遍历链表，累加求和
3、，计算总分及平均分，并输出相关信息。程序代码如下：/实验1.1线性表的链接存储结构#include#include#include#definePWRS5/定义评委人数/定义评委信息structpwcharname8;/姓名shortage;/年龄floatscore;/评分;typedefstructpwPW;/定义链表结点structnodePWdata;structnode*next;；typedefstructnodeNODE;NODE*create(intn);/建立单链表voidinput(NODE*s,inti);/输入第i个评委信息voidoutput(NODE*s);/输出评
4、委信息voidtraverse(NODE*head);/遍历链表voidcalc(NODE*head);/计算及数据处理voidmain()NODE*head=NULL;head二create(PWRS);/建立评委信息单链表printf(n所有评委的评分信息如下:n);traverse(head);/输出所有评委的评分信息calc(head);/计算成绩printf(该参赛者去掉一个最高分和一个最低分后的有效评委的评分信息如下:n);traverse(head);/输出有效评委的评分信息/尾插法建立带头结点的单链表NODE*create(intn)NODE*head,*p,*q;inti;p
5、=(NODE*)malloc(sizeof(NODE);head二p;q=p;p-next=NULL;for(i=1;idata.name，&sdata.age，&sdata.score);/输出评委信息voidoutput(NODE*s)printf(评委姓名：%6s年龄：%d评分：6.2fn,s-data.name,s-data.age,s-data.score);/遍历链表，输出所有评委的评分信息voidtraverse(NODE*head)NODE*p=head-next;/指向第一个结点while(p!二NULL)output(p);p=pnext;printf(n)；/输出最高分及
6、最低分评委信息，删除最高分及最低分结点并计算参赛者的最后平均分voidcalc(NODE*head)NODE*q,*p,*pmin,*pmax;floatsum=0;/总分floatave=0;/平均分/查找最高分和最低分并计算总分p二head-next;pmin=pmax=p;while（p!二NULL）sum+=p-data.score;if（p-data.scorepmax-data.score）pmax=p;/pmax扌旨向最高分结点if（p-data.scoredata.score）pmin=p;/pmin扌旨向最低分结点p=pnext;/输出最高分及最低分评委信息printf（给出
7、最高分的评委姓名：%6s年龄：%d评分：6.2fn,pmax-data.name,pmax-data.age,pmax-data.score）;printf（给出最低分的评委姓名：%6s年龄：%d评分：6.2fn,pmin-data.name,pmin-data.age,pmin-data.score）;printf（n）；/去掉一个最高分和一个最低分，计算并输出参赛者的最后平均分sum二pmaxdata.score;sum二pmindata.score;ave二sum/（PWRS2）;printf（该参赛者去掉一个最高分和一个最低分后的平均得分为：6.2fn,ave）;printf（n）；/
8、在链表中删除最高分和最低分结点for(q二head,p=head-next;p!=NULL;q=p,p=p-next)if(p=pmin)q-next二p-next;p=q;/删除最低分结点if(p=pmax)q-next二p-next;p=q;/删除最高分结点实验结果：显*C:Dacuents：andSettmgsYAllUsers桌面syl_ll)ebugsyl_l.eze名名名名名姓姓姓姓姓-IU-1-1-1-1-评评评评评.个个个个个1234*5川IAIAIAC變SBS琲賈请-q-出一._年龄和评分：b年曲和评年嚇吭平毎齢和评分：e45364852的8G75随7S5682843453如
9、年年年年年自心信abcde分评捋委各各各各各评姓姓进姓姓拿S菜荼善所评评评评评评平评评评l-rr-.rlrl.r!*7500昶伽90078.015龄：52评分:龄：36评分:陵参赛者去掉一个最高分和一个最低分后的平均得分为；81-33者名名名需姓姓参臺奚该评评评去掉一个最高分和一个最低分后的有效评委的评分信息如下二:a年龄：45评分=B6.P0:c年龄：48评分：BS.W；e笠龄；38评分；78.6R*essanykeytuccontinue实验的心得体会：实验小结(1) 线性表采用链式存储(链表)时，用结构变量存储结点，动态生成结点，用指针链接结点，能有效利用存储空间，插入删除方便。(2)
10、链表不能随机访问，是顺序访问方式，可从某结点访问到其后继结点，通常对单链表的遍历即从表头结点顺序访问到表尾结点，任何在链表上做的查找运算都是在遍历的基础上进行的。(3) 单链表操作的关键步骤包括:1）建立链表的头插法：指针变量p开辟单元，生成结点，指针变量q始终指向头结点；操作为：p-next=q-next;q-next=p;2）建立链表的尾插法：指针变量p开辟单元，生成结点，指针变量q始终指向尾结点；操作为：q-next=p;q=p;3）插入：p结点的后面插入新结点s；操作为：s-next=p-next;p-next=s;4）删除：p，q指向相邻结点，q结点是p结点的后继，删除q结点；操作为：pnext=qnext;5）遍历：p指向后继结点；操作为：p=p-next;实验思考：链式存储结构弥补了基于顺序存储结构插入或删除兀素时候会涉及大量兀素移动效率上的问题，同时插入和删除操作需要保证链表的完整性。指导教师评语指导教师日期
