sqlist.cpp

链表的初始化 判断是否为空 计算长短 输入输出

#include "iostream.h"
#include "stdlib.h"
#define LIST_INIT_SIZE 10
#define LISTINCREMENT 2
typedef int ElemType;
//顺序表结构
typedef struct {
	ElemType *elem;
	int length;
	int listsize;
}SL;
//顺序表初始化
void listinit(SL &L)
{L.elem=new ElemType[LIST_INIT_SIZE];
L.length=0;
L.listsize=LIST_INIT_SIZE;
}
//建立顺序表
void listcreate(SL &L)
{ElemType x;
int k=0;
cout<<"enter x, 0 to end"<<endl;
cin>>x;
while(x)
{L.elem[k++]=x;
cin>>x;}
L.length=k;
}
//顺序表输出
void print(SL &L)
{int i;
for(i=0;i<L.length;i++)
cout<<L.elem[i]<<"  ";
cout<<endl;
}
//顺序表置空
void listnull(SL &L)
{ L.length=0;
}
//求顺序表长度
int listlen(SL L)
{return L.length;
}
//判断顺序表是否为空
int listempty(SL L)
{ if(L.length==0) return 1;
else return 0;
}
//销毁顺序表
void listdestory(SL &L)
{L.length=0;
L.listsize=0;
delete []L.elem;
}
//求顺序表中第i个元素
void getlist(SL L,int i,ElemType &e)
{ if(listempty(L)) e=L.elem[i-1];
else e=-1;
}
//求顺序表中元素e的直接前驱
void prior(SL L,ElemType e,ElemType &pre)
{int i;
for(i=0;i<L.length;i++)
if(L.elem[i]==e) break;
if((i!=0)&&(i<=L.length-1))pre=L.elem[i-1];
else cout<<"无前驱或元素不存在!"<<endl;
}

//求顺序表中元素e的直接后继
void next(SL L,ElemType e,ElemType &net)
{int i;
for(i=0;i<L.length;i++)
if(L.elem[i]==e) break;
if(i<L.length-1)net=L.elem[i+1];
else cout<<"无后驱或元素不存在!"<<endl;
}

//在顺序表的第i个位置插入元素x；
void listinsert(SL &L,int i,ElemType x)
{int j;ElemType *newbase;
 if(L.length>=L.listsize)
newbase =(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
if(!newbase) exit(0);
L.elem=newbase;
 L.listsize=L.listsize+LISTINCREMENT;

	 if(i<0||i>=L.length) cout<<"插入位置错误"<<endl;
	else
	{
  for(j=L.length;j>i-1;j--)
	  L.elem[j]=L.elem[j-1];
L.elem[j]=x;
L.length++;
	}

}
//在顺序表中元素e的后面插入元素y
void listafterinsert(SL &L,ElemType e,ElemType y)
{
int i,j;
for(i=0;i<L.length;i++) if(L.elem[i]==e) break;
if(i>=L.length) cout<<"元素"<<e<<"不存在，插入失败！"<<endl;
else
{for(j=L.length;j>i+1;j--)
	  L.elem[j]=L.elem[j-1];
L.elem[j]=y;
L.length++;
}
}
//在顺序表中元素e的前面插入元素y
void listbeforeinsert(SL &L,ElemType e,ElemType y)
{
int i,j;
for(i=0;i<L.length;i++) if(L.elem[i]==e) break;
if(i>=L.length) cout<<"元素"<<e<<"不存在，插入失败！"<<endl;
else
{for(j=L.length;j>i;j--)
	  L.elem[j]=L.elem[j-1];
L.elem[j]=y;
L.length++;
}
}
//删除顺序表中第i个元素
void listdelete(SL &L,int i,ElemType &e)
{int j;
 
	if(i<0||i>=L.length) cout<<"删除位置错误"<<endl;
	else
	{e=L.elem[i-1];

  for(j=i-1;j<L.length-1;j++)
	  L.elem[j]=L.elem[j+1];
L.length--;
	}
}
//删除顺序表中元素e
void listlocatdelete(SL &L,ElemType e)
{int j,i;
 for(i=0;i<L.length;i++) if(L.elem[i]==e) break;
if(i>=L.length) cout<<"被删除元素不存，删除失败"<<endl;
	else
	{
  for(j=i;j<L.length-1;j++)
	  L.elem[j]=L.elem[j+1];
L.length--;
	}
}

//删除顺序表中元素e的直接前驱
void listpriordelete(SL &L,ElemType e)
{int j,i;
 for(i=0;i<L.length;i++) if(L.elem[i]==e) break;
if(i==0||i>=L.length) cout<<"无前驱或被删除元素不存，删除失败"<<endl;
	else
	{
  for(j=i-1;j<L.length-1;j++)
	  L.elem[j]=L.elem[j+1];
L.length--;
	}
}

//删除顺序表中元素e的直接后驱
void listnextdelete(SL &L,ElemType e)
{int j,i;
 for(i=0;i<L.length;i++) if(L.elem[i]==e) break;
if(i>=L.length-1) cout<<"无后驱或被删除元素不存，删除失败"<<endl;
	else
	{
  for(j=i+1;j<L.length-1;j++)
	  L.elem[j]=L.elem[j+1];
L.length--;
	}
}
//将顺序表LA逆置并存放到顺序表LB中。即如果LA={a1,a2,..,an}则LB={an,…,a2,a1}
void invers(SL LA,SL &LB)
{
int i;
if(LA.length==0) cout<<"空表，不能置逆"<<endl;
else
{for(i=LA.length-1;i>=0;i--) LB.elem[LA.length-i-1]=LA.elem[i];
LB.length =LA.length;}
}

//顺序表L就地逆置，即利用原顺序表的存储单元，把L={a0,a1,…,an-1}逆置为{an-1,an-2,…,a1,a0}
void inversyuan(SL &LA)
{
int i,k,n;
if(LA.length==0) cout<<"空表，不能置逆"<<endl;
else
{ n=LA.length/2;
for(i=0;i<n;i++)
{k=LA.elem [i];LA.elem [i]=LA.elem [LA.length-i-1];LA.elem [LA.length-i-1]=k;}
}
}



void main()
{	ElemType y=100;
	SL L1,L2;
	listinit(L1);
	listcreate(L1);
	print(L1);
	listinsert(L1,3,y);
		print(L1);
/*listnull(L1);
	print(L1);
listdestory(L1);

//
//	listbeforeinsert(L1,45,212);
	
next(L1,34,pr);
cout<<pr<<endl;

//print(L1);
	ElemType pr=0;

listnextdelete(L1,34);
print(L1);
	listinit(L2);
	invers(L1,L2);
	print(L2);
inversyuan(L1);
print(L1);*/

  }