實(shí)驗(yàn)二鏈表操作實(shí)現(xiàn)

1、實(shí)驗(yàn)二 鏈表操作實(shí)現(xiàn)實(shí)驗(yàn)日期：2017年旦月16日實(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. 通過本實(shí)驗(yàn)加深對(duì) C語言的使用（特別是函數(shù)的參數(shù)調(diào)用、指針類型的應(yīng)用）實(shí)驗(yàn)容已知程序文件linklist.cpp已給出學(xué)生身高信息鏈表的類型定義和基本運(yùn)算函數(shù)定義(1) 鏈表類型定義typedef struct int xh; /* 學(xué)號(hào) */float sg; /* 身高 */int sex; /*性別，0為男生，1為女生*/ datatype;typed

2、ef struct nodedatatype data;/* 數(shù)據(jù)域 */struct node *next;/* 指針域 */ Lin kNode, *Lin kList;(2) 帶頭結(jié)點(diǎn)的單鏈表的基本運(yùn)算函數(shù)原型LinkListinitList();/* 置一個(gè)空表(帶頭結(jié)點(diǎn))*/void createList_1(LinkList head);/* 創(chuàng)建單鏈表 */void createList_2(LinkList head);/* 創(chuàng)建單鏈表 */void sort_xh(LinkList head);/* 單鏈表排序 */void reverse(LinkList head);/*

3、對(duì)單鏈表進(jìn)行結(jié)點(diǎn)倒置*/void Error(char *s);/*自定義錯(cuò)誤處理函數(shù)*/void pntList(LinkList head);/* 打印單鏈表 */void save(LinkList head,char strname);/*保存單鏈表到文件 */任務(wù)一創(chuàng)建程序文件 linklist.cpp ，其代碼如下所示，理解 LinkList 類型和基本運(yùn)算函數(shù) 后回答下列問題。#include <stdio.h>#include <stdlib.h>/* 單鏈表結(jié)點(diǎn)類型 */typedef struct int xh; /* 學(xué)號(hào)*/float sg; /

4、*身高 */int sex; /*性別， 0為男生， 1為女生*/ datatype;typedef struct nodedatatype data; /* 數(shù)據(jù)域 */struct node *next; /* 指針域 */ LinkNode, *LinkList;/* 帶表頭的單鏈表的基本運(yùn)算函數(shù) */LinkList initList();/* 置一個(gè)空表(帶頭結(jié)點(diǎn)) */void createList_1(LinkList head);/* 創(chuàng)建單鏈表 */void createList_2(LinkList head);/* 創(chuàng)建單鏈表 */void sort_xh(LinkLis

5、t head);/* 單鏈表排序 */void reverse(LinkList head);/* 單鏈表倒置 */void Error(char *s);/* 自定義錯(cuò)誤處理函數(shù) */void pntList(LinkList head);/* 打印單鏈表 */void save(LinkList head,char strname);/*保存單鏈表到文件 */*置一個(gè)空表 */LinkList initList() LinkList p; p=(LinkList)malloc(sizeof(LinkNode);p->next=NULL;return p;/*創(chuàng)建單鏈表 */void

6、createList_1(LinkList head) FILE *fp;int xh;float sg;int sex;LinkList p;if(fp=fopen("records.txt","r")=NULL) Error("can not open file !");return ;while(!feof(fp) fscanf(fp,"%d%f%d",&xh,&sg,&sex); p=(LinkList)malloc(sizeof(LinkNode); p->data.xh=x

7、h; p->data.sg=sg; p->data.sex=sex; p->next=head->next; head->next=p;fclose(fp);/* 創(chuàng)建單鏈表 */void createList_2(LinkList head) FILE *fp;int xh;float sg;int sex;LinkList p,rear;if(fp=fopen("records.txt","r")=NULL) Error("can not open file !");return ;rear=head

8、;while(!feof(fp) fscanf(fp,"%d%f%d",&xh,&sg,&sex); p=(LinkList)malloc(sizeof(LinkNode); p->data.xh=xh; p->data.sg=sg; p->data.sex=sex; p->next=NULL; rear->next=p;rear=p;fclose(fp);/* 單鏈表排序 */void sort_xh(LinkList head)LinkList q,p,u; p=head->next;head->next

9、=NULL;/* 利用原表頭結(jié)點(diǎn)建新的空表 */while(p) q=p; /*q 為被插入的結(jié)點(diǎn) */ p=p->next;/*用p記錄后繼結(jié)點(diǎn)*/*遍歷新鏈表查找插入位置 */ u=head;while(u->next!=NULL)/* 查找插入位置 */ if(u->next->data.xh>q->data.xh)break; u=u->next;/*插入在u結(jié)點(diǎn)的后面*/ q->next=u->next;u->next=q;/*單鏈表倒置 */void reverse(LinkList head) LinkList p, r

10、;p=head->next; head->next=NULL;while(p) r=p;p=p->next;/*r 指向結(jié)點(diǎn)頭插到鏈表 */ r->next=head->next;head->next=r;/*輸出單鏈表 */ void pntList(LinkList head) LinkList p; p=head->next;while(p!=NULL)printf("%2d: %.2f %dn",p->data.xh,p->data.sg,p->data .sex); p=p->next;/*自定義錯(cuò)

11、誤處理函數(shù) */ void Error(char *s) printf("n %s", s);exit(1); /*返回OS該函數(shù)定義在stdlib.h中*/*保存單鏈表到文件*/void save(L in kList head,char strn ame) FILE *fp;Lin kList p;if(fp=fope n(strname,"w")=NULL) prin tf("ca n not ope n file !");return ;p=head->n ext;while(p!=NULL) fprin tf(fp,&

12、quot;%2d %5.2f %2dn",p->data.xh,p->data.sg,p->data.sex); p=p->n ext;fclose(fp);請(qǐng)回答下列問題：(1) 由單鏈表結(jié)點(diǎn)類型定義可知，該鏈表結(jié)點(diǎn)類型名為L(zhǎng)inkNode ,結(jié)點(diǎn)的指針類變量new中的語句是:型為L(zhǎng)in kList，向系統(tǒng)申請(qǐng)一個(gè)學(xué)生結(jié)點(diǎn)空間并把起始地址存于上述結(jié)點(diǎn)指針p=(Li nkList)malloc(sizeof(L in kNode);(2) 回答問題：A畫出執(zhí)行head=initList();語句后的鏈表結(jié)構(gòu)示意headnpa) 已知：LinkList head

13、 ;圖* 順序：1-13-7-15-2b) 在a)操作的基礎(chǔ)上，根據(jù)records.txt中的數(shù)據(jù)，畫出執(zhí)行createList_1(head); 語句后的鏈表結(jié)構(gòu)示意圖headheadc)在b)操作的基礎(chǔ)上，畫出執(zhí)行sort_xh(head)語句后的鏈表結(jié)構(gòu)示意圖d）在c）操作的基礎(chǔ)上，畫出執(zhí)行reverse（head）語句后的鏈表結(jié)構(gòu)示意圖heade）在d）操作的基礎(chǔ)上，寫出執(zhí)行pntList（head）;語句后屏幕輸出結(jié)果（3）寫出下列操作對(duì)應(yīng)的執(zhí)行語句（以下的指針變量的類型都是上述定義的結(jié)點(diǎn)指 針類型）a）把一個(gè)new指針指向的結(jié)點(diǎn)頭插到以h為頭指針帶表頭結(jié)點(diǎn)的單鏈表中 的語句n ew

14、- >n ext=h->n ext;h->n ext=n ew;b）把一個(gè)new指針指向的結(jié)點(diǎn)頭插到以h為頭指針不帶表頭結(jié)點(diǎn)的單鏈表 中的語句n ew- >n ext=h;h=n ew;c）在單鏈表中刪除r所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)（假設(shè)存在）的語句r->n ext=r- >n ext- >n extd） 分別寫出循環(huán)及非循環(huán)單鏈表中判斷r所指結(jié)點(diǎn)是尾結(jié)點(diǎn)（假設(shè)存在） 的條件循環(huán)：r->next= =NULL非循環(huán)：r->n ext!=NULL任務(wù)二1 .題目要求創(chuàng)建一個(gè)新的程序文件sy12.cpp,請(qǐng)調(diào)用linklist.cpp提供的功能函數(shù)(以

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

16、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為頭指針的學(xué)生鏈表中指定身高的所有學(xué)生結(jié)點(diǎn)，刪除成功返 回1,否則返回0;2 .請(qǐng)根據(jù)題目功能要求或程序中的注釋完整sy12.cpp代碼#in clude "li nklist.cpp"int count(

17、LinkList head,float sg_fm,float sg_m);/* 統(tǒng)計(jì) head為頭指針的學(xué)生鏈表中 身高達(dá)標(biāo)人數(shù)并返回*/void insertX(LinkList head, datatype x);/*在學(xué)號(hào)從小到大排序的學(xué)生鏈表中插入 值為x的學(xué)生仍保持學(xué)號(hào)的有序性*/int delete(LinkList head,float sg);/*刪除head為頭指針的學(xué)生鏈表中指定身高的所 有學(xué)生結(jié)點(diǎn)，刪除成功返回1,否則返回0*/void mai n() Lin kList head;int c,flag;float sg,sg_fm,sg_m;datatype x;/*

18、建立與源數(shù)據(jù)文件同序的學(xué)生鏈表并輸出；*/head= initList() ; /* 建空鏈表 */一createList_2(head);/*調(diào)用建鏈表函數(shù)建立所需鏈表*/printf("n與數(shù)據(jù)文件同序的學(xué)生鏈表：n");pntList(head) ; /*調(diào)用函數(shù)打印輸出鏈表息*/ getchar();/*統(tǒng)計(jì)學(xué)生鏈表中身高達(dá)標(biāo)人數(shù)(男女生的身高達(dá)標(biāo)值由鍵盤輸入)并打印結(jié) 果；*/printf("n輸入達(dá)標(biāo)的女生、男生身高值：");sca nf("%f%f", &sg_fm, &sg_m);c=count( he

19、ad, sg_fm, sg_m );printf("n達(dá)標(biāo)學(xué)生人數(shù)為：%d",c);getchar();/*對(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);prin tf("n new list after in sert:n");pn tList(head);getchar();/*對(duì)學(xué)生鏈表進(jìn)行倒置，結(jié)果輸出到文件result.txt中；*/reverse(head);save(head,"

20、result.txt");getchar();/*刪除鏈表中身高為指定值的所有學(xué)生結(jié)點(diǎn);*/sg=1.67;flag= dele(head, sg);if(flag)prin tf("ndelete succeed!' n");elseprin tf("ndelete failed'n");prin tf("n new list after delete:' n");pn tList(head);getchar();統(tǒng)計(jì)學(xué)生鏈表中身高達(dá)標(biāo)人數(shù)并返回(sg_fm女生身高達(dá)標(biāo)值、sg_m男生身高達(dá)標(biāo)值)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 &