实验一 顺序表基本操作

实验一 顺序表基本操作一 实验目的1.学会定义线性表的顺序存储类型，实现C程序的基本结构，对线性表的一些基本操作和具体的函数定义。2.掌握顺序表的基本操作，实现顺序表的插入、删除、查找以及求并集等运算。3.掌握对多函数程序的输入、编辑、调试和运行过程。二 实验要求1预习C语言中结构体的定义与基本操作方法。2对顺序表的每个基本操作用单独的函数实现。3编写完整程序完成下面的实验内容并上机运行。4整理并上交实验报告。 三 实验内容：1编写程序实现顺序表的下列基本操作： (1)初始化顺序表La。 (2)将La置为空表。 (3)销毁La。 (4)在La中插入一个新的元素。 (5)删除La中的某一元素。 (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)删除La中的某一元素。(6)在La中查找某元素，若找到，则返回它在La中第一次出现的位置，否则返回0。(7)打印输出La中的元素值。#include#include#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#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.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 e) ElemType *p; if (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 (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 (iL.length) return 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 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; else return 0;/打印顺序表void PrintList_Sq(SqList L) int i; for(i=0;iL.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); scanf(%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(插入元素后线性表为：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(-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_Sq(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，其元素都按值非递减顺序排列。(2)实现归并La和Lb得到新的顺序表Lc，Lc的元素也按值非递减顺序排列。(3)假设两个顺序线性表La和Lb分别表示两个集合A和B，利用union_Sq操作实现A=AB。#include#include#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 ElemType ;#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;/*/Status ListInsert_Sq(SqList &L, int i, ElemType e)/ 在顺序线性表L的第i个元素之前插入新的元素e ElemType *p; if (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.elem = 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 (iL.length) return 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个值与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,*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 = 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+) pl=LocateElem_Sq(La,Lb.elemi-1,cmp); if(pl=0) ListInsert_Sq(La,+len1,Lb.elemi-1); len1=La.length; for(i=0;ilen1;i+) if(La.elemi=La.elemi+1) ListDelete_Sq(La,i+2,e); /*注意在原来La中，如果有重复也要删除到只剩下一个*/void PrintList_Sq(SqList L) int i; for(i=0;iL.length;i+) printf(%d ,L.elemi); printf(n);