🌍新人小白的博客
⌛️希望大家多多关注
🌱一起加油,共同成长
🎃以后会经常更新哒~🙈
⭐️个人主页: 收藏加关注,永远不迷路~⭐️
数据结构系列👀
一:顺序表的操作,你真的学会了吗?
二:顺序栈的基本操作
三:循环队列的基本操作,你学会了吗?
前言😺
🌱Tips:文章有点长,小主耐心一点哦~
😎编程实现单链表的以下基本操作:建立顺序表,修改顺序表,插入顺序表,删除顺序表。😜
一、单链表是什么?🙉
单链表是线性表的链式存取结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。💪🏻ヾ(◍°∇°◍)ノ゙
二、实现步骤🙊
1.定义存储表示🐒
例如顺序表的最大长度,存储空间基址,表长等。
//单链表的存储结构
typedef struct LNode
{
ElemType data;
struct LNode *next;
} LNode,*LinkList;
2.定义操作函数🐗
对函数进行初始化,构造销毁线性表的函数DestoryList,清空线性表的函数ClearList,求线性表长度的函数ListLength,判断线性表是否为空的函数ListEmpty,获取线性表中的指定位置元素内容GetElem,求前驱、后继的函数,在线性表指定位置插入元素的函数ListInsert,删除线性表指定位置元素ListDelete,显示线性表函数和退出的操作。
//初始化
Status InitList(LinkList &L)
{
L=new LNode;
L->next=NULL;
return OK;
}
//销毁
Status DestroyList(LinkList &L)
{
LinkList p;
while(L)
{
p=L;
L=L->next;
delete p;
}
return OK;
}
//清空
Status ClearList(LinkList L)
{// 将L重置为空表
LinkList p,q;
p=L->next; //p指向第一个结点
while(p) //没到表尾
{q=p->next; delete p; p=q;}
L->next=NULL; //头结点指针域为空
return OK;
}
//求长度
int ListLength(LinkList L)
{ //返回L中数据元素个数
LinkList p=L->next; //p指向第一个结点
int count=0;
while(p){//遍历单链表,统计结点数
++count;
p=p->next;
}
return count;
}
//判断是否为空
bool ListEmpty(LinkList L)
{//若L为空表,则返回true,否则返回false
if(L->next==NULL)
return true;
else
return false;
}
//取值
Status GetElem(LinkList L,int i,ElemType &e)
{
LinkList p=L->next;
int j=1;
while(p&&j<i)
{
p=p->next;
++j;
}
if(!p||j>i) return ERROR;
e=p->data;
return OK;
}
//按值查找
LNode *LocateElem(LinkList L,ElemType e)
{
LinkList p=L->next;
while(p &&p->data!=e)
p->next;
return p;
}
//插入
Status ListInsert(LinkList &L,int i,ElemType e)
{
LinkList p=L;
int j=0;
while(p && (j<i-1))
{
p=p->next;
++j;
}
if(!p||j>i-1) return ERROR;
LinkList s=new LNode;
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
//删除
Status ListDelete(LinkList &L,int i)
{
LinkList p=L;
int j=0;
while((p->next)&&(j<i-1))
{
p=p->next;
++j;
}
if(!(p->next)||(j>i-1)) return ERROR;
LinkList q=p->next;
p->next=q->next;
delete q;
return OK;
}
//前插法创建单链表
void CreateList_H(LinkList &L,int n)
{
L=new LNode;
L->next=NULL;
for(int i=0; i<n; ++i)
{
LinkList p=new LNode;
cin>>p->data;
p->next=L->next;
L->next=p;
}
}
//后插法创建单链表
void CreateList_R(LinkList &L,int n)
{
L=new LNode;
L->next=NULL;
LinkList r=L;
for(int i=0; i<n; ++i)
{
LinkList p=new LNode;
cin>>p->data;
p->next=NULL;
r->next=p;
r=p;
}
}
//查找哪个元素的前驱
Status ListPrior(LinkList L,ElemType cur_e,ElemType *pre_e)
{
LinkList q=L->next;//第一个结点
if(!q)//若链表为空
return ERROR;
LinkList p=q->next;//第二个结点
while(p)
{
if(p->data==cur_e)
{
*pre_e=q->data;
return OK;
}
else
{
q=p;
p=p->next;
}
}
return ERROR;
}
//查找哪个元素的后继
Status ListNext(LinkList L,ElemType cur_e,ElemType *next_e)
{
LinkList p=L->next;
while(p)
{
if(p->data==cur_e&&p->next)
{
*next_e=p->next->data;
return OK;
}
else
p=p->next;
}
return ERROR;
}
//显示线性表
void DisplayList(LinkList L)
{
LinkList p=L->next;
while(p)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
return;
}
3.采用菜单样式让操作更加方便清楚。🐵
此功能用来实现一个小菜单哦😜
void show_help()
{
cout<<"******* Data Structure ******"<<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;
}
4.完整代码🐻
代码可直接运行😄
#include <iostream>
using namespace std;
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef int Status;
//单链表的存储结构
typedef struct LNode
{
ElemType data;
struct LNode *next;
} LNode,*LinkList;
//初始化
Status InitList(LinkList &L)
{
L=new LNode;
L->next=NULL;
return OK;
}
//销毁
Status DestroyList(LinkList &L)
{
LinkList p;
while(L)
{
p=L;
L=L->next;
delete p;
}
return OK;
}
//清空
Status ClearList(LinkList L)
{// 将L重置为空表
LinkList p,q;
p=L->next; //p指向第一个结点
while(p) //没到表尾
{q=p->next; delete p; p=q;}
L->next=NULL; //头结点指针域为空
return OK;
}
//求长度
int ListLength(LinkList L)
{ //返回L中数据元素个数
LinkList p=L->next; //p指向第一个结点
int count=0;
while(p){//遍历单链表,统计结点数
++count;
p=p->next;
}
return count;
}
//判断是否为空
bool ListEmpty(LinkList L)
{//若L为空表,则返回true,否则返回false
if(L->next==NULL)
return true;
else
return false;
}
//取值
Status GetElem(LinkList L,int i,ElemType &e)
{
LinkList p=L->next;
int j=1;
while(p&&j<i)
{
p=p->next;
++j;
}
if(!p||j>i) return ERROR;
e=p->data;
return OK;
}
//按值查找
LNode *LocateElem(LinkList L,ElemType e)
{
LinkList p=L->next;
while(p &&p->data!=e)
p->next;
return p;
}
//插入
Status ListInsert(LinkList &L,int i,ElemType e)
{
LinkList p=L;
int j=0;
while(p && (j<i-1))
{
p=p->next;
++j;
}
if(!p||j>i-1) return ERROR;
LinkList s=new LNode;
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
//删除
Status ListDelete(LinkList &L,int i)
{
LinkList p=L;
int j=0;
while((p->next)&&(j<i-1))
{
p=p->next;
++j;
}
if(!(p->next)||(j>i-1)) return ERROR;
LinkList q=p->next;
p->next=q->next;
delete q;
return OK;
}
//前插法创建单链表
void CreateList_H(LinkList &L,int n)
{
L=new LNode;
L->next=NULL;
for(int i=0; i<n; ++i)
{
LinkList p=new LNode;
cin>>p->data;
p->next=L->next;
L->next=p;
}
}
//后插法创建单链表
void CreateList_R(LinkList &L,int n)
{
L=new LNode;
L->next=NULL;
LinkList r=L;
for(int i=0; i<n; ++i)
{
LinkList p=new LNode;
cin>>p->data;
p->next=NULL;
r->next=p;
r=p;
}
}
//查找哪个元素的前驱
Status ListPrior(LinkList L,ElemType cur_e,ElemType *pre_e)
{
LinkList q=L->next;//第一个结点
if(!q)//若链表为空
return ERROR;
LinkList p=q->next;//第二个结点
while(p)
{
if(p->data==cur_e)
{
*pre_e=q->data;
return OK;
}
else
{
q=p;
p=p->next;
}
}
return ERROR;
}
//查找哪个元素的后继
Status ListNext(LinkList L,ElemType cur_e,ElemType *next_e)
{
LinkList p=L->next;
while(p)
{
if(p->data==cur_e&&p->next)
{
*next_e=p->next->data;
return OK;
}
else
p=p->next;
}
return ERROR;
}
//显示线性表
void DisplayList(LinkList L)
{
LinkList p=L->next;
while(p)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
return;
}
void show_help()
{
cout<<"******* Data Structure ******"<<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;
}
int main()
{
char operate_code;
show_help();
LinkList L;
InitList(L);
ElemType e;
int i;
while(1)
{
cout<<"请输入操作代码:";
cin>>operate_code;
if(operate_code=='1')
{
cout<<"The list has been cleared."<<endl;
ClearList(L);//调用操作函数
}
else if (operate_code=='2')
{
if(ListEmpty(L))
cout<<"The list is empty."<<endl;
else
cout<<"The list is not empty."<<endl;
}
else if (operate_code=='3')
{
cout<<"The length of list is:"<<ListLength(L)<<endl;
}
else if (operate_code=='4')
{
cout<<"请输入指定的位置:"<<endl;
cin>>i;
if(GetElem(L,i,e) == 1) cout<<"这个位置的数据是:"<<e<<endl;
else cout <<"error"<<endl;
}
else if (operate_code=='5')
{
int n;
cout<<"请输入你想查找哪个元素的前驱:"<<endl;
cin>>n;
if(ListPrior(L,n,&e) == 1) cout<<n<<"的前驱为:"<<e<<endl;
else cout<<"error"<<endl;
}
else if (operate_code=='6')
{
int n;
cout<<"请输入你想查找哪个元素的后继:"<<endl;
cin>>n;
if(ListNext(L,n,&e)==1) cout<<n<<"的后继为:"<<e<<endl;
else cout<<"error"<<endl;
}
else if (operate_code=='7')
{
cout<<"请输入插入元素及其位置:"<<endl;
cin>>e>>i;
if(ListInsert(L,i,e)==ERROR) cout<<"您的输入不合法"<<endl;
}
else if (operate_code=='8')
{
cout<<"请输入你想要删除哪个位置的元素:"<<endl;
cin>>i;
if(ListDelete(L,i)==ERROR) cout<<"error"<<endl;
}
else if (operate_code=='9')
{
cout<<"The contents of the list are:"<<endl;
DisplayList(L);
}
else if (operate_code=='0')
{
break;
}
else
{
cout<<"\n操作码错误!!!"<<endl;
show_help();
}
}
//调用销毁线性表函数,如Destroy_List(L);
DestroyList(L);
return 0;
}
5.运行结果🐾
这里是运行的结果哦 ❤️
文章来源:https://www.toymoban.com/news/detail-406255.html
结语🌍
本文用来介绍数据结构中单链表的代码实现过程及运行结果示例。用菜单样式实现单链表的以下基本操作:建立顺序表,修改顺序表,插入顺序表,删除顺序表。🚀🚀🚀
文章来源地址https://www.toymoban.com/news/detail-406255.html
到了这里,关于单链表的操作(超详细),保证你看完不后悔的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!