線性表實驗報告

1、一.實驗名稱1 .線性表基本操作；2.處理約瑟夫環(huán)問題二.試驗?zāi)康模? .熟悉C語言的上機(jī)環(huán)境，掌握C語言的基本結(jié)構(gòu)。2 .定義單鏈表的結(jié)點類型。3 .熟悉對單鏈表的一些基本操作和具體的函數(shù)定義。4 .通過單鏈表的定義掌握線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點。5 .熟悉對單鏈表的一些其它操作。三.實驗內(nèi)容L編制一個演示單鏈表初始化、建立、遍歷、求長度、查詢、插入、刪除等操作的程序。2 .編制一個能求解除約瑟夫環(huán)問題答案的程序。實驗一線性表表的基本操作問題描述:1 .實現(xiàn)單鏈表的定義和基本操作。該程序包括單鏈表結(jié)構(gòu)類型以及對單鏈表操作 的具體的函數(shù)定義程序中的單鏈表（帶頭結(jié)點）結(jié)點為結(jié)構(gòu)類型，結(jié)點值為整型

2、。/*定義DataType為int類型*/typedef int DataType;/*單鏈表的結(jié)點類型*/typedef struct LNode DataType data; struct LNode *next;LNodez *LinkedList;LinkedList LinkedListlnit () /初始化單鏈表void LinkedListClear (LinkedList L) / 清空單鏈表 int LinkedListEmpty (LinkedList L)檢查單鏈表是否為空 void LinkedListTraverse (LinkedList L) / 遍歷單鏈表 i

3、nt LinkedListLength (LinkedList L) 求單鏈表的長度 /*從單鏈表表中查找元素*/ LinkedList LinkedListGet(LinkedList L,int i)/*從單鏈表表中查找與給定元素值相同的元素在鏈表中的位置*/ int LinkedListLocate(LinkedList L, DataType x) void LinkedListlnsert (LinkedList L, int iz DataType x) 向單鏈表中插入元素/*從單鏈表中刪除元素*/void LinkedListDel(LinkedList L,DataType x

4、)/*用尾插法建立單鏈表*/LinkedList LinkedListCreat ()2.約瑟夫環(huán)問題：任給正整數(shù)N和K,按下述方法可以得到1,2,n的一個置換，將 數(shù)字1,2,n環(huán)形排列，按順時針方向自1開始報數(shù)，報到K時輸出該位置上的數(shù) 字，并使其出列。然后從他在順時針方向的下一個數(shù)字繼續(xù)報數(shù)，如此下去，直到 所有的數(shù)字全部出列為止。例如N=10, K=3,則正確的出列順序應(yīng)為3, 6, 9, 2, 7, 1, 8, 5, 10, 4o3,試單鏈表實現(xiàn)一個簡單的電子通訊本管理軟件，要求能查找聯(lián)系地址，增加和刪除 聯(lián)系人。聯(lián)系方式假定包括姓名、電話和地址?；疽螅? .上機(jī)前要做好準(zhǔn)備工作

5、，包括程序框圖、數(shù)據(jù)結(jié)構(gòu)以及算法。2 .按時實驗3 .服從實驗室老師的安排4 .獨(dú)立實驗，有問題可以討論，但不得翻版。5 .遵守實驗室的各項紀(jì)律。四、概要設(shè)計1.單鏈表的操作(1)為了實現(xiàn)上述程序功能，需要定義單鏈表的抽象數(shù)據(jù)類型：ADT LuikedList 數(shù)據(jù)對象：D=ai ai G stiuct LNode set,i=0J2數(shù)據(jù)關(guān)系：R= <ai,ai+1 >|ai,ai+1 D基本操作：LinkedListInit()操作結(jié)果：構(gòu)造了一個帶頭節(jié)點的空鏈表L;LHikedListCreatQ初始條件：單鏈表L已存在；操作結(jié)果：建立了一個帶頭節(jié)點的非空鏈表；LinkedLi

6、stClear(&L)初始條件：單鏈表L已存在；操作結(jié)果：將L重置為帶頭節(jié)點的空鏈表；LuikedListEmptv(&L)初始條件：單鏈表L已存在；操作結(jié)果：如果鏈表L為空則返回1,鏈表L非空則返回0：LHikedListLength(&L)初始條件：單鏈表L已存在；操作結(jié)果：返回單鏈表L中數(shù)據(jù)元素的個數(shù)，若L為空表則返回0： LuikedListTraverse(&L)初始條件：單鏈表L已存在；操作結(jié)果：依次返回單鏈表L中各節(jié)點的元素值，若L為空表則顯示鏈表為空； LuikedListGet(&L, i)初始條件：單鏈表L已存在；操作結(jié)果：顯示鏈表L

7、中第1個節(jié)點個元素值，若鏈表L中沒有第1個節(jié)點則顯示查詢位置 不正確：LuikedListLocate(&L, x)初始條件：單鏈表L已存在；操作結(jié)果：顯示鏈表L中元素x的位置，若鏈表L中沒有元素x則顯示所查找元素不存在： LuikedListInseit(&L, i, x)初始條件：單鏈表L已存在；操作結(jié)果：在單鏈表L第1個節(jié)點后插入一個元素值為x的節(jié)點，L的長度加1,若單鏈表 L中沒有第1個節(jié)點則顯示插入位置不正確；LuikedListDel(&L, i)初始條件：單鏈表L已存在；操作結(jié)果：在單鏈表L中刪除第1個節(jié)點，L的長度減1,若單鏈表L中沒有第1個節(jié)點則 顯示

8、刪除位置不正確；(2)本程序包含11個函數(shù)：1 .主函數(shù)niarnQ2 .初始化單鏈表函數(shù)LuikListhutO3 .清空單鏈表函數(shù)LuikedListClear ()4 .檢查單鏈表是否為空函數(shù)LuikedListEmpty ()5,遍歷遍歷單鏈表函數(shù)LmkudListTraverse ()6 .求單鏈表的長度函數(shù)LnikedListLength ()7 .從單鏈表表中查找元素函數(shù)LmkedListGet ()8從單鏈表表中查找指定元素的位序函數(shù)LuikedListLocate ()9 .插入元素函數(shù) LnikedListliisert ()10 .刪除元素函數(shù)LinkedListDel

9、()11 .建立單鏈表函數(shù)LinkedListCreat()各函數(shù)之間的關(guān)系：LuikL IStllllt 0Luike dList Clear ()Linke dList EmptLiiike dList Trave rse ()Liiike dList Lengt h ()LinkeLiiikeLiiikeLinkeLiiikedListdListdListldListdListGetOLocatnseitDelOCreat(e ()()五.詳細(xì)設(shè)計1結(jié)點類型和指針類型 typedef stnict LNode mt data;struct LNode "next; LNode,

10、*LuikedList;2單鏈表的基本操作(1)初始化單鏈表LnikedList LmkedListlnitQ LuikedList L;L=(LinkedList)malloc(sizeof(LNode);L->next=NULL;return L;)(2)清空單鏈表void LinkedListCleai (LnikedList L) L->next=NULL;pnntf("鏈表已經(jīng)清空n)(3)檢查單鏈表是否為空 mt LnikedListEmpty(LuikedList L)if(L->next=NULL) return TRUE;else return F

11、ALSE;)(4)遍歷單鏈表void LinkedListTraverse(LuikedList L) LuikedList p;p=L->next;if(p=NULL) pnntf("單鏈表為空表 1T);elseprintf("鏈表中的元素為NT);while(p!=NULL)printf(H%d fp->data); p=p->next; jpnntff'n")；(5)求單鏈表長度mt LuikedListLength (LuikedList L) LuikedList p;intj;p=L->next;J=°；wh

12、ile(p!=NULL) j+;p=p->next; return j;(6)從鏈表中查找元素LuikedList LuikedListGet(LHikedList Ljnt i) LuikedList p=L->next; j=l;while (p!=NULL && j<i)p=p->next; j+; if (j=i) return p; else return NULL; )(7)從鏈表中查找與給定元素值相同的元素在順序表中的位置 mt LnikedListLocate (LuikedList L, mt x) LuikedList p=L->

13、;next; j=l;while (p!=NULL && p->data != x) p=p->next;j+; if(p) return j;else return 0;j(8)向鏈表中插入元素void LinkedListIiisert(LiiikedList L, mt i, mt x) LuikedList p,s;intj;J=1；P=L；while(p&&j<i)p=p->nextj+; if(p=NULL|j>i) pnntf("插入位置不正確n) else s=(LNode *)nialloc(sizeof

14、(LNode); s->data=x;s->next=p->next; p->next=s;pnntf("d已插入到鏈表中11"了)； ) )(9)從鏈表中刪除元素void LinkedListDel(LiiikedList L,int i) LinkedList p,q;intj;J=1；P=L；while(p->next&&j <i)p=p->next;j+;if(p->next=NULL)pnntf("刪除位置不正確n")；else q=p->next;p->next=q-

15、>next;fiee(q);printf("第d個元素已從鏈表中刪除111);) )(10)建立單鏈表LinkedList LiiikedListCreat() LinkedList L=LinkedListInit(),p,t; mt x;r=L;pnntf("請依次輸入鏈表中的元素，輸入負(fù)數(shù)時結(jié)束1門； scanf(”d”,&x);while (x>=0)p=(LuikedList)malloc(sizeof(LNode);p->data=x;r->next=p; r=p；scanf("%d”.&x);)r->ne

16、xt=NULL;return L;)(11)主函數(shù)niainQ mt i,h,d,e,xj,n,q; chai ch;LinkedList L,p;while(q!=0) pnntf("請選擇要進(jìn)行的操作W)pnntf(“L初始化2.清空3.求鏈表長度4.檢查鏈表是否為空n")；pnntf("5.遍歷鏈表6,從鏈表中查找元素n")；pnntf(”7 .從鏈表中查找與給定元素值相同的元素在順序表中的位置n")；pnntf(”8.向鏈表中插入元素9.從鏈表中刪除元素W)priiitf(nl 0 .建立單鏈表 n")； printf(&qu

17、ot;按其它鍵結(jié)束n) scanf(”d”,&x);switch(x)case l:L=LinkudList!nit();printf("鏈表已經(jīng)初始化 nn);break;case 2:LinkedListCleai(L);prmtf(niiH);bieak;case 3:printf("鏈表的長雇為 %dn,LinkedListLength(L);bieak;case 4:i= LinkedListEmpty(L);if pnntf("鏈表為空 n");else printf("鏈表非空 n”);break;case 5 :Link

18、edListTraveise(L); break;case 6:pnntf(“請輸入待查詢元素在鏈表中的位置:")；scanf(”%d”,&j);p=LnikedListGet(L,j);if(p) pnntff鏈表中第泡 個元素的值為:dh“j,p->data);else piintf("查詢位置不正確n)break;case 7:pnntf("請輸入待查詢元素的值:)scanf(',%d,&e);h=LinkedListLocate(L,e);時)pnntf("d在鏈表中的位置是:%MT,e,h);else pnntf(

19、"鏈表中沒有值為(1的元素n”,e);break;case 8:pnntf(“請輸入插入元素的位置和值(中間以空格或回車分隔)An”)；scanff'%d%d”,&d,&e);LnikedListIiisert(L,d,e);break;case 9:if(LuikedListLength(L)=O)pnntf("鏈表已經(jīng)為空，不能刪除n)else pnntf("請輸入待刪除元素的彳立置:n")；scanf(”d”,&n);LnikedListDel(L,n);break;case 10: L=LHikedListCrea

20、t();prmtf(nnH);break;default:q=O:)六.測試結(jié)果1、單鏈表的操作(1)建立單鏈表：選擇1,然后選擇10 ,輸入123.4.5.6.7,8.9最后一個負(fù)數(shù)(2)求鏈表長度：選擇3,得到執(zhí)行結(jié)果：鏈表的長度為9(3)檢查鏈表是否為空：選擇4,得到執(zhí)行結(jié)果：單鏈表非空(4)遍歷鏈表：選擇5,得到執(zhí)行結(jié)果：鏈表中的元素為1, 2, 3, 4, 5, 6, 7,8, 9,(5)從鏈表中查找元素：選擇6,輸入5,顯示：鏈表中第5個元素的值為5(6)從鏈表中查找與給定元素值相同的元素在順序表中的位置選擇7,輸入2,顯示：2在鏈表中的位置是：2選擇7,輸入25,顯示：鏈表中沒有

21、值為25的元素向鏈表中插入元素選擇8,輸入(6, 5),顯示5以插入到鏈表中選擇5：鏈表中的元素為1, 2, 3, 4, 5, 5, 6, 7, 8, 9,(8)從鏈表中刪除元素選擇9,輸入5,顯示第5個元素已從表中刪除選擇9,輸入12,顯示刪除位置不正確選擇5,顯示鏈表中的元素為鏈表中的元素為1, 2, 3, 4, 5, 6, 7, 8, 9,實驗二約瑟夫環(huán)1.問J描述設(shè)有編號1,2,3。n（n>0）的N個人圍成一個圈，每個人持有一個密碼（正整數(shù)）。開始時從第k （1<=k<=n）個人按順時針方向自1開始順序報數(shù)，報到m （m為第K個人的密碼）的人出圈，再以這個人順時針方向

22、上的下一個人的密碼為m,并開始重新從1報數(shù)。如此下去，宜至所有人 全部出列為止。試設(shè)計一個程序求出出列順序。例如，設(shè)總?cè)藬?shù)n的初值為8.他們所持的密碼分 別為：3,10,7,1,4,8,4,5,開始報數(shù)人的編號k的初值為7,則出列順序為:2,1,3,4,8,57,62.數(shù)據(jù)結(jié)構(gòu)設(shè)計問題中以序號標(biāo)示某個人，所以結(jié)點的數(shù)據(jù)域設(shè)為一個整型類型的變量當(dāng)某人出圈后，報數(shù)的工作要從下一個人開始繼續(xù)，剩下的人仍然圍成一圈，可以使用循環(huán) 表。由于出圈的人將不再屈于圈內(nèi)，意味著數(shù)據(jù)元素的刪除。因此，算法中存有頻繁的元素刪除 操作，存儲結(jié)構(gòu)宜采用鏈表。每個結(jié)點中既存儲密碼還存儲初始位置，所以結(jié)點有兩個數(shù)據(jù)域， 一

23、個指針域。另外，每個結(jié)點代表一個人所以，可以令尾結(jié)點指針指向首元結(jié)點來進(jìn)行循環(huán)。/結(jié)點類template <class ElemType>struct Node/數(shù)據(jù)成員：/數(shù)據(jù)域 指針域ElemType data;ElemType num;Node<ElemType> *next;/構(gòu)造函數(shù)：Node();/無參數(shù)的構(gòu)造函數(shù)Node(ElemType item, ElemType iteml ,Node<ElemType> *link = NULL);/已知數(shù)數(shù)據(jù)元素值和指針建立結(jié)構(gòu);/結(jié)點類的實現(xiàn)部分 template<class ElemType

24、> Node<ElemType>:Node()/操作結(jié)果：構(gòu)造指針域為空的結(jié)點 (next = NULL;)template<class ElemType>Node<ElemType>:Node(ElemType item, ElemType iteml,Node<ElemType>*link)/操作結(jié)果：構(gòu)造一個數(shù)據(jù)域為item和iteml,指針域為link的結(jié)點data = item;num = iteml;next = link; #endif3.算法設(shè)計編寫一個函數(shù)實現(xiàn)結(jié)點的刪除與輸入工作，另編寫一個主函數(shù)main ()完成鏈 表的

25、創(chuàng)建與函數(shù)調(diào)用工作。(1)插入template <class ElemType>Status LinkList<ElemType>:lnsert(int position, const ElemType &e)/操作結(jié)果：在線性表的第position個位置前插入元素e/ position 的取值范圍為 1WpositionWLength()+1/ position合法時返回SUCCESS,否則函數(shù)返回RANGE_ERROR(if (position < 1 | position > Length() + 1) “position 范圍錯return

26、RANGE_ERROR; / 位置不合法) else/ position 合法Node<ElemType> *tmpPtr;/取出指向第position-1個結(jié)點的指針tmpPtr = GetElemPtr(position - 1);Node<ElemType> *newPtr;if(position>Length()/如果插入尾結(jié)點，則域指針指向首元結(jié)點newPtr = new Node<ElemType>(e, position,head->next); elsenewPtr= new Node<ElemType>(e, pos

27、ition,tmpPtr->next);/ 生成新結(jié)點/將tmpPtr插入到鏈表中/設(shè)置當(dāng)前位置的序號設(shè)置指向當(dāng)前位置的指針/插入成功后元素個數(shù)加1tmpPtr->next = newPtr; curPosition = position; curPtr = newPtr;count+;return SUCCESS;)(2)刪除template <class ElemType>Status LinkList<ElemType>:Delete(int position, ElemType &e)操作結(jié)果：刪除線性表的第position個位置的元素，并用

28、e返回其值,/ position 的取值范圍為 1WpositionWLength。,/ position合法時函數(shù)返回SUCCESS,否則函數(shù)返回RANGE.ERROR/ position 合法Node<ElemType> *tmpPtr;if(position=1)/如果刪除首元結(jié)點，取出指向尾結(jié)點的指針tmpPtr=GetElemPtr(Length();else/取出指向第position-1個結(jié)點的指針tmpPtr = GetElemPtr(position - 1);Node<ElemType> *nextPtr = tmpPtr->next;if(p

29、osition=1)頭結(jié)點與新的首元結(jié)點相連head->next=nextPtr->next; / nextPtr 為 tmpPtr 的后繼 tmpPtr->next = nextPtr->next;II 刪除結(jié)點e = nextPtr->data;用e返回被刪結(jié)點元素值if (position = Length()/設(shè)置當(dāng)前位置的序號 設(shè)置指向當(dāng)前位置的指針 II刪除尾結(jié)點,當(dāng)前結(jié)點變?yōu)轭^結(jié)點curPosition = 1;curPtr = head->next;)else/刪除非尾結(jié)點，當(dāng)前結(jié)點變?yōu)榈趐osition個結(jié)點curPosition = po

30、sition; curPtr = tmpPtr->next;)count-;delete nextPtr;return SUCCESS;)(3)出圈次序的算法描述template <class ElemType>/設(shè)置當(dāng)前位置的序號II設(shè)置指向當(dāng)前位置的指針I(yè)I刪除成功后元素個數(shù)減1II釋放被刪結(jié)點int LinkList<ElemType>:Pass(int position , int n ,ElemType &e)int i;curPtr = GetElemPtr(position);curPosition=position;for(i=0;i<

31、;n-1 ;i+)curPtr = curPtr->next;curPosition+;)coutvvcurPtr->numvv" ”；e=curPosition;當(dāng)前指針指向position記錄當(dāng)前位置依次報數(shù)直到n輸出起始位置)(4)主程序#includeHassistance.hH#include"lk_list.h"int POS(int n,int i)計算當(dāng)前位置的函數(shù)jf(n%i=O) n=i;else n=n%i;return n;int main() int tmp,i,k=O,n=O,key;int pos;LinkList<

32、int> Ic;創(chuàng)建空鏈表while(n<1|n>20)限制人數(shù)cout<<”請輸入人數(shù)，人數(shù)小于20:”；cin»n;coutvv”請輸入每個人的密碼，用空格分隔，密碼大于0:“vvendl;for(i=1;i<=n;i+)cin»tmp;插入尾結(jié)點lc.lnsert(i,tmp); 1while(k<1|k>n) coutvv”從幾號開始？ 0<K<=H«n<<,1:11;cin»k;coutvv"出列順序:"；for(i=n;i>0;i-)if(i=n

33、)一開始，從k開始報數(shù)出列計算出列位置刪除當(dāng)前結(jié)點，當(dāng)前指針指向當(dāng)前位置的下游取當(dāng)前位置的密碼從當(dāng)前位置開始報數(shù)，并出列計算出列位置lc.GetElem(k,key); lc.Pass(k,key,tmp); pos=POS(tmp,i); lc.Delete(pos,tmp);)elselc.GetElem(key); lc.Pass(key,tmp); pos=POS(tmp,i); lc.Delete(pos,tmp); ) ) system(Hpause"); return 0;)九：心得體會通過做這次實驗，發(fā)現(xiàn)自己在數(shù)據(jù)結(jié)構(gòu)這門課程中還有很多不足，有很多知識 還沒掌握實驗的

34、時候出現(xiàn)了很多錯誤，有很多知識還不能運(yùn)用，最后在同學(xué)的幫助 下，終于完成了任務(wù)。因為以前的C語言沒學(xué)好，這學(xué)期的數(shù)據(jù)結(jié)構(gòu)感到學(xué)的時候有些吃力，在實驗 的時候，我所以的不足都體現(xiàn)出來了，如果沒有同學(xué)的幫助，我程序中的問題可能 需要很長時間才會解決，所以以后還是要努力趕上來。在這次實驗中，我也得到了很多收獲，比如鏈表的應(yīng)用，以前總是弄不明白，通過這次實驗，在鏈表這一方面我懂了很多，但還不能運(yùn)用自如，需要更多的練習(xí)。這次實驗，對本學(xué)期所學(xué)習(xí)的內(nèi)容也是一次鞏固，讓我加深了對學(xué)過知識的記 憶?？傊@次實驗讓我既發(fā)現(xiàn)了自身的很多不足，又增長了很多知識。#include<stdio .h>#i

35、nclude<malloc.h>#defuie TRUE 1#defuie FALSE 0typedef stnict LNodehit data;stnict LNode *next; LNode, *LnikedList;LnikedList LinkedListImt()LinkedList L;L=(LinkedList)malloc(sizeof(LNode);L->next=NULL;return L;void LinkedListCleai(LuikedList L)L->next=NULL;pnntf("鏈表已經(jīng)清空n)mt LinkedLis

36、tEnipty(LnikedList L) if(L->next=NULL) return TRUE;else return FALSE;void LinkedListTraverse(LHikedList L)LinkedList p;p=L->next;if(p=NULL) pnntf("單鏈表為空表 n”)；elsepnntf("鏈表中的元素為:n");wliile(p!=NULL)priiitf(M%d fp->data); p=p->next;mt LinkedListLength (LinkedList L) LinkedLis

37、t p;intj;p=L->next;J=0；while(p!=NULL)j+；p=p->next; return j;LnikedList LuikedListGet(LnikedList L,int i)LinkedList j;p=L->next; j=l;while (p!=NULL && j<i)p=p->next; j+; if (j=i) return p; else return NULL;mt LinkedListLocate (LinkedList L. int x) LinkedList p=L->next; j=l;w

38、hile ( p!=NULL && p->data != x) p=p->next;j+; if(p) retuinj;else return 0;void LinkedListIiiseit(LHikedList L, mt i. int x) LinkedList p,s;intj;j=l；P=L；while(p&&j<i)p=p->next;j+;if(p=NULL|j>i)pnntf("插入位置不正確11");else s=(LNode *)malloc(sizeof(LNode);s->data=

39、x;s->next=p->next;p->next=s;pnntf("%d已插入到鏈表中11"不)；void LinkedListDel(LHikedList Ljnt i) LuikedList p,q;intj;j=l；P=L；wlule(p->next&&j<i)p=p->next;j+; if(p->next=NULL) pnntf("刪除位置不正確n")； else q=p->next;p->next=q->next;fiee(q);printf("第d個元素已從鏈表中刪除)LuikedList LuikedListCreat() LuikedList L=LuikedListIiiit(),p,i;mt x;r=L;pnn氓”請依次輸入鏈表中的元素，輸入負(fù)數(shù)時結(jié)束 scanfC%d&