实验一 顺序表基本操作

1、实验一 顺序表基本操作一 实验目的1.学会定义线性表的顺序存储类型，实现C程序的基本结构，对线性表的一些基本操作和具体的函数定义。2.掌握顺序表的基本操作，实现顺序表的插入、删除、查找以及求并集等运算。3.掌握对多函数程序的输入、编辑、调试和运行过程。二 实验要求1预习C语言中结构体的定义与基本操作方法。2对顺序表的每个基本操作用单独的函数实现。3编写完整程序完成下面的实验内容并上机运行。4整理并上交实验报告。 三 实验内容：1编写程序实现顺序表的下列基本操作： (1)初始化顺序表La。 (2)将La置为空表。 (3)销毁La。 (4)在La中插入一个新的元素。 (5)删除La中的某一元素。

2、(6)在La中查找某元素，若找到，则返回它在La中第一次出现的位置，否则返回0。 (7)打印输出La中的元素值。2编写程序完成下面的操作：(1)构造两个顺序线性表La和Lb，其元素都按值非递减顺序排列。(2)实现归并La和Lb得到新的顺序表Lc，Lc的元素也按值非递减顺序排列。(3)假设两个顺序线性表La和Lb分别表示两个集合A和B，利用union_Sq操作实现A=AB。四 思考与提高假设两个顺序线性表La和Lb分别表示两个集合A和B，如何实现A=A B ？1编写程序实现顺序表的下列基本操作：(1)初始化顺序表La。(2)将La置为空表。(3)销毁La。(4)在La中插入一个新的元素。(5)删

3、除La中的某一元素。(6)在La中查找某元素，若找到，则返回它在La中第一次出现的位置，否则返回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;/构造空的顺序表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("请输入元素个数：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)构造两个顺序线性表La和Lb，

14、其元素都按值非递减顺序排列。(2)实现归并La和Lb得到新的顺序表Lc，Lc的元素也按值非递减顺序排列。(3)假设两个顺序线性表La和Lb分别表示两个集合A和B，利用union_Sq操作实现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)/构造空的顺序表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元素个数：n");scanf("%d",&n1);if(InitList_Sq(La) for(i=1;i<=n1;i+) printf("请输入La