實(shí)驗(yàn)三：線性表應(yīng)用--鏈表

1、上海建橋?qū)W院本科數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告（三） 課程名稱：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)類型：綜合實(shí)驗(yàn)室名稱：機(jī)房開課學(xué)院：信息技術(shù)學(xué)院學(xué)生姓名：趙婧玥專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)1班學(xué)號(hào)：10B01010109指導(dǎo)老師： 趙正德實(shí)驗(yàn)三：線性表應(yīng)用鏈表實(shí)驗(yàn)日期： 年 月 日 評(píng)閱成績(jī)： 實(shí)驗(yàn)?zāi)康募耙?. 熟練掌握線性表的基本操作在鏈?zhǔn)酱鎯?chǔ)上的實(shí)現(xiàn)；2. 以線性表的各種操作（建立、插入、刪除、遍歷等）的實(shí)現(xiàn)為重點(diǎn)；3. 掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的定義和基本操作的實(shí)現(xiàn)；4. 通過(guò)本實(shí)驗(yàn)加深對(duì)C語(yǔ)言的使用（特別是函數(shù)的參數(shù)調(diào)用、指針類型的應(yīng)用）。實(shí)驗(yàn)內(nèi)容已知程序文件linklist.cpp已給出學(xué)生身高信息鏈表的類型定義和基本運(yùn)

2、算函數(shù)定義。（1）鏈表類型定義typedef struct int xh; /*學(xué)號(hào)*/ float sg; /*身高*/ int sex; /*性別，0為男生，1為女生*/ datatype;typedef struct node datatype data; /*數(shù)據(jù)域*/ struct node *next; /*指針域*/ LinkNode, *LinkList; （2）帶頭結(jié)點(diǎn)的單鏈表的基本運(yùn)算函數(shù)原型LinkList initList();/*置一個(gè)空表（帶頭結(jié)點(diǎn)）*/void createList_1(LinkList head);/*建一個(gè)單鏈表，頭部插入*/void crea

3、teList_2(LinkList head);/*建一個(gè)單鏈表，尾部插入*/void sort_xh(LinkList head);/*單鏈表按學(xué)號(hào)升序排序*/void reverse(LinkList head);/*對(duì)單鏈表進(jìn)行結(jié)點(diǎn)倒置*/void Error(char *s);/*自定義錯(cuò)誤處理函數(shù)*/void pntList(LinkList head);/*打印單鏈表*/void save(LinkList head,char strname);/*保存單鏈表到文件*/任務(wù)一閱讀程序linklist.cpp（見電子文檔），理解LinkList類型和基本運(yùn)算函數(shù)。任務(wù)二1題目要求創(chuàng)建

4、一個(gè)新的程序文件sy3.cpp，請(qǐng)調(diào)用linklist.cpp提供的功能函數(shù)（以#include “l(fā)inklist.cpp” 方式導(dǎo)入函數(shù)庫(kù)）及自定義的函數(shù)完成以下操作：l 從數(shù)據(jù)文件records.txt中讀取學(xué)生信息，建立與源數(shù)據(jù)同序的學(xué)生鏈表并打印在屏幕上；l 統(tǒng)計(jì)學(xué)生鏈表中身高達(dá)標(biāo)人數(shù)（男女生的身高達(dá)標(biāo)值由鍵盤輸入），并打印結(jié)果；l 對(duì)上述學(xué)生鏈表按學(xué)號(hào)進(jìn)行排序，然后將一位學(xué)生的相關(guān)信息插入到已按學(xué)號(hào)排序的學(xué)生鏈表中后仍然保持學(xué)號(hào)的有序性，將結(jié)果鏈表打印在屏幕上；l 對(duì)上述操作后的學(xué)生鏈表進(jìn)行倒置，結(jié)果輸出到數(shù)據(jù)文件result.txt中；l 刪除鏈表中身高為指定值的所有學(xué)生結(jié)點(diǎn)并打

5、??； l 將當(dāng)前的學(xué)生鏈表拆分為男生鏈表和女生鏈表（沒有新結(jié)點(diǎn)生成），分別打印到屏幕上。在程序文件sy3.cpp需再定義以下四個(gè)功能函數(shù)：（1）int count(LinkList head,float sg_fm,float sg_m)功能：已知女生達(dá)標(biāo)身高為sg_fm，男生達(dá)標(biāo)身高為sg_m，統(tǒng)計(jì)head為頭指針的學(xué)生鏈表中身高達(dá)標(biāo)人數(shù)并返回；（2）void insertX(LinkList head, datatype x)功能：在學(xué)號(hào)從小到大排序的學(xué)生鏈表中插入值為x的學(xué)生仍保持學(xué)號(hào)的有序性（3）int delete(LinkList head,float sg)功能：刪除head為頭

6、指針的學(xué)生鏈表中指定身高的所有學(xué)生結(jié)點(diǎn)，刪除成功返回1，否則返回0；（4）void split(LinkList head, LinkList hm, LinkList hfm)功能：將head為頭指針的學(xué)生鏈表拆分成男生身高鏈表hm與女生鏈表hfm2sy3.cpp源程序清單（含必要的注釋）#include "linklist.cpp"int count(LinkList head,float sg_fm,float sg_m);/*統(tǒng)計(jì)head為頭指針的學(xué)生鏈表中身高達(dá)標(biāo)人數(shù)并返回*/void insertX(LinkList head, datatype x);/*在學(xué)

7、號(hào)從小到大排序的學(xué)生鏈表中插入值為x的學(xué)生仍保持學(xué)號(hào)的有序性*/int dele(LinkList head,float sg);/*刪除head為頭指針的學(xué)生鏈表中指定身高的所有學(xué)生結(jié)點(diǎn)，刪除成功返回1，否則返回0*/void split(LinkList head, LinkList hm, LinkList hfm);/*將head為頭指針的學(xué)生鏈表拆分成男生身高鏈表hm與女生鏈表hfm*/void main() LinkList head,hm,hfm; int c,flag; float sg,sg_fm,sg_m; datatype x; /*建立與源數(shù)據(jù)文件同序的學(xué)生鏈表并輸出；

8、*/ head=initList(); createList_2(head); printf("n與數(shù)據(jù)文件同序的學(xué)生鏈表：n"); pntList(head); getchar(); /*統(tǒng)計(jì)學(xué)生鏈表中身高達(dá)標(biāo)人數(shù)（男女生的身高達(dá)標(biāo)值由鍵盤輸入），并打印結(jié)果；*/ printf("n輸入達(dá)標(biāo)的女生、男生身高值："); scanf("%f%f",&sg_fm,&sg_m); c=count(head,sg_fm,sg_m); printf("n達(dá)標(biāo)學(xué)生人數(shù)為：%d",c); getchar(); /

9、*對(duì)學(xué)生鏈表按學(xué)號(hào)進(jìn)行排序*/ sort_xh(head); /*在學(xué)生鏈表中插入指定的學(xué)生元素后使鏈表仍按學(xué)號(hào)有序*/ x.xh=3; x.sg=1.67; x.sex=0; insertX(head,x); printf("n new list after insert:n"); pntList(head); getchar(); /*對(duì)學(xué)生鏈表進(jìn)行倒置，結(jié)果輸出到文件result.txt中；*/ reverse(head); save(head,"result.txt"); getchar(); /*刪除鏈表中身高為指定值的所有學(xué)生結(jié)點(diǎn);*/ sg

10、=1.67; flag=dele(head,sg); if(flag) printf("ndelete succeed!n"); else printf("ndelete failedn"); printf("n new list after delete:n"); pntList(head); getchar(); /*將學(xué)生鏈表拆分為男生鏈表和女生鏈表,分別打印在屏幕上*/ hm=initList(); hfm=initList(); split(head,hm,hfm); printf("nmale list：n&qu

11、ot;); pntList(hm); printf("nfemale list：n"); pntList(hfm);int count(LinkList head,float sg_fm,float sg_m) int n=0; LinkList p; p=head->next; while(p!=NULL) if(p->data.sex=1)/*sex：1 女生*/ if(p->data.sg>=sg_fm) n+; else if(p->data.sg>=sg_m) n+; p=p->next; return n;void in

12、sertX(LinkList head, datatype x) LinkList p,u; p=(LinkList)malloc(sizeof(LinkNode); p->data.xh=x.xh; p->data.sg=x.sg; p->data.sex=x.sex; u=head; while(u->next!=NULL ) if(u->next->data.xh>x.xh) break; u=u->next; p->next=u->next; u->next=p;int dele(LinkList head,float

13、sg) LinkList p,q,v; int flag=0; q=head; p=head->next; while(p!=NULL) if(p->data.sg=sg) v=p; p=p->next; q->next=p; free(v); flag=1; else q=p; p=p->next; return flag;void split(LinkList head, LinkList hm, LinkList hfm) LinkList q,p,rm,rfm; p=head->next; rm=hm;/*鏈表尾指針*/ rfm=hfm; while(p!=NULL) /*取結(jié)點(diǎn)q插入到男生鏈表或女生鏈表*/ q=p; p=p->next ; if(q->data.sex=1)/*sex：1 女生*/ q->next =rfm->next ; /*尾部插入新鏈表*/ rfm->next=q; rfm=q; else q->next =rm->n