數(shù)據(jù)結(jié)構(gòu)單鏈表

實(shí)驗(yàn)一 單鏈表一、實(shí)驗(yàn)?zāi)康?、掌握用Vc++上機(jī)調(diào)試程序的基本方法；2、掌握單鏈表的建立、插入、刪除以及相關(guān)操作。二、實(shí)驗(yàn)內(nèi)容1、單鏈表的插入算法；2、單鏈表的刪除算法；3、兩個(gè)有序單鏈表合并成一個(gè)有序單鏈表的算法。三、實(shí)驗(yàn)要求1、學(xué)生用C++/C完成算法設(shè)計(jì)和程序設(shè)計(jì)并上機(jī)調(diào)試通過；2、撰寫實(shí)驗(yàn)報(bào)告，提供實(shí)驗(yàn)測試數(shù)據(jù)和實(shí)驗(yàn)結(jié)果；3、分析算法，要求給出具體的算法分析結(jié)果，包括時(shí)間復(fù)雜度和空間復(fù)雜度，并簡要給出算法設(shè)計(jì)小結(jié)和心得。四、實(shí)驗(yàn)準(zhǔn)備1、復(fù)習(xí)C語言中指針的用法，特別是結(jié)構(gòu)體的指針的用法；2、了解單鏈表的概念，單鏈表的定義方法；3、掌握線性表在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)基本操作：查找、插入、刪除的算法；在實(shí)現(xiàn)這些算法的時(shí)候，要注意判斷輸入數(shù)據(jù)的合法性，除此之外還要注意以下內(nèi)容：在實(shí)現(xiàn)查找的時(shí)候，首先要判斷該單鏈表是否為空，其次要判斷查找后的結(jié)果(查到時(shí)輸出查到的數(shù)據(jù)，未查到時(shí)給出錯(cuò)誤提示)。在實(shí)現(xiàn)插入的時(shí)候，由于是鏈?zhǔn)酱鎯?chǔ)，它可以隨機(jī)產(chǎn)生和回收存儲(chǔ)空間，所以它不要判斷線性表是否為滿，但仍需判斷要插入的位置是否合法，其次要注意插入的時(shí)候語句的順序不可顛倒，否則出錯(cuò)。在實(shí)現(xiàn)刪除的時(shí)候，首先要判斷線性表是否為空，為空則不能刪除；其次在刪除后要回收空間。五、實(shí)驗(yàn)步驟、編程實(shí)現(xiàn)建立一個(gè)單鏈表，并在此表中插入一個(gè)元素和刪除一個(gè)元素5通過鍵盤讀取元素建立單鏈表；指定一個(gè)位置，在此位置之前插入一個(gè)新元素；指定一個(gè)位置，刪除此位置元素。2、兩個(gè)有序單鏈表合并成一個(gè)有序單鏈表的算法。通過鍵盤讀取元素建立2個(gè)有序單鏈表；將二兩個(gè)有序單鏈表合并成一個(gè)有序單鏈表；輸出合并后的單鏈表。六、實(shí)驗(yàn)參考代碼 1、編程實(shí)現(xiàn)建立一個(gè)單鏈表，并在此表中插入一個(gè)元素和刪除一個(gè)元素 #include"stdio.h"#include"stdlib.h"#defineOK1#defineERROR0typedefintElemType;typedefintStatus;typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;//以下是建立單鏈表voidCreatList_L(LinkList&head){LinkListtail,p;intn,i;p=(Lnode*)malloc(sizeof(Lnode));head=tail=p;head->next=NULL;printf("Pleaseinputlengthtocreatalist:\n");scanf("%d",&n);printf("Pleaseinputagroupofvaluesofthelist:\n");for(i=1;i<=n;i++){p=(Lnode*)malloc(sizeof(Lnode));scanf("%d",&p->data);p->next=NULL;tail->next=p;tail=p;}printf("Alisthasbeencreatedsuccessfully!'n");}//以下是輸出單鏈表voidOutputList_L(LinkListL){LinkListp=L->next;if(p==NULL){printf("\nNolist'n");return;}printf("Thelistis:\n ”);while(p){printf("%4d",p->data);p=p_>next;}printf("\n");}//在第i個(gè)元素之前插入一個(gè)元素StatusListInsert_L(LinkListL,inti,ElemTypee){LinkListp,s;p=L;intj=0;while(p&&j<i-1){p=p->next;++j;}if(!p||j>i-1)returnERROR;s=(LinkList)malloc(sizeof(Lnode));s->data=e;s->next=p->next;歡迎下載 2p_>next=s;returnOK;}//刪除第i個(gè)元素StatusListDelete_L(LinkListL,inti,ElemType&e){LinkListp,q;p=L;intj=0;while(p->next&&j<i-1){p=p->next;++j;}if(!(p->next)||j>i-1)returnERROR;q=p->next;p->next=q_>next;e=q_>data;free(q);returnOK;}voidmain(){LinkListL;intchoice,i;ElemTypee;choice=1;printf("Weshouldcreatealistfirst!");CreatList_L(L);OutputList_L(L);while(choice!=0){printf("\nmenu\n");printf("1insertaelem");printf("2deleteaelem");printf("3outputalist");printf(”4exit");printf("\n----------------------------------------------------------------------------\n");printf("pleasechoice(1,2,3,4)");scanf("%d",&choice);if(choice==0)break;elseif(choice==1){printf("Pleaseinputaposandavaluewhatyouwanttoinsert:\n；”)scanf("%d%d",&i,&e);if(ListInsert_L(L,i,e)){printf("Theinsertingactionhasbeendone!\n");OutputList_L(L);}elseprintf("Theinsertingposiserror!pleasedoagain!\n");}elseif(choice==2){printf("Pleaseinputaposwhatyouwanttodelete:\n");scanf("%d",&i);if(ListDelete_L(L,i,e)){printf("Thedeletingactionhasbeendone,thedeletedvalueis%d\n",e);歡迎下載 3OutputList_L(L);}elseprintf("Theposwhatyouwanttodeleteiserror!pleasedoagain!\n；”)}elseif(choice==3){OutputList_L(L);}elseif(choice!=0)printf("choiceerror\n");}}2、兩個(gè)有序單鏈表合并成一個(gè)有序單鏈表的算法。實(shí)現(xiàn)提示：程序需要3個(gè)指針：pa,pb,pc,其中pa, pb分別指向La表、Lb表的首結(jié)點(diǎn)，用 pa遍歷La表，pb遍歷Lb表，pc指向合并后的新表的最后一個(gè)結(jié)點(diǎn) (即尾結(jié)點(diǎn))， pc的初值指向La表的頭8結(jié)點(diǎn)。合并的思想是：先建立好兩個(gè)鏈表 La表和Lb表，然后依次掃描 La和Lb中的元素，比較當(dāng)前元素的值，將較小者鏈到 *pc之后，如此重復(fù)直到 La或Lb結(jié)束為止，再將另一個(gè)鏈表余下的內(nèi)容鏈到pc所指的結(jié)點(diǎn)之后。#include"stdio.h"#include"stdlib.h"typedefintElemType;typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;//以下是建立單鏈表voidCreatList_L(LinkList&head){LinkListtail,p;intn,i;p=(Lnode*)malloc(sizeof(Lnode));head=tail=p;head->next=NULL;printf("Pleaseinputlengthtocreatalist:\n");scanf("%d",&n);printf("Pleaseinputagroupofvaluesofthelist:\n");for(i=1;i<=n;i++){p=(Lnode*)malloc(sizeof(Lnode));seanf("%d",&p->data);p->next=NULL;tail->next=p;tail=p;}歡迎下載 4printf("Alisthasbeencreatedsuccessfully!'n");}//以下是輸出單鏈表voidOutputList_L(LinkListL){LinkListp=L->next;if(p==NULL){printf("\nNolist'n");return;}printf("Thelistis:\n ”);while(p){printf("%4d",p->data);p=p_>next;}printf("\n");}//以下將La和Lb表合并為Lc表voidMergeList(LinkList&Lc,LinkList&La,LinkList&Lb){LinkListpa,pb,pc;pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}}pc->next=pa?pa:pb;free(Lb);}//以下是主程序voidmain(){LinkListLa,Lb,Lc;printf("Weshouldcreatetwoincrementalandorderlylistsfirst!\n");printf("pleasecreataincrementalandorder