數(shù)據(jù)結構單鏈表

實驗一 單鏈表一、實驗目的1、掌握用Vc++上機調試程序的基本方法；2、掌握單鏈表的建立、插入、刪除以及相關操作。二、實驗內容1、單鏈表的插入算法；2、單鏈表的刪除算法；3、兩個有序單鏈表合并成一個有序單鏈表的算法。三、實驗要求1、學生用C++/C完成算法設計和程序設計并上機調試通過；2、撰寫實驗報告，提供實驗測試數(shù)據(jù)和實驗結果；3、分析算法，要求給出具體的算法分析結果，包括時間復雜度和空間復雜度，并簡要給出算法設計小結和心得。四、實驗準備1、復習C語言中指針的用法，特別是結構體的指針的用法；2、了解單鏈表的概念，單鏈表的定義方法；3、掌握線性表在鏈式存儲結構上實現(xiàn)基本操作：查找、插入、刪除的算法；在實現(xiàn)這些算法的時候，要注意判斷輸入數(shù)據(jù)的合法性，除此之外還要注意以下內容：在實現(xiàn)查找的時候，首先要判斷該單鏈表是否為空，其次要判斷查找后的結果(查到時輸出查到的數(shù)據(jù)，未查到時給出錯誤提示)。在實現(xiàn)插入的時候，由于是鏈式存儲，它可以隨機產生和回收存儲空間，所以它不要判斷線性表是否為滿，但仍需判斷要插入的位置是否合法，其次要注意插入的時候語句的順序不可顛倒，否則出錯。在實現(xiàn)刪除的時候，首先要判斷線性表是否為空，為空則不能刪除；其次在刪除后要回收空間。五、實驗步驟、編程實現(xiàn)建立一個單鏈表，并在此表中插入一個元素和刪除一個元素5通過鍵盤讀取元素建立單鏈表；指定一個位置，在此位置之前插入一個新元素；指定一個位置，刪除此位置元素。2、兩個有序單鏈表合并成一個有序單鏈表的算法。通過鍵盤讀取元素建立2個有序單鏈表；將二兩個有序單鏈表合并成一個有序單鏈表；輸出合并后的單鏈表。六、實驗參考代碼 1、編程實現(xiàn)建立一個單鏈表，并在此表中插入一個元素和刪除一個元素 #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個元素之前插入一個元素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個元素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、兩個有序單鏈表合并成一個有序單鏈表的算法。實現(xiàn)提示：程序需要3個指針：pa,pb,pc,其中pa, pb分別指向La表、Lb表的首結點，用 pa遍歷La表，pb遍歷Lb表，pc指向合并后的新表的最后一個結點 (即尾結點)， pc的初值指向La表的頭8結點。合并的思想是：先建立好兩個鏈表 La表和Lb表，然后依次掃描 La和Lb中的元素，比較當前元素的值，將較小者鏈到 *pc之后，如此重復直到 La或Lb結束為止，再將另一個鏈表余下的內容鏈到pc所指的結點之后。#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