3數(shù)據(jù)結(jié)構(gòu)實(shí)驗鏈表答案

1、實(shí)驗報告院（系）：信息科學(xué)與技術(shù)學(xué)院課程名稱：數(shù)據(jù)結(jié)構(gòu)日期:班級專業(yè)學(xué)號實(shí)驗室姓名計算機(jī)號實(shí) 驗 名 稱所 用 軟 件 實(shí) 驗 目 的線性鏈表的運(yùn)算V C 或 TC1.2.3.掌握線性鏈表的基本概念掌握線性鏈表的建立、插入和刪除等方法。 掌握線性鏈表的基本算法。成績評定教師簽名實(shí) 驗 總 結(jié)#i nclude stdio.h#i nclude stdlib.htyp edef char elemt ype;typ edef struct no deelemt ype data;struct node *n ext; NODE,*NODE PTR;NODEPTR一、程序:createlistf(

2、) char ch;NODE PTR head;NODE *p; head=(NODE PTR )malloc(sizeof(NODE); head-n ext=0;ch=getchar(); while(ch!=n) p=(NODE *)malloc(sizeof(NODE); p-data=ch;p-n ext=head-n ext; head-n ext=p;ch=getchar();return (head);/* q指向p的后繼結(jié)點(diǎn)*/*修改P結(jié)點(diǎn)的指針域*/*刪除并釋放結(jié)點(diǎn)*/int In sLi nkList(NODE *p, char x)NODE *s;/*定義指向結(jié)點(diǎn)類型的

3、指針*/s=(NODE *)malloc(sizeof(NODE);/*生成新結(jié)點(diǎn)*/s-data=x;s-n ext =p-n ext;p-n ext=s;return 1;void DelL in kList(NODE *p) NODE *q;if(p- next!=0) q=p-n ext;p-n ext=q-n ext; free(q); NODE *lbcz(NODE *h,i nt x) NODE *p;p=h;while (p!=0 & p-data!=x) p=p-n ext;return( p);void prin tl in k(NODE *h)NODE *p;p=h-n

4、ext;prin tf(n);while (p !=0)prin tf(%c, p-data);p=p-n ext;prin tf(n);void mai n()NODE *h,* p;charx;printf(n頭插法建立單鏈表，應(yīng)包含字符a,以回車作為結(jié)束符n);h=createlistf();printf(n建立的單鏈表為n);prin tl in k(h);printf(n在鏈表中查找字符an);p=lbcz(h,a);printf(n將字符k插入到字符a后面n);In sLi nkList( p,k);printf(n插入字符后的鏈表為n);prin tl in k(h);print

5、f(n輸入鏈表中被刪除字符的前一個字符n);scan f(%c, &x);p=lbcz(h,x);printf(n刪除該字符后的一個字符n);DelLi nkList( p);printf(n刪除字符后的鏈表為n);prin tl in k(h);知甜建立單班衷.應(yīng)包含宇弘.呃M作寵結(jié)朿利 ocbriiruhbairhf brR靦入宇符后射坯衷為Hirhfhck輸入缽表中被刑璨三蔚的前一八字符lA州除該字軒G的一字符刪矗字符后閑縫表為二、源代碼以及輸入數(shù)據(jù)輸出結(jié)果為:#in clude stdio.h#i nclude stdlib.htyp edef int elemt ype;typ ed

6、ef struct no deelemt ype data; struct node *n ext; NODE,*NODE PTR;NODE PTRcreatelistf()int ch;NODE PTR head;NODE *p;head=(NODE PTR )malloc(sizeof(NODE); head-n ext=0;sca nf(%d,&ch);while(ch!=0) p=(NODE *)malloc(sizeof(NODE); p-data=ch;p-n ext=head-n ext;head-n ext=p;/*定義指向結(jié)點(diǎn)類型的指針 */scan f(%d，& ch);r

7、eturn (head);int In sLi nkList(NODE *h, i nt x)NODE *s,*q,* p;p=h;q=p;while( p-n ext!=NULL & p-data next;0作為結(jié)束n”);用先傭法建廿序鍍龕 注意輸入數(shù)字的順序與得到煩序相民 如忙勺結(jié)束98 87 34 76 65 52 41 32 0a立的鏈表為32 41 52 65 7& 4 87 99血詬的鏈表為32 41 52 55 65 76 84 37 ?S三、已知單鏈表L,寫一算法，刪除其重復(fù)結(jié)點(diǎn)。算法思路：用指針P指向第一個數(shù)據(jù)結(jié)點(diǎn)，從它的后繼結(jié)點(diǎn)開始到表的結(jié)束，找與其值相同的結(jié)點(diǎn)并刪除之

8、；P指向下一個；依此類推，P指向最后結(jié)點(diǎn)時算法結(jié)束。源程序如下：#in elude stdio.h#i nclude stdlib.htyp edef char elemt ype;typ edef struct no de elemt ype data; struct node *n ext; NODE,*NODE PTR;NODE PTR createlistf() char ch;NODE PTRNODE *p;printf(”printf(”head;頭插法建立鏈表n);請輸入字符串，以回車鍵結(jié)束:head=(NODE PTR )malloc(sizeof(NODE);head-n e

9、xt=0; ch=getchar();while(ch!=n) p=(NODE *)malloc(sizeof(NODE);p-data=ch;p-n ext=head-n ext;head-n ext=p;ch=getchar();return (head);void deLi nkList(NODE PTR H) NODE *p ,*q,*r;p=H-n ext;while (p !=NULL) q=p;while (q- next!=NULL)/ if (q-n ext-data=p-data) r=q-n ext;/q-n ext=r- n ext;free(r);else q=q-n

10、 ext;/while(q- next)p”);指向第一個結(jié)點(diǎn)從*p的后繼開始找重復(fù)結(jié)點(diǎn)找到重復(fù)結(jié)點(diǎn)，用r指向，刪除*rp=p-n ext;/p指向下一個，繼續(xù)/while( p-n ext)void pli nk(NODE *h)NODE *p;p=h-n ext;prin tf(n);while (p !=NULL)prin tf(%c, p-data);p=p-n ext;prin tf(n);void mai n()NODE *h;h=createlistf();printf(建立的鏈表為);pli nk(h);deLi nkList(h);printf(”刪除了重復(fù)結(jié)點(diǎn)的鏈表為”)；

11、pli nk(h);St C;enl s and Sett ingsAdsinist ratd斗袖法建縮表請輸人罕W串.以回車鑲結(jié)fiSDFflSPEEFRS 建立的鏈表齊SAFEEDSAFDSA刪除了重復(fù)結(jié)點(diǎn)的鏈表為SflFEDFres3 any Fey to continue四、設(shè)有兩個單鏈表 A、B,其中元素遞增有序，編寫算法將A B歸并成一個按元素值遞減（允許有相同值）有序的鏈表C,要求用A、B中的原結(jié)點(diǎn)形成，不能重新申請結(jié)點(diǎn)。#i nclude stdio.h#in elude stdlib.htyp edef int elemt ype; typ edef struct node

12、elemt ype data; struct node *n ext; NODE,*NODE PTR;NODE PTR createlistfO/使用尾插法建立線性鏈表 int x;NODE PTR head,r;NODE *p;head=(NODE PTR )malloc(sizeof(NODE); head-n ext=0;r=head;/rprin tf(請輸入整型數(shù)據(jù)到線性表中，scan f(%d, &x);while(x!=-1)作為尾指針-1作為結(jié)束符n);/ p=(NODE *)malloc(sizeof(NODE); p-data=x;r-n ext =p;r=p;scan f

13、(%d，& x);r-n ext=0;return (head);NODE PTR merge(NODE PTR A,NODE PTR B) NODE PTR C;NODE *p ,*q,*s;p=A-n ext;q=B-n ext;C=A;C- next=NULL;free(B);while (p&q) if (p-datadata) s=p;p=p- next; elses=q;q=q- next; s-n ext=C-n ext; C-n ext=s;if (p=NULL) p=q; while (p)/ s=p;p=p-n ext; s-n ext=C-n ext; C-n ext=s

14、; return C;void pli nk(NODE *h)c/while使用-1作為輸入結(jié)束符/ 線性鏈表的合并表的頭結(jié)點(diǎn)從原AB表上摘下較小者 插入到C表的頭部將剩余的結(jié)點(diǎn)一個個摘下插入到C表的頭部*/線性鏈表的輸出047774別Press any kew to contiNODE *p;p=h-n ext;prin tf(n);while (p !=0)prin tf(%d ”,p-data);p=p-n ext;prin tf(n);void mai n()NODE *a,*b;printf(建立有序線性鏈表a和線性鏈表b (升序)n);a=createlistf();b=creat

15、elistf();printf(所建立的線性鏈表a和線性鏈表b分別為：n);pli nk(a);pli nk(b);a=merge(a,b);printf(”合并后的線性鏈表為：n);pli nk(a);841113 IE 3545合并后的線性錐表為;55453635 iS 131211inue五、已知單鏈表表示的線性表中含有兩類的數(shù)據(jù)元素（字母字符，數(shù)字字符）。試設(shè)計算法，按結(jié)點(diǎn)的值將單鏈表拆分成兩個循環(huán)鏈表，分別只含有數(shù)字或字母。要求：利用 原表中的結(jié)點(diǎn)空間作為這兩個表的結(jié)點(diǎn)空間，頭結(jié)點(diǎn)可另開辟空間。#i nclude stdio.h#in elude stdlib.h typ edef

16、char elemt ype; typ edef struct nodeelemt ype data; struct node *n ext; NODE,*NODE PTR;/單鏈表的輸出/使用尾插法建立線性單鏈表NODE PTR createlistfO char x;NODE PTR head,r;NODE *p;head=(NODE PTR )malloc(sizeof(NODE); head-n ext=0;r=head;/r作為尾指針printf(”請輸入字符到線性表中，以回車作為結(jié)束符n);x=getchar();使用回車作為輸入結(jié)束符while(x!=n)/ p=(NODE *)

17、malloc(sizeof(NODE);p-data=x;r-n ext =p;r=p；x=getchar();r-n ext=NULL;return (head);void pli nk(NODE *a)NODE *p;p=a-n ext;prin tf(n);while (p !=NULL)prin tf(%c ”,p-data);p=p-n ext;prin tf(n);void ploo plin k(NODE *a)NODE *p;p=a-n ext;prin tf(n);while (p !=a)prin tf(%c ”,p-data);p=p-n ext;prin tf(n);循

18、環(huán)單鏈表的輸出/線性鏈表的拆分/void chaife n(NODE PTR h) NODE PTR a,b;NODE *ar,*br,* p;if(h-n ext =NULL) retur n ;a=(NODE PTR )malloc(sizeof(NODE);a-n ext=a;/ar=a;b=(NODE PTR )malloc(sizeof(NODE);/b-n ext=b;br=b;p=h-n ext;while( p!=NULL)if(p-data=0 & p-datan ext=p; ar=ar- n ext;else申請a頭結(jié)點(diǎn)申請b頭結(jié)點(diǎn)br-n ext=p ;br=br- n

19、 ext; p=p-n ext;ar-n ext=a;br-n ext=b;printf(”拆分后的線性鏈表為：n);ploop li nk(a);ploop li nk(b);prin tf(n); void mai n()NODE *a;printf(”建立線性鏈表an);a=createlistf();printf(”所建立的線性鏈表a為：n);pli nk(a);prin tf(對線性鏈表進(jìn)行拆分n);chaife n( a);建立踐性鎧表豈請輸入字符到踐性表中，以回車作為結(jié)束符12訐6七5石S日WSfdGh?所建立的線性犍表我為：8ffk5fd61i7fPvessan即 keytoc

20、 0 n t: in lie用參數(shù)傳遞方式：/*已知單循環(huán)鏈表表示的線性表中含有兩類的數(shù)據(jù)元素(字母字符，數(shù)字字 符)。試設(shè)計算法，按結(jié)點(diǎn)的值將單鏈表拆分成兩個循環(huán)鏈表，分別只含有數(shù)字或 字母。要求：利用原表中的結(jié)點(diǎn)空間作為這兩個表的結(jié)點(diǎn)空間，頭結(jié)點(diǎn)可另開辟空 間。*/#i nclude stdio.h#i nclude stdlib.h#defi ne NULL 0typ edef char elemt ype;typ edef struct nodeelemt ype data;struct node *next;/頭插法建立循環(huán)單鏈表 NODE,*NODE PTR;NODE PTR cr

21、eatelistfOchar ch;NODE PTR head;NODE *p;head=(NODE PTR )malloc(sizeof(NODE);head- next=head;/建立循環(huán)空鏈表ch=getchar();while(ch!=n) p=(NODE *)malloc(sizeof(NODE);p-data=ch;p-n ext=head-n ext;head-n ext=p;ch=getchar();return(head);void chaife n(N ODE PTR h,NODE PTR *a,NODE PTR *b) II 線性鏈表的拆分 NODE *ar,*br,* p;if(h-n ext=h) return ;II 空表返回(*a)=(NODEPTR )malloc(sizeof(NODE);