1、實驗一線性表的基本操作1. 一、實驗目的與基本要求掌握數據結構中的一些基本概念。數據、數據項、數據元素、數據類型和數據結構，以及它們之間的關系。2. 了解數據的邏輯結構和數據的存儲結構之間的區別與聯系；數據的運算與數據的邏輯結構的關系。3. 掌握順序表和鏈表的基本操作：插入、刪除、查找以及表的合并等運算。4. 掌握運用C語言上機調試線性表的基本方法。二、實驗條件硬件：一臺微機軟件：操作系統和C語言系統三、實驗方法確定存儲結構后，上機調試實現線性表的基本運算。1. 四、實驗內容建立順序表，基本操作包括：初始化，建立一個順序存儲的鏈表，輸出順序表，判斷是否為空，取表中第i個元素，定位函數（返回第一

2、個與x相等的元素位置），插入，刪除。2. 建立單鏈表，基本操作包括：初始化，建立一個鏈式存儲的鏈表，輸出順序表，判斷是否為空，取表中第i個元素，定位函數（返回第一個與x相等的元素位置），插入，刪除。3.假設有兩個按數據元素值非遞減有序排列的線性表A和B,均以順序表作為存儲結構。編寫算法將A表和B表歸并成一個按元素值非遞增有序（允許值相同）排列的線性表C。（可以利用將B中元素插入A中，或新建C表）4.假設有兩個按數據元素值非遞減有序排列的線性表A和B,均以單鏈表作為存儲結構。編寫算法將A表和B表歸并成一個按元素值遞減有序（即非遞增有序，允許值相同）排列的線性表C。五、附源程序及算法程序流程圖1.

3、源程序（1）源程序（實驗要求1和3）#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstructarrint*elem;intlength;intlistsize;Sqlist;voidmenu（）;出nn"）;printf("1.創建線性表Lann");printf("2.判斷La是否為空表nn");printf("3.插入元素(La)nn");printf("4.刪除元素(La)nn");printf("5.定位元素(La)nn&qu

4、ot;);printf("6.取元素(La)nn");printf("7.輸出線性表nn");printf("8.創建線性表Lbnn");printf("9.歸并為一個線性表Lann");printf("*nn");/*創建順序線性表L*/voidInitList(Sqlist*L)intn;inti=0;L->elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int);if(NULL=L->elem)printf("儲存分配失敗！n"

5、;);elseL->length=0;L->listsize=LIST_INIT_SIZE;printf("輸入順序表a:n");scanf("%d”,&n);while(n)L->elemi=n;i+;L->length+;L->listsize=L->listsize-4;scanf("%d",&n);/*輸出順序線性表*/voidShowList(Sqlist*p)inti;if(0=p->length)printf("數組為空！n");elsefor(i=0;

6、i<p->length;i+)printf("%d”,p->elemi);/*判斷L是否為空表*/voidListEmpty(Sqlist*p)(if(0=p->length)printf("L是空表！n");elseprintf("L不是空表！n");/*在順序線性表中第i個元素前插入新元素e*/voidListInsert(Sqlist*p,inti,inte)(int*newbase;int*q1;int*q2;while(i<1|i>p->length+1)(printf("您輸入的i

7、超出范圍!n請重新輸入要插入的位置n:");scanf("%d”,&i);if(p->length>=p->listsize)(newbase=(int*)realloc(p->elem,(p->listsize+LISTINCREMENT)*sizeof(int);if(!newbase)exit(0);else(p->elem=newbase;p->listsize+=LISTINCREMENT;q1=&(p->elemi-1);for(q2=&(p->elemp->length-1);

8、q2>=q1;-q2)*(q2+1)=*q2;*q1=e;+p->length;/*/在順序線性表中刪除第i個元素，并用e返回其值*/voidListDelete(Sqlist*p,inti,int&e)(int*q1,*q2;(printf(-您輸入的i超出范圍！請重新輸入:");scanf("%d”,&i);q1=&(p->elemi-1);e=*q1;q2=p->elem+p->length-1;for(+q1;q1<=q2;+q1)*(q1-1)=*q1;-p->length;/*對比a與b相等*/b

9、oolcompare(inta,intb)(if(a=b)return1;elsereturn0;/*在順序線性表L中查找第1個值與e滿足compare()d元素的位序*/voidLocateElem(Sqlist*L,inte)(inti=1;int*p;p=L->elem;while(i<=L->length&&!compare(*p+,e)+i;if(i<=L->length)printf("第1個與e相等的元素的位序為%dn",i);elseprintf("沒有該元素！n");/*用e返回L中第i個數

10、據元素的值*/voidGetList(Sqlist*p,inti,int&e)(Sqlist*p1;p1=p;e=p1->elemi-1;/*已知順序線性表La和Lb是元素按值非遞減排列*/*把La和Lb歸并到La上,La的元素也是按值非遞減*/voidMergeList_L(Sqlist*La,Sqlist*Lb)(inti=0,j=0,k,t;int*newbase;Sqlist*pa,*pb;pa=La;pb=Lb;while(i<pa->length&&j<pb->length)(if(pa->elemi>=pb->

11、;elemj)(if(pa->listsize=0)(newbase=(int*)realloc(pa->elem,(pa->listsize+LISTINCREMENT)*sizeof(int);if(!newbase)exit(0);for(k=pa->length-1;k>=i;k-)pa->elemk+1=pa->elemk;pa->length+;pa->elemi=pb->elemj;i+;j+;elsei+;while(j<pb->length)(if(pa->listsize<pb->le

12、ngth-j)(newbase=(int*)realloc(pa->elem,(pa->listsize+LISTINCREMENT)*sizeof(int);if(!newbase)exit(0);for(j;j<pb->length;j+,i+)(pa->elemi=pb->elemj;pa->length+;for(i=0;i<pa->length/2;i+)(t=pa->elemi;pa->elemi=pa->elempa->length-i-1;pa->elempa->length-i-1=t;

13、(2)源程序(實驗要求2和4)typedefstructLNode(intdata;structLNode*next;LNode,*LinkList;voidmenu();LinkListInitList();voidShowList(LinkListL);voidListDelete(LinkListL,inti,int&e);voidListEmpty(LinkListL);voidGetList(LinkListL,inti,int&e);voidListInsert(LinkListL,inti,inte);boolcompare(inta,intb);voidLoca

14、teElem(LinkListL,inte);LinkListMergeList_L(LinkListLa,LinkListLb);inttotal=0;voidmain()(LinkListLa;LinkListLb;La=(LinkList)malloc(sizeof(structLNode);La->next=NULL;Lb=(LinkList)malloc(sizeof(structLNode);Lb->next=NULL;intn;intm;intx;menu();scanf("%d",&n);while(n)(switch(n)(case0:

15、;break;case1:La->next=InitList();break;case2:ListEmpty(La);break;case3:printf("請輸入要插入到第幾個節點前：n");scanf("%d”,&m);printf("請輸入插入的數據:n");scanf("%d",&x);ListInsert(La,m,x);break;case4:printf("請輸入刪除元素的位序:n");scanf("%d",&m);ListDelete(La

16、,m,x);printf("刪除的元素為:%dn",x);break;case5:printf("請輸入要找的與線性表中相等的數:n");scanf("%d",&m);LocateElem(La,m);break;case6:printf("請輸入查找的位序:n");scanf("%d",&m);GetList(La,m,x);printf("La中第d個元素的值為%dn",m,x);break;case7:ShowList(La);break;case8:L

17、b->next=InitList();break;case9:La=MergeList_L(La,Lb);printf("歸并成功n");break;menu();scanf("%d",&n);voidmenu()printf("*,*nn”)；printf("0.退出nn");printf("1.創建線性表Lann");printf("2.判斷是否為空表nn");printf("3.插入廿nn");printf("4.刪除兀素nn"

18、;);printf("5.正位兀素nn");printf("6.取兀素nn");printf("7.輸出線性表nn");printf("8.創建線性表Lbnn");printf("9.歸并兩線性表nn");printf("*nn");程圖（實驗要求1和3）圖1主函數流程圖圖2創建線性表La流程圖圖3判斷La是否為空表流程圖圖4插入元素（La）流程圖圖5刪除元素（La）流程圖圖6定位元素（La）流程圖圖7取元素（La）流程圖圖8輸出線性表流程圖圖9輸出線性表流程圖流程圖（實驗要求2和4）結束、/圖10主函數流程圖圖11創建線性表La流程圖圖12判斷是否為空表流程圖圖13插入元素流程圖圖14刪除元素流程圖開始VJLinkListp;p=L;p->next&&!compare(p->data,e)p=p->next;i+;<!(p)|j>i-ONY沒有找到要查找的位置e=p->data;結束圖15定位元素流程圖圖（結束圖16取元素流程圖圖17創建Lb流程圖圖18歸并兩表流程圖六、運行結果1. （實驗要求1和3）點擊運行，首先出現的是菜單界面，選擇菜單選項進行操作，如圖所示。按“T回車后，即可以創建