Loading [MathJax]/jax/output/HTML-CSS/jax.js

AcWing 826. 从零开始学数据结构：线性表（中）    原题链接    简单

作者： 作者的头像   Pigwantofly ,  2023-09-11 21:54:50 ,  所有人可见 ,  阅读 146

2


1

数据结构 单链表小结

AcWing 826. 从零开始学数据结构：线性表（上）

AcWing 827. 从零开始学数据结构：线性表（下）

三、单链表

1.单链表的储存结构定义

单链表(single linked list)是用一组任意的储存结构存放线性表的元素，这组存储单元可以连续亦可以不连续，甚至可以零散分布在内存中的任意位置。为了正确存储元素之间的逻辑关系，每个储存单元在储存数据元素的同时，还要存储后继元素的地址信息，这个地址信息称为指针，这两部分构成了这个数据元素的储存映像，称为节点(node).单链表正是通过指针域将线性表的数据元素按其逻辑联系在一起。每一个结点只有一个指针域，故称为单链表。

在使用单链表时，关心的只是数据元素以及数据元素之间的逻辑关系，而不是每个数据元素在存储器中的实际位置。常将单链表画出如下图表示的形式：
线性表之单链表结构.jpg
如上图所示，单链表的每一个结点的存储地址都存放在其前驱结点的next域中，而第一个元素无前驱，所以设头结点指向第一个元素所在结点（称为开始结点）。整个单链表的存取必须从头指针开始，因此头结点具有识别单链表的作用。由于最后一个元素无后继，所以最后一个元素所在结点（称为终止结点）的指针域为空，图示中用 ^ 表示，这个空指针称为尾标志(tail mark).

头结点：除了开始结点外，单链表的每一个结点的存储地址都存放在其前驱节点的next域中，而开始结点是由头指针指示的。这个特例需要在单链表实现时特殊处理，增加了程序复杂性和出现bug的机会。因此，通常在单链表之前附设一个相同类型的结点，称为头结点。

2.单链表的实现

单链表的存储思想通过指针来表示结点与结点的逻辑关系，首先先分清指针变量、指针、指针所指结点和结点四个密切相关的不同概念。

如果p是一个指针变量，则p的值是一个指针。有时为了叙述方便，将”指针变量“简称为”指针“。如将”头指针变量“简称为”头指针“。

设指针p指向某个Node类型的结点，则该结点用*p来表示，*p为结点变量。有时把”指针p所指结点”简称为”结点p“。

在单链表中，结点p由两个域构成：存放数据元素的数据域和存放后继结点地址的指针域。分别用(*p).data和(*p).next来标识，为了方便使用，C语言为指向结构体提供了运算符->即用p->data,p->next来表示p的数据域和指针域。

·单链表的结点结构定义

下面给出单链表的结点结构定义：

typedef int DataType; //定义线性表的数据类型，这里假设为int

typedef struct Node //定义单链表的结点类型
{
    DataType data;
    struct Node* next;
}Node;

#### · 单链表的初始化
初始化单链表就是生成只有头结点的空单链表，代码如下:
c Node* InitList() { Node* first = (Node*)malloc(sizeof Node); first->next = NULL; return first; }

· 判空操作

单链表的判空操作只需要判断单链表是否只有头结点，代码实现如下：

int Empty(Node* first)
{
    if (first->next == NULL) return 1;
    else return 0;
}

· 遍历操作

遍历单链表是指按照序号依次访问单链表中的所有结点。可以设置一个工作指针，依次指向各结点，输出该结点的数据域。遍历单链表需要将单链表扫描一遍，因此时间复杂度为O(n),代码如下：

void PrintList(Node* first)
{
    Node* p = first->next; //工作指针初始化

    while (p != NULL)
    {
        printf("%d ", p->data); //输出结点的数据域
        p = p->next; //将工作指针后移至下一个结点
    }
}

· 求单链表的长度

由于单链表的储存结构定义中没有储存线性表的长度，因此，不能直接得到线性表的长度。但我们可以通过遍历的方式来求其长度。代码如下：

int Length(Node* first)
{
    Node* p = first->next;
    int count = 0; //累加器

    while (p != NULL)
    {
        p = p->next;
        count++;
    }

    return count;
}

· 按值查找

在单链表中，实现按值查找操作，需要对单链表中的元素进行依次比较，如果查找成功，返回元素的序号，否则返回0表示查找失败，代码如下：

int Locate(Node* first, DataType x)
{
    Node* p = first->next;
    int count = 1;

    while (p != NULL)
    {
        if (p->data == x)
        {
            return count; //查找成功，返回序号
        }
        p = p->next;
        count++;
    }

    return 0; //查找失败，返回0
}

· 按位查找

在单链表当中，即使知道被访问的结点的序号，也不能直接的访问。只能从头结点开始向下搜索，若找到该位置，则返回该位置的数据域，否则搜索下一个结点，直到p为NULL时，查找失败。代码如下：

int Get(Node* first, int i, DataType *ptr)
{
    Node* p = first->next;
    int count = 1;
    while (p != NULL && count < i)
    {
        p = p->next;
        count++;
    }
    if (p == NULL) 
    {
        printf("位置错误，查找失败\n");
        return 0;
    }
    else
    {
        *ptr = p->data;
        return 1;
    }
}

· 插入操作

单链表的插入操作是将值为x的新结点插入单链表的第i的位置。所以必须先扫描单链表找到ai−1的储存位置p，然后生成一个新结点s，将结点s的next域指向$a_i$，将结点p的next域指向新结点s，图示如下：
单链表的插入操作.jpg
插入算法的时间复杂度主要消耗在查找正确的插入位置上，故时间复杂度为O(n)。函数的返回值表示插入操作是否成功，代码如下：

int Insert(Node* first, int i, DataType x)
{
    Node* s = NULL, * p = first;
    int count = 0;
    while (p != NULL && count < i - 1) //查找第i-1个结点
    {
        p = p->next; //工作指针后移
        count++;
    }
    if (p == NULL)
    {
        printf("位置错误，插入失败\n");
        return 0;
    }
    else
    {
        s = (Node*)malloc(sizeof Node); // 申请一个新结点s
        s->data = x;
        s->next = p->next;
        p->next = s;
        return 1;
    }
}

· 建立单链表

设给定的数据元素存放在数组a[n]中，建立单链表就是生成储存这n个数据元素的单链表。
有两种建立方法，头插法和尾插法。
头插法的基本思想是每次将新申请的结点插在头结点的后边，执行操作如图所示，代码如下：
```c
Node CreatList(DataType a[], int n)
{
Node s = NULL;
Node first = (Node)malloc(sizeof Node);
first->next = NULL;

for (int i = 0; i < n; i++)
{
    s = (Node*)malloc(sizeof Node);
    s->data = a[i];
    s->next = first->next;
    first->next = s; //将结点插入头结点之后
}

return first;

}
```
头插法.jpg
尾插法的基本思想是每次将新申请的结点插在终端结点的后面，为此，需要设尾指针指向当前的终端结点，操作如图所示，代码如下：

Node* CreatList(DataType a[], int n)
{
    Node* s = NULL,*r = NULL;
    Node * first = (Node*)malloc(sizeof Node);
    r = first;
    for (int i = 0; i < n; i++)
    {
        s = (Node*)malloc(sizeof Node);
        s->data = a[i];
        r->next = s;
        r = s;
    }
    r->next = NULL;
    return first;
}

尾插法.jpg

· 删除操作

删除操作是将单链表的第i结点删去。因为在单链表中结点ai的储存地址在其前驱结点的指针域中，所以必须首先将ai−1的储存地址，然后令p的next域指向ai的后继结点，即把结点ai从链上摘下来，最后把结点ai的存储空间释放代码如下：

int Delete(Node* first, int i, DataType* ptr)
{
    Node* p = first, * q = NULL;
    int count = 0;
    DataType x;
    while (p != NULL && count < i - 1)
    {
        p = p->next;
        count++;
    }
    if (p == NULL || p->next == NULL) //p结点或p的后继结点不存在
    {
        printf("位置错误，删除失败\n");
        return 0;
    }
    else
    {
        q = p->next;
        *ptr = q->data;
        p->next = q->next;
        free(q);
        return 1;
    }
}

删除的图示：
线性表删除操作.jpg

· 销毁单链表

单链表是动态存储分配，单链表的结点时在程序中动态申请的。因此，在单链表变量退出作用域之前，先要释放单链表的存储空间。算法如下：

void DeatroyList(Node* first)
{
    Node* p = first; //依次释放每一个结点，包括头结点
    while (first != NULL)
    {
        first = first->next;
        free(p);
        p = first;
    }
}

3.单链表的使用

#include<stdio.h>
#include<stdlio.h>

//上述函数

int main()
{
    int r[5] = { 1, 2, 3, 4, 5 }, x, i;
    Node* first = NULL;
    first = CreatList(r, 5);
    printf("当前线性表的数据为：");
    PrintList(first);
    Insert(first, 2, 8);
    printf("执行插入操作后的数据为：");
    PrintList(first);
    printf("当前单链表的长度为：%d", Length(first));
    printf("请输入查找的元素值：");
    scanf("%d", &x);
    i = Locate(first, x);
    if (i != 0) printf("元素%d的元素位置为：%d\n", x, i);
    else printf("单链表中没有元素%d\n", x);
    printf("请输入要删除第几个元素：");
    scanf("%d", &i);
    if (Delete(first, i, &x) == 1)
    {
        printf("删除的的元素值是%d,执行删除操作后数据为: ", x);
        PrintList(first);
    }
    else
    {
        printf("删除操作失败\n");
    }

    DestroyList(first);

    return 0;
}

0 评论

1024
x