链表.docx
《链表.docx》由会员分享，可在线阅读，更多相关《链表.docx（13页珍藏版）》请在冰点文库上搜索。
链表
链表
#include//cout,cin
#include"process.h"//exit（）
#include"stdio.h"//EOF,NULL
charpause;
typedefintT;
template
structNode
{
Tdata;//数据域，存放表元素
Node*next;//指针域，指向下一个结点
};
template
classLinkList
{
private:
Node*Head;//链表头指针
public:
LinkList（）;//构造函数，创建空链表
~LinkList（）;//析构函数，删除表空间
voidCreateList（intn）;//创建具有n个元素的线性链表
voidInsert（inti,Te）;//在表中第i个位置插入元素
TDelete（inti）;//删除表中第i个元素
TGetElem（inti）;//获取第i个元素的值
intLocate（Te）;//在链表中查找值为e的元素
Tprior（Te）;//返回元素e的前驱
intEmpty（）;//测表空
intLength（）;//测表长
voidListDisplay（）;//输出表元素
};
template
LinkList:
:
LinkList（）
{//构建函数，建一空链表
Head=newNode;
Head->next=NULL;
}
template
LinkList:
:
~LinkList（）
{//析构函数，释放链表所占空间
Node*p;
while（Head）//从头结点开始，依次释放结点
{
p=Head;
Head=Head->next;
deletep;
}
Head=NULL;//头结点指向空
}
template
voidLinkList:
:
CreateList（intn）
{//尾插法（正序）创建具有n个元素的线性表
Node*p,*s;//设置工作指针。
p指向尾结点
p=Head;
cout<<"请依次输入"<"<for（inti=1;i<=n;i++）
{
s=newNode;//新建元素结点
cin>>s->data;//输入新建数据元素值
s->next=p->next;//新结点链入表尾
p->next=s;
p=s;
}
}
template
voidLinkList:
:
Insert（inti,Te）
{//在指定位置插入元素
intj=0;
Node*p;
p=Head;//工作指针初始化
while（p&&j{
p=p->next;//
j++;
}
if（!
p||j>i-1）throw"位置异常";//插入位置不合理，i<0或i>表长
else
{
Node*s;
s=newNode;//
s->data=e;//
s->next=p->next;//结点S链接到p结点之后
p->next=s;//
}
}
template
TLinkList:
:
Delete（inti）
{//删除指定位置元素
Tx;
Node*p,*q;//设置工作指针
p=Head;//查找从头结点开始
intj=0;//计数器初始化
while（p->next&&j{
p=p->next;//
j++;
}
if（!
p->next||j>i-1）//删除位置不合理
throw"位置异常";
else//删除位置合理
{
q=p->next;//暂存删除结点位置
p->next=q->next;//从链表中摘除删除结点
x=q->data;//取删除数据元素的值
deleteq;//释放删除点
returnx;//返回删除元素的值
}
}
template
intLinkList:
:
Locate（Te）
{//按元素值查找，找到，返回元素在表中的位序；否则，返回0
intj=1;
Node*p;//工作指针
p=Head->next;//首元结点为查找起始位置
while（p&&p->data!
=e）
{
p=p->next;
j++;
}
if（p==NULL）return0;//末找到，返回0
elsereturnj;//找到，返回位序
}
template
TLinkList:
:
GetElem（inti）
{//获取第i个元素的值
Node*p;//设置工作指针
p=Head->next;//从首结点开始
intj=1;//计数器初始化
while（p&&j{
p=p->next;j++;
}
if（!
p||j>i）//定位位置不合理：
空表或i小于0或i大于表长
throw"位置";
else//位置合理
returnp->data;
}
template
intLinkList:
:
Empty（）
{//测表空。
if（Head->next==NULL）
return1;//空表，返回1
else
return0;//不空，返回0
}
template
TLinkList:
:
prior（Te）
{//返回元素前驱
Node*p,*q;
p=Head;q=p->next;
while（q&&q->data!
=e）
{
p=q;q=q->next;
}
if（p==Head）
throw"首元素，无前驱";
elseif（q==NULL）
throw"元素不存在";
else
returnp->data;
}
template
intLinkList:
:
Length（）
{//测表长
intlen=0;//计数器初始化
Node*p;//设置工作指针
p=Head;//指向头结点
while（p->next）
{
len++;p=p->next;
}
returnlen;//返回表长
}//Length
template
voidLinkList:
:
ListDisplay（）
{//遍历显示链表
Node*p;//设置工作指针
p=Head->next;//从首元结点开始遍历
inti=1;//元素位序
while（p）
{
cout<data<<"\t";
p=p->next;
i++;
}
cout<}
intmain（）
{
inti;
Te,prior_e;
LinkListL;//
system（"cls"）;//执行系统命令cls，清屏
intchoice;
do
{//显示主菜单
cout<<"1-创建链表\n";
cout<<"2-按位序插入\n";
cout<<"3-按位序删除\n";
cout<<"4-按位序查找\n";
cout<<"5-按值查找\n";
cout<<"6-按值求前驱\n";
cout<<"7-测表空\n";
cout<<"8-测表长\n";
cout<<"9-显示链表\n";
cout<<"10-退出\n";
cout<<"Enterchoice:
";
cin>>choice;
switch（choice）
{
case1:
//创建链表
cout<<"请输入要创建的链表中元素个数:
";
cin>>i;
cout<L.CreateList（i）;
break;
case2:
//在指定位置插入元素
cout<<"请输入插入位置:
";
cin>>i;
cout<cout<<"请输入插入元素的值:
";
cin>>e;
cout<try
{
L.Insert（i,e）;
}
catch（char*err）
{
cout<}
break;
case3:
//删除指定位置元素
cout<<"请输入删除位置:
";
cin>>i;
cout<try
{
e=L.Delete（i）;
cout<<"被删除元素为：
"<}
catch（char*err）
{
cout<}
cin.get（pause）;
system（"pause"）;
break;
case4:
//按位序查找
cout<<"请输入要查询的元素位置:
";
cin>>i;
try
{
e=L.GetElem（i）;
cout<<"第"<"<}
catch（char*err）
{
cout<}
cin.get（pause）;
system（"pause"）;
break;
case5:
//按值查找
cout<<"请输入要查询的元素值:
";
cin>>e;//
i=L.Locate（e）;
cout<<"查询元素"<"<cin.get（pause）;
system（"pause"）;
break;
case6:
//求元素前驱
cout<<"请输入要求前驱元素的值:
";
cin>>e;
try
{
prior_e=L.prior（e）;
cout<<"元素"<"<}
catch（char*err）
{
cout<}
cin.get（pause）;
system（"pause"）;
break;
case7:
//测表空
i=L.Empty（）;
if（i）
cout<<"表空"<else
cout<<"表不空"<cin.get（pause）;
system（"pause"）;
break;
case8:
//测表长
cout<<"链表长度为：
"<cin.get（pause）;
system（"pause"）;
break;
case9:
//显示表
L.ListDisplay（）;
cout<cin.get（pause）;
system（"pause"）;
break;
case10:
//退出
cout<<"结束运行"<break;
default:
//
cout<<"Invalidchoice\n";
system（"pause"）;
break;
}
}while（choice!
=11）;//
return0;
}
升级会员 