sqlist.h

数据结构基础代码

#include <process.h>
#include <iostream.h>
//预定义常量和类型
const True=1;
const False=0;
const oK=1;
const error=0;
const infeasible=-1;
const overflow =2;
const maxsize=100;
const list_int_size=100;
const listincrement=10;
const underflow=0;

//预定义类型
typedef struct{
	int *elem;
	int length;
	int listsize;
	int incrementsize;
}sqlist;

//创建空表
void creatlist(sqlist &l)
{
	int x,i;
	//构造一个最大容量为maxsize的顺序表l
	l.elem=new int[maxsize];	//为顺序表分配一个最大容量为maxsize的数组空间
	l.length=0;
}

//初始化
void creatlist_sq(sqlist &l)
{
	int x,i;
	//构造一个最大容量为maxsize的顺序表l
	l.elem=new int[maxsize];	//为顺序表分配一个最大容量为maxsize的数组空间
	l.length=0;
	cout<<"请键入元素:"<<endl;
	for(i=0;i<maxsize;i++)
	{
		cin>>x;
		l.elem[i]=x;
		if(l.elem[i]==0)
			break;
		l.length++;
	}
}

//输出线性表的所有元素
void outputlist_sq(sqlist &l)
{
	int i;
	for(i=0;i<l.length;i++)
	{
		cout<<l.elem[i]<<'\t';
	}
}

//求长度
int len_sq(sqlist l)
{
return l.length;
}

//取元素
int getelem(sqlist l,int i)
{
	//在顺序表l中找到第i个位置的元素
	if(i<1||i>len_sq(l))	return 0;
	else return l.elem[i-1];
}

	


//查找元素
int locateelem_sq(sqlist l,int e)
{
	//在顺序表中l中查找第一个与e相等的数据元素
	//若找到，则返回其在l中的位序，否则返回0
	int i=1;
	while(i<=l.length && l.elem[i]!=e)	++i;
	if(i<=l.length)	return i+1;
	else return 0;
}

//出错信息处理函数
void errormessage(char *s)
{
	cout<<s<<endl;
	exit(1);
}


//插入元素
void listinsert_sq(sqlist &l,int i,int e)
{
	//在顺序表l的第i个元素之前插入新的元素e
	//i的合法值为1<=i<=l.length+1,若表中容量不足，则按该顺序表的预定义增量扩充
	if(i<1||i>l.length+1) errormessage("i值不合法!");
	for(int j=l.length-1;j>i;--j)
		l.elem[j+1]=l.elem[j];
	l.elem[i-1]=e;
	++l.length;
}


//删除元素
int listDelete_sq(sqlist &l,int i)       //删除
{
	if(i<1||i>l.length)  return error;
	if (l.length==0)  return underflow; // 表空
	for (int j=i;j<l.length; ++j)        
  		//被删除元素之后的元素前移
	l.elem[j-1]=l.elem[j]; 
	--l.length;   //表长减1
	return oK; 
}
	

//置空一个线形表
void Destroylist_sq(sqlist &l)   
{
	delete[]l.elem;
		l.listsize=0;
		l.length=0;
}

//非递减线性表合并
void mergelist(sqlist la,sqlist lb,sqlist &lc)
{
	int i=1;
	int j=1;
	int k=0;
	int ai,bi,ci;
	int la_len,lb_len;
	la_len=len_sq(la);
	lb_len=len_sq(lb);
	while((i<=la_len)&&(j<=lb_len))
	{
		ai=getelem(la,i);
		bi=getelem(lb,j);
		if(ai<=bi)
		{
			listinsert_sq(lc,++k,ai);
			++i;
		}
		else 
		{
			listinsert_sq(lc,++k,bi);
			++j;
		}
	}
	while(i<=la_len)
	{
		ai=getelem(la,i++);
		listinsert_sq(lc,++k,ai);
	}
	while(j<=lb_len)
	{
		bi=getelem(lb,j++);
		listinsert_sq(lc,++k,bi);
	}
	Destroylist_sq(la);
	Destroylist_sq(lb);
}