list1.cpp

建立了顺序表数据结构

#include <iostream>
#include <ctime>

//顺序表存储空间的总分配量
#define maxsize 100
#define true 1
#define false 0
using namespace std;
//顺序存储类型
struct seqlist
{
	int data[maxsize];//存放线性表的数组
	int length;//顺序表长度
};
//函数声明
seqlist seqlistinit();
seqlist listclear(seqlist L);    
int  listlength(seqlist L);
int  listempty(seqlist L);
int  listfull(seqlist L);
seqlist listtraverse(seqlist L);
seqlist listget(seqlist L,int i);
int  listlocate(seqlist L,int x);
seqlist listinsert(seqlist L,int i,int x);
seqlist listdelete(seqlist L,int i);
int  listprior(seqlist L,int e);
int  listnext(seqlist L,int e);
seqlist delallx(seqlist L,int x);
seqlist nizhi(seqlist L);
//初始化线性表
seqlist seqlistinit()
{
	seqlist L;
	L.length=0;
	return L;
}
//清空线性表
seqlist listclear(seqlist L)
{
	L.length=0;
	return L;
}
//求顺序表长度
int listlength(seqlist L)
{
	return L.length;
}
//检查顺序表是否为空
int listempty(seqlist L)
{
	return(L.length==0? true: false);	
}
//检查顺序表是否为满
int listfull(seqlist L)
{
	return(L.length==maxsize? true: false);
}
//遍历顺序表
seqlist listtraverse(seqlist L)
{
	int i;
	if(L.length==0)
		cout<<"线性表为空"<<endl;
	else
		for(i=0;i<L.length;i++)
			cout<<"第"<<i+1<<"个元素："<<L.data[i]<<endl;
	return L;
}
//从顺序表中查找元素
seqlist listget(seqlist L,int i)
{
	if(L.length==0)
	{	
		cout<<"顺序表为空\n";
		return L;
	}
	if(i<1||i>L.length)
		cout<<"您输入的位置不正确!"<<endl;
	else
		cout<<"顺序表中第"<<i<<"个元素的值为:"<<L.data[i-1]<<endl;	
	return L;
}
//查找与给定元素值相同的元素位置
int listlocate(seqlist L,int x)
{
	if(L.length==0)
	{
		cout<<"顺序表为空\n";
		return -1;
	}
	int i=1;
	while(i<=L.length && L.data[i-1]!=x)
		i++;
	if(i<=L.length)
		return i;
	else
		return 0;
}
//向顺序表中插入元素
seqlist listinsert(seqlist L,int i,int x)
{
	if(L.length==maxsize)
	{	
		cout<<"顺序表已满\n";
		cin.get();
		return L;
	}
	if(i<1 || i>L.length+1)
	{
		cout<<"您插入的位置有误"<<endl;
		cin.get();
		return L;
	}
	for(int j=L.length-1;j>=i-1;j--)
		L.data[j+1]=L.data[j];
	L.data[i-1]=x;
	L.length++;
	return L;
}
//从顺序表中删除元素
seqlist listdelete(seqlist L,int i)
{
	if(i<1 || i>L.length)
	{
		cout<<"您输入的位置有误"<<endl;
		return L;
	}
	for(int j=i;j<=L.length-1;j++)
		L.data[j-1]=L.data[j];
	L.length--;
	return L;

}
//求顺序表中元素的前驱
int  listprior(seqlist L,int e)
{
	int i=0;
	while(i<=L.length-1 && L.data[i]!=e)
		i++;
	if(i==0)
	{
		cout<<"第一个元素没有前驱\n";
		return 0;
	}
	else
		if(i<=L.length-1)
			return L.data[i-1];
		else
		{	
			cout<<"不存在值为"<<e<<"的元素"<<endl;
			return 0;
		}
}
//求顺序表中元素的后继
int  listnext(seqlist L,int e)
{
	int i=0;
	while(i<=L.length-1 && L.data[i]!=e)
		i++;
	if(i==L.length-1)
	{
		cout<<"最后一个元素没有后驱\n";
		return 0;
	}
	else
		if(i>=0 && i<L.length-1)
			return L.data[i+1];
		else
		{	
			cout<<"不存在值为"<<e<<"的元素"<<endl;
			return 0;
		}
}
//删除所有与X值相同的元素
seqlist delallx(seqlist L,int x)
{
	int i=0,k=0;
	while(i<L.length)
	{
		if(L.data[i]==x)
			k++;
		else
			L.data[i-k]=L.data[i];
		i++;
	}
	L.length=L.length-k;
	return L;
}
//将顺序表中元素逆置
seqlist nizhi(seqlist L)
{
	int i=0,temp;
	for(i=0;i<L.length/2;i++)
	{
		temp=L.data[i];
		L.data[i]=L.data[L.length-1-i];
		L.data[L.length-1-i]=temp;
	}
	return L;
}
//输出主菜单
void show_mainmenu()
{  
 cout<<"                       "<<"=============线性表============"<<endl;
 time_t t;
 time(&t);
 cout  <<  "                 当前系统时间是:  " << ctime(&t) << endl;
 cout<<"********************************************************************************";
 cout<<"\t1 初始化线性表\t\t\t2 清空线性表\n";
 cout<<"\t3 求顺序表长度\t\t\t4 检查顺序表是否为空\n";
 cout<<"\t5 检查顺序表是否为满\t\t6 遍历顺序表\n";
 cout<<"\t7 从顺序表中查找元素\t\t8 查找与给定元素值相同的元素位置\n";
 cout<<"\t9 向顺序表中插入元素\t\t10从顺序表中删除元素\n";
 cout<<"\t11求顺序表中元素的前驱\t\t12求顺序表中元素的后继\n";
 cout<<"\t13删除所有与X值相同的元素\t14将顺序表中元素逆置\n";
 cout<<"\t15退出系统\n";
 cout<<"\t\t******第一次操作请先建立顺序表******"<<endl;
 cout<<"********************************************************************************";
}
//主函数
void main()
{ 
int n;
int i,x,e,prior,next;
seqlist L;

show_mainmenu();
cout<<"请你选择操作:"<<endl;
cin>>n;
 
while(n!=1&&n!=15)
{
	while(n<1 || n>15)
	{
		cout<<"===>提示：菜单里没有你输入的选项."<<endl;
		cout<<"你的输入有误，请重新输入:\n";
		cin>>n;		
	}
    while(n>1&&n<15)  
    {
         cout<<"在你还没有建立线性表之前，你只能进行1或者15操作，请重新输入:\n";
         cin>>n;
    }
}

if(n==1)
{
	L=seqlistinit(); 
}
if(n==15)
{
	cout<<"退出系统，再见."<<endl; 
	exit(1);
}

do
{  
cin.get();		
system("cls");
show_mainmenu();
cout<<"请你选择操作:"<<endl;
cin>>n; 
while(n<1 && n>15)
{
	cout<<"===>提示：菜单里没有你输入的选项."<<endl;
	cout<<"你的输入有误，请重新输入:\n";
	cin>>n;
}
cin.get();
switch(n)//选择操作，并在每一次操作后返回该操作完成后的头指针，以便保存该操作。。。
{
      case 1:
        L=seqlistinit(); 
		break;
      case 2:
        L=listclear(L);
		break;
      case 3:
        cout<<"线性表的长度为："<<listlength(L)<<endl;
		break;
      case 4:
		if(listempty(L))
			cout<<"顺序表为空\n";
		else 
			cout<<"顺序表不为空\n";
		break;
      case 5: 
        if(listfull(L))
			cout<<"顺序表满\n";
		else 
			cout<<"顺序表不满\n";
		break;
      case 6:
        L=listtraverse(L);
		break;
      case 7:
		cout<<"请输入要查找元素的位置\n";
		cin>>i;
        L=listget(L,i);		
		cin.get();
		break;
	  case 8:
		 cout<<"请输入要查找的元素的值\n";
		 cin>>x;
		 i=listlocate(L,x);
		 if(i>0)
			 cout<<"顺序表中值为"<<x<<"的位置是:"<<i<<endl;			 
		 if(i==0)
			 cout<<"顺序表中不存在值为"<<x<<"的元素\n";
		 cin.get();
		 break;		 
      case 9:
		 cout<<"请输入要插入的元素的位置和其值:\n";
		 cin>>i>>x;
         L=listinsert(L,i,x);
		 break;
      case 10:
		 cout<<"请输入要删除的元素的位置:\n";
		 cin>>i;
         L=listdelete(L,i);
		 break;
      case 11:
		 cout<<"请输入要查找的元素的值\n";
		 cin>>e;
		 prior=listprior(L,e);
		 if(prior) 
		    cout<<e<<"的前驱是:"<<prior<<endl;
		 cin.get();
		 break;
	  case 12:
		 cout<<"请输入要查找的元素的值\n";
		 cin>>e;
		 next=listnext(L,e);
		 if(next) 
		    cout<<e<<"的后继是:"<<next<<endl;
		 cin.get();
		 break;	
	  case 13:
		  cout<<"请输入要删除元素的值\n";
		  cin>>x;
		  L=delallx(L,x);
		  break;
	  case 14:
		  L=nizhi(L);
		  break;
	  case 15:
		  {
			 cout<<"退出系统，再见."<<endl; 
			 exit(1);
		  }
      default :
	 //输入选择的操作，如果菜单里没有，报错。。。
          cout<<"===>提示：菜单里没有你输入的选项."<<endl;
          cout<<"你的输入有误，请重新输入:"<<endl;
		  cin>>n;
     }
   }while(n<=15);
}