深圳幻海软件技术有限公司 欢迎您！
更多

单链表的操作（超详细），保证你看完不后悔

2023-04-27

next cout endl
🌍新人小白的博客⌛️希望大家多多关注🌱一起加油，共同成长🎃以后会经常更新哒~🙈⭐️个人主页：收藏加关注，永远不迷路~⭐️数据结构系列👀一：顺序表的操作，你真的学会了吗？二：顺序栈的基本操作三：循环队列的基本操作，你学会了吗？文章目录数据结构系列👀前言😺一、单链表是什么？🙉二、实现步骤

🌍新人小白的博客
⌛️希望大家多多关注
🌱一起加油，共同成长
🎃以后会经常更新哒~🙈
⭐️个人主页： 收藏加关注，永远不迷路~⭐️

数据结构系列👀

一：顺序表的操作，你真的学会了吗？
二：顺序栈的基本操作
三：循环队列的基本操作，你学会了吗？

文章目录

  • 数据结构系列👀
  • 前言😺
  • 一、单链表是什么？🙉
  • 二、实现步骤🙊
    • 1.定义存储表示🐒
    • 2.定义操作函数🐗
    • 3.采用菜单样式让操作更加方便清楚。🐵
    • 4.完整代码🐻
    • 5.运行结果🐾
  • 结语🌍

前言😺

🌱Tips：文章有点长，小主耐心一点哦~

😎编程实现单链表的以下基本操作：建立顺序表，修改顺序表，插入顺序表，删除顺序表。😜

一、单链表是什么？🙉


单链表是线性表的链式存取结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。💪🏻ヾ(◍°∇°◍)ﾉﾞ

二、实现步骤🙊

1.定义存储表示🐒

例如顺序表的最大长度，存储空间基址，表长等。

//单链表的存储结构
typedef struct LNode
{
    ElemType data;
    struct LNode *next;
} LNode,*LinkList;

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

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;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182

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;

}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

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;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
  • 223
  • 224
  • 225
  • 226
  • 227
  • 228
  • 229
  • 230
  • 231
  • 232
  • 233
  • 234
  • 235
  • 236
  • 237
  • 238
  • 239
  • 240
  • 241
  • 242
  • 243
  • 244
  • 245
  • 246
  • 247
  • 248
  • 249
  • 250
  • 251
  • 252
  • 253
  • 254
  • 255
  • 256
  • 257
  • 258
  • 259
  • 260
  • 261
  • 262
  • 263
  • 264
  • 265
  • 266
  • 267
  • 268
  • 269
  • 270
  • 271
  • 272
  • 273
  • 274
  • 275
  • 276
  • 277
  • 278
  • 279
  • 280
  • 281
  • 282
  • 283
  • 284
  • 285
  • 286
  • 287
  • 288
  • 289
  • 290
  • 291
  • 292
  • 293
  • 294
  • 295
  • 296
  • 297
  • 298

5.运行结果🐾

这里是运行的结果哦 ❤️



结语🌍

本文用来介绍数据结构中单链表的代码实现过程及运行结果示例。用菜单样式实现单链表的以下基本操作：建立顺序表，修改顺序表，插入顺序表，删除顺序表。🚀🚀🚀

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览45136 人正在系统学习中
【算法系列篇】滑动窗口
走进人工智能|深度学习 算法的创世纪