数据结构实验报告-顺序表.doc

1
江西理工大学软件学院
计算机类课程实验报告
课程名称： 数据结构
班 级：
姓 名： deleteElem(int i,ElemType& e);
//取第i个元素
int getElem(int i,ElemType& e);
//求顺序表中元素的个数
int getLength();
//求顺序表存储空间的大小
int getListSize();
//在第i个元素之前插入一个元素
Status insert(int i,ElemType e);
//判断顺序表是否为空
bool isEmpty();
//查找第1个与e满足compare关系的元素的序号
int locateElem(ElemType e,Status(*compare)(ElemType,ElemType));
12
//返回某个元素的后继
Status nextElem(ElemType e,ElemType& next_e);
//重载复制运算符
SqList<ElemType> operator =(SqList<ElemType> rightL);
//返回某个元素的前驱
Status priorElem(ElemType e,ElemType& prior_e);
//在顺序表中顺序查找某个元素、
int sequentialSearch(ElemType e);
};
//顺序表的方法
//有序顺序表的折半查找
template <typename ElemType>
int SqList<ElemType>::bin_Search(ElemType key)
{
int low,mid,high;//查找区域的起始、中间以及最后一个元素的下标
low=0,high= n-1;
while(low<=high)
{
mid=(low+high)/2;
if(elem[mid]==key)
12
return mid+1;
else if(elem[mid]<key)
low=mid+1;
else high=mid-1;
}
return 0;
}
//把顺序表置空
template <typename ElemType>
void SqList<ElemType>::clear()
{
n=0;
}
//删除第i个元素
template <typename ElemType>
Status SqList<ElemType>::deleteElem(int i,ElemType& e)
{
if(i<1||i>n) return ERROR;
e=elem[i-1];
for(int j=i+1;j<=n;++j)
elem[j-2]=elem[j-1];
--n;
13
return OK;
}
//取第i个元素
template <typename ElemType>
Status SqList<ElemType>::getElem(int i,ElemType& e)
{
if(i<1||i>n) return ERROR;
e=elem[i-1];
return OK;
}
//求顺序表中元素的个数
template <typename ElemType>
int SqList<ElemType>::getLength()
{
return n;
}
//取顺序表存储空间的大小
template <typename ElemType>
int SqList<ElemType>::getListSize()
{
return listSize;
}
14
//在第i元素之前插入一个元素
template <typename ElemType>
Status SqList<ElemType>::insert(int i,ElemType e)
{
ElemType *newbase;
if(i<1||i>n+1)
return ERROR;
if(n>=listSize)
{
newbase =new ElemType[listSize+LISTINCERMENT];
assert(newbase!=0);
for(int j=1;j<n;++j)
ne