國家開放大學《數(shù)據(jù)結(jié)構(gòu)》課程實驗報告(實驗2-線性表)參考答案

實用文檔《數(shù)據(jù)結(jié)構(gòu)》課程實驗報告（實驗2線性表）學生姓名學號班級指導老師實驗名稱實驗成績實驗報告實驗概述實驗目的：掌握線性表的鏈式存儲結(jié)構(gòu)及基本操作，深入了解順序表的基本特性。實驗要求：（1）建立一個評委打分的單向鏈表。（2）顯示刪除相關(guān)結(jié)點后的鏈表信息。（3）顯示要求的結(jié)果。實驗基本原理：某項比賽中，評委們給某參賽者的評分信息存儲在一個帶頭結(jié)點的單向鏈表中，編寫程序：（1）顯示在評分中給出最高分和最低分的評委的有關(guān)信息（姓名、年齡、所給分數(shù)等）。（2）在鏈表中刪除一個最高分和一個最低分的結(jié)點。（3）計算該參賽者去掉一個最高分和一個最低分后的平均成績。實驗內(nèi)容實驗設(shè)計思路、步驟和方法等：設(shè)計思路（1）評委信息結(jié)點用結(jié)構(gòu)變量存儲，包含三個成員項，即姓名、年齡、評分。結(jié)構(gòu)類型定義如下：//定義評委信息structpw{charname[8];//姓名shortage;//年齡floatscore;//評分};（2）用頭插法或尾插法建立帶頭結(jié)點的單鏈表，本實驗采用尾插法。（3）遍歷鏈表并逐次比較求最高分和最低分。（4）在鏈表中物理刪除，即實際刪除最高分和最低分結(jié)點；也可以進行邏輯刪除，即在被刪結(jié)點的數(shù)據(jù)域設(shè)置一個刪除標記，本實驗采用物理刪除的方法。（5）遍歷鏈表，累加求和，計算總分及平均分，并輸出相關(guān)信息。完整程序//實驗1.1線性表的鏈接存儲結(jié)構(gòu)#include#include#include#definePWRS5//定義評委人數(shù)//定義評委信息structpw{charname[8];//姓名shortage;//年齡floatscore;//評分};typedefstructpwPW;//定義鏈表結(jié)點structnode{PWdata;structnode*next;};typedefstructnodeNODE;NODE*create(intn);//建立單鏈表voidinput(NODE*s,inti);//輸入第i個評委信息voidoutput(NODE*s);//輸出評委信息voidtraverse(NODE*head);//遍歷鏈表voidcalc(NODE*head);//計算及數(shù)據(jù)處理voidmain(){NODE*head=NULL;head=create(PWRS);//建立評委信息單鏈表printf("\n所有評委的評分信息如下:\n");traverse(head);//輸出所有評委的評分信息calc(head);//計算成績printf("該參賽者去掉一個最高分和一個最低分后的有效評委的評分信息如下:\n");traverse(head);//輸出有效評委的評分信息}//尾插法建立帶頭結(jié)點的單鏈表NODE*create(intn){NODE*head,*p,*q;inti;p=(NODE*)malloc(sizeof(NODE));head=p;q=p;p->next=NULL;for(i=1;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("%s%d%f",&s->,&s->data.age,&s->data.score);}//輸出評委信息voidoutput(NODE*s){printf("評委姓名：%6s年齡：%d評分：%6.2f\n",s->,s->data.age,s->data.score);}//遍歷鏈表，輸出所有評委的評分信息voidtraverse(NODE*head){NODE*p=head->next;//指向第一個結(jié)點while(p!=NULL){output(p);p=p->next;}printf("\n");}//輸出最高分及最低分評委信息，刪除最高分及最低分結(jié)點并計算參賽者的最后平均分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.score>pmax->data.score)pmax=p;//pmax指向最高分結(jié)點if(p->data.scoredata.score)pmin=p;//pmin指向最低分結(jié)點p=p->next;}//輸出最高分及最低分評委信息printf("給出最高分的評委姓名：%6s年齡：%d評分：%6.2f\n",pmax->,pmax->data.age,pmax->data.score);printf("給出最低分的評委姓名：%6s年齡：%d評分：%6.2f\n",pmin->,pmin->data.age,pmin->data.score);printf("\n");//去掉一個最高分和一個最低分，計算并輸出參賽者的最后平均分sum-=pmax->data.score;sum-=pmin->data.score;ave=sum/(PWRS-2);printf("該參賽者去掉一個最高分和一個最低分后的平均得分為：%6.2f\n",ave);printf("\n");//在鏈表中刪除最高分和最低分結(jié)點for(q=head,p=head->next;p!=NULL;q=p,p=p->next){if(p==pmin){q->next=p->next;p=q;}//刪除最低分結(jié)點if(p==pmax){q->next=p->next;p=q;}//刪除最高分結(jié)點}}實驗過程（實驗中涉及的記錄、數(shù)據(jù)、分析）：1）建立鏈表的頭插法：指針變量p開辟單元，生成結(jié)點，指針變量q始終指向頭結(jié)點；操作為：p->next=q->next;q->next=p;2）建立鏈表的尾插法：指針變量p開辟單元，生成結(jié)點，指針變量q始終指向尾結(jié)點；操作為：q->next=p;q=p;3）插入：p結(jié)點的后面插入新結(jié)點s；操作為：s->next=p->next;p->next=s;4）刪除：p，q指向相鄰結(jié)點，q結(jié)點是p結(jié)點的后繼，刪除q結(jié)點；操作為：p->next=q->next;5）遍歷：p指向后繼結(jié)點；操作為：p=p->next;實驗結(jié)果：實驗小結(jié)實驗的心得體會：通過對評委系統(tǒng)案例的學習，更深入地理解線性表的知識和應用。實驗思考：（1）線性表采用鏈式存儲（鏈表）時，用結(jié)構(gòu)變量存儲結(jié)點，動態(tài)生成結(jié)點，用指針鏈接結(jié)點，能有效利用存儲空間