單鏈表的操作實(shí)現(xiàn)實(shí)驗(yàn)報(bào)告

1、數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)報(bào)告學(xué)號(hào)：104100058姓名：趙德剛班級(jí)：10A實(shí)驗(yàn)時(shí)間：年月日實(shí)驗(yàn)地點(diǎn)：同析3號(hào)樓開發(fā)環(huán)境：C+課程名稱：數(shù)據(jù)結(jié)構(gòu)-C語言描述實(shí)驗(yàn)性質(zhì)：口綜合性實(shí)驗(yàn)設(shè)計(jì)性實(shí)驗(yàn)口驗(yàn)證實(shí)驗(yàn)實(shí)驗(yàn)內(nèi)容：單鏈表的實(shí)現(xiàn)題目來源：教材頁題口 "教師補(bǔ)充口自選題目主要功能描述：鏈表的初始化、鏈表的創(chuàng)建（頭部插入法、尾部插入法）、求表長、查找（按值查找、按序號(hào)查找）、插入、刪除、輸出、兩個(gè)有序單鏈表的合并等。設(shè)計(jì)分析：初始化：為單鏈表申請頭結(jié)點(diǎn)空間，將單鏈表設(shè)置為空；創(chuàng)建：（1）頭部插入法：（a）初始化空表；（b）申請新結(jié)點(diǎn)并賦值；（c）插入新結(jié)點(diǎn)；（d）插入第i個(gè)元素。（2）尾部插入法：建空表

2、（b）申請結(jié)點(diǎn)并賦值；（c）插入第一個(gè)結(jié)點(diǎn)；（d） r->next-s,r-s;表長：從表頭開始，將指針依次指向各個(gè)結(jié)點(diǎn)，一直到p->next-NULL為止，用j來計(jì)數(shù)。查找：（1）按值查找：在表中查找第 i個(gè)結(jié)點(diǎn)，找到就返回該結(jié)點(diǎn)的存儲(chǔ)位置，用j來存儲(chǔ)掃描過的結(jié)點(diǎn)數(shù)（j的初值為0），但j=i時(shí)，結(jié)束。（2）按序號(hào)查找：從表中第一個(gè)結(jié)點(diǎn)開始，當(dāng)key等于查找到的元素的數(shù)據(jù)時(shí)停止查找。插入：在單鏈表中第i-1個(gè)結(jié)點(diǎn)并由指針指示，申請結(jié)點(diǎn)空間q,將數(shù)據(jù)域置為x,更新指針。刪除：從頭結(jié)點(diǎn)開始，刪除第i個(gè)結(jié)點(diǎn)并釋放空間；輸出：當(dāng)表不為空時(shí)，依次輸出表中元素；合并：與順序表一樣，只需為新的結(jié)

3、點(diǎn)申請一個(gè)空間。典型測試數(shù)據(jù)輸入：輸入數(shù)據(jù)個(gè)數(shù)：4數(shù)據(jù)：1，2，3, 4輸出：1 , 2, 3, 4預(yù)期結(jié)果：基本實(shí)現(xiàn)了單鏈表的基本 各種操作。程序及運(yùn)行結(jié)果正誤判斷：口非常好正確，還可改進(jìn)口基本正確，還需改進(jìn)口還有錯(cuò)誤不足之處或設(shè)計(jì)經(jīng)驗(yàn)小結(jié)：（1） L是單鏈表的頭指針的指針，用來接收頭指針變量的地址，*L待初始化的單鏈表為頭指針變量；（2）節(jié)省了空間，訪問結(jié)點(diǎn)時(shí)，只需知道頭指針，就可以找到其他的元素；（3）頭插法建表得到的鏈表中的結(jié)點(diǎn)的次序和輸入的順序相反，尾插法則一致；（4） 求表長時(shí)，算法的時(shí)間復(fù)雜度為0 （n）。任課教師評(píng)語：教師簽字：年月日注：每學(xué)期至少有一次設(shè)計(jì)性實(shí)驗(yàn)。每學(xué)期結(jié)束請

4、任課教師按時(shí)按量統(tǒng)一交到教學(xué)秘書處。源程序文件名及組成文件：#in clude<stdio.h>,# in clude<stdlib.h>,# in clude<co nio.h>,#i nclude<wi ndows.h>算法設(shè)計(jì)思想算法描述#in clude<stdio.h>#in clude<stdlib.h>#in clude<c oni o.h>#i nclude<wi ndows.h>#defi ne TRUE 1#defi ne FALSE 0typedef int ElemType;

5、 typedef struct NodeElemType data; struct Node * n ext;Node,*Li nkList;/*初始化*/void In it(Li nkList *head)*head=(L in kList)malloc(sizeof(Node); (*head)-> next=NULL;Lin kList create(i nt n)Lin kList h,r,p;int x,i;h=(Node*)malloc(sizeof(Node);r=h;printf("請輸入數(shù)據(jù):n”);for(i=1;i<=n ;i+)sca nf(&q

6、uot;%d", &x); p=(Node*)malloc(sizeof(Node); p->data=x;r->n ext=p; r=p;r->n ext=NULL; return h;/*頭部插入*/int CreatfromH(L in kList head)Lin kList p;ElemType x;puts("輸入數(shù)據(jù)，輸入-1000結(jié)束輸入r?; while(1)sca nf("%d"，&x);if(x!=-1000)p=(Node*)malloc(sizeof(Node); p_>data=x;p-

7、>n ext=head->n ext;head->n ext=p;else break;return 1;return 0;/*尾部插入*/Lin kList CreatfromT(Li nkList head)Lin kList p,q,t;ElemType x;q=head;t=head;puts("輸入數(shù)據(jù)，輸入-1000結(jié)束輸入r?；while(1)sca nf("%d", &x);if(x!=-1000)p=(Node*)malloc(sizeof(Node); p->data=x;p-> next=NULL;t_&

8、gt;n ext=p;t=p;return q;int In slist(L in kList *head,i nt i,ElemType x)Lin kList p,q;p=(*head);int j=0;while(p&&j<i-1)p=p->n ext;j+;if(!p|j>i-1)printf（”插入位置不合法！"）;return 0;q=(Node*)malloc(sizeof(Node); q_>data=x;q_>n ext=p->n ext;p_>n ext=q; return 1;/輸出void Output

9、(L in kList head)/*定義節(jié)點(diǎn)指針類型，并指向首元結(jié)點(diǎn)*/Lin kList p;p=head->n ext;while(p!=NULL)prin tf("n%d",p->data); p=p->n ext;prin tf("n ”);/*求表長*/int Len gthList(L in kList head)int i;Lin kList p;i=0;p=head->n ext;while(p!=NULL)i+;p=p->n ext; return i;/*查找*/int Locate1(L in kList he

10、ad,ElemType x)Lin kList p;int i=1;p=head->n ext;while(p!=NULL&&p->data!=x)p=p->n ext; i+; if(p=NULL) return 0;return i;int Locate2(L in kList head,i nt i)int j;Lin kList p;p=head;j=0；if(i<=1|j>i)return NULL; while(p-> next!=O&&j<i) j+;p=p->n ext;return p->d

11、ata;/*刪除*/int Del(LinkList *head,int i)Lin kList p,q;int j=0; p=(*head); while(p-> next!=NULL&&j<i-1) p=p->n ext; j=j+；if(p=NULL&&j>i-1)printf("刪除位置不合理!"); return 0;q=p->n ext;p->n ext=p->n ext- >n ext;free(q); return 1;/*合并兩個(gè)單鏈表*/Lin kList merge(L i

12、n kList La,L in kList Lb) Lin kList Lc;Lin kList q,p,r;p=La->n ext; q=Lb->n ext; Lc=La;Lc-> next=NULL; r=Lc;while(p!=NULL&&q!=NULL) if(p->data<=q->data)r->n ext=p;r=p;p=p->n ext; elser->n ext=q;r=q;q=q-> next; if(p)r->n ext=p; elser->n ext=q;free(Lb); retu

13、rn(Lc); void mai n()Lin kList head,La,Lb;int i; char zdg,y; ElemType x;while(zdg!=0) getch(); system("CLS"); puts("n"); puts(" puts("* puts("* puts("* puts("* puts(" prin tf("n"); printf("請選擇功能:n");w*");功能選擇1-創(chuàng)建2-插入4-表長5-查找7-

14、合并0-退出3-輸出6-刪除*");*");*");*");"*");sca nf("%c", &zdg); switch(zdg)case'0':puts(”nn”)；puts("*");puts("*"puts("*謝謝使用，再見！*"puts("*"puts("*");break;case'1':puts("n");puts("*"

15、);puts("*0-般創(chuàng)建1 -頭部插入法2-尾部插入法*");puts(" !*printf("請選擇:n");scan f("%c", &y);y=getch();if(y='0')printf("輸入數(shù)字的個(gè)數(shù):n");scan f("%d", &i);head=create(i);if(y='1')CreatfromH(head);printf(”新的單鏈表為:");Output(head);if(y=2)printf

16、(-新的單鏈表為:"); Output(CreatfromT(head);break;case'2':puts("n");printf("請輸入要插入的位置:n"); scan f("%d",&i);printf("請輸入要插入的數(shù)據(jù):n"); scan f("%d"，& x);if(I nslist(&head,i,x)!=0)printf("插入成功!");Output(head); break;case'3

17、9;:puts("n"); printf("輸入的數(shù)據(jù)為:n");Output(head);break;case'4':puts("n");printf("長度為:%d",LengthList(head); break;case'5':puts("n"););puts("*1-按值查找2-按序號(hào)查找);puts(');puts('printf("請選擇:n");scan f("%c", &y

18、);y=getch();if(y='1')printf("請輸入要查找的元素:n"); scan f("%d", &x);if(Locate1(head,x)!=0)printf("查找成功！該元素的位置是%d",Locate1(head,x);elseprintf("無此元素，查找失敗!");if(y=2)printf("請輸入要查找的元素的位置:n");scan f("%d", &i);if(Locate2(head,i)!=0)printf("查找成功 該%d 號(hào)位置上的是 %d!",i,Locate2(head,i); elseprintf("無此元素，查找失敗!");break;case'6':puts("n");printf("請輸入你要?jiǎng)h除的元素序號(hào)：”);scan f("%d",&i);Del(& head,i);Output(head);break;case'