#include <iostream>
using namespace std;
void menu();
template <class T>
class seqList
{
private:
int len; //数组的长度
int cnt; //实际的长度
T *v;
public:
seqList(int m);
void input(); //添加元素
int is_empty(); //判断数组是否为空
int is_full(); //判断数组是否满
void Insert(int value,int i ); //插入元素
int del(int i); //删除元素
void inversion(); //倒置元素
void sort(); //排序
int find(int val); //查找元素
void print();
};
//建立空顺序表
template <class T>
seqList<T>::seqList(int m)
{
len=m;
v=new T[len];
cnt=0;
//return;
}
template <class T>
void seqList<T>::input()
{
cout<<"\n* 请输入数据:";
int i;
for(i=0;i<len;i++)
{
cin>>v[i];
cnt++;
}
}
//判断数组是否为空
template<class T>
int seqList<T>::is_empty()
{
if(0 == cnt)
{
return 1;
}
else
{
return 0;
}
}
//判断数组是否满
template<class T>
int seqList<T>::is_full()
{
if(cnt == len)
{
return 1;
}
else
{
return 0;
}
}
//在表的指定元素前插入新元素
template<class T>
void seqList<T>::Insert(int value,int i)
{
int k;
if(cnt==len)
{
cout<<"overflow"<<endl;
}
if(i>cnt)
i=cnt+1;
if(i<1)
i=1;
for(k=cnt;k>=i;k--)
v[k]=v[k-1];
v[i-1]=value;
cnt++;
//return ;
}
//在顺序表中删除指定元素,并返回元素值
template<class T>
int seqList<T>::del(int i)
{
int k;
if(cnt==0)
{
cout<<"underflow!"<<endl;
}
int val=v[i-1];
for(k=i;k<cnt;k++)
v[k-1]=v[k];
cnt--;
return val;
}
//倒置元素
template<class T>
void seqList<T>::inversion()
{
int i = 0;
int j = cnt - 1;
int t;
while(i < j)
{
t = v[i];
v[i] = v[j];
v[j] = t;
i++;
j--;
}
}
//排序,冒泡排序算法
template<class T>
void seqList<T>::sort()
{
int t;
for(int i = 0; i < cnt; i++)
{
for(int j = i + 1; j < cnt; j++)
{
if(v[i] > v[j])
{
t = v[i];
v[i] = v[j];
v[j] = t;
}
}
}
}
template<class T>
int seqList<T>::find(int val)
{
int i = 1;
while(i <= cnt && !(v[i - 1] == val))
{
i++;
}
if(i <= cnt)
{
return i;
}
else
{
return 0 ;
}
}
template<class T>
void seqList<T>::print()
{
if(cnt==0)
{
cout << "数组为空!" << endl;
}
else
{
for(int i = 0; i < cnt; i++)
{
cout << v[i] << ' ';
}
cout << endl;
}
}
void menu()
{
cout<<"\n **********菜单**********\n"<<endl
<<" * 1.判断数组是否为空 *"<<endl
<<" * 2.判断数组是否满 *"<<endl
<<" * 3.将表中第i个元素删去,通过函数返回该元素 *"<<endl
<<" * 4.将新元素value插入表中的第i个位置 *"<<endl
<<" * 5.倒置元素*"<<endl
<<" * 6.排序*"<<endl
<<" * 7.查找元素*"<<endl
<<" * 8.结束 *"<<endl
<<"\n ************************\n"<<endl
<<"请输入所需功能: ";
}
void main()
{
int i,m,k,option;
cout<<"\n* 创建顺序表 *\n"<<endl;
cout<<"请输入数组长度:";
cin>>m;
seqList<int> s(m);
s.input();
cout<<"\n* 显示当前顺序表数据: ";
s.print();
menu();
cin>>option;
while(option!=8)
{
switch(option)
{
case 1:
{
cout<<"\n* 判断数组是否为空 *"<<endl;
k=s.is_empty();
if(k==1)
cout<<"\n* 数组为空: "<<endl;
if(k==0)
cout<<"\n* 数组不为空"<<endl;
}break;
case 2:
{
cout<<"\n* 判断数组是否为满 *"<<endl;
k=s.is_full();
if(k==1)
cout<<"\n* 数组为满。 "<<endl;
if(k==0)
cout<<"\n* 数组不为满。"<<endl;
}break;
case 3:
{
cout<<"\n* 将链表中第i个元素删去,通过函数返回该元素 *"<<endl;
cout<<"\n输入要删除元素的位置: ";
cin>>i;
k=s.del(i);
cout<<"\n返回删除元素值:"<<k<<endl;
cout<<"\n* 显示当前链表数据: ";
s.print();
}break;
case 4:
{
cout<<"\n* 将新元素value插入链表中的第i个位置 *"<<endl;
cout<<"\n* 输入你要插入的元素: ";
cin>>m;
cout<<"\n* 输入你要插入的位置: ";
cin>>i;
s.Insert(m,i);
cout<<"\n* 显示当前链表数据: ";
s.print();
}break;
case 5:
{
cout<<"\n倒置元素"<<endl;
s.inversion();
cout<<"\n* 显示当前链表数据: ";
s.print();
}break;
case 6:
{
cout<<"\n排序"<<endl;
s.sort();
cout<<"\n* 显示当前链表数据: ";
s.print();
}break;
case 7:
{
cout<<"\n* 在表中搜索数据value,并返回其位置 *"<<endl;
cout<<"\n* 输入你要查找的元素: ";
cin>>m;
k=s.find(m);
if(k==0)
cout<<"\n* 该元素不存在"<<endl;
if(k!=0)
cout<<"\n* 该元素所在位置: "<<k<<endl;
}break;
default:cout<<"序号输入错误,请重新输入^_^ "<<endl;break;
}
cout<<endl<<"输入功能序号:";
cin>>option;
}
}