鏈表完整版本

武夷學(xué)院實(shí)驗(yàn)報(bào)告課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)_____項(xiàng)目名稱：_鏈表的基本操作與實(shí)現(xiàn)_姓名：_專業(yè)：班級：_學(xué)號：__同組成員_無實(shí)驗(yàn)預(yù)習(xí)部分注：1、實(shí)驗(yàn)預(yù)習(xí)部分包括實(shí)驗(yàn)環(huán)境準(zhǔn)備和實(shí)驗(yàn)所需知識點(diǎn)準(zhǔn)備。注：1、實(shí)驗(yàn)預(yù)習(xí)部分包括實(shí)驗(yàn)環(huán)境準(zhǔn)備和實(shí)驗(yàn)所需知識點(diǎn)準(zhǔn)備。2、若是單人單組實(shí)驗(yàn)，同組成員填無。實(shí)驗(yàn)環(huán)境準(zhǔn)備：1.硬件：PC機(jī)一臺2.軟件：Windows操作系統(tǒng)、C語言運(yùn)行環(huán)境實(shí)驗(yàn)所需知識點(diǎn)準(zhǔn)備：用數(shù)組實(shí)現(xiàn)表時(shí)，無需為表示表元素之間的邏輯關(guān)系增加額外的存儲空間，可以方便地隨機(jī)存取表中任一位置的元素。但是插入和刪除運(yùn)算不方便，效率較低，而且數(shù)組需要分配連續(xù)的存儲空間，不利于表大小的動態(tài)改變。用指針將存儲表元素的那些單元依次串聯(lián)在一起，避免了在數(shù)組中用連續(xù)的單元存儲元素的缺點(diǎn)，在執(zhí)行插入和刪除運(yùn)算時(shí)，不再需要移動元素來騰出空間或填補(bǔ)空缺。但是，需要在每個(gè)單元中設(shè)置指針來表示表中元素之間的邏輯關(guān)系，增加了額外的存儲空間開銷。為了將存儲表元素的所有單元用指針串聯(lián)起來，每個(gè)單元包含一個(gè)元素和一個(gè)指針，其中指針指向表中下一個(gè)元素所在的單元。對于表元素的插入刪除操作，只需要接解除結(jié)點(diǎn)間鏈接的邏輯關(guān)系即可，而無需移動元素。用指針表示表的結(jié)構(gòu)通常稱為單鏈接表，簡稱單鏈表或鏈表。了解并掌握單鏈表的存儲結(jié)構(gòu)的描述方法，上機(jī)實(shí)現(xiàn)單鏈表的基本操作。二、實(shí)驗(yàn)過程記錄注：實(shí)驗(yàn)過程記錄要包含實(shí)驗(yàn)?zāi)康?、?shí)驗(yàn)原理、實(shí)驗(yàn)步驟，頁碼不夠可自行添加。注：實(shí)驗(yàn)過程記錄要包含實(shí)驗(yàn)?zāi)康摹?shí)驗(yàn)原理、實(shí)驗(yàn)步驟，頁碼不夠可自行添加。1.實(shí)驗(yàn)內(nèi)容與要求（1）建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表head，并輸出該鏈表。單鏈表的數(shù)據(jù)元素由用戶從鍵盤輸入，用戶輸入的值為-1時(shí)代表結(jié)束。（2）在鏈表中插入一個(gè)數(shù)據(jù)元素，輸出插入后的鏈表。（3）在鏈表中刪除一個(gè)元素，輸出刪除后的鏈表。2.源代碼（包括主要結(jié)構(gòu)、主要語句、函數(shù)注釋說明）#include<stdio.h>#include<stdlib.h>typedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;LinkListCreateList(LNode*head)//創(chuàng)建單鏈表{intc=1,data;LNode*p,*q; p=(LNode*)malloc(sizeof(LNode)); data=0;p->next=NULL;head=p;while(c){printf("請輸入數(shù)據(jù)元素且當(dāng)輸入值為-1時(shí)結(jié)束輸入:");scanf("%d",&data); if(-1!=data){q=(LNode*)malloc(sizeof(LNode));q->data=data;p->next=q;p=q;}elsec=0;p->next=NULL;}returnhead;}LinkListListInsert(LNode*head,inti,inte){ //在帶頭結(jié)點(diǎn)的單鏈線性表head中第i個(gè)位置之前插入元素e intj=0; LinkLists=NULL,p=NULL; p=head; while(p&&j<i-1){p=p->next;++j;}//尋找第i-1個(gè)結(jié)點(diǎn) if(!p||j>i-1)//i小于1或者大于表長+1 {printf("輸入的位置不合法!\n"); returnhead;} s=(LinkList)malloc(sizeof(LNode));//生成新結(jié)點(diǎn) s->data=e;s->next=p->next;//插入head中 p->next=s; returnhead;}LinkListListDelete(LNode*head,inti,inte){ //在帶頭結(jié)點(diǎn)的單鏈線性表head中，刪除第i個(gè)元素，并由e返回其值intj;LinkListq=NULL,p=NULL;p=head;j=0;while(p->next&&j<i-1){//尋找第i個(gè)結(jié)點(diǎn)，并令p指向其前趨p=p->next;++j; }if(!(p->next)||j>i-1) {printf("輸入的位置不合法!\n");returnhead; }q=p->next;p->next=q->next;//刪除并釋放結(jié)點(diǎn)free(q);returnhead;}voidprint(LNode*head)//輸出單鏈表{ LNode*p; p=head; p=p->next; printf("單鏈表為:"); while(p!=NULL) { printf("%d",p->data); p=p->next;} printf("\n");}voidmain(){intm,i,e;LNode*head=NULL;head=CreateList(head);print(head);do{ printf("\n***********目錄************\n");printf("1.在單鏈表中插入數(shù)據(jù)元素\n");printf("2.在單鏈表中刪除數(shù)據(jù)元素\n");printf("0.結(jié)束程序\n");printf("***************************\n");printf("請選擇所需操作(0-2)：");scanf("%d",&m);switch(m){case1://在單鏈表中插入數(shù)據(jù)元素printf("依次輸入插入位置和數(shù)據(jù)元素(空格隔開)：");scanf("%d%d",&i,&e);head=ListInsert(head,i,e);print(head);break;case2://在單鏈表中刪除數(shù)據(jù)元素printf("輸入需要?jiǎng)h除的元素的位置：");scanf("%d",&i);head=ListDelete(head,i,e);print(head);break;case0://結(jié)束程序printf("已結(jié)束程序?。?！\n");break;default:printf("輸入有誤?。。n");}}while(m!=0);}運(yùn)行結(jié)果（包括程序如何使用，輸入數(shù)據(jù)和輸出結(jié)果）（1）單鏈表的創(chuàng)建 （2）單鏈表的插入（3）單鏈表的刪除（4）結(jié)束程序（5）如果單鏈表的操作有誤的話，程序會提示操作有誤。三、實(shí)驗(yàn)結(jié)果與討論：注：1、實(shí)驗(yàn)小結(jié)應(yīng)包含實(shí)驗(yàn)所需知識點(diǎn)和實(shí)驗(yàn)方法的總結(jié)，實(shí)驗(yàn)心得體會等。2、分組實(shí)驗(yàn)需包含同組討論內(nèi)容。有了上次做順序表的基本操作與實(shí)現(xiàn)這個(gè)實(shí)驗(yàn)的基礎(chǔ)，這次實(shí)驗(yàn)相比上次感覺做的更加順手，由于單鏈表和順序表知識是相關(guān)聯(lián)的，所以我根據(jù)做上次