单链表的基本操作

65 阅读 0 评论 43 点赞

我是靠谱客的博主怕孤单水杯，最近开发中收集的这篇文章主要介绍单链表的基本操作，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

#include <iostream>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef int elemtype;
typedef struct LNode{
//单链表的存储结构
elemtype date;
//结点的数据域
struct LNode *next; //结点的指针域
}LNode,*Linklist;
//Linklist为指向结构体LNode的指针类型
Status Initlist_L(Linklist &L)//构造一个空的单链表L
{
L=new LNode;//生成新结点作为头结点，用头指针L指向头结点
L->next=NULL;//头结点的指针域为空
return OK;
}
Status Getelem_L(Linklist L,int i,elemtype &e)//按序号查找，在带头结点的单链表L中
//查找第i个元素
{
int j;
LNode *p;
p=L->next;j=1;//初始化，p指向第一个结点，j为计数器
while(p&&j<i) //顺链域向后扫描，直至p指向第i个元素或p为空
{
p=p->next;j++;
}
if(!p||j>i)
return ERROR;//第i个元素不存在
e=p->date;//取第i个元素
return OK;
}
//按值查找
LNode *Locatelem_L(Linklist L,elemtype e)
{
LNode *p;
p=L->next;
while(p&&p->date!=e)//寻找满足条件的结点
p=p->next;//返回L中值为e的数据元素的值，查找失败返回NULL
return p;
}
//单链表的插入
//在带头结点的单链表L中第i个位置之前插入元素e
Status Linkinsert_L(Linklist &L,int i,elemtype e)
{
LNode *p,*s;
int j;
p=L;j=0;
while(p&&j<i-1)//寻找第i-1个结点
{
p=p->next;
j++;
}
if(!p||j>i-1)	return ERROR;//i大于表长+1 或小于1
s=new LNode;
//生成新结点s
s->date=e;
//将结点s的数据域设为e
s->next=p->next;//将结点插入L中
p->next=s;
return OK;
}
//单链表的删除
Status Listdelete_L(Linklist &L,int i,elemtype &e)
{
LNode *p,*q;
int j;
p=L;j=0;
while(p->next&&j<i-1)
{
p=p->next;
j++;
}
if(!(p->next)||j>i-1) return ERROR;
q=p->next;//临时保存被删除结点的地址以备释放
p->next=q->next;//改变删除结点前驱结点的指针域
e=q->date;//保存删除结点的数据域
delete q;//释放删除结点的空间
return OK;
}
//前插法创建单链表
void Createlist_F(Linklist &L,int n)
{
int i;
LNode *p;
L=new LNode;//先建立一个带头结点的空链表
L->next=NULL;
for(i=n;i>0;i--)
{
p=new LNode;//生成新结点
cin>>p->date;//输入元素值
p->next=L->next;//插入到表头
L->next=p;
}
}
//后插法创建单链表
void Createlist_L(Linklist &L,int n)
{
LNode *p,*r;
L=new LNode;
L->next=NULL;
r=L;//尾指针指向头结点
cout<<"请输入元素：";
for(int i=0;i<n;i++)
{
p=new LNode;
cin>>p->date;
p->next=NULL;//插入到表尾
r->next=p;
r=p;//r指向新的尾结点
}
}
int main()
{
int choose,a,b,n1;
elemtype
rec;
LNode *p,*la;
cout<<"1.建立链表n";
cout<<"2.输入数据n";
cout<<"3.按位置查找元素n";
cout<<"4.按值查找元素n";
cout<<"5.链表的插入n";
cout<<"6.链表的删除n";
cout<<"7.输出数据n";
cout<<"0.退出nn";
choose=-1;
while(choose!=0)
{
cout<<"请选择:";
cin>>choose;
switch(choose)
{
case 1:
if(Initlist_L(la))
cout<<"成功建立链表！nn";
break;
case 2:
cout<<"请输入要输入的元素个数：";
cin>>n1;
Createlist_L(la,n1);
cout<<"成功创建链表！"<<endl<<endl;
break;
case 3:
cout<<"请输入要查找的元素的位置：";
cin>>a;
if(Getelem_L(la,a,rec))
cout<<"查找成功！第"<<a<<"个数是"<<rec<<endl<<endl;
else
cout<<"查找失败！nn";
break;
case 4:
cout<<"请输入一个数值来查找：";
cin>>b;
if(Locatelem_L(la,b)!=NULL)
cout<<"查找成功！nn";
else
cout<<"查找失败！元素"<<b<<"没有找到！nn";
break;
case 5:
cout<<"请分别输入两个数代表要插入的元素及其位置：";
cin>>a>>b;
if(Linkinsert_L(la,b,a))
cout<<"成功将"<<a<<"插入"<<"第"<<b<<"个位置nn";
else
cout<<"插入失败！nn";
break;
case 6:
cout<<"请输入要删除的元素的位置：";
cin>>a;
if(Listdelete_L(la,a,rec))
cout<<"删除成功！被删除的数是："<<rec<<"nn";
else
cout<<"删除失败！nn";
break;
case 7:
cout<<"当前链表里的元素是：";
p=la->next;
while(p)
{
cout<<p->date<<" ";
p=p->next;
}
cout<<endl<<endl;
break;
}
}
}