🌍新人小白的博客
⌛️希望大家多多关注
🌱一起加油，共同成长
🎃以后会经常更新哒~🙈
⭐️个人主页： 收藏加关注，永远不迷路~⭐️
数据结构系列👀
一：顺序表的操作，你真的学会了吗？
二：顺序栈的基本操作
三：循环队列的基本操作，你学会了吗？
文章目录
- 数据结构系列👀
- 前言😺
- 一、单链表是什么？🙉
- 二、实现步骤🙊
- 1.定义存储表示🐒
- 2.定义操作函数🐗
- 3.采用菜单样式让操作更加方便清楚。🐵
- 4.完整代码🐻
- 5.运行结果🐾
- 结语🌍
前言😺
🌱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，否则返回falseif(L->next==NULL)return true;elsereturn 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;}elsep=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，否则返回falseif(L->next==NULL)return true;elsereturn 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;}elsep=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;elsecout<<"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.运行结果🐾
这里是运行的结果哦 ❤️
结语🌍
本文用来介绍数据结构中单链表的代码实现过程及运行结果示例。用菜单样式实现单链表的以下基本操作：建立顺序表，修改顺序表，插入顺序表，删除顺序表。🚀🚀🚀
