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

1实验一顺序表的设计与实现一．实验目的1．进一步熟悉VC环境，会在其中编写调试运行c++代码，并理解多文件项目的组织，为以后的实验编程做准备。2．掌握在VC环境中进行代码的调试3．掌握顺序表的设计过程，并能通过一实例对设计的顺序表进行测试。二、实验内容1．顺序表的设计（Sqlist.h）：设计头文件sqlist.h，其内容如下：①类型设计②基本操作的设计（包括初始化、求数据元素个数、插入、删除、取数据元素等）（补充完整）#defineLIST_INIT_SIZE10#defineLIST_INCREMENT2//线性表的动态分配顺序存储结构structSqList{ElemType*elem;intlength;intlistsize;};//顺序表的初始化voidInitList(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;}2//在线性表的第i个位置上插入数据元素eStatusListInsert(SqList&L,inti,ElemTypee){ElemType*newbase,*q,*p;//判断插入的位置是否合理，不合理则返回错误信息if(i1||iL.length+1)returnERROR;//判断是否有足够的空间插入元素，空间不够则增补空间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;returnOK;}//删除线性表中第i个数据元素StatusListDelete(SqList&L,inti,ElemType&e){ElemType*p,*q;//判断删除的元素是否存在，不存在则返回错误信息if(i1||iL.length)returnERROR;//将第i+1个元素及其后所有元素前移一个位置，实现元素的删除p=L.elem+i-1;e=*p;q=L.elem+L.length-1;for(++p;p=q;++p)*(p-1)=*p;3//删除元素后，线性表的长度减1L.length--;//返回操作成功的提示信息returnOK;}//在顺序表中找给定元素值e的元素是否存在。存在则返回其位序，不存在返回0intLocate(SqListL,ElemTypee){//依次访问顺序表中的数据元素，并和e做比较，若相等则放回其位序，否则返回0for(inti=0;iL.length;i++)if(L.elem[i]==e)returni+1;return0;}//遍历线性表voidListTraverse(SqListL,void(*visit)(ElemType)){ElemType*p=L.elem;inti;for(i=1;i=L.length;i++)visit(*p++);coutendl;}2．测试：设计测试文件test.cpp，验证所设计的顺序表的正确性。其内容如下：①设计一个函数求解两个集合的并集。②设计一个主函数。#includeiostream.htypedefintElemType;#includeSqList.hvoidprint(ElemTypec){coutc;}Statusequal(ElemTypea,ElemTypeb){if(a==b)4returnTRUE;elsereturnFALSE;}voidunionlist(SqListLA,SqListLB,SqList&LC){for(inti=0;iLA.length;i++){LC.elem[i]=LA.elem[i];LC.length++;}for(i=0;iLB.length;i++){intk=LocateElem(LA,LB.elem[i],equal);if(!k){ListInsert(LC,LC.length+1,LB.elem[i]);}}}voidmain(){SqListLA,LB,LC;ElemTypea[4]={12,32,21,45};ElemTypeb[5]={32,34,54,12,27};InitList(LA);InitList(LB);InitList(LC);for(inti=1;i5;i++)ListInsert(LA,i,a[i-1]);for(i=1;i=5;i++)ListInsert(LB,i,b[i-1]);ListTraverse(LA,print);ListTraverse(LB,print);unionlist(LA,LB,LC);cout合并数据元素后的线性表为：;ListTraverse(LC,print);}3．思考：如何实现有序顺序表：