//vc6.0实现的C++版
//功能：静态链表实现线性表的基本功能
#include <iostream.h>//读入必须包含的头文件
#include <windows.h>//清屏和颜色设置需要
#include <iomanip.h>
enum returninfo{success,fail,overflow,underflow,range_error};//定义返回信息清单
#define NULLP -1//静态链表的空地址模拟
const int MAXSIZE=10;//静态链表的总空间大小
class node
{
public:
int data;//数据域
int next;//指针域
};
/*
定义一个线性表类staticlinklist
*/
class staticlinklist
{
private:
node dataarray[MAXSIZE];//定义静态链表的数组
int freep,headp;//freep管理空闲空间，headp管理实际线性表空间
int count;//计数器 统计结点个数即线性表的长度
public:
staticlinklist();//构造函数
~staticlinklist();//析构函数
int getnewnode(void);//申请一个新的可用空间
returninfo create(int number);//静态链表的初始化
bool empty(void) const;//判断是否空链
int size(void) const;//求静态链表的长度
void deletenode(int position);//把某个空间地址归还给空闲空间
returninfo traverse(void);//遍历静态链表所有元素
returninfo retrieve(int position,int &item) const;//读取一个结点
returninfo replace(int position,const int &item);//修改一个结点
returninfo insert(int position,const int &item);//插入一个结点
returninfo remove(int position);//删除一个结点
returninfo invertlist(void);//静态链表所有数据反转
void showinfo(void);//显示静态链表相关信息
};
staticlinklist::staticlinklist()//构造函数
{
//静态链表初始化，约定开始时地址域为从小到大顺序挂链，最后一个为NULLP（即-1）
int i;
for(i=0;i<MAXSIZE;i++)
dataarray[i].next=i+1;
dataarray[MAXSIZE-1].next=-1;
freep=0;//设置空闲区的指针
count=0;//计数器清零，表明开始时没有实际数据
headp=NULLP;
}
staticlinklist::~staticlinklist()//析构函数
{
}
staticlinklist::getnewnode(void)
{
int tempaddress;//定义一个临时地址指针
tempaddress=freep;//保存目前可用空间的第一个地址
freep=dataarray[freep].next;//可用空间头指针后移
return tempaddress;
}
returninfo staticlinklist::create(int number)//静态链表的初始化
{
int tempaddress,tempp;
cout<<"请依次输入数据（用空格隔开）：";
for(int i=1;i<=number;i++)
{
tempaddress=getnewnode();
cin>>dataarray[tempaddress].data;
dataarray[tempaddress].next=NULLP;
count++;
if(i==1)//挂第一个结点
{
headp=tempaddress;
tempp=headp;
}
else//挂其他结点
{
dataarray[tempp].next=tempaddress;
tempp=tempaddress;
}
}
return success;
}
bool staticlinklist::empty(void) const//判断是否空链
{
if(headp==NULLP)
return true;
else
return false;
}
int staticlinklist::size(void) const//求静态链表的长度
{
return count;
}
void staticlinklist::deletenode(int position)
{
dataarray[position].next=freep;
freep=position;
}
returninfo staticlinklist::traverse(void)//遍历静态链表中的所有元素
{
int searchp;//启用搜索指针
if(empty())
return underflow;//空表的处理
searchp=headp;
cout<<"静态链表中的全部数据为：Headp->";//提示显示数据开始
while(searchp!=NULLP)//循环显示所有数据
{
cout<<"["<<dataarray[searchp].data;
if(dataarray[searchp].next==NULLP)
cout<<"|^]";
else
cout<<"|-]->";
searchp=dataarray[searchp].next;
}
cout<<endl;//最后有一个回车的控制
return success;//本次操作成功
}
returninfo staticlinklist::retrieve(int position,int &item) const//读取一个结点
{
if(empty())//处理意外，空表
return underflow;
if(position<=0||position>=count+1) //处理意外，范围不正确
return range_error;
int searchp=headp;//定义搜索指针，初始化
for(int i=1;i<position&&searchp!=NULLP;i++)//提示：注意小于号
searchp=dataarray[searchp].next;//顺序访问方式，用循环，算法复杂度是O(n)
item=dataarray[searchp].data;//返回读取的数据
return success;//本次操作成功
}
returninfo staticlinklist::replace(int position,const int &item)//修改一个结点
{
if(empty())//处理意外，空表
return underflow;
if(position<=0||position>=count+1) //处理意外，范围不正确
return range_error;
int searchp=headp;//定义搜索指针，初始化
for(int i=1;i<position&&searchp!=NULLP;i++)//提示：注意小于号
searchp=dataarray[searchp].next;//顺序访问方式，用循环，算法复杂度是O(n)
dataarray[searchp].data=item;//实际修改数据的语句
return success;//本次操作成功
}
returninfo staticlinklist::insert(int position,const int &item)//插入一个结点
{
if(position<=0||position>=count+2) //处理意外，范围不正确
return range_error;
int newnodep,searchp=headp,followp=NULLP;
newnodep=getnewnode();//此处需要申请新的一个可用空间，地址赋给newnodep
if(newnodep==NULLP)
return overflow;
dataarray[newnodep].data=item;//给数据赋值
if(position==1)
{
dataarray[newnodep].next=headp;
headp=newnodep;
count++;
return success;
}
for(int i=1;i<position&&searchp!=NULLP;i++)//以下为查找插入位置
{
followp=searchp;
searchp=dataarray[searchp].next;
}
//以下开始修改链表，完成插入数据
dataarray[newnodep].next=dataarray[followp].next;//注意此处的次序相关性
dataarray[followp].next=newnodep;
count++;//计数器加1
return success;
}
returninfo staticlinklist::remove(int position)//删除一个结点
{
if(empty())//处理意外，空表
return underflow;
if(position<=0||position>=count+1) //处理意外，范围不正确
return range_error;
int searchp=headp,followp=NULLP;//这里两个指针的初始值设计一前一后
if(position==1)
{
searchp=headp;
headp=dataarray[headp].next;
deletenode(searchp);//释放该结点空间
count--;//计数器减1
return success;
}
for(int i=1;i<position&&searchp!=NULLP;i++)
{
followp=searchp;
searchp=dataarray[searchp].next;
}
dataarray[followp].next=dataarray[searchp].next;//删除结点的实际语句
deletenode(searchp);//释放该结点
count--;//计数器减1
return success;
}
returninfo staticlinklist::invertlist(void)//静态链表所有数据反转
{
int nowp,midp,lastp;//启用多个辅助指针
if(empty())
return underflow;
nowp=dataarray[headp].next;
midp=NULLP;
while(nowp!=NULLP)
{
lastp=midp;
midp=nowp;
nowp=dataarray[nowp].next;
dataarray[midp].next=lastp;
}
dataarray[headp].next=midp;
return success;
}
void staticlinklist::showinfo(void)//显示静态链表相关信息
{
int searchp;
cout<<"目前静态链表总空间："<<setw(3)<<MAXSIZE<<"地址为（0--"<<MAXSIZE-1<<"）"<<endl;
cout<<"其中自由空间大小为："<<setw(3)<<MAXSIZE-count<<"编号为：";
searchp=freep;
while(searchp!=NULLP)
{
cout<<" "<<searchp;
searchp=dataarray[searchp].next;
}
cout<<endl;
cout<<"线性表的已用空间为："<<setw(3)<<count<<"编号为：";
searchp=headp;
while(searchp!=NULLP)
{
cout<<" "<<searchp;
searchp=dataarray[searchp].next;
}
cout<<endl;
}
/*
定义一个实现静态链表功能的菜单处理类interfacebase
*/
class interfacebase
{
private:
staticlinklist listonface;
public:
void clearscreen(void);//清屏
void showmenu(void);//显示菜单函数
int userchoice(void);//用户的选项
returninfo processmenu(int menuchoice);//菜单函数
};
void interfacebase::clearscreen(void)
{
system("cls");
}
void interfacebase::showmenu(void)
{
cout<<"静态链表基本功能菜单"<<endl;
cout<<"=================="<<endl;
cout<<"1.输入数据（键盘输入）"<<endl;
cout<<"2.显示数据（遍历全部数据）"<<endl;
cout<<"3.修改数据（要提供位置和新值）"<<endl;
cout<<"4.插入数据（要提供位置和新值）"<<endl;
cout<<"5.删除数据（要提供位置）"<<endl;
cout<<"6.读取数据（要提供位置）"<<endl;
cout<<"7.求表长度"<<endl;
cout<<"8.数据反转（全部数据逆序存储）"<<endl;
cout<<"9.静态链表相关信息"<<endl;
cout<<"0.退出程序"<<endl;
cout<<"=================="<<endl;
}
int interfacebase::userchoice(void)
{
int menuchoice;
cout<<"请输入您的选择：";
cin>>menuchoice;
return menuchoice;
}
returninfo interfacebase::processmenu(int menuchoice)
{
int position,item,returnvalue;
switch(menuchoice)//根据用户的选择进行相应的操作
{
case 1:
cout<<"请问你要输入数据的个数，注意要在"<<MAXSIZE<<"个以内：";
cin>>item;
if(item>MAXSIZE)
cout<<"对不起，输入数据超限，操作已取消！请按任意键继续..."<<endl;
else
{
returnvalue=listonface.create(item);
if(returnvalue==success)
cout<<"建立静态链表操作成功！请按任意键继续..."<<endl;
}
break;
case 2:
returnvalue=listonface.traverse();
if(returnvalue==underflow)
cout<<"静态链表目前为空，没有数据可以显示！请按任意键继续..."<<endl;
else
cout<<"静态链表遍历操作成功！请按任意键继续..."<<endl;
break;
case 3:
cout<<"请输入要修改数据的位置：";
cin>>position;
cout<<"请输入要修改的新数据：";
cin>>item;
returnvalue=listonface.replace(position,item);
if(returnvalue==underflow)
cout<<"对不起，静态链表已空！请按任意键继续..."<<endl;
else if(returnvalue==range_error)
cout<<"对不起，修改的位置超出了范围！请按任意键继续..."<<endl;
else
cout<<"修改操作成功！请按任意键继续..."<<endl;
break;
case 4:
cout<<"请输入要插入数据的位置：";
cin>>position;
cout<<"请输入要插入的新数据：";
cin>>item;
returnvalue=listonface.insert(position,item);//注意这个位置的参数
if(returnvalue==overflow)
cout<<"对不起，静态链表溢出，无法插入新数据！请按任意键继续..."<<endl;
else if(returnvalue==range_error)
cout<<"对不起，插入的位置超出了范围！请按任意键继续..."<<endl;
else
cout<<"插入操作成功！请按任意键继续..."<<endl;
break;
case 5:
cout<<"请输入要删除数据的位置：";
cin>>position;
returnvalue=listonface.remove(position);//注意这个位置的参数
if(returnvalue==underflow)
cout<<"对不起，静态链表已空！请按任意键继续......"<<endl;
else if(returnvalue==range_error)
cout<<"对不起，删除的位置超出了范围！请按任意键继续..."<<endl;
else
cout<<"删除操作成功！请按任意键继续..."<<endl;
break;
case 6:
cout<<"请输入要读取数据的位置：";
cin>>position;
returnvalue=listonface.retrieve(position,item);
if(returnvalue==underflow)
cout<<"对不起，静态链表已空！请按任意键继续......"<<endl;
else if(returnvalue==range_error)
cout<<"对不起，读取的位置超出了范围！请按任意键继续..."<<endl;
else
cout<<"读取的数据为："<<item<<endl<<"读取操作成功！请按任意键继续..."<<endl;
break;
case 7:
cout<<"静态链表目前的长度为："<<listonface.size()<<endl;
cout<<"求静态链表长度操作成功！请按任意键继续..."<<endl;
break;
case 8:
returnvalue=listonface.invertlist();
if(returnvalue==underflow)
cout<<"对不起，链表已空！请按任意键继续......"<<endl;
else
cout<<"链表所有元素反转操作成功！请按任意键继续..."<<endl;
break;
case 9:
listonface.showinfo();
break;
case 0:
exit(0);
default:
cout<<"对不起，您输入的功能编号有错！请重新输入！！！"<<endl;
break;
}
return success;
}
/*
程序主入口
*/
void main(void)
{
int menuchoice;//定义变量，菜单选单项的选择
interfacebase interfacenow;
staticlinklist linklistnow;
system("color f0");//修改屏幕的背景色和字的颜色
interfacenow.clearscreen();//清屏
while(1)//永真循环
{
interfacenow.showmenu();//显示菜单
menuchoice=interfacenow.userchoice();//获取用户的选择
interfacenow.processmenu(menuchoice);//处理用户的选择
system("pause");//暂停
interfacenow.clearscreen();//清屏
}
}//主函数结束
分享
