实验一-顺序表的设计与实现.doc

实验一 顺序表的设计与实现一实验目的1进一步熟悉VC环境，会在其中编写调试运行c+代码，并理解多文件项目的组织，为以后的实验编程做准备。2掌握在VC环境中进行代码的调试3掌握顺序表的设计过程，并能通过一实例对设计的顺序表进行测试。 二、实验内容1顺序表的设计（Sqlist.h）：设计头文件sqlist.h，其内容如下： 类型设计基本操作的设计（包括初始化、求数据元素个数、插入、删除、取数据元素等）（补充完整）#define LIST_INIT_SIZE 10 #define LIST_INCREMENT 2 /线性表的动态分配顺序存储结构struct SqList ElemType *elem; int length; int listsize; ; /顺序表的初始化void InitList(SqList &L) /动态分配存储空间，并将分配到的存储空间的首地址保持在顺序表的elem项中L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!L.elem) exit(OVERFLOW);/将顺序表的长度初始化为0L.length=0;/将顺序表的容量初始化为分配的空间数L.listsize=LIST_INIT_SIZE;/在线性表的第i个位置上插入数据元素eStatus ListInsert(SqList &L,int i,ElemType e) ElemType *newbase,*q,*p; /判断插入的位置是否合理，不合理则返回错误信息if(iL.length+1) return ERROR;/判断是否有足够的空间插入元素，空间不够则增补空间if(L.length=L.listsize) newbase=(ElemType*)realloc(L.elem,(L.listsize+LIST_INCREMENT)*sizeof(ElemType);if(!newbase) exit(OVERFLOW);L.elem=newbase; L.listsize+=LIST_INCREMENT; /插入数据元素（先将第i个元素及其后所有元素后移一个位置） q=L.elem+i-1; for(p=L.elem+L.length-1;p=q;-p) *(p+1)=*p;/将元素e插入到第i个位置*q=e; /线性表的长度增加1+L.length; return OK;/删除线性表中第i个数据元素Status ListDelete(SqList &L,int i,ElemType &e) ElemType *p,*q;/判断删除的元素是否存在，不存在则返回错误信息 if(iL.length) return ERROR;/将第i+1个元素及其后所有元素前移一个位置，实现元素的删除p=L.elem+i-1; e=*p; q=L.elem+L.length-1; for(+p;p=q;+p) *(p-1)=*p;/删除元素后，线性表的长度减1L.length-; /返回操作成功的提示信息return OK;/在顺序表中找给定元素值e的元素是否存在。存在则返回其位序，不存在返回0int Locate(SqList L,ElemType e)/依次访问顺序表中的数据元素，并和e做比较，若相等则放回其位序，否则返回0for(int i=0;iL.length;i+)if(L.elemi=e)return i+1;return 0;/遍历线性表void ListTraverse(SqList L,void(*visit)(ElemType) ElemType *p=L.elem; int i; for(i=1;i=L.length;i+) visit(*p+); coutendl;2测试：设计测试文件test.cpp，验证所设计的顺序表的正确性。其内容如下：设计一个函数求解两个集合的并集。设计一个主函数。#include typedef int ElemType; #include SqList.hvoid print(ElemType c) coutc ;Status equal(ElemType a,ElemType b)if(a=b)return TRUE;else return FALSE;void unionlist(SqList LA, SqList LB,SqList &LC)for(int i=0;iLA.length;i+)LC.elemi=LA.elemi;LC.length+;for(i=0;iLB.length;i+)int k=LocateElem(LA,LB.elemi,equal);if(!k)ListInsert(LC,LC.length+1,LB.elemi);void main()SqList LA,LB,LC;ElemType a4=12,32,21,45;ElemType b5=32,34,54,12,27;InitList(LA);InitList(LB);InitList(LC);for(int i=1;i5;i+)ListInsert(LA,i,ai-1);for(i=1;i=5;i+)ListInsert(LB,i,bi-1);ListTr