C語言數(shù)據(jù)結(jié)構(gòu)線性表的基本操作實驗報告

1、實驗一 線性表的基本操作一、實驗?zāi)康呐c基本要求1掌握數(shù)據(jù)結(jié)構(gòu)中的一些基本概念。數(shù)據(jù)、數(shù)據(jù)項、數(shù)據(jù)元素、數(shù)據(jù)類型和數(shù) 據(jù)結(jié)構(gòu)，以及它們之間的關(guān)系。2了解數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲結(jié)構(gòu)之間的區(qū)別與聯(lián)系；數(shù)據(jù)的運算與數(shù) 據(jù)的邏輯結(jié)構(gòu)的關(guān)系。3掌握順序表和鏈表的基本操作：插入、刪除、查找以及表的合并等運算。4掌握運用 C 語言上機調(diào)試線性表的基本方法。二、實驗條件1硬件：一臺微機2軟件：操作系統(tǒng)和 C 語言系統(tǒng)三、實驗方法確定存儲結(jié)構(gòu)后，上機調(diào)試實現(xiàn)線性表的基本運算。四、實驗內(nèi)容1建立順序表，基本操作包括：初始化，建立一個順序存儲的鏈表，輸出順序 表，判斷是否為空，取表中第 i 個元素，定位函數(shù)（返回

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

3、、附源程序及算法程序流程圖1. 源程序（1）源程序 （實驗要求 1和 3）#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct arrint * elem;int length;int listsize;出 nn）;Sqlist;void menu（）;printf( 1.創(chuàng)建線性表 Lann);printf( 2. 判斷 La 是否為空表 nn);printf( 3.插入元素 (La)nn);printf( 4.刪除元素 (La)nn);printf( 5.定位元素 (La)nn);printf( 6.取元素 (La

4、)nn);printf( 7.輸出線性表 nn);printf( 8.創(chuàng)建線性表 Lbnn);printf( 9. 歸并為一個線性表 Lann);printf(*nn);/* 創(chuàng)建順序線性表 L*/ void InitList(Sqlist *L)int n;int i=0;L-elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int); if(NULL=L-elem)printf( 儲存分配失敗 !n);elseL-length=0;L-listsize=LIST_INIT_SIZE;printf( 輸入順序表 a:n); scanf(%d,&n);while

5、(n)L-elemi=n;i+;L-length+;L-listsize=L-listsize-4; scanf(%d,&n);/* 輸出順序線性表 */ void ShowList(Sqlist *p)int i;if(0=p-length)printf( 數(shù)組為空 !n);elsefor(i=0;ilength;i+)printf(%d ,p-elemi);printf(n);/* 判斷 L 是否為空表 */ void ListEmpty(Sqlist *p)if(0=p-length)printf(L是空表 !n);elseprintf(L不是空表 !n);i/* 在順序線性表中第i 個

6、元素前插入新元素 e */void ListInsert(Sqlist *p,int i,int e)int *newbase;int *q1;int *q2;while(ip-length+1)n:);printf( 您輸入的 i 超出范圍 !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+=LIST

7、INCREMENT; q1=&(p-elemi-1); for(q2=&(p-elemp-length-1);q2=q1;-q2)*(q2+1)=*q2;*q1=e;+p-length;/*/在順序線性表中刪除第i個元素，并用e返回其值*/void ListDelete(Sqlist *p,int i,int &e)int *q1,*q2;while(ip-length) printf( 您輸入的 i 超出范圍 ! 請重新輸入 :); scanf(%d,&i); q1=&(p-elemi-1); e=*q1;q2=p-elem+p-length-1; for(+q1;q1length;/* 對

8、比 a 與 b 相等 */ bool compare(int a,int b)if(a=b) return 1;else return 0;/* 在順序線性表 L 中查找第 1 個值與 e 滿足 compare()d 元素的位序 */ void LocateElem(Sqlist *L,int e)int i=1;int *p; p=L-elem; while(ilength & !compare(*p+,e) +i;if(ilength) printf( 第 1 個與 e 相等的元素的位序為 %dn,i);else printf( 沒有該元素 !n);/* 用 e 返回 L 中第 i 個數(shù)據(jù)

9、元素的值 */ void GetList(Sqlist *p,int i,int &e)Sqlist *p1; p1=p; e=p1-elemi-1;/* 已知順序線性表 La 和 Lb 是元素按值非遞減排列 */* 把La和Lb歸并到La上,La的元素也是按值非遞減*/void MergeList_L(Sqlist *La,Sqlist *Lb)int i=0,j=0,k,t;int *newbase;Sqlist *pa,*pb;pa=La;pb=Lb;while(ilength & jlength)if(pa-elemi = pb-elemj)if(pa-listsize=0)newba

10、se=(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(jlength)if( pa-listsize length-j )newbase=(int*)realloc(pa-elem,(pa-listsize+LISTINCREMENT)*sizeof(int); if(!newbase)e

11、xit(0);for(j;jlength;j+,i+)pa-elemi=pb-elemj;pa-length+;for(i=0;ilength/2;i+)t=pa-elemi;pa-elemi=pa-elempa-length-i-1;pa-elempa-length-i-1=t;(2)源程序 (實驗要求 2 和 4)typedef struct LNodeint data; struct LNode *next;LNode, *LinkList; void menu();LinkList InitList();void ShowList(LinkList L);void ListDelete

12、(LinkList L,int i,int &e);void ListEmpty(LinkList L);void GetList(LinkList L,int i,int &e);void ListInsert(LinkList L,int i,int e);bool compare(int a,int b);void LocateElem(LinkList L,int e);LinkList MergeList_L(LinkList La,LinkList Lb); int total=0;void main()LinkList La;LinkList Lb;La=(LinkList)ma

13、lloc(sizeof(struct LNode); La-next=NULL;Lb=(LinkList)malloc(sizeof(struct LNode); Lb-next=NULL;int n;int m;int x; menu();scanf(%d,&n); while(n)switch(n)case 0: ; break; case 1:La-next=InitList();break;case 2:ListEmpty(La);break;case 3:n);printf( 請輸入要插入到第幾個節(jié)點前 scanf(%d,&m);printf( 請輸入插入的數(shù)據(jù) :n); scanf

14、(%d,&x);ListInsert(La,m,x);break;case 4:printf( 請輸入刪除元素的位序 :n);scanf(%d,&m);ListDelete(La,m,x);printf( 刪除的元素為 :%dn,x);break;case 5:printf( 請輸入要找的與線性表中相等的數(shù) :n); scanf(%d,&m);LocateElem(La,m);break;case 6:printf( 請輸入查找的位序 :n);scanf(%d,&m);GetList(La,m,x);printf(La中第 d個元素的值為 dn,m,x);break;case 7:ShowLi

15、st(La);break;case 8:Lb-next=InitList();break;case 9:La=MergeList_L(La,Lb);printf( 歸并成功 n);break;menu();scanf(%d,&n);void menu()printf(*nn);printf(0.退出 nn ”)；printf(1.創(chuàng)建線性表 Lann);printf(2.判斷是否為空表 nn);printf(3.插入元素 nn);printf(4.刪除元素 nn);printf(5.定位元素 nn);printf(6.取元素 nn);printf(7.輸出線性表 nn);printf(8.創(chuàng)建

16、線性表 Lbnn);printf(9.歸并兩線性表 nn);printf(*nn);程圖(實驗要求1和3)圖1主函數(shù)流程圖圖2創(chuàng)建線性表La流程圖圖3判斷La是否為空表流程圖 圖4插入元素(La)流程圖 圖5刪除元素(La)流程圖 圖6定位元素(La)流程圖圖7取元素(La)流程圖 圖8輸出線性表流程圖 圖9輸出線性表流程圖 流程圖(實驗要求2和4)開始圖10主函數(shù)流程圖圖11創(chuàng)建線性表La流程圖圖12判斷是否為空表流程圖圖13插入元素流程圖 圖14刪除元素流程圖圖15定位元素流程圖圖圖16取元素流程圖圖17創(chuàng)建Lb流程圖 圖18歸并兩表流程圖六、運行結(jié)果1. （ 實驗要求 1和 3） 點擊運行，首先出現(xiàn)的是菜單界面，選擇菜單選項進行操作，如圖所示。按“ 1”回車后，即可以創(chuàng)建順序表La，輸入“0”結(jié)束添加，如圖所示 輸入 2，判斷 La 是否為空表，如圖所示。 輸入 3，在指定的位序插入元素，如圖所示