實驗一 順序表基本操作

1、實驗一 順序表基本操作一 實驗目的1.學會定義線性表的順序存儲類型，實現(xiàn)C程序的基本結(jié)構(gòu)，對線性表的一些基本操作和具體的函數(shù)定義。2.掌握順序表的基本操作，實現(xiàn)順序表的插入、刪除、查找以及求并集等運算。3.掌握對多函數(shù)程序的輸入、編輯、調(diào)試和運行過程。二 實驗要求1預習C語言中結(jié)構(gòu)體的定義與基本操作方法。2對順序表的每個基本操作用單獨的函數(shù)實現(xiàn)。3編寫完整程序完成下面的實驗內(nèi)容并上機運行。4整理并上交實驗報告。 三 實驗內(nèi)容：1編寫程序?qū)崿F(xiàn)順序表的下列基本操作： (1)初始化順序表La。 (2)將La置為空表。 (3)銷毀La。 (4)在La中插入一個新的元素。 (5)刪除La中的某一元素。

2、(6)在La中查找某元素，若找到，則返回它在La中第一次出現(xiàn)的位置，否則返回0。 (7)打印輸出La中的元素值。2編寫程序完成下面的操作：(1)構(gòu)造兩個順序線性表La和Lb，其元素都按值非遞減順序排列。(2)實現(xiàn)歸并La和Lb得到新的順序表Lc，Lc的元素也按值非遞減順序排列。(3)假設兩個順序線性表La和Lb分別表示兩個集合A和B，利用union_Sq操作實現(xiàn)A=AB。四 思考與提高假設兩個順序線性表La和Lb分別表示兩個集合A和B，如何實現(xiàn)A=A B ？1編寫程序?qū)崿F(xiàn)順序表的下列基本操作：(1)初始化順序表La。(2)將La置為空表。(3)銷毀La。(4)在La中插入一個新的元素。(5)刪

3、除La中的某一元素。(6)在La中查找某元素，若找到，則返回它在La中第一次出現(xiàn)的位置，否則返回0。(7)打印輸出La中的元素值。#include<stdio.h>#include<stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define YES 1#define NO 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int ElemType;#define LIST_INIT_SIZE 100#

4、define LISTINCREMENT 10typedef struct ElemType *elem; int length; int listsize;SqList;Status cmp(ElemType a,ElemType b) if(a=b) return YES; else return NO;/構(gòu)造空的順序表LaStatus InitList_Sq(SqList &L) L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!L.elem) exit(OVERFLOW); L.length=0; L.

5、listsize=LIST_INIT_SIZE; return OK;/撤銷線性表L；Status Destroy_Sq(SqList &L) free(L.elem); L.elem=NULL; L.length=0; L.listsize=0; return OK;/清空線性表Status ClearList_Sq(SqList &L) L.length=0;/memset(L,0,sizeof(L); return OK;/ 在順序線性表L的第i個元素之前插入新的元素eStatus ListInsert_Sq(SqList &L, int i, ElemType

6、e) ElemType *p; if (i < 1 | i > L.length+1) return ERROR; if (L.length >= L.listsize) ElemType *newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof (ElemType); if (!newbase) return ERROR; L.elem = newbase; L.listsize += LISTINCREMENT; ElemType *q = &(L.elemi-1); for (

7、p = &(L.elemL.length-1); p>=q; -p) *(p+1) = *p; *q = e; +L.length; return OK;/ 在順序線性表L中刪除第i個元素，并用e返回其值Status ListDelete_Sq(SqList &L, int i, ElemType &e) ElemType *p, *q; if (i<1 | i>L.length) return ERROR; p = &(L.elemi-1); e = *p; q = L.elem+L.length-1; for (+p; p<=q; +

8、p) *(p-1) = *p; -L.length; return OK; / ListDelete_SqStatus LocateElem_Sq(SqList L, ElemType e,Status (*compare)(ElemType, ElemType) / 在順序線性表L中查找第1個值與e滿足compare()的元素的位序 int i; ElemType *p; i = 1; p = L.elem; while (i <= L.length && !(*compare)(*p+, e) +i; if (i <= L.length) return i; e

9、lse return 0;/打印順序表void PrintList_Sq(SqList L) int i; for(i=0;i<L.length;i+) printf("%d ",L.elemi); printf("n");int main()SqList La;int i,n,e;printf("請輸入元素個數(shù)：n");scanf("%d",&n);if(InitList_Sq(La) for(i=1;i<=n;i+) printf("請輸入第%d個元素n",i); sca

10、nf("%d",&e); ListInsert_Sq(La,i,e); printf("-n你輸入的元素分別為：n"); PrintList_Sq(La); printf("-n");else printf("初始化線性表出錯！n"); printf("-n");printf("請輸入你要插入的元素及插入的位置：n");/插入元素scanf("%d%d",&e,&i);if(ListInsert_Sq(La,i,e) printf(

11、"插入元素后線性表為：n"); PrintList_Sq(La); printf("-n");else printf("輸入位置有錯！n"); printf("-n");/*/printf("請輸入你要刪除的元素的位置：n");/刪除元素scanf("%d",&i);if(ListDelete_Sq(La,i,e) printf("你刪除的元素為：%d,刪除元素后線性表為：n",e); PrintList_Sq(La); printf("

12、-n");else printf("輸入位置有錯！n"); printf("-n");printf("請輸入你要查找的元素：n");/查找元素scanf("%d",&e);if(i=LocateElem_Sq(La,e,cmp) printf("你要查找的元素在第%d個位置。n",i); printf("-n");else printf("找不到這個元素：n"); printf("-n");if(ClearList_S

13、q(La)/清空線性表 printf("線性表已清空。n"); printf("-n");else printf("線性表清空出錯。n"); printf("-n");if(Destroy_Sq(La)/撤銷線性表 printf("線性表已撤銷。n"); printf("-n");else printf("線性表清空出錯。n"); printf("-n");return 0;2編寫程序完成下面的操作：(1)構(gòu)造兩個順序線性表La和Lb，

14、其元素都按值非遞減順序排列。(2)實現(xiàn)歸并La和Lb得到新的順序表Lc，Lc的元素也按值非遞減順序排列。(3)假設兩個順序線性表La和Lb分別表示兩個集合A和B，利用union_Sq操作實現(xiàn)A=AB。#include<stdio.h>#include<stdlib.h>#define TRUE 1#define FALSE 0#define YES 1#define NO 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int E

15、lemType ;#define LIST_INIT_SIZE 100#define LISTINCERMENT 10typedef struct ElemType *elem; int length; int listsize;SqList;Status InitList_Sq(SqList &L)/構(gòu)造空的順序表La L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!L.elem)exit(OVERFLOW); L.length=0; L.listsize=LIST_INIT_SIZE; return OK

16、;/*/Status ListInsert_Sq(SqList &L, int i, ElemType e)/ 在順序線性表L的第i個元素之前插入新的元素e ElemType *p; if (i < 1 | i > L.length+1) return ERROR; if (L.length >= L.listsize) ElemType *newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCERMENT)*sizeof (ElemType); if (!newbase) return ERROR; L.el

17、em = newbase; L.listsize += LISTINCERMENT; ElemType *q = &(L.elemi-1); for (p = &(L.elemL.length-1); p>=q; -p) *(p+1) = *p; *q = e; +L.length; return OK;Status ListDelete_Sq(SqList &L, int i, ElemType &e) / 在順序線性表L中刪除第i個元素，并用e返回其值 ElemType *p, *q; if (i<1 | i>L.length) retur

18、n ERROR; p = &(L.elemi-1); e = *p; q = L.elem+L.length-1; for (+p; p<=q; +p) *(p-1) = *p; -L.length; return OK; / ListDelete_SqStatus cmp(ElemType a,ElemType b) if(a=b) return YES; else return NO;Status LocateElem_Sq(SqList L, ElemType e,Status (*compare)(ElemType, ElemType) / 在順序線性表L中查找第1個值與

19、e滿足compare()的元素的位序 int i; ElemType *p; i = 1; p = L.elem; while (i <= L.length && !(*compare)(*p+, e) +i; if (i <= L.length) return i; else return 0;void MergeList_Sq(SqList La, SqList Lb, SqList &Lc) / 已知順序線性表La和Lb的元素按值非遞減排列。歸并La和Lb得到新的順序線性表Lc，Lc的元素也按值非遞減排列。 ElemType *pa,*pb,*pc,*

20、pa_last,*pb_last; pa = La.elem; pb = Lb.elem; Lc.listsize = Lc.length = La.length+Lb.length; pc = Lc.elem = (ElemType *)malloc(Lc.listsize*sizeof(ElemType); if (!Lc.elem) exit(OVERFLOW); / 存儲分配失敗 pa_last = La.elem+La.length-1; pb_last = Lb.elem+Lb.length-1; while (pa <= pa_last && pb <

21、= pb_last) / 歸并 if (*pa <= *pb) *pc+ = *pa+; else *pc+ = *pb+; while (pa <= pa_last) *pc+ = *pa+; / 插入La的剩余元素 while (pb <= pb_last) *pc+ = *pb+; / 插入Lb的剩余元素 / MergeListvoid Union_Sq(SqList &La,SqList Lb) int len1=La.length; int len2=Lb.length; int i,pl;ElemType e;/ for(i=1;i<=len2;i+

22、) pl=LocateElem_Sq(La,Lb.elemi-1,cmp); if(pl=0) ListInsert_Sq(La,+len1,Lb.elemi-1); len1=La.length; for(i=0;i<len1;i+) if(La.elemi=La.elemi+1) ListDelete_Sq(La,i+2,e); /*注意在原來La中，如果有重復也要刪除到只剩下一個*/void PrintList_Sq(SqList L) int i; for(i=0;i<L.length;i+) printf("%d ",L.elemi); printf("n");int main()SqList La,Lb,Lc;int i,n1,n2,e;printf("請輸入La元素個數(shù)：n");scanf("%d",&n1);if(InitList_Sq(La) for(i=1;i<=n1;i+) printf("請輸入La