sqlist.cpp

实现线性表的顺序存储表示及基于顺序存储表示实现线性表的初始化、查找、插入与删除等基本操作。具体实现要求：1．从键盘输入10个整数

// SqList.cpp: implementation of the CSqList class.
//
//////////////////////////////////////////////////////////////////////

#include "SqList.h"
#include "malloc.h"
#include "iostream.h"
#include "stdlib.h"


//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
CSqList::CSqList()
{
   InitList(List);  
}
CSqList::~CSqList()
{
   DestroyList(List);
}

Status CSqList::InitList(SqList &L)
{
	//构造一个空的有序表L;如果构造成功,函数返回TRUE,否则返回FALSE 
	L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
	if(!L.elem)
	{
		cout<<"OVERFLOW"<<endl;
		exit(0);  //存储分配失败
	}
	L.length = 0;        //空表长度为0
	L.listsize = LIST_INIT_SIZE;  //初始存储容量
	return OK;
}

void CSqList::DestroyList(SqList &L)
{
   //销毁有序表L。
   free(L.elem);
   L.listsize=0;
}

void CSqList::ClearList(SqList &L)
{
  //将有序表L置为空表
   L.length=0;

}

Status CSqList::ListEmpty(SqList L)
{
	//判断有序表L是否为空；是则返回值TRUE，否则返回值FALSE。
	if(L.length==0) return TRUE;
	return FALSE;
}

int CSqList::ListLength(SqList L)
{
	//返回有序表L的长度。
	return L.length;
}

Status CSqList::GetElem(SqList L, int pos, ElemType &e)
{
	//若1≤pos≤ListLength(L)，则用e返回表中第pos个数据元素,函数返回值TRUE
	//否则,函数返回值FALSE。
	if(1<=pos&&pos<=ListLength(L)){
		e=L.elem[pos];
		return TRUE;
	}
	return FALSE;
}

int CSqList::LocateElem(SqList L, ElemType e, int &q)
{
	//若表L中存在元素e，则q指示L中第一个值为e的元素的位置，函数返回值TRUE
	//否则q指示表L中第一个大于e的元素的前驱的位置，函数返回值FALSE。
	int i=0;
	while(i<=L.length){
		if(L.elem[i]==e) break;
		i++;
	}
	if(i<L.length){
		q=i+1;
		return TRUE; 
	}
	return FALSE;
}

Status CSqList::ListInsert(SqList &L, int pos, ElemType e)
{
    //若有序表L已存在且1≤pos≤ListLength(L)+1。
    //则将数据元素e插入到有序表L中，e成为有序表L的第pos个元素。
	ElemType *p,*q,*newbase;
	if(pos <1||pos >L.length+1)return ERROR; // pos值不合法
	if(L.length>=L.listsize){ //当前存储空间满,增加分配
		newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
		if(!newbase)
		{
			cout<<"OVERFLOW"<<endl;
			exit(0);  //存储分配失败
		}
		L.elem=newbase;   //新基址
		L.listsize+=LISTINCREMENT;
	}
	q=&(L.elem[pos -1]); //q为插入位置
	for(p=&(L.elem[L.length-1]);p>=q;--p)* (p+1)=*p;  //插入位置及其后元素右移1位
	*q=e;  //插入e
	++L.length;  //表长加1;
	return OK;
}

Status CSqList::ListDelete(SqList &L, int pos, ElemType &e)
{
	//删除有序表L的第pos个元素,并用e返回其值,L的长度减1。
	ElemType *p,*q;
	if(pos <1||pos >L.length)return ERROR; // pos值不合法
	q=&(L.elem[pos -1]); //q为删除位置
	e=*q;
	for(p=&(L.elem[L.length-1]);q<p;++q) *q = *(q+1);  //删除位置及其后元素左移1位
	--L.length;  //表长加1;
	return OK;
}

Status CSqList::ListEditElement(SqList &L, int pos, ElemType e)
{
	//将有序表L的第pos个元素的值替换为e,并返回TRUE,否则返回FALSE。
    ElemType *q; 
	if(pos <1||pos >L.length)return ERROR; // pos值不合法
	q=&(L.elem[pos -1]); //q为修改位置
	*q = e;
	return OK;
}

void CSqList::ListDisplay(SqList L)
{
	//从表头至表尾,顺序输出线性表L中的每一个数据元素。
	int i;
	for(i=0;i<L.length;++i) 
		cout<<L.elem[i]<<"  ";
	cout<<endl;
}