1. Johngo学长首页
  2. 技术点详细复盘专题
  3. 数据结构和算法

《数据结构》（C语言版）学习笔记——第2章 线性表（单链表的基本操作）

• 数据结构和算法 • 阅读 108

2.5线性表的链式表示和实现

2.5.1单链表的定义与表示

线性表链式存储结构的特点是：用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）

  • 结点：数据元素的存储映像。
  • 结点包括两个域：存储数据元素信息的数据域，存储直接后继存储位置的指针域。指针域中存储的信息称为指针或链。n个结点链结成一个链表，即为线性表
    (a1, a2;··, an)。
  • 单链表是由头指针唯一确定，因此单链表可以用头指针的名字来命名。
  • 单链表：结点只有一个指针域的链表
  • 双链表：结点有两个指针域的链表
  • 循环链表：首尾相接的链表
  • 头指针：链表中第一个结点的指针
  • 首元结点：链表中存储第一个数据元素的结点
  • 头结点：链表的首元结点之前附设的一个结点

如何表示空表？

  • 无头结点时，头指针为空时表示空表
  • 有头结点时，当头结点的指针域为空时表示空表

在链表中设置头结点有什么好处？

  • 便于首元结点的处理，首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其他位置一致，无需进行特殊处理
  • 便于空表和非空表的统一处理，无论链表是否为空，头指针都是指向头节点的非空指针，因此空表和非空表的处理也就统一了

头结点的数据域内存储什么呢？

  • 头结点的数据域可以为空，也可以存放线性表长度等附加信息，但此结点不能计入链表长度值。

链表的特点

  • 结点在存储器中的位置是任意的
  • 访问时只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描其余结点（顺序存取法）
  • 单链表的存储结构
typedef struct LNode
{
    ElemType date;//结点的数据域
    struct LNode* next;//结点的指针域
}LNode ,* LinkList;//LinkList 为指向结构体 LNode 的指针类型

2.5.2 单链表基本操作的实现

算法2.6 初始化单链表

单链表的初始化操作就是构造一个如图2.10 (b)所示的空表。

《数据结构》（C语言版）学习笔记——第2章 线性表（单链表的基本操作）

【算法描述】
①生成新结点作为头结点，用头指针L 指向头结点
②头结点的指针域置空。

Status InitList(LinkList& L)
{//构建一个空的单链表L
    L = new LNode;//生成新的结点作为头结点，用头指针指向头结点
    if (!L->date)
    {
        printf("初始化失败！\n");
        return ERROR;
    }
    L->next = NULL;//头结点的指针域置空
    printf("初始化成功！\n");
    return OK;
}

算法2.7 单链表取值

和顺序表不同，链表中逻辑相邻的结点并没有存储在物理相邻的单元中，这样， 根据给定的结点位置序号i,在链表中获取该结点的值不能像顺序表那样随机访问，而只能从链表的首元结点出发，顺着链域 next 逐个结点向下访问。
【算法步骤】
①用指针p指向首元结点，用八故计数器初值赋为1。
②从首元结点开始依次顺着链域 next 向下访问，只要指向当前结点的指针 p 不为空(NULL), 并且没有到达序号为I的结点，则循环执行以下操作：

  • p指向下一个结点
  • 计数器j相应加l
    ③退出循环时， 如果指针p为空， 或者计数器j大于i, 说明指定的序号i值不合法（i大于表长n或i小于等于0), 取值失败返回ERROR; 否则取值成功， 此时j=i时，p所指的结点就是要找的第i个结点，用参数e保存当前结点的数据域， 返回OK。
    【算法描述】
Status GetElem(LinkList L, int i, ElemType& e)
{//在带头结点的单链表L中根据序号l.获取元素的值，用e返回L中第l.个数据元素的值
    LNode* p = L->next;//初始化，p指向首元结点
    int j = 1;//计数器
    while (p && j < i)//顺链域向后扫描，直到p为空或p指向第i个元素
    {
        p = p->next;//p指向下一个结点
        ++j;//计数器加一
    }
    if (!p || j > i)return ERROR;
    e = p->date; //取第i个结点的数据域
    return OK;
}

算法2.8 单链表的按值查找

链表中按值查找的过程和顺序表类似，从链表的首元结点出发， 依次将结点值和给定值e进行比较， 返回查找结果 。
【算法步骤】
①用指针p指向首元结点 。
②从首元结点开始依次顺着链域next向下查找， 只要指向当前结点的指针p不为空， 并且p所指结点的数据域不等千给定值e, 则循环执行以下操作： p指向下一个结点 。
③返回p。若查找成功，p此时即为结点的地址值，若查找失败，p的值即为NULL。
【算法描述】

LNode* LocateElem(LinkList L, ElemType e)
{//返回结点的地址
    LNode* p = L->next;//初始化，p指向首元结点
    while (p && p->date != e)
        p = p->next;
    return p;
}

算法2.9 单链表插入

假设要在单链表的两个数据元素a和b之间插入一个数据元素X, 已知p为其单链表存储结构中指向结点a的指针， 如图2.11 (a) 所示。

《数据结构》（C语言版）学习笔记——第2章 线性表（单链表的基本操作）
【算法步骤】
将值为 e 的新结点插人到表的第i个结点的位置上， 即插入到结点 (a_{i-1}) 与 (a_i) ;之间，具体插入过程如图 2.12 所示， 图中对应的 5 个步骤说明如下。
心查找结点 (a_{i-1}) 并由指针p指向该结点。
＠生成一个新结点 _s。
＠将新结点_s 的数据域置为 e。
＠将新结点 _s 的指针域指向结点(a_i) 。
＠将结点_p 的指针域指向新结点*s。
【算法描述】 
Status ListInsert(LinkList& L, int i, ElemType e)
{//在带头结点的单链表L的第i个位置插入值为e的新结点
    LNode* p = L;//初始化，p指向头结点
    int j = 0;//计数器
    while (p && (j < i - 1))
    {
        p = p->next;//查找第i-1个结点，p指向该结点
        ++j;
    }
    if (!p || j > i - 1)return ERROR;
    LNode* s = new LNode;//生成新结点s
    s->date = e;//将结点*s的数据域置为e
    s->next = p->next;//将结点*s的指针域指向结点ai
    p->next = s;//将结点*p的指针域指向结点*s
    return OK;
}

算法2.10 单链表删除

《数据结构》（C语言版）学习笔记——第2章 线性表（单链表的基本操作）
【算法步骤】
删除单链表的 第！个结点a的具体过程如图2.14所示，图中的对应的4个步骤说明如下。
①查找结点 (a_{i-1}) 并由指针p指向该结点。
②临时保存待删除结点 (a_i) ; 的地址在q中 ，以备释放。
③将结点*p的指针域指向 (a_i) 的直接后继结点。
④释放结点 (a_i) 的空间。
【算法步骤】 
Status ListDelete(LinkList& L, int i)
{//在带头结点的单链表L中，删除第i个元素
    LNode* p = L;//初始化，p指向头结点
    int j = 0;//计数器
    while ((p->next) && (j < i - 1))
    {
        p = p->next;//查找第i-1个结点，p指向该结点
        ++j;
    }
    if (!(p->next) || (j > i - 1))return ERROR;
    LNode* q;
    q = p->next;//临时保存被删除结点的地址以备释放
    p->next = q->next;//改变删除结点前驱结点的指针域
    delete q;//释放删除结点的空间
    return OK;
}

算法2.11 前插法创建单链表

前插法是通过将新结点逐个插入链表的头部（头结点之后）来创建链表，每次申请一个新结点，读入相应的数据元素值，然后将新结点插入到头结点之后
【算法步骤】
①创建一个只有头结点的空链表。
②根据待创建链表包括的元素个数n, 循环n次执行以下操作：

  • 生成一个新结点*p;
  • 输入元素值赋给新结点*p的数据域；
  • 将新结点*p插入到头结点之后。
    图2.15所示为线性表(a,b,c,d,e)前插法的创建过程，因为每次插入在链表的头部，所以应该逆位序输入数据，依次输入e、d、 C、b、a, 输入顺序和线性表中的逻辑顺序是相反的。
    《数据结构》（C语言版）学习笔记——第2章 线性表（单链表的基本操作）

【算法描述】

void CreateList_H(LinkList& L, int n)
{//逆序输入n个元素的值，建立带头结点的单链表L
    LNode* p;
    for (int i = 0; i < n; i++)
    {
        p = new LNode;//生成新节点*p
        cout << "请输入第" << n - i << "个元素：";
        cin >> p->date; //输入元素值赋给新结点* p的数据域
        p->next = L->next; //将新结点* p插人到头结点之后
        L->next = p;
    }
}

算法2.12 后插法创建单链表

后插法是通过将新结点逐个插入到链表的尾部来创建链表。 同前插法一样， 每次申请一个新结点， 读入相应的数据元素值。 不同的是， 为了使新结点能够插入到表尾， 需要增加一个尾指针r指向链表的尾结点。
【算法步骤】
①创建一个只有头结点的空链表。
②尾指针r初始化， 指向头结点。
③根据创建链表包括的元素个数n, 循环n次执行以下操作：

  • 生成一个新结点*p;
  • 输入元素值赋给新结点*p 的数据域；
  • 将新结点 _p 插入到尾结点_r之后；
  • 尾指针r指向新的尾结点*p。
    图2.16所示为线性表 (a,b,c,d,e) 后插法的创建过程， 读入数据的顺序和线性表中的逻辑顺序是相同的。
    《数据结构》（C语言版）学习笔记——第2章 线性表（单链表的基本操作）
void CreateList_r(LinkList& L, int n)
{//正序输入n个元素的值，建立带头结点的单链表L
    LNode* r = L; //尾指针r指向头结点
    LNode* p;

    for (int i = 0; i < n; i++)
    {
        p = new LNode;//生成新节点*p
        cout << "请输入第" << n - i << "个元素：";
        cin >> p->date; //输入元素值赋给新结点* p的数据域
        p->next = NULL; //将新结点* p插人尾结点* r之后
        r->next = p;
        r = p;
    }
}

单链表基本操作详细代码

#include
#include
#include
#include
#define OK 1
#define ERROR 0
using namespace std;
typedef int ElemType;
typedef int Status;

//定义单链表
typedef struct LNode
{
    ElemType date;
    struct LNode* next;
}LNode ,* LinkList;

//初始化单链表
Status InitList(LinkList& L)
{//构建一个空的单链表L
    L = new LNode;//生成新的结点作为头结点，用头指针指向头结点
    if (!L->date)
    {
        printf("初始化失败！\n");
        return ERROR;
    }
    L->next = NULL;//头结点的指针域置空
    printf("初始化成功！\n");
    return OK;
}

//前插法创建单链表
void CreateList_H(LinkList& L, int n)
{//逆序输入n个元素的值，建立带头结点的单链表L
    LNode* p;
    for (int i = 0; i < n; i++)
    {
        p = new LNode;//生成新节点*p
        cout << "请输入第" << n - i << "个元素：";
        cin >> p->date; //输入元素值赋给新结点* p的数据域
        p->next = L->next; //将新结点* p插人到头结点之后
        L->next = p;
    }
}

//后插法创建单链表
void CreateList_r(LinkList& L, int n)
{//正序输入n个元素的值，建立带头结点的单链表L
    LNode* r = L; //尾指针r指向头结点
    LNode* p;

    for (int i = 0; i < n; i++)
    {
        p = new LNode;//生成新节点*p
        cout << "请输入第" <<  i+1 << "个元素：";
        cin >> p->date; //输入元素值赋给新结点* p的数据域
        p->next = NULL; //将新结点* p插人尾结点* r之后
        r->next = p;
        r = p;
    }
}

//单链表取值
Status GetElem(LinkList L, int i, ElemType& e)
{//在带头结点的单链表L中根据序号i获取元素的值，用e返回L中第i个数据元素的值
    LNode* p = L->next;//初始化，p指向首元结点
    int j = 1;//计数器
    while (p && j < i)//顺链域向后扫描，直到p为空或p指向第i个元素
    {
        p = p->next;//p指向下一个结点
        ++j;//计数器加一
    }
    if (!p || j > i)return ERROR;
    e = p->date; //取第i个结点的数据域
    return OK;
}

//单链表查找
LNode* LocateElem(LinkList L, ElemType e)
{//返回结点的地址
    LNode* p = L->next;//初始化，p指向首元结点
    while (p && p->date != e)
        p = p->next;
    return p;
}

//单链表插入
Status ListInsert(LinkList& L, int i, ElemType e)
{//在带头结点的单链表L的第i个位置插入值为e的新结点
    LNode* p = L;//初始化，p指向头结点
    int j = 0;//计数器
    while (p && (j < i - 1))
    {
        p = p->next;//查找第i-1个结点，p指向该结点
        ++j;
    }
    if (!p || j > i - 1)return ERROR;
    LNode* s = new LNode;//生成新结点s
    s->date = e;//将结点*s的数据域置为e
    s->next = p->next;//将结点*s的指针域指向结点ai
    p->next = s;//将结点*p的指针域指向结点*s
    return OK;
}

//单链表删除
Status ListDelete(LinkList& L, int i)
{//在带头结点的单链表L中，删除第i个元素
    LNode* p = L;//初始化，p指向头结点
    int j = 0;//计数器
    while ((p->next) && (j < i - 1))
    {
        p = p->next;//查找第i-1个结点，p指向该结点
        ++j;
    }
    if (!(p->next) || (j > i - 1))return ERROR;
    LNode* q;
    q = p->next;//临时保存被删除结点的地址以备释放
    p->next = q->next;//改变删除结点前驱结点的指针域
    delete q;//释放删除结点的空间
    return OK;
}
//判断单链表是否为空
Status ListEmpty(LinkList& L)
{//若L为空表，则返回1，否则返回0
    if (L->next)
        return ERROR;
    return OK;
}

//单链表的销毁
void DestoryList(LinkList& L)
{
    LNode* p = new LNode;//或LinkList p;
    while (L)
    {
        p = L;
        L=L->next;
        delete p;
    }
}

//单链表的清空
Status ClearList(LinkList& L)//将L重置为空表。
{
    LNode* p, * q;
    p = L->next;
    q = new LNode;
    while (p)
    {
        q = p->next;
        delete p;
        p = q;
    }
    L->next = NULL;
    return OK;
}

//获取单链表长度
int ListLength(LinkList L)
{
    int i = 0;
    while (L->next)
    {
        i++;
        L = L->next;
    }
    return i;
}

//遍历单链表
Status PrintList(LinkList L)
{
    LNode* p = L->next;
    if (ListEmpty(L))
    {
        cout << "该单链表为空！" << endl;
        return ERROR;
    }
    while (p)
    {
        cout << p->date <next;
    }
    cout << endl;
    return OK;
}

int main()
{
    cout << "建立List1" << endl;
    LinkList List1;//定义单链表
    InitList(List1);//初始化单链表
    CreateList_H(List1, 5);//前插法创建单链表
    cout << "List1:";
    PrintList(List1);//遍历单链表
    int* e = new int;

    GetElem(List1, 2, *e);//取值
    cout << "List1中第二位值为：" << *e << endl;

    ListInsert(List1, 3, 100);//插入
    cout << "List1中第三位插入100：" << endl;
    PrintList(List1);//遍历单链表

    cout << "建立List2" << endl;
    LinkList List2;
    InitList(List2);
    CreateList_r(List2, 5);//后插法创建单链表
    cout << "List2:";
    PrintList(List2);//遍历单链表

    ListDelete(List2, 4);//删除
    cout << "List2中删除第四个元素：" << endl;
    PrintList(List2);//遍历单链表

    return 0;
}

Original: https://www.cnblogs.com/WMX-0121/p/15871970.html
Author: WMX_0121
Title: 《数据结构》（C语言版）学习笔记——第2章 线性表（单链表的基本操作）

原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/583947/

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
0

【自取】最近整理的，有需要可以领取学习：



Linux核心资料大放送~

全栈面试题汇总（持续更新&可下载）

一个提高学习100%效率的工具！

【超详细】深度学习面试题目！

LeetCode Python刷题答案下载！

LeetCode Java版刷题答案下载！

LeetCode C++ 版本，抓紧保存！

LeetCode GO语言 刷题答案下载！

大家都在看

亲爱的 Coder【最近整理，可免费获取】👉 最新必读书单  | 👏 面试题下载  | 🌎 免费的AI知识星球