seqlist.cpp

有关队列的排序问题

#include <iostream>
#include <cstdlib>
//#include <climits>
#include "seqlist.h"

using namespace std;

//////////////////////////////////////////////////////////
void InitList_sq(Sqlist& l)
{  //构造一个空的线性表
	
	l.elem=new ElemType[List_Init_Size];
	if(!l.elem) 
	{
		cout<<"OVERFLOW"<<endl;
		exit(1);
	}//存储空间分配失败
	l.length=0;
	l.listsize= List_Init_Size;
	
}
//////////////////////////////////////////////////////////
void DestroyList_sq(Sqlist& l)
{ //销毁顺序表l
	
	delete []l.elem;
	l.elem=NULL;
	l.length=l.listsize=0;
}
/////////////////////////////////////////////////////////
void ClearList_sq(Sqlist& l)
{ //将线性表置为空表
	l.length=0;
}
/////////////////////////////////////////////////////////
bool ListEmpty_sq(Sqlist l)
{
	return(l.length==0);
}
///////////////////////////////////////////////////////////
int ListLength_sq(Sqlist l)
{
	return(l.length);
}
////////////////////////////////////////////////////////
void GetElem_sq(Sqlist l, int i, ElemType& e)
{  //若1≤i≤l.length, 则用e返回线性表的第i个数据元素
	if( ( i>=1)&&(i<=l.length) ) e=l.elem[i-1];
	else e=-1;
}
///////////////////////////////////////////////////////
int LocateElem_sq(Sqlist l, ElemType e)
{ // 在顺序表l中查找第1个值与e满足compare()的元素的位序, 若找到, 返回其在// l中的位序,否则返回0
	int i=1;
	ElemType *p;
	p=l.elem;
	while( (i<=l.length) && (!compare(*p,e)) )
	{
		p++;
		i++;
	}
	if(i<=l.length) return i;
	else return 0;
}
////////////////////////////////////////////////////////////
void PriorElem_sq(Sqlist l, ElemType cur_e, ElemType& Pre_e)
{//若cur_e是l的数据元素, 且不是第一个, 则用pre_e返回它的直接前驱, 
	//否则操作失败, pre_e无定义
	int pos;

	pos= LocateElem_sq(l, cur_e);
	if(pos&&pos!=1) 
	{
		Pre_e=l.elem[pos-2];
	}
	else Pre_e=-1;
}
//////////////////////////////////////////////////////////////
void NextElem_sq(Sqlist l, ElemType cur_e, ElemType& Next_e)
{//若cur_e是l的数据元素, 且不是最后一个, 则用next_e返回它的直接后继, 否则操作失败, next_e无定义
	int pos= LocateElem_sq(l, cur_e);
	if(pos && pos!=l.length) 
	{
		Next_e=l.elem[pos];
	}
	else Next_e=-1;
}
//////////////////////////////////////////////////////////////////
void ListInsert_sq(Sqlist& l, int i, ElemType e)
{// 在顺序表l中第i个数据元素之前插入一个数据元素e,其中1<=i<=l.length+1
	ElemType* newbase;
	int j;

	if ( (i<1)||(i> l.length+1) ) 
	{
		cout<<"invalid i!"<<endl;
		exit(1);
	}
	if (l.length>=l.listsize)
	{
		//当前存储空间已满,增加分配
		newbase=new ElemType[l.listsize+ ListIncrement];
		if(!newbase) 
		{
			cout<<"OVERFLOW"<<endl;
			exit(1);//存储分配失败
		}
		l.listsize+= ListIncrement;//增加存储容量
		for(j=0; j<i-1; j++) newbase[j]=l.elem[j];
		newbase[j]=e;
		for(j=i; j<=l.length; j++) newbase[j]=l.elem[j-1];
		delete []l.elem;
		l.elem=newbase; //新基址
	}
	else
	{
		for(j=l.length;j>=i; j--) l.elem[j]=l.elem[j-1];
		l.elem[i-1]=e;
	}

	l.length++;//表长增1
}//ListInsert_sq
///////////////////////////////////////////////////////////////////
void ListDelete_sq(Sqlist&l, int i, ElemType& e)
{ //在顺序表l中删除第i个数据元素,并用e返回其值,其中1<=i<=l.length
	ElemType *p,*q;
	
	if  ( (i<1)||(i>l.length) ) 
	{
		cout<<"invalid i"<<endl;//非法的i
		exit(1);
	}
	p=&(l.elem[i-1]); //p为被删除元素的位置
	e=*p; //被删除元素的赋给e
	q=l.elem+l.length-1;
	for(++p; p<=q; p++) *(p-1)=*p; //被删除元素之后的元素前移
	l.length--;
}//ListDelete_sq
///////////////////////////////////////////////////////////////
void ListTraverse (Sqlist l)
{
	ElemType *p,*q;

	p=l.elem;
	q=l.elem+l.length;
	cout<<"here are the elements of L:"<<endl;
	while(p<q)
	{
		cout<<*p<<' ';
		p++;
	}
	cout<<endl<<"end of l"<<endl;
}
//////////////////////////////////////////////////////////
bool compare(ElemType x,ElemType y)
{
	if (x!=y) return false;
	else return true;
}