實驗二單鏈表基本操作

1、實驗二單鏈表根本操作一實驗?zāi)康?. 學(xué)會定義單鏈表的結(jié)點類型，實現(xiàn)對單鏈表的一些根本操作和具體 的函數(shù)定義，了解并掌握單鏈表的類定義以與成員函數(shù)的定義與調(diào)用。2. 掌握單鏈表根本操作與兩個有序表歸并、 單鏈表逆置等操作的實現(xiàn)。二實驗要求1. 預(yù)習(xí)C語言中結(jié)構(gòu)體的定義與根本操作方法。2對單鏈表的每個根本操作用單獨的函數(shù)實現(xiàn)。3. 編寫完整程序完成下面的實驗內(nèi)容并上機運行。4. 整理并上交實驗報告。三實驗內(nèi)容1.編寫程序完成單鏈表的如下根本操作：(1) 初始化單鏈表La。(2) 在La中第i個元素之前插入一個新結(jié)點。(3) 刪除La中的第i個元素結(jié)點。(4) 在La中查找某結(jié)點并返回其位置。(5)

2、 打印輸出La中的結(jié)點元素值。2 .構(gòu)造兩個帶有表頭結(jié)點的有序單鏈表 La、Lb，編寫程序?qū)崿F(xiàn)將La、 Lb合并成一個有序單鏈表Lc。合并思想是：程序需要3個指針：pa、pb、pc,其中pa, pb分別指 向La表與Lb表中當(dāng)前待比擬插入的結(jié)點，pc指向Lc表中當(dāng)前最后一個結(jié) 點。依次掃描La和Lb中的元素，比擬當(dāng)前元素的值，將較小者到*pc之后, 如此重復(fù)直到La或Lb完畢為止，再將另一個鏈表余下的內(nèi)容到 pc所指的 結(jié)點之后。3.構(gòu)造一個單鏈表L，其頭結(jié)點指針為head，編寫程序?qū)崿F(xiàn)將L逆置。 即最后一個結(jié)點變成第一個結(jié)點，原來倒數(shù)第二個結(jié)點變成第二個結(jié)點， 如此等等。四思考與提高1. 如

3、果上面實驗內(nèi)容2中合并的表內(nèi)不允許有重復(fù)的數(shù)據(jù)該如何操作？2. 如何將一個帶頭結(jié)點的單鏈表 La分解成兩個同樣結(jié)構(gòu)的單鏈表Lb， Lc，使得Lb中只含La表中奇數(shù)結(jié)點，Lc中含有La表的偶數(shù)結(jié)點？1 編寫程序完成單鏈表的如下根本操作：初始化單鏈表La。(2) 在La中第i個元素之前插入一個新結(jié)點(3) 刪除La中的第i個元素結(jié)點。(4) 在La中查找某結(jié)點并返回其位置。打印輸出La中的結(jié)點元素值。#in clude#in clude#i nclude #defi ne OK 1#defi ne ERROR 0 typedef int Status; typedef int ElemType;/

4、定義存儲結(jié)構(gòu)typedef struct Lno deint data; /*每個元素數(shù)據(jù)信息*/struct Lnode *n ext; /*存放后繼元素的地址 */ LNode,*L in kList;int mai n()void Create_L(L in kList &L,i nt n);void Prin t_L(Li nkList L);Status List In sert_L(L in kList &L,i nt i,ElemType e);Status ListDelete_L(LinkList &L,int i,ElemType &e);Status Find_L(Lin

5、kList L,int e);LinkList La;/創(chuàng)建單鏈表Laint n;printf(請輸入鏈表La中的元素個數(shù):n);scan f(%d, &n);Create_L(La ,n);/初始化單鏈表printf(”現(xiàn)在La中的元素為:n);Prin t_L(La);printf(-nn “);n);prin tf(現(xiàn)在準(zhǔn)備插入元素，請輸入插入位置與所插入元素的值int i,e;scanf(%d %d，&i,&e);List In sert_L(La,i,e);printf(”插入后La中的元素為：n);Prin t_L(La);printf(-nn “);prin tf(現(xiàn)在準(zhǔn)備刪除元

6、素，請輸入刪除位置 n);scan f(%d, &i);ListDelete_L(La,i,e);printf(刪除后La中的元素為:n);Prin t_L(La);printf(nn);printf(請輸入所要查找元素的值:n);scan f(%d, &e);Fin d_L(La,e);printf(所要查找元素的位置為：dn,Fi nd_L(La,e); void Create_L(LinkList &L,int n)int j=1;L=(Li nkList)malloc(sizeof(L no de);L- next =NULL;先建立一個帶頭結(jié)點的單鏈線性表Lfor(i nt i=n

7、;i0;-i)Lin kList p=(L in kList)malloc(sizeof(L no de);printf(請輸入鏈表La中的第d個元素:n,j+);scan f(%d，& p-data);p-n ext=L-n ext;L-n ext =p;(逆序?qū)崿F(xiàn))/*Lin kList q=L; for(i nt i=1;in ext=p;p- next=NULL;q=q-n ext ;printf(”請輸入鏈表La中的第d個元素:n,i);scan f(%d,&p-data);(正序?qū)崿F(xiàn))*/初始化單鏈表/輸出單鏈表void Prin t_L(Li nkList L)Lin kList

8、 p;p=L-n ext;while(p)prin tf(%d ,p-data );p=p-n ext;prin tf(n);/在單鏈表L的第i個位置前插入元素eStatus List In sert_L(L in kList &L,i nt i,ElemType e)Lin kList p=L;int j=0;while(p&jn ext; +j;if(!p|ji-1) return ERROR;Lin kList s=(L in kList)malloc(sizeof(LNode); s-data=e; s-n ext=p-n ext;p_n ext=s;return OK; /ListI

9、 nsert_L/刪除單鏈表L中第i個位置上的元素Status ListDelete_L(LinkList &L,int i,ElemType &e) Lin kList p=L;int j=0;while( p- next & jn ext; +j;if(!p- next|ji-1)return ERROR;Lin kList q=p-n ext; p-n ext=q-n ext; e=q_data;free(q);return OK;/Li nkDelete_L/*查找元素并返回位置*/Status Fi nd_L(L in kList L,i nt e)Lin kList p=L-n e

10、xt;int j=1;while(p-data!=e&p-n ext) p=p-n ext; j+;if(p-data=e) retur n j;elseprintf(無當(dāng)前元素n);return ERROR;if(!p)printf(無當(dāng)前元素n);return ERROR;/定位2 .構(gòu)造兩個帶有表頭結(jié)點的有序單鏈表 La、Lb,編寫程序?qū)崿F(xiàn)將La、Lb合并 成一個有序單鏈表Lc。合并思想是：程序需要3個指針：pa、pb、pc，其中pa，pb分別指向La表與Lb表中當(dāng)前待比擬插入的結(jié)點，pc指向Lc表中當(dāng)前最后一個結(jié)點。依次掃描La和Lb中的元素，比擬當(dāng)前元素的值，將較小者到*pc之后，如

11、此重復(fù)直到La 或Lb完畢為止，再將另一個鏈表余下的內(nèi)容到pc所指的結(jié)點之后。#in clude#in clude#i nclude #defi ne OK 1#defi ne ERROR 0typedef int Status;typedef int ElemType;/定義存儲結(jié)構(gòu)typedef struct Lno deint data; /*每個元素數(shù)據(jù)信息*/struct Lnode *n ext; /*存放后繼元素的地址 */ LNode,*L in kList;void mai n()void Create_L(L in kList &L,i nt n);void Prin t_

12、L(Li nkList L);void MergeList_L(LinkList &La, LinkList &Lb,LinkList &Lc);Lin kList La, Lb,Lc;創(chuàng)建單鏈表 La,Lb,Lcint n;printf(請輸入鏈表La中的元素個數(shù):n);scan f(%d, &n);Create_L(La ,n);/初始化單鏈表printf(”現(xiàn)在La中的元素為:n);Prin t_L(La);printf(請輸入鏈表Lb中的元素個數(shù):n);scan f(%d, &n);Create_L(Lb ,n);/初始化單鏈表printf(”現(xiàn)在Lb中的元素為:n);Prin t_L

13、(Lb);Create_L(Lc,O);printf(-nn “);printf(開始合并:n);MergeList_L(La, Lb,Lc);printf(-nn “);printf(合并后，Lc的元素為n);Prin t_L(Lc);void Create_L(LinkList &L,int n)int j=1;L=(Li nkList)malloc(sizeof(L no de);L- next =NULL;先建立一個帶頭結(jié)點的單鏈線性表Lfor(i nt i=n ;i0;-i)Lin kList p=(L in kList)malloc(sizeof(L no de);printf(請

14、輸入鏈表中的第d個元素：n,j+);scan f(%d，& p-data);p-n ext=L-n ext;L_n ext =p;(逆序?qū)崿F(xiàn))/*Lin kList q=L;for(i nt i=1;in ext=p;p- next=NULL;q=q_n ext ;printf(請輸入鏈表La中的第d個元素:n,i);scan f(%d,&p-data);/( 正序?qū)崿F(xiàn))*/初始化單鏈表有序單鏈表La和Lb的歸并void MergeList_L(LinkList &La, LinkList &Lb,LinkList &Lc)Lin kList pa=La-n ext;Lin kList pb=

15、Lb-n ext;Lin kList pc;Lc=pc=La;while (pa&pb)if (pa-datadata)pc-n ext=pa; pc=pa;pa=pa-n ext;else pc- n ext=pb; pc=pb;pb=pb-n ext; pc- n ext=pa?pa:pb;free(Lb);prin tf(ppppppppppppppp);/MergeList/輸出單鏈表void Prin t_L(Li nkList L)Lin kList p;p=L-n ext;while(p)prin tf(%d ,p-data );p=p-n ext;prin tf(n);3構(gòu)造一

16、個單鏈表L,其頭結(jié)點指針為head，編寫程序?qū)崿F(xiàn)將L逆置。即最后 一個結(jié)點變成第一個結(jié)點，原來倒數(shù)第二個結(jié)點變成第二個結(jié)點，如此等等。#in clude#in clude#i nclude /定義存儲結(jié)構(gòu)typedef struct Lno deint data; /*每個元素數(shù)據(jù)信息*/struct Lnode *n ext; /*存放后繼元素的地址 */ LNode,*L in kList;void mai n()void Create_L(L in kList &L,i nt n);void Prin t_L(Li nkList L);void ReverseList(L in kLis

17、t L);LinkList La;/創(chuàng)建單鏈表Laint n;printf(”請輸入鏈表La中的元素個數(shù)：n);scan f(%d, &n);Create_L(La ,n);/初始化單鏈表printf( 現(xiàn)在La中的元素順序為:n); Prin t_L(La);printf(-nn “);ReverseList(La);printf(逆置后，La的元素順序為:n);Prin t_L(La);void Create_L(LinkList &L,int n)int j=1;L=(Li nkList)malloc(sizeof(L no de);L- next =NULL;先建立一個帶頭結(jié)點的單鏈線性表Lfor(i nt i=n ;i0;-i)Lin kList p=(L in kList)malloc(sizeof(L no de);printf(請輸入鏈表中的第d個元素：n,j+);scan f(%d，& p-data);p-n ext=L-n ext;L-n ext =p;/(逆序?qū)崿F(xiàn))/*Lin kList q=L; for(i nt i=1;in ext=p;p- next=NULL;q=q-n ext ;printf(請輸入鏈表La中的第d個元素:n,i);scan f(%d,&p-data);/( 正序?qū)崿F(xiàn))*/初始化單鏈表/輸