实验一顺序表的设计与实现
1.实验目的
1.进一步熟悉VC坏境，会在其中编写调试运行C++代码，并理解多文件项目的组织，为 以后的实验编程做准备。
2.掌握在VC环境中进行代码的调试
3.掌握顺序表的设计过程，并能通过一实例对设计的顺序表进行测试。
二、 实验内容
1.顺序表的设计(Sqlisth)：设计头文件sqlist.h,其内容如下：生态驳岸
1类型设计
2基本操作的设计(包扌舌初始化、求数据元素个数、插入、删除、取数据元素等)
(补充完整)
#define LIST_INIT_SIZE 10
#define LIST_INCREMENT 2
〃线性表的动态分配顺序存储结构
stmct SqList
{
ElemTvpe *elem;
mt length;
mt listsize;
};
〃顺序表的初始化
void InitList(SqList &L)
{
//动态分配存储空间，并将分配到的存储空间的首地址保持在顺序表的elem项中 L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!L.elem)
exit(OVERFLOW);
〃将顺序表的长度初始化为0
L.length=0;
〃将顺序表的容量初始化为分配的空间数
L.Ustsize=LIST_INIT_SIZE;
}
//在线性表的第i个位置上插入数据元素e
Status ListInrt(SqList &Ljnt i,EleniTvpe e)
中外差异{
ElemTvpe *newba/q,*p;
〃判断插入的位置是否合理，不合理则返回错误信息
if(i<l ||i>L.length+l)
return ERROR:
//判断是否有足够的空间插入元素，空间不够则增补空间
if(L.length=L Jistsize)
{
newba=(ElemT\?pe*)realloc(L.elenL(L.listsize+LIST_INCREMENT)*sizeof(ElemType)); if(!newba)
exit(OVERFLOW);
L.elem=newba;
L.listsize+=LIST_INCREMENT;
心率过快的原因}
//插入数据元素(先将第1个元素及其后所有元素后移一个位置)
q=L.elem+i-l;
fbi (p=L.elem+L.length-1 ;p>=q;-p)
*(p+l)=*p;
〃将元素e插入到第出生年月日查缺五行i个位置
*q=e;
〃线性表的长度增加1
++L」ength;
return OK;
}
〃删除线性表中第1个数据元素
Status ListDelete(SqList &L,int i.ElemType &e)
{
工作证明
ElemTvpe *p,*q;
〃判断删除的元素是否存在，不存在则返回错误信息
if(i<l||i>L.length)
return ERROR:
〃将第1+1清一色个元素及其后所有元素前移一个位置，实现元素的删除
p=L.elem+i-l;
e=*p;
q=L.elem+L length";
+p；p<=q；卄p)
〃删除元素后，线性表的长度减1
L.length--;
〃返回操作成功的提示信息
return OK:
}
〃在顺序表中找给定元素值e的元素是否存在。存在则返回其位序，不存在返回0
mt Locate(SqList L.ElemType e)
{
〃依次访问顺序表中的数据元素，并和e做比较，若相等则放回其位序，否则返回0 i=O;i<L.length;i++)
if(L.elem[i]==e)
return i+1;
return 0;
}
〃遍历线性表
void ListTiavei(SqList L,void(*visit)(ElemType))
{
ElemTvpe *p=L.elem;
inti;
foi(i= 1 ;i<=L.length;i++)
visit(*p++);
cout«endl;
}
2.测试：设计测试文件test.cpp,苹果用英语怎么读验证所设计的顺序表的正确性。其内容
如下：
1设计一个函数求解两个集合的并集。
2设计一个主函数。
#include <iostreain.h>
tvpedef int ElemTvpe;
射综合
#include HSqList.hM
void piiiit(ElemType c)
{
cout«c«H ”；
}
Status equal(ElemType a.ElemTvpe b)
if(a=b)
return TRUE;
el
return FALSE;
void unioiilist(SqList LA, SqList LB.SqList &LC)
for(int i=O;i<LA.lengtli;i-H-)
LC.elem[i]=LA.elem[i];
LC.length++； mt k=LocateElem(LA,LB.elem[i].equal); if(!k)
ListInrt(LC,LC.lengtli+1 ,LB.elem[i]);
void main()
SqList LA,LB.LC;
ElemTvpe a[4]={ 12,32,2X45};
ElemTvpe b[5]={32,34,54,12,27}; IiutList(LA);
IiutList(LB);
IiutList(LC);
for(int i=l;i<5;i++)
ListIiirt(LA4,a[i-l]); for(i=l;i<=5;i-H-)
ListInrt(LB,i,b[i-1 ]);
ListTraver(LA,print); ListTraver(LB,print); umoiilist(LA,LB,LC); cout«"合并数据元素后的线性表为：”; ListTraver(LC,print);
3.思考：如何实现有序顺序表:
