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

1、實驗二 鏈表操作實現(xiàn)實驗日期： 2017 年 3 月 16 日 實驗目的及要求1. 熟練掌握線性表的基本操作在鏈式存儲上的實現(xiàn)；2. 以線性表的各種操作（建立、插入、刪除、遍歷等）的實現(xiàn)為重點；3. 掌握線性表的鏈式存儲結構的定義和基本操作的實現(xiàn)；4. 通過本實驗加深對C語言的使用（特別是函數(shù)的參數(shù)調(diào)用、指針類型的應用）。實驗內(nèi)容已知程序文件linklist.cpp已給出學生身高信息鏈表的類型定義和基本運算函數(shù)定義。（1）鏈表類型定義typedef struct int xh; /*學號*/ float sg; /*身高*/ int sex; /*性別，0為男生，1為女生*/ datatype

2、;typedef struct node datatype data; /*數(shù)據(jù)域*/ struct node *next; /*指針域*/ LinkNode, *LinkList; （2）帶頭結點的單鏈表的基本運算函數(shù)原型LinkList initList();/*置一個空表（帶頭結點）*/void createList_1(LinkList head);/*創(chuàng)建單鏈表*/void createList_2(LinkList head);/* 創(chuàng)建單鏈表*/void sort_xh(LinkList head);/*單鏈表排序*/void reverse(LinkList head);/*對

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

4、ex; /*性別，0為男生，1為女生*/ datatype;typedef struct node datatype data; /*數(shù)據(jù)域*/ struct node *next; /*指針域*/ LinkNode, *LinkList;/*帶表頭的單鏈表的基本運算函數(shù)*/LinkList initList();/*置一個空表（帶頭結點）*/void createList_1(LinkList head);/*創(chuàng)建單鏈表*/void createList_2(LinkList head);/*創(chuàng)建單鏈表*/void sort_xh(LinkList head);/*單鏈表排序*/void r

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

6、 *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=xh;p->data.sg=sg;p->data.sex

7、=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;while(!feof(fp)fscanf(fp,"%d%f%d

8、",&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=NULL;/*利用原表頭結點建新的空表*/ while(p) q=p; /*q為被插入的

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

10、p) r=p; p=p->next; /*r指向結點頭插到鏈表*/ 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;/*自定義錯誤處理函數(shù)*/void Error(char *s) printf("n %s&

11、quot;, s); exit(1); /*返回OS,該函數(shù)定義在stdlib.h中*/*保存單鏈表到文件*/void save(LinkList head,char strname)FILE *fp;LinkList p;if(fp=fopen(strname,"w")=NULL) printf("can not open file !"); return ;p=head->next;while(p!=NULL) fprintf(fp,"%2d %5.2f %2dn",p->data.xh,p->data.sg,p

12、->data.sex); p=p->next;fclose(fp);請回答下列問題：（1）由單鏈表結點類型定義可知，該鏈表結點類型名為 LinkNode ，結點的指針類型為 LinkList ，向系統(tǒng)申請一個學生結點空間并把起始地址存于上述結點指針變量new中的語句是： p=(LinkList)malloc(sizeof(LinkNode); 。（2）回答問題：a）已知：LinkList head ; 畫出執(zhí)行head=initList();語句后的鏈表結構示意圖head*順序：1-13-7-15-2 pb）在a)操作的基礎上，根據(jù)records.txt中的數(shù)據(jù)，畫出執(zhí)行creat

13、eList_1(head);語句后的鏈表結構示意圖head1315172 c）在b)操作的基礎上，畫出執(zhí)行sort_xh(head) ;語句后的鏈表結構示意圖 head1513721d）在c)操作的基礎上，畫出執(zhí)行reverse(head) ;語句后的鏈表結構示意圖 head1512713e）在d)操作的基礎上，寫出執(zhí)行pntList(head) ;語句后屏幕輸出結果（3）寫出下列操作對應的執(zhí)行語句（以下的指針變量的類型都是上述定義的結點指針類型）a）把一個new指針指向的結點頭插到以h為頭指針帶表頭結點的單鏈表中的語句new->next=h->next;h->next=ne

14、w;b）把一個new指針指向的結點頭插到以h為頭指針不帶表頭結點的單鏈表中的語句new->next=h;h=new;c）在單鏈表中刪除r所指結點的后繼結點（假設存在）的語句 r->next=r->next->nextd）分別寫出循環(huán)及非循環(huán)單鏈表中判斷r所指結點是尾結點（假設存在）的條件循環(huán)：r->next= =NULL非循環(huán)：r->next!=NULL任務二1題目要求創(chuàng)建一個新的程序文件sy12.cpp，請調(diào)用linklist.cpp提供的功能函數(shù)（以#include “l(fā)inklist.cpp” 方式導入函數(shù)庫）及自定義的函數(shù)完成以下操作：l 從數(shù)據(jù)文件

15、records.txt中讀取學生信息，建立與源數(shù)據(jù)同序的學生鏈表并打印在屏幕上；l 統(tǒng)計學生鏈表中身高達標人數(shù)（男女生的身高達標值由鍵盤輸入），并打印結果；l 從鍵盤輸入一位學生的相關信息插入到已排序的學生身高鏈表中后仍然保持學號的有序性；l 對上述操作后的學生鏈表進行倒置，結果輸出到數(shù)據(jù)文件result.txt中；l 刪除鏈表中身高為指定值的所有學生結點并打印； 在程序文件sy12.cpp需再定義以下三個功能函數(shù)：（1）int count(LinkList head,float sg_fm,float sg_m)功能：已知女生達標身高為sg_fm，男生達標身高為sg_m，統(tǒng)計head為頭指針

16、的學生鏈表中身高達標人數(shù)并返回；（2）void insertX(LinkList head, datatype x)功能：在學號從小到大排序的學生鏈表中插入值為x的學生仍保持學號的有序性（3）int delete(LinkList head,float sg)功能：刪除head為頭指針的學生鏈表中指定身高的所有學生結點，刪除成功返回1，否則返回0；2請根據(jù)題目功能要求或程序中的注釋完整sy12.cpp代碼#include "linklist.cpp"int count(LinkList head,float sg_fm,float sg_m);/*統(tǒng)計head為頭指針的學生

17、鏈表中身高達標人數(shù)并返回*/void insertX(LinkList head, datatype x);/*在學號從小到大排序的學生鏈表中插入值為x的學生仍保持學號的有序性*/int delete(LinkList head,float sg);/*刪除head為頭指針的學生鏈表中指定身高的所有學生結點，刪除成功返回1，否則返回0*/void main() LinkList head; int c,flag; float sg,sg_fm,sg_m; datatype x; /*建立與源數(shù)據(jù)文件同序的學生鏈表并輸出；*/ head= initList() ; /*建空鏈表*/ create

18、List_2(head) ; /*調(diào)用建鏈表函數(shù)建立所需鏈表*/ printf("n與數(shù)據(jù)文件同序的學生鏈表：n"); pntList(head) ; /*調(diào)用函數(shù)打印輸出鏈表中信息*/ getchar(); /*統(tǒng)計學生鏈表中身高達標人數(shù)（男女生的身高達標值由鍵盤輸入）并打印結果；*/ printf("n輸入達標的女生、男生身高值："); scanf("%f%f",&sg_fm,&sg_m); c=count( head, sg_fm, sg_m ); printf("n達標學生人數(shù)為：%d",c

19、); getchar(); /*對學生鏈表按學號進行排序*/ sort_xh(head); /*在學生鏈表中插入指定的學生元素后使鏈表仍按學號有序*/ x.xh=3; x.sg=1.67; x.sex=0; insertX( head, x ); printf("n new list after insert:n"); pntList(head); getchar(); /*對學生鏈表進行倒置，結果輸出到文件result.txt中；*/ reverse(head); save(head,"result.txt"); getchar(); /*刪除鏈表中身

20、高為指定值的所有學生結點;*/ sg=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();/統(tǒng)計學生鏈表中身高達標人數(shù)并返回(sg_fm女生身高達標值、sg_m男生身高達標值)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+;elseif (p->d