c.h

数据结构中相关ADT的C++实现,注解清晰,让你快速掌握

//实现顺序表
#include<iostream.h>
#include<stdlib.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define OVERFLOW  -2
#define OK 1
typedef struct
{
	int * elem;
int length;
int listsize;
}
list;
void initlist(list & L)
{//构造一个空的线性表L
	L.elem=new int[LIST_INIT_SIZE];
if(!L.elem) exit(OVERFLOW);
L.length=0;
L.listsize=LIST_INIT_SIZE;
return ;
}
void destroylist(list & L)
{//销毁一个线性表L
	if(L.elem)
	{
		delete L.elem;
	}
	return ;
}
void clearlist(list & L)
{//清空一个线性表
	if(L.elem)
	{
		delete L.elem;
		L.elem=new int[L.listsize];
	}
	return ;
}
int listempty(list L)
{//判断线性表是否为空
	if(L.elem&&L.length==0)
		return 1;
    else
		return 0;
}
int listlength(list L)
{//返回线性表中元素的个数
	if(L.elem)
		return L.length;
if(!L.elem) exit(OVERFLOW);
}
int getelem(list L,int i,int & e)
{//用e返回L中第i个元素的值
	if(L.elem&&i>=1&&i<=L.length)
	{
		e=L.elem[i-1];
	}
	return e;
}
int compare(double m,double n)
{//比较两个数大小,1代表m>n,0代表m=n,-1代表m<n
	if(m>n) return 1;
	if(m<n) return 0;
	if(m==n) return -1;
}
int locateelem(list L,int e,const int c)//常量c的值为compare函数中三种返回值的一种,代表了L和e三种比较关系
{//返回L中第一个与e满足关系c的数据元素的位序,若这样的数据元素不存在,则返回值为0
	for(int i=0;i<L.length;i++)
	{
		if(compare(L.elem[i],e)==c)
			return i+1;
	}
	return 0;
}
int priorelem(list L,int cur_e,int & pre_e)
{//返回前驱
	int k=0;
	for(int i=0;i<L.length;i++)
	{
		if(cur_e==L.elem[i])
		{
			k=i+1;
			break;
		}
	}
	if(k<2)
     exit(OVERFLOW);
	pre_e=L.elem[k-2];
	return pre_e;
}
int nextelem(list L,int cur_e,int & next_e)
{//返回后继
	int k=0;
	for(int i=0;i<L.length;i++)
	{
		if(cur_e==L.elem[i])
		{
			k=i+1;
			break;
		}
		
	}
	if(k==0||k==L.length)
     exit(OVERFLOW);
	next_e=L.elem[k];
		return next_e;
}
void listinsert(list & L,int i,int e)
{//插入元素
	if(i<1||i>(L.length+1)||!L.elem)
		exit(OVERFLOW);
	if(L.length>=L.listsize)
	{
		int * newbase=new int[L.listsize+LISTINCREMENT];
		for(int j=0;j<L.length;j++)
		{
			newbase[j]=L.elem[j];
		}
		L.elem=newbase;
		L.listsize+=LISTINCREMENT;
	}
	int * q=& L.elem[i-1];
	for(int * p=& L.elem[L.length-1];p>=q;p--)
		*(p+1)=*p;
	* q=e;
	L.length++;
}
int listdelete(list & L,int i,int & e)
{//删除元素
	if(i<1||i>L.length||!L.elem)
		exit(OVERFLOW);
	int * q=& L.elem[i-1];
	e=* q;
	for(int *p=& L.elem[L.length-1];q<=p;q++)
		* q=*(q+1);
	L.length--;
	return e;
}
void listtraverse(list L)
{//遍历线性表
	if(L.elem)
	{
for(int j=0;j<L.length;j++)
{
	cout<<L.elem[j]<<endl;
}
	}
else exit(OVERFLOW);
	}




void main()
{int n;
	list L;
	L.elem=NULL;
initlist(L);
cout<<"1代表空表,0为不空"<<listempty(L)<<endl;
for(int i=0;i<10;i++)
{
L.elem[i]=i;
L.length=10;
}
cout<<"1代表空表,0为不空"<<listempty(L)<<endl;
listinsert(L,11,10);
listtraverse(L);
clearlist(L);
for(int j=0;j<10;j++)
{
L.elem[j]=j;
L.length=10;
}
listtraverse(L);
cout<<listlength(L)<<endl;
cout<<getelem(L,3,n)<<endl;
cout<<priorelem(L,3,n)<<endl;
cout<<nextelem(L,3,n)<<endl;
cout<<listdelete(L,10,n)<<endl;
destroylist(L);
}