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

數(shù)據(jù)結(jié)構(gòu)單鏈表數(shù)據(jù)結(jié)構(gòu)單鏈表數(shù)據(jù)結(jié)構(gòu)單鏈表xxx公司數(shù)據(jù)結(jié)構(gòu)單鏈表文件編號：文件日期：修訂次數(shù)：第1.0次更改批準審核制定方案設(shè)計，管理制度實驗一單鏈表一、實驗目的1、掌握用Vc++上機調(diào)試程序的基本方法；2、掌握單鏈表的建立、插入、刪除以及相關(guān)操作。二、實驗內(nèi)容1、單鏈表的插入算法；2、單鏈表的刪除算法；3、兩個有序單鏈表合并成一個有序單鏈表的算法。三、實驗要求1、學生用C++/C完成算法設(shè)計和程序設(shè)計并上機調(diào)試通過；2、撰寫實驗報告，提供實驗測試數(shù)據(jù)和實驗結(jié)果；3、分析算法，要求給出具體的算法分析結(jié)果，包括時間復雜度和空間復雜度，并簡要給出算法設(shè)計小結(jié)和心得。四、實驗準備1、復習C語言中指針的用法，特別是結(jié)構(gòu)體的指針的用法；2、了解單鏈表的概念，單鏈表的定義方法；3、掌握線性表在鏈式存儲結(jié)構(gòu)上實現(xiàn)基本操作：查找、插入、刪除的算法；在實現(xiàn)這些算法的時候，要注意判斷輸入數(shù)據(jù)的合法性，除此之外還要注意以下內(nèi)容：在實現(xiàn)查找的時候，首先要判斷該單鏈表是否為空，其次要判斷查找后的結(jié)果(查到時輸出查到的數(shù)據(jù)，未查到時給出錯誤提示)。在實現(xiàn)插入的時候，由于是鏈式存儲，它可以隨機產(chǎn)生和回收存儲空間，所以它不要判斷線性表是否為滿，但仍需判斷要插入的位置是否合法，其次要注意插入的時候語句的順序不可顛倒，否則出錯。在實現(xiàn)刪除的時候，首先要判斷線性表是否為空，為空則不能刪除；其次在刪除后要回收空間。五、實驗步驟1、編程實現(xiàn)建立一個單鏈表，并在此表中插入一個元素和刪除一個元素5(1)通過鍵盤讀取元素建立單鏈表；(2)指定一個位置，在此位置之前插入一個新元素；(3)指定一個位置，刪除此位置元素。2、兩個有序單鏈表合并成一個有序單鏈表的算法。(1)通過鍵盤讀取元素建立2個有序單鏈表；(2)將二兩個有序單鏈表合并成一個有序單鏈表；(3)輸出合并后的單鏈表。六、實驗參考代碼1、編程實現(xiàn)建立一個單鏈表，并在此表中插入一個元素和刪除一個元素#include""#include""#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個元素之前插入一個元素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;p->next=s;returnOK;}//刪除第i個元素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);OutputList_L(L);}elseprintf("Theposwhatyouwanttodeleteiserror!pleasedoagain!\n");}elseif(choice==3){OutputList_L(L);}elseif(choice!=0)printf("choiceerror\n");}}2、兩個有序單鏈表合并成一個有序單鏈表的算法。實現(xiàn)提示：程序需要3個指針：pa,pb,pc，其中pa，pb分別指向La表、Lb表的首結(jié)點，用pa遍歷La表，pb遍歷Lb表，pc指向合并后的新表的最后一個結(jié)點（即尾結(jié)點），pc的初值指向La表的頭8結(jié)點。合并的思想是：先建立好兩個鏈表La表和Lb表，然后依次掃描La和Lb中的元素，比較當前元素的值，將較小者鏈到*pc之后，如此重復直到La或Lb結(jié)束為止，再將另一個鏈表余下的內(nèi)容鏈到pc所指的結(jié)點之后。#include""#include""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));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");}//以下將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=papa:pb;free(Lb);}//以下是主程序voidmain(){LinkListLa,Lb,Lc;printf("Weshouldcreatetwoincrementalandorderlylistsfirst!\n");printf("pleasecreataincrement