list.h

在Dos下面模拟仓库的管理模式

/*该程序是数据结构第二章线性表的一个小程序！
程序员是黄俊冬  01（8）06010836
完成时间：2003年3月6日*/
# include<iostream.h>
# include<stdlib.h>
# include<iomanip.h>
struct List
{ ElemType list[MaxSize];
  int size;
};
//1初始化线性表
void InitList(List &L)
{
	L.size=0;
}
//2删除线性表中的所有元素
void ClearList(List &L)
{L.size=0;
}
//3得到线性表的长度
int ListSize(List &L)
{
	return L.size;
}
//4检查线性表是否为空
int ListEmpty(List &L)
{
	return(L.size==0);
}
//5得到线性表中指定序号的元素
ElemType GetElem(List &L, int pos)
{
	if(pos<1||pos>L.size) //若pos越界则退出程序
	{
		cerr<<"pos is out range!"<<endl;
		exit(1);
	}
	return L.list[pos-1];//返回线性表中第pos个元素的值
}
//6遍历一个线性表
void TraverseList(List &L)
{ for(int i=0;i<L.size;i++)
  cout<<setw(4)<<L.list[i];//设置打印宽度，需要包含iomanip.h
  cout<<endl;
}
//7从线性表中查找具有给定值的第一个元素
int Find(List &L, ElemType &item)
{
	for(int i=0;i<L.size;i++)
    if(L.list[i]==item)
	{
		item=L.list[i];
		return 1;
	}
	return 0;
}
//8更新线性表中具有给定值的第一个元素
int Update(List &L,const ElemType &item)
{
	for(int i=0;i<L.size;i++)
		if(L.list[i]==item)
		{L.list[i]=item;
		 return 1;
		}
		return 0;
}
//9向线性表的末尾添加一个元素
void InsertRear(List &L,const ElemType &item)
{
	if(L.size==MaxSize)//若表已满，则停止插入，退出程序运行
	{
		cerr<<"List overflow!"<<endl;
		exit(1);
	}
	L.list[L.size]=item;//把item的值插入到表尾，即写入到最后一个元素的后一个位置上
	L.size++;
}
//10向线性表的表头插入一个元素
void InsertFront(List &L, const ElemType &item)
{
	if(L.size==MaxSize)
	{
		cerr<<"List overflow!"<<endl;
		exit(1);
	}
	for(int i=L.size-1;i>=0;i--)
		L.list[i+1]=L.list[i];
	    L.list[0]=item;
		L.size++;
}
//11在线性表中第i个元素前插入元素
void Insert(List &L,int i,ElemType x)
{
	if(i<1||i>L.size+1)
	{
		cerr<<"Index is out of range:"<<endl;
		exit(1);
	}
	if(L.size==MaxSize)
	{
		cerr<<"list overflow!"<<endl;
		exit(1);
	}
	for(int j=L.size-1;j>=i-1;j--)
		L.list[j+1]=L.list[j];
	L.list[i-1]=x;
	L.size++;
}
//12向线性表中满足条件的位置插入一个元素
void InsertItem(List &L,const ElemType &item)
{
	if(L.size==MaxSize)
	{
		cerr<<"List overflow!"<<endl;
		exit(1);
	}
	for(int i=0;i<L.size;i++)
		if(item<L.list[i])
			break;
		for(int j=L.size-1;j>=i;j--)
			L.list[j+1]=L.list[j];
		L.list[i]=item;
		L.size++;
}
//13从线性表中删除表头元素
ElemType DeleteFront(List &L)
{
	if(L.size==0)
	{
		cerr<<" Deleting from an empty list!"<<endl;
		exit(1);
	}
	ElemType temp=L.list[0];
	for(int i=1;i<L.size;i++)
		L.list[i-1]=L.list[i];
	L.size--;
	return temp;
}
//14从线性表中删除等于给定值的第一个元素
int Delete(List &L,const ElemType &item)
{
	if(L.size==0)
	{
		cerr<<" L is an empty list!"<<endl;
		return 0;
	}
	for(int i=0;i<L.size;i++)
		if(L.list[i]==item)
			break;
		if(i==L.size)
		{
			cerr<<" Deleted element is not exist!"<<endl;
			return 0;
		}
		for(int j=i+1;j<L.size;j++)
			L.list[j-1]=L.list[j];
		L.size--;
		return 1;
}
//15对线性表进行排列
void Sort(List &L)
{
	int i,j;
	ElemType x;
	for(i=1;i<L.size;i++)
	{
		x=L.list[i];
		for(j=i-1;j>=0;j--)
			if(x<L.list[j])
				L.list[j+1]=L.list[j];
			else break;
			L.list[j+1]=x;
	}
}
//将两个有序表合并成一个新的有序表
void Merge(List &L1,List &L2,List &L)
{
	if(L1.size+L2.size>MaxSize)
	{
		cerr<<"List overflow."<<endl;
		exit(1);
	}
	int i=0,j=0,k=0;
	while((i<L1.size)&&(j<L2.size))
	{
		if(L1.list[i]<=L2.list[j])
		{L.list[k]=L1.list[i];
		i++;
		}
	
	else
	{
		L.list[k]=L2.list[j];
		j++;
	}
	k++;
	}
	while(i<L1.size)
	{
		L.list[k]=L1.list[i];
		i++;
		k++;
	}
	while(j<L2.size)
	{
		L.list[k]=L2.list[j];
		j++;
		k++;
	}
	L.size=k;
}