鏈表基本操作實(shí)驗(yàn)報(bào)告.doc

1、。實(shí)驗(yàn) 2鏈表基本操作實(shí)驗(yàn)一、實(shí)驗(yàn)?zāi)康? 定義單鏈表的結(jié)點(diǎn)類(lèi)型。2 熟悉對(duì)單鏈表的一些基本操作和具體的函數(shù)定義。3 通過(guò)單鏈表的定義掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)。二、實(shí)驗(yàn)內(nèi)容與要求該程序的功能是實(shí)現(xiàn)單鏈表的定義和主要操作。 如：?jiǎn)捂湵斫?、輸出、插入、刪除、查找等操作 。該程序包括單鏈表結(jié)構(gòu)類(lèi)型以及對(duì)單鏈表操作的具體的函數(shù)定義和主函數(shù)。程序中的單鏈表（帶頭結(jié)點(diǎn)）結(jié)點(diǎn)為結(jié)構(gòu)類(lèi)型，結(jié)點(diǎn)值為整型。要求：同學(xué)們可參考指導(dǎo)書(shū)實(shí)驗(yàn) 2 程序、教材算法及其他資料編程實(shí)現(xiàn)單鏈表相關(guān)操作。必須包括單鏈表創(chuàng)建、輸出、插入、刪除操作，其他操作根據(jù)個(gè)人情況增減。三、 算法分析與設(shè)計(jì)。1. 創(chuàng)建單鏈表：LinkedL

2、ist LinkedListCreat( )創(chuàng)建鏈表函數(shù)LinkedList L=LinkedListInit(),p, r;調(diào)用初始化鏈表函數(shù)r=L; r指向頭結(jié)點(diǎn)使用 malloc 函數(shù)動(dòng)態(tài)分配存儲(chǔ)空間， 指針 p 指向新開(kāi)辟的結(jié)點(diǎn)， 并將元素存放到新開(kāi)辟結(jié)點(diǎn)的數(shù)據(jù)域，p=(LinkedList)malloc(sizeof(LNode);p-data=x;r-next=p;將新的結(jié)點(diǎn)鏈接到頭結(jié)點(diǎn)r 之后r=p;r指向 p 結(jié)點(diǎn)scanf(%d,&x);滿(mǎn)足條件循環(huán)輸入鏈表元素while(x!=flag)當(dāng)輸入不為 -1 時(shí)循環(huán)r-next=NULL; return L;將鏈表結(jié)尾賦空值，返

3、回頭結(jié)點(diǎn)L頭結(jié)點(diǎn) LL.AnA1A2。1。2. 單鏈表插入void LinkedListInsert(LinkedList L,int i,ElemType x)鏈表插入函數(shù)（L 頭指針， i 插入位置， x 插入元素）LinkedList p,s;定義結(jié)構(gòu)體類(lèi)型指針p,sj=1;p=L;定義整型j 計(jì)數(shù)，尋找插入位置，p 指針指向頭結(jié)點(diǎn)p=p-next;j+;滿(mǎn)足條件時(shí)p 指針后移， j 自加 1while(p&ji)當(dāng) p 為真且 ji時(shí)循環(huán)p=NULL|jdata=x;s-next=p-next; p-next=s;3. 單鏈表的刪除： pbcp-next=p-next-next;。2。

4、四、 運(yùn)行結(jié)果1. 單鏈表初始化2. 創(chuàng)建單鏈表3. 求鏈表長(zhǎng)度4. 檢查鏈表是否為空5. 遍歷鏈表6. 從鏈表中查找元素7. 從鏈表中查找與給定元素值相同的元素在順序表中的位置。3。8. 向鏈表中插入元素插入元素之后的鏈表9. 從鏈表中刪除元素刪除位置為 6 的元素 ( 是 3)10. 清空單鏈表五、實(shí)驗(yàn)體會(huì)經(jīng)過(guò)這次單鏈表基本操作實(shí)驗(yàn)， 自己的編程能力有了進(jìn)一步的提高， 認(rèn)識(shí)到自己以前在思考一個(gè)問(wèn)題上思路不夠開(kāi)闊， 不能靈活的表達(dá)出自己的想法， 雖然在打完源代碼之后出現(xiàn)了一些錯(cuò)誤， 但是經(jīng)過(guò)認(rèn)真查找、 修改，最終將錯(cuò)誤一一修正，主要是在寫(xiě)算法分析的時(shí)候出現(xiàn)了障礙， 經(jīng)過(guò)從網(wǎng)上查找資料， 自己

5、也對(duì)程序做了仔細(xì)的分析，對(duì)單鏈表創(chuàng)建、插入、刪除算法畫(huà)了詳細(xì)的N-S 流程圖。4。六、C語(yǔ)言版原代碼# include# include/*定義 ElemType 為 int類(lèi)型 */typedef int ElemType;# define TRUE 1# define FALSE 0# define NULL 0# define flag -1/* 單鏈表的結(jié)點(diǎn)類(lèi)型 */typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkedList;/* 初始化單鏈表 */LinkedList LinkedListInit()L

6、inkedList L;L=(LinkedList)malloc(sizeof(LNode);L-next=NULL;return L;/* 清空單鏈表 */void LinkedListClear(LinkedList L)L-next=NULL;printf(鏈表已經(jīng)清空 n);/* 檢查單鏈表是否為空 */int LinkedListEmpty(LinkedList L)if(L-next=NULL) return TRUE;else return FALSE;/* 遍歷單鏈表 */void LinkedListTraverse(LinkedList L)LinkedList p;。5。

7、p=L-next;if(p=NULL) printf(單鏈表為空表 n);elseprintf(鏈表中的元素為： n);while(p!=NULL)printf(%d ,p-data); p=p-next;printf(n);int LinkedListLength (LinkedList L)LinkedList p;int j;p=L-next;j=0;while(p!=NULL)j+;p=p-next;return j;LinkedList LinkedListGet(LinkedList L,int i)LinkedList p;int j;p=L-next;j=1;while(p!=

8、NULL&jnext;j+;if(j=i) return p;else return NULL;int LinkedListLocate(LinkedList L,ElemType x)LinkedList p;int j;p=L-next;j=1;while(p!=NULL&p-data!=x)p=p-next;j+;if(p) return j;else return 0;void LinkedListInsert(LinkedList L,int i,ElemType x)LinkedList p,s;int j;j=1;p=L;。6。while(p&jnext;j+;if(p=NULL

9、|ji)printf(插入位置不正確 n);elses=(LNode *)malloc(sizeof(LNode);s-data=x;s-next=p-next;p-next=s;printf(%d已插入到鏈表中 n,x);void LinkedListDel(LinkedList L,int i)LinkedList p,q;int j;j=1;p=L;while(p-next&jnext;j+;if(p-next=NULL)printf(刪除位置不正確 n);elseq=p-next;p-next=q-next;free(q);printf(第%d 個(gè)元素已從鏈表中刪除 n,i);Link

10、edList LinkedListCreat()LinkedList L=LinkedListInit(),p,r;ElemType x;r=L;printf(請(qǐng)依次輸入鏈表中的元素，輸入-1 結(jié)束 n);scanf(%d,&x);while(x!=flag)p=(LinkedList)malloc(sizeof(LNode);p-data=x;r-next=p;r=p;scanf(%d,&x);r-next=NULL;return L;int scan()。7。int d;printf(請(qǐng)選擇要進(jìn)行的操作 n);printf(-n);printf(1.初始化 2.清空 3.求鏈表長(zhǎng)度 4.檢

11、查鏈表是否為空 n);printf(-n);printf(5.遍歷鏈表 6.從鏈表中查找元素 n);printf(-n);printf(7.從鏈表中查找與給定元素值相同的元素在順序表中的位置n);printf(-n);printf(8.向鏈表中插入元素9.從鏈表中刪除元素10 創(chuàng)建線性表 n);printf(-n);printf(其他鍵退出。 n);printf(輸入 :);scanf(%d,&d);return(d);main()int quit=0;int i,locate;ElemType e;LinkedList L,p;while(!quit)switch(scan()case 1:

12、L=LinkedListInit();printf(n);break;case 2:LinkedListClear(L);printf(n);break;case 3:printf(鏈表長(zhǎng)度為 %dn,LinkedListLength(L);break;case 4:if(LinkedListEmpty(L)printf(鏈表為空 n);else printf(鏈表非空 n);break;case 5:LinkedListTraverse(L);break;case 6:printf( 請(qǐng)輸入待查詢(xún)?cè)卦阪湵碇械奈恢?:); scanf(%d,&i);p=LinkedListGet(L,i);

13、if(p) printf(鏈表第 %d個(gè)元素的值為 :%dn,i,p-data);else printf(查詢(xún)位置不正確 n);break;case 7:printf(請(qǐng)輸入待查詢(xún)?cè)氐闹?);scanf(%d,&e);locate=LinkedListLocate(L,e);if(locate)printf(%d在鏈表中的位置是 :%dn,e,locate);else printf(鏈表中沒(méi)有值為 %d的元素 n,e);break;case 8:printf(請(qǐng)輸入插入元素的位置和值( 中間以空格或回車(chē)分隔 ):n);。8。scanf(%d%d,&i,&e);LinkedListInsert(L,i,e);break;case 9:if(LinkedListLength(L