(中央电大)数据结构实验报告1

国家开放大学实验报告（学科：数据结构）姓名班级学号实验日期实验名称：实验一线性表线性表的链式存储结构【问题描述】某项比赛中，评委们给某参赛者的评分信息存储在一个带头结点的单向链表中，编写程序：（1）显示在评分中给出最高分和最低分的评委的有关信息（姓名、年龄、所给分数等）。（2）在链表中删除一个最高分和一个最低分的结点。（3）计算该参赛者去掉一个最高分和一个最低分后的平均成绩。【基本要求】（1）建立一个评委打分的单向链表；（2）显示删除相关结点后的链表信息。（3）显示要求的结果。【实验步骤】（1）运行PC中的MicrosoftVisualC++6.0程序，（2）点击“文件”→“新建”→对话窗口中“文件”→“c++SourceFile”→在“文件名”中输入“X1.cpp”→在“位置”中选择储存路径为“桌面”→“确定”，（3）输入程序代码，程序代码如下:#includestdio.h#includestdlib.h#includemalloc.h#includeiostream.h#includeconio.h#defineNULL0#definePWRS5//定义评委人数structpw//定义评委信息{charname[6];floatscore;intage;};typedefstructpwPW;structnode//定义链表结点{structpwdata;structnode*next;};typedefstructnodeNODE;NODE*create(intm);//创建单链表intcalc(NODE*h);//计算、数据处理voidprint(NODE*h);//输出所有评委打分数据voidinput(NODE*s);//输入评委打分数据voidoutput(NODE*s);//输出评委打分数据voidmain(){NODE*head;floatave=0;floatsum=0;head=create(PWRS);printf(所有评委打分信息如下:\n);print(head);//显示当前评委打分calc(head);//计算成绩printf(该选手去掉1最高分和1最低分后的有效评委成绩:\n);print(head);//显示去掉极限分后的评委打分}voidinput(NODE*s){printf(请输入评委的姓名:);scanf(%S,&s-data.name);printf(年龄:);scanf(%d,&s-data.age);printf(打分:);scanf(%f,&s-data.score);printf(\n);}voidoutput(NODE*s){printf(评委姓名:%8s,年龄:%d,打分:%2.2f\n,s-data.name,s-data.age,s-data.score);}NODE*create(intm){NODE*head,*p,*q;inti;p=(NODE*)malloc(sizeof(NODE));head=p;q=p;p-next=NULL;for(i=1;i=m;i++){p=(NODE*)malloc(sizeof(NODE));input(p);p-next=NULL;q-next=p;q=p;}return(head);}voidprint(NODE*h){for(inti=1;((i=PWRS)&&(h-next!=NULL));i++){h=h-next;output(h);}printf(\n);}intcalc(NODE*h){NODE*q,*p,*pmin,*pmax;floatsum=0;floatave=0;p=h-next;//指向首元结点pmin=pmax=p;//设置初始值sum+=p-data.score;p=p-next;for(;p!=NULL;p=p-next){if(p-data.scorepmax-data.score)pmax=p;if(p-data.scorepmin-data.score)pmin=p;sum+=p-data.score;}cout给出最高分的评委姓名：pmax-data.name年龄：pmax-data.age分值：pmax-data.scoreendl;cout给出最低分的评委姓名：pmin-data.name年龄：pmin-data.age分值：pmin-data.scoreendl;printf(\n);sum-=pmin-data.score;sum-=pmax-data.score;for(q=h,p=h-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;}//删除最高分结点}ave=sum/(PWRS-2);cout该选手的最后得分是：aveendl;return1;}程序运行结果如下:实验结束。实验结论：线性表采用链式存储（链表）时：以结构变量存储结点，动态生成结点，以指针链接结点，能有效利用存储空间，插入删除方便，但不能随机访问.单向链表可从某结点访问到后继结点。单向链表操作的关键步骤：建立链表的头插法：指针变量p开辟单元，生成结点，指针变量q始终指向头结点，操作为：p-next=q-next;q-next=p;尾插法：指针变量q始终指向尾结点，p指针开辟单元，生成结点：q-next=p;q=p;?插入：p所指向结点的后面插入新结点s所指结点s-next=p-next;p-next=s;?删除：p，q指向相邻结点，q所指结点是p所指结点的后继，删除q所指结点，p-next=q-next;?遍历：p=p-next;