單鏈表的操作實現(xiàn)實驗報告

1、單鏈表的操作實現(xiàn)實驗報告單鏈表的操作實現(xiàn)實驗報告單鏈表的操作實現(xiàn)實驗報告信息學院數(shù)據(jù)結構上機實驗報告學號：104100058姓名：趙德剛班級：10A實驗時間：年月日實驗地址：同析3號樓開發(fā)環(huán)境：C+課程名稱：數(shù)據(jù)結構-C語言描述實驗性質：綜合性實驗設計性實驗考據(jù)明驗實驗內容：單鏈表的實現(xiàn)題目本源：教材頁題教師補充自選題目主要功能描述：鏈表的初始化、鏈表的創(chuàng)辦（頭部插入法、尾部插入法）、求表長、查找（按值查找、挨次號查找）、插入、刪除、輸出、兩個有序單鏈表的合并等。設計解析：初始化：為單鏈表申請頭結點空間，將單鏈表設置為空；創(chuàng)辦：（1）頭部插入法：（a）初始化空表；（b）申請新結點并賦值；（c）

2、插入新結點；（d）插入第i個元素。（2）尾部插入法：(a)建空表（b）申請結點并賦值；（c）插入第一個結點；（d）r-next=s,r=s;表長：從表頭開始，將指針依次指向各個結點，向到達p-next=NULL為止，用j來計數(shù)。查找：（1）按值查找：在表中查找第i個結點，找到就返回該結點的儲藏地址，用j來儲藏掃描過的結點數(shù)（j的初值為0），但j=i時，結束。（2）挨次號查找：從表中第一個結點開始，當key等于查找到的元素的數(shù)據(jù)時停止查找。插入：在單鏈表中第i-1個結點并由指針指示，申請結點空間q，將數(shù)據(jù)域置為x，更新指針。刪除：重新結點開始，刪除第i個結點并釋放空間；輸出：當表不為空時，依次輸

3、出表中元素；合并：與次序表相同，只需為新的結點申請一個空間。典型測試數(shù)據(jù)輸入：輸入數(shù)據(jù)個數(shù)：4輸出：1，2，3，4預期結果：基本實現(xiàn)了單鏈表的基本數(shù)據(jù)：1，2，3，4各種操作。程序及運行結果正誤判斷：特別好正確，還可改進基本正確，還需改進還有錯誤不足之處或設計經驗小結：（1）L是單鏈表的頭指針的指針，用來接收頭指針變量的地址，*L待初始化的單鏈表為頭指針變量；2）節(jié)約了空間，接見結點時，只需知道頭指針，就可以找到其他的元素；3）頭插法建表獲取的鏈表中的結點的次序和輸入的次序相反，尾插法規(guī)一致；4）求表長時，算法的時間復雜度為O（n）。任課教師考語：教師簽字：年月日注：每學期最少有一次設計性實驗

4、。每學期結束請任課教師準時按量一致交到授課秘書處。源程前言件名及組成文件：#include,#include,#include,#include算法設計思想算法描述#include#include#include#include#defineTRUE1#defineFALSE0typedefintElemType;typedefstructNodeElemTypedata;structNode*next;Node,*LinkList;/*初始化*/voidInit(LinkList*head)*head=(LinkList)malloc(sizeof(Node);(*head)-next=NU

5、LL;LinkListcreate(intn)LinkListh,r,p;intx,i;h=(Node*)malloc(sizeof(Node);r=h;printf(請輸入數(shù)據(jù):n);for(i=1;idata=x;r-next=p;r=p;r-next=NULL;returnh;/*頭部插入*/intCreatfromH(LinkListhead)LinkListp;ElemTypex;puts(輸入數(shù)據(jù)，輸入-1000結束輸入!);while(1)scanf(%d,&x);if(x!=-1000)p=(Node*)malloc(sizeof(Node);p-data=x;p-next=h

6、ead-next;head-next=p;elsebreak;return1;return0;/*尾部插入*/LinkListCreatfromT(LinkListhead)LinkListp,q,t;ElemTypex;q=head;t=head;puts(輸入數(shù)據(jù)，輸入-1000結束輸入!);while(1)scanf(%d,&x);if(x!=-1000)p=(Node*)malloc(sizeof(Node);p-data=x;p-next=NULL;t-next=p;t=p;returnq;intInslist(LinkList*head,inti,ElemTypex)LinkLis

7、tp,q;p=(*head);intj=0;while(p&jnext;j+;if(!p|ji-1)printf(插入地址不合法！);return0;q=(Node*)malloc(sizeof(Node);q-data=x;q-next=p-next;p-next=q;return1;輸出voidOutput(LinkListhead)/*定義節(jié)點指針種類，并指向首元結點*/LinkListp;p=head-next;while(p!=NULL)printf(n%d,p-data);p=p-next;printf(n);/*求表長*/intLengthList(LinkListhead)in

8、ti;LinkListp;i=0;p=head-next;while(p!=NULL)i+;p=p-next;returni;/*查找*/intLocate1(LinkListhead,ElemTypex)LinkListp;inti=1;p=head-next;while(p!=NULL&p-data!=x)p=p-next;i+;if(p=NULL)return0;returni;intLocate2(LinkListhead,inti)intj;LinkListp;p=head;j=0;if(ii)returnNULL;while(p-next!=0&jnext;returnp-data

9、;/*刪除*/intDel(LinkList*head,inti)LinkListp,q;intj=0;p=(*head);while(p-next!=NULL&jnext;j=j+;if(p=NULL&ji-1)printf(刪除地址不合理!);return0;q=p-next;p-next=p-next-next;free(q);return1;/*合并兩個單鏈表*/LinkListmerge(LinkListLa,LinkListLb)LinkListLc;LinkListq,p,r;p=La-next;q=Lb-next;Lc=La;Lc-next=NULL;r=Lc;while(p!

10、=NULL&q!=NULL)if(p-datadata)r-next=p;r=p;p=p-next;elser-next=q;r=q;q=q-next;if(p)r-next=p;elser-next=q;free(Lb);return(Lc);voidmain()LinkListhead,La,Lb;inti;charzdg,y;ElemTypex;while(zdg!=0)getch();system(CLS);puts(n);puts(*);puts(*puts(*puts(*puts(*0-退出3-輸出6-刪除功能選擇1-創(chuàng)辦2-插入4-表長5-查找7-合并*);*);*);*);pu

11、ts(*);printf(n);printf(請選擇功能:n);scanf(%c,&zdg);switch(zdg)case0:puts(nn);puts(puts(puts(puts(puts(break;*);*感謝使用，再見！*);*);*);*);case1:puts(n);puts(*);puts(*0-般創(chuàng)辦1-頭部插入法2-尾部插入法*);puts(*);printf(請選擇:n);scanf(%c,&y);y=getch();if(y=0)printf(輸入數(shù)字的個數(shù):n);scanf(%d,&i);head=create(i);if(y=1)CreatfromH(head);

12、printf(新的單鏈表為:);Output(head);if(y=2)printf(新的單鏈表為:);Output(CreatfromT(head);break;case2:puts(n);printf(請輸入要插入的地址:n);scanf(%d,&i);printf(請輸入要插入的數(shù)據(jù):n);scanf(%d,&x);if(Inslist(&head,i,x)!=0)printf(插入成功!);Output(head);break;case3:puts(n);printf(輸入的數(shù)據(jù)為:n);Output(head);break;case4:puts(n);printf(長度為:%d,Le

13、ngthList(head);break;case5:puts(n);puts(*);puts(*1-按值查找2-挨次號查找*);puts(*);printf(請選擇:n);scanf(%c,&y);y=getch();if(y=1)printf(請輸入要查找的元素:n);scanf(%d,&x);if(Locate1(head,x)!=0)printf(查找成功!該元素的地址是%d,Locate1(head,x);elseprintf(無此元素,查找失敗!);if(y=2)printf(請輸入要查找的元素的地址:n);scanf(%d,&i);if(Locate2(head,i)!=0)printf(查找成功,該%d號地址上的是%d!,i,Locate2(head,i);elseprintf(無此元素,查找失敗!);break;case6:puts(n);printf(請輸入你要刪除的元素序號:);scanf(%d,&i);Del(&head,i);Output(head);break;case7:puts(n);printf(請輸入La的數(shù)據(jù):);printf(輸入數(shù)字的個數(shù):n);scanf(%d,&i);La=create(i);printf(請輸入Lb的數(shù)據(jù):);printf(輸入數(shù)字的個數(shù):n);scanf(%d,&i);L