顺序表的应用.docx

1、顺序表的应用实验一 顺序表的应用一、实验目的1. 掌握线性表的顺序存储结构的存储特点与操作特点。2. 掌握顺序表的存储表示与基本操作的实现方法。3. 熟悉顺序表的基本应用。4. 了解抽象数据类型的定义、表示与实现的含义。二、实验容按如下要求编写程序，进行调试，写出调试正确的源代码，给出测试结果。实现线性表在顺序存储结构下的存储表示和基本操作，并应用抽象数据类型线性表完成如下操作：1分别创建两个空的线性表L1、L2；2分别将若干元素插入到L1、L2中，输出操作后表L1和L2的容；3. 实现两表的合并操作：L1=L1L2，输出合并后表L1的容。4. 实现两表的求差操作：L1=L1-L2，输出求差后

2、表L1的容。三、实验结果源代码：#include#include#define OK 1#define TRUE 1#define FALSE 0#define ERROR 0#define OVERFLOW -2#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef int Status;typedef int ElemType;typedef struct/存储表示 ElemType *elem; int length; int listsize;SqList;/基本操作的函数声明Status InitList_Sq(SqList

3、 & L);Status ListInsert_Sq(SqList &L,int i,ElemType e);Status equal(ElemType a,ElemType b);Status GetElem_Sq(SqList L,int i,ElemType &e);int ListLength_Sq(SqList L);void Unoin(SqList& La,SqList Lb);void cha(SqList &La,SqList &Lb);int LocateElem_Sq(SqList L,ElemType e,Status(*compare)(ElemType,ElemTy

4、pe);/基本操作的算法实现Status 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;Status ListInsert_Sq(SqList &L,int i,ElemType e) ElemType *newbase,*p,*q; if(iL.length+1) return ERROR; if(L.length=L.l

5、istsize) newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType); if(!newbase) exit(OVERFLOW); L.elem=newbase; L.listsize+=LISTINCREMENT; 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) E

6、lemType *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;void cha(SqList &La,SqList &Lb) int la_len,lb_len,i,e; la_len=ListLength_Sq(La); lb_len=ListLength_Sq(Lb); for(i=1;i=lb_len;i+) GetElem_Sq(Lb,i,e); if(LocateElem_Sq(L

7、a,e,equal) ListDelete_Sq(La,LocateElem_Sq(La,e,equal),e); Status equal(ElemType a,ElemType b) if(a=b) return TRUE; else return FALSE;Status GetElem_Sq(SqList L,int i,ElemType &e) if(iL.length) return ERROR; e=*(L.elem+i-1); return OK; int ListLength_Sq(SqList L) return L.length;void Unoin(SqList& La

8、,SqList Lb) int la_len,lb_len,i,e; la_len=ListLength_Sq(La); lb_len=ListLength_Sq(Lb); for(i=1;i=lb_len;i+) GetElem_Sq(Lb,i,e); if(!LocateElem_Sq(La,e,equal) ListInsert_Sq(La,+la_len,e); int LocateElem_Sq(SqList L,ElemType e,Status(*compare)(ElemType,ElemType) int i=1;ElemType *p; p=L.elem; while(i=

9、L.length&!(*compare)(*p+,e) +i; if(i=L.length) return i; else return 0;void main() int m,n,i; ElemType e; SqList L1,L2; InitList_Sq(L1); InitList_Sq(L2); coutm; coutn; cout请输入m个元素到L1表中endl; for(i=1;ie; ListInsert_Sq(L1,i,e); cout请输入n个元素到L2表中endl; for(i=1;ie; ListInsert_Sq(L2,i,e); coutL1表的容endl; for

10、(i=1;i=ListLength_Sq(L1);i+) GetElem_Sq(L1,i,e); coutet; coutendl; coutL2表的容endl; for(i=1;i=ListLength_Sq(L2);i+) GetElem_Sq(L2,i,e); coutet; coutendl; cout输出L1和L2的合并后; Unoin(L1,L2); coutL1表的容endl; for(i=1;i=ListLength_Sq(L1);i+) GetElem_Sq(L1,i,e); coutet; coutendl; cout输出L1和L2的差后; cha(L1,L2); coutL1表的容endl; for(i=1;i=ListLength_Sq(L1);i+) GetElem_Sq(L1,i,e); coutet; coutendl;运行结果：1运行结果：2