鏈表基本操作實驗報告.doc

1、。實驗 2鏈表基本操作實驗一、實驗目的1 定義單鏈表的結點類型。2 熟悉對單鏈表的一些基本操作和具體的函數(shù)定義。3 通過單鏈表的定義掌握線性表的鏈式存儲結構的特點。二、實驗內容與要求該程序的功能是實現(xiàn)單鏈表的定義和主要操作。 如：單鏈表建立、輸出、插入、刪除、查找等操作 。該程序包括單鏈表結構類型以及對單鏈表操作的具體的函數(shù)定義和主函數(shù)。程序中的單鏈表（帶頭結點）結點為結構類型，結點值為整型。要求：同學們可參考指導書實驗 2 程序、教材算法及其他資料編程實現(xiàn)單鏈表相關操作。必須包括單鏈表創(chuàng)建、輸出、插入、刪除操作，其他操作根據(jù)個人情況增減。三、 算法分析與設計。1. 創(chuàng)建單鏈表：LinkedL

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

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

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

5、也對程序做了仔細的分析，對單鏈表創(chuàng)建、插入、刪除算法畫了詳細的N-S 流程圖。4。六、C語言版原代碼# include# include/*定義 ElemType 為 int類型 */typedef int ElemType;# define TRUE 1# define FALSE 0# define NULL 0# define flag -1/* 單鏈表的結點類型 */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(鏈表已經清空 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 個元素已從鏈表中刪除 n,i);Link

10、edList LinkedListCreat()LinkedList L=LinkedListInit(),p,r;ElemType x;r=L;printf(請依次輸入鏈表中的元素，輸入-1 結束 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(請選擇要進行的操作 n);printf(-n);printf(1.初始化 2.清空 3.求鏈表長度 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(鏈表長度為 %dn,LinkedListLength(L);break;case 4:if(LinkedListEmpty(L)printf(鏈表為空 n);else printf(鏈表非空 n);break;case 5:LinkedListTraverse(L);break;case 6:printf( 請輸入待查詢元素在鏈表中的位置 :); scanf(%d,&i);p=LinkedListGet(L,i);

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