2021年国家开放大学-数据结构-实验报告2-线性表的链式存储结构.docx
数据结构课程实验报告学生姓名学号班级指导老师实验名称线性表的链式存储结构实验成绩实验报告实验概述实验目的：掌握线性表的链式存储结构及基本操作，深入了解顺序表的基本特性。实验要求：(I)建立一个评委打分的单向链表。(2)显示删除相关结点后的链表信息。(3)显示要求的结果。实验基本原理：用尾插法建立带头结点的单链表，逐次比较求最高分和最低分，用物理删除的方法累加求和，计算总分及平均分。实验内容实验设计思路、步骤和方法等：某项比赛中，评委们给某参赛者的评分信息存储在一个带头结点的单向链表中，编写程序：(1)显示在评分中给出最高分和最低分的评委的有关信息(姓名、年龄、所给分数等)。(2)在链表中删除一个最高分和一个最低分的结点。(3)计算该参赛者去掉一个最高分和一个最低分后的平均成绩。实验过程(实验中涉及的记录、数据、分析)：(1)评委信息结点用结构变量存储，包含三个成员项，即姓名、年龄、评分。结构类型定义如下：/定义评委信息structpw(charname8;/姓名shortage;年龄floatscore;/评分;（2）用头插法或尾插法建立带头结点的单链表，本实验采用尾插法。（3）遍历链表并逐次比较求最高分和最低分。（4）在链表中物理删除，即实际删除最高分和最低分结点；也可以进行逻辑删除，即在被删结点的数据域设置个删除标记，本实验采用物理删除的方法。（5）遍历链表，累加求和，计算总分及平均分，并输出相关信息。程序代码如下：实验1.1线性表的链接存储结构#include#include#includedefinePWRS5定义评委人数定义评委信息structpwcharname8;姓名shortage;年龄floatscore;评分；typedefstructpwPW;定义链表结点structnodePWdata;structnode*next;；typedefstructnodeNODE;NODE*create(intn);建立单链表voidinput(NODE*s,inti);/输入第i个评委信息voidoutput(NODE*s);输出评委信息voidtraverse(NODE*head);/遍历链表voidcalc(NODE*head);计算及数据处理voidmain()NODE*head=NULL;head=create(PWRS);建立评委信息单链表printfn所有评委的评分信息如下：n)；traverse(head);输出所有评委的评分信息calc(head);/计算成绩Printf(该参赛者去掉一个最高分和一个最低分后的有效评委的评分信息如下:n);traverse(head);/输出有效评委的评分信息尾插法建立带头结点的单链表NODE*create(intn)NODE*head,*p,*q;inti;P=(NODE*)malloc(sizeof(NODE);head=p;q=p;p->next=NULL;for(i=l;i<=n;i+)P=(NODE*)malloc(sizeof(NODE);input(p,i);p->next=NULL;q->next=p;q二P；return(head);输入评委信息，包括姓名、年龄和评分voidinput(NODE*s,inti)Printf("请输入第%d个评委的姓名、年龄和评分：，i);scanf("%sl%f,&s->data.name,s->data.age,s->data.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;指向第一个结点whiIe(p!=NULL)output(p);p=p->next;printf(z,11z,)；输出最高分及最低分评委信息，删除最高分及最低分结点并计算参赛者的最后平均分voidcalc(NODE*head)NODE*q,*p,*pmin,*pmax;floatsum=0;总分floatave=0;/平均分查找最高分和最低分并计算总分p=head->next;pmin=pmax=p;whiIe(p!=NULL)sum+=p->data.score;if(p->data.score>pma->data.score)pmax=p;PmaX指向最高分结点if(p->data.scoredata,score)pmin=p;Pmirl指向最低分结点p=p->next;输出最高分及最低分评委信息Printf("给出最高分的评委姓名：%6s年龄：%d评分：%6.2fn”,pma->data.name,pma->data.age,pma->data.score);Printf("给出最低分的评委姓名：%6s年龄：%d评分：%6.2f11z,pmin->data.name,pmin->data.age,pmin->data.score);printf(,11z,)；去掉一个最高分和个最低分，计算并输出参赛者的最后平均分sum-=pma->data.score;sum-=pmin->data.score;ave=sum/(PWRS-2);Printf("该参赛者去掉一个最高分和一个最低分后的平均得分为：%6.2fn”,ave);printf(,11z,)；在链表中删除最高分和最低分结点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;/删除最高分结点实验结果：-CDocuentS and SettingsXAll USers桌面syrllDebugsyl 1.入入入入入12 3 4 5名名名名名 姓姓姓姓姓 -Sn 评评评评评 个个个个个年龄和评分 年龄和评分 年龄和评分 年舲知锌分 军薛知谷分a 45 86 b 36 75 c 48 80 d 52 90 e 38 78分评的 委名名名名名 球姓姓姓妣 妻w!妻下龄龄龄龄龄 文55555 息78出鲁高分的评爱姓名：d年龄：52评分：90.00出最底分的评委琏名：b车龄：36评分：75.0081.33¾名名分龄龄龄高年年年低分分分最评评评00 0.8实 验小 结anykeytocontinue实验的心得体会：（1）线性表采用链式存储（链表）时，用结构变量存储结点，动态生成结点，用指针链接结点，能有效利用存储空间，插入删除方便。（2）链表不能随机访问，是顺序访问方式，可从某结点访问到其后继结点，通常对单链表的遍历即从表头结点顺序访问到表尾结点，任何在链表上做的查找运算都是在遍历的基础上进行的。（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结点；操作为：p->next=q->next;5）遍历：P指向后继结点；操作为：p=p->next;实验思考：链式存储结构弥补了基于顺序存储结构插入或删除元素时候会涉及大量元素移动效率上的问题，同时插入和删除操作需要保证链表的完整性。指导教师评语指导教师日期
