sqlist.cpp

各种算法的c语言程序

#include "SqList.h"

//顺序表的函数定义

Status InitList_Sq(Sqlist &L)
{
	//构造一个空的线性表L
	L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
	if(!L.elem)return OVERFLOW;//存储分配失败
	L.length=0;				  //空表长度为0
	L.listsize=LIST_INIT_SIZE;//初始存储容量
	return OK;
}//InitList_Sq

void DestroyList_Sq(Sqlist &L)
{
	//销毁已存在的顺序表
	free(L.elem);
}//DestroyList_Sq

Status ClearList(Sqlist &L)
{
	//把顺序表置空
	if(L.elem)
	{
		L.length=0;
		return TRUE;
	}
	else 
		return FALSE;
}//ClearList_Sq

Status CreateList_Sq(Sqlist &L)
{
	//键盘输入线性表的初始长度，各个元素，创建顺序表
	int len,i;
	ElemType e;
	cout<<"Input the length of the list:";
	cin>>len;
	if(len<1)
		return ERROR;
	cout<<"Input every member\n";
	for(i=1;i<=len;i++)
	{
		//cout<<i<<":";
		cin>>e;
		if(ListInsert_Sq(L,L.length+1,e)==OVERFLOW)
			return OVERFLOW;
	}
	return OK;	
}//CreateList_Sq

Status ListEmpty_Sq(Sqlist L)
{
	//判断顺序表是否为空
	if(L.length==0) return TRUE;
	else return FALSE;
}//ListEmpty_Sq

int ListLength_Sq(Sqlist L)
{
	//顺序表长度
	return L.length;
}//ListLength_Sq

Status GetElem_Sq(Sqlist L,int i,ElemType &e)
{
	//取得顺序表元素
	if(0,i&&i<=L.length)
	{
		e=*(L.elem+i-1);
		return OK;
	}
	else if(i<=0)
		 return ERROR;
	else return OVERFLOW;
}//GetElem_Sq

int LocateElem_Sq(Sqlist L,ElemType e,Status (*compare)(ElemType e1,ElemType e2))
{
	//取得某元素的位置
	for (int i=0;i<L.length;i++)
		if(compare(*(L.elem+i),e))
			return i+1;
	return 0;
}//LocateElem_Sq

Status PriorElem_Sq(Sqlist L,ElemType cur_e,ElemType &pre_e)
{
	//取得某元素之前的一个元素
	for(int i=1;i<L.length;i++)
		if(*(L.elem+i)==cur_e)
		{
		   pre_e=*(L.elem+i-1);
		   return TRUE;
		}
	return FALSE;
}//PriorElem_sq

Status NextElem_Sq(Sqlist L,ElemType cur_e,ElemType &next_e)
{
	//取得某元素之后的一个元素
	for(int i=0;i<L.length;i++)
		if(*(L.elem+i)==cur_e)
		{
			next_e=*(L.elem+i+1);
			return TRUE;
		}
	return FALSE;
}//NextElem_Sq

Status ListInsert_Sq(Sqlist &L,int i,ElemType e)
{
	//在指定位置之前插入一个元素
	if((i<1)||(i>L.length+1))
		return ERROR;
	if(L.length>=L.listsize)
	{
		//当前存储空间已满，增加分配
		ElemType *newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
		if(!newbase)return OVERFLOW;
		L.elem=newbase;//新基址
		L.listsize+=LISTINCREMENT;
	}
	ElemType *q=L.elem+i-1;//q为插入位置
	for(ElemType *p=L.elem+L.length-1;p>=q;--p)
		*(p+1)=*p;
	*q=e;
	++L.length;
	return OK;
}//ListInsert_Sq


Status ListDelete_Sq(Sqlist &L,int i,ElemType &e)
{
	//在顺序表L中删除第i个元素，并用e返回其值
	if((i<1)||(i>L.length))
		return ERROR;
	ElemType *p=L.elem+i-1;
	e=*p;
	ElemType *q=L.elem+L.length-1;
	for(p++;p<=q;p++)
		*(p-1)=*p;
	L.length--;
	return OK;
}//ListDelete_Sq

void ListDisplay_Sq(Sqlist L)
{
	if(L.length==0)
		cout<<"Empty List!!";
	for(int i=0;i<L.length;i++)
		cout<<*(L.elem+i)<<" ";
}//ListDisplay_Sq