使用C++实现线性表的基本功能
#include <iostream.h>
#include <conio.h>
#include <alloc.h>
typedef int Elemtype;
//线性表的基本操作
void Initiallist(Elemtype *L);
int Isempty(Elemtype *L);
void ListTraverse(Elemtype *L);
int NextElem(Elemtype *L);
int PriorElem(Elemtype *L);
int LocateElem(Elemtype *L,Elemtype &e);
void GetElem(Elemtype *L);
void ListInsert(Elemtype *L);
void ListDelete(Elemtype *L);
void ClearList(Elemtype *L);
const int N=10;
Elemtype temp;//全局变量!
void Initiallist(Elemtype *L)
{
for(int i=0;i<N;i++)
*(L+i)='#';
}
int Isempty(Elemtype *L)
{
if(*L=='#')
return 1;
else
return 0;
}
void ListTraverse(Elemtype *L)
{
static int k;
if(*(L)==35)
cout<<"The list is NULL!\n";
else
{
cout<<"The records of the list are:\n";
for(int i=0;i<N+k;i++)
{
if((*(L+i)>32768))
break;
else
cout<<*(L+i)<<" ";
}
k++;
}
}
int NextElem(Elemtype *L)
{
int index;
Elemtype e;
cout<<"Input the records for searching it's next Elem!\n";
cin>>e;
index=LocateElem(L,e);
if(*(L+index+1)>32768)
cout<<"It has no next Elem!\n";
else
cout<<e<<"的后继是:"<<*(L+index+1)<<endl;
}
int PriorElem(Elemtype *L)
{
int index;
Elemtype e;
cout<<"Input the records for searching it's prior Elem!\n";
cin>>e;
index=LocateElem(L,e);
if(index>N)
cout<<"It has no next Elem!\n";
else if(index==-1||index==0)
{
cout<<"It has no prior Elem!\n";
return 0;
}
else
cout<<e<<"的前驱是:"<<*(L+index-1)<<endl;
}
int LocateElem(Elemtype *L,Elemtype &e)
{
int i;
for(i=0;i<N+1&&(*(L+i)!='#');i++)
{
if(*(L+i)==e)
return i;
else
continue;
}
if(i<N||i>=N)
return -1;
return i;
}
void GetElem(Elemtype *L)
{
int index;
cout<<"Input the value of i:\n";
cin>>index;
if(*(L+index-1)>32768)
cout<<"The records NULL!\n";
else
cout<<"The records which you want to search are: "<<*(L+index-1)<<endl;
}
void ListInsert(Elemtype *L)
{
Elemtype e;
int index,i;
cout<<"Please input only one inserted number and it's location!\n";
cin>>e;
cin>>index;
if(index>N)
*(L+index-1)=e;
else
{
for(i=N;i>=index;i--)
*(L+i)=*(L+i-1);
*(L+index-1)=e;
}
ListTraverse(L);
}
void ListDelete(Elemtype *L)
{
Elemtype e;
int index,i;
cout<<"Input the number which you want to deleted!\n";
cin>>e;
index=LocateElem(L,e);
for(i=index;i<N+1&&(*(L+i)!='#');i++)
*(L+i-1)=*(L+i);
cout<<"Deleted "<<e<<endl;
ListTraverse(L);
}
void ClearList(Elemtype *L)
{
for(int i=0;i<N+1;i++)
*(L+i)='#';
}
int main()
{
int choice,flag=0;
char ch;
Elemtype *p,e;
p=(Elemtype *)malloc((N+1)*sizeof(Elemtype));
if(!p)
{
cout<<"No more memory can be obtained!\n";
goto loop;
}
loop: p=(Elemtype *)realloc(p,(N+1)*sizeof(Elemtype));
if(!p)
{
cout<<"overflow!\n";
exit(0);
}
Initiallist(p);
cout<<"Input "<<N<<" records!\n";//数据互不相同!
for(int i=0;i<N;i++)
cin>>*(p+i);
if(Isempty(p))
cout<<"The list is NULL!\n";
cout<<" Menu Fuction \n"
<<" 1: 遍历线性表的元素!( 只允许调用一次!)\n"
<<" 2: 求某一元素的前驱和后继!\n"
<<" 3: 获取线性表L中的第i个数据元素内容!\n"
<<" 4: 在线性表中插入一个元素!\n"
<<" 5: 删除线性表中值为e的元素!\n"
<<" 6: 检索值为e的数据元素!\n"
<<" 7: 清空线性表!"<<endl;
do
{
cout<<"Please input your choice!\n";
cin>>choice;
switch(choice)
{
case 1: ListTraverse(p); break;
case 2: NextElem(p);
PriorElem(p);
break;
case 3: GetElem(p); break;
case 4: ListInsert(p); break;
case 5: ListDelete(p); break;
case 6:
cout<<"Input the records !\n" ;
cin>>e;
cout<<"It's location is "<<LocateElem(p,e)+1;
break;
case 7: ClearList(p);
cout<<"Now ";
ListTraverse(p);
break;
}
cout<<"\nDid you want to continue the operation?(Y/N)\n";
cin>>ch;
if(ch=='Y'||ch=='y')
flag=1;
else
flag=0;
}while(flag);
free(p);
getch();
return 0;
}