数据结构(3)-线性表之单向链表

2020-04-07 本文已影响0人 xxxxxxxx_123

定义

线性表之链式存储结构是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。那么我们如何通过一个元素，找到另一个元素呢？答案是在当前元素中存储下一个元素的地址。我们为设计每一个的元素的时候，不仅存储值，而且还存储其后继元素的地址，这样就可以通过这个地址，一个一个的找到后面的元素。

通常情况下，我们把存储数据元素信息的域称为数据域，把存储后继元素地址的域称为指针域。这两部分信息组成数据元素的存储映像，称为结点(Node)。

n个结点链接成一个链表，即为线性表的链式存储结构，如果每个结点只有一个指针域，则称为单链表。我们把链表的第一个结点的存储位置叫做头指针，而最后一个元素由于不存在后继元素，则将其指针置为NULL。

一般情况下，我们为了方便，会在单链表的第一个结点前设置一个结点，称之为头结点。头结点的数据域可以不存储任何信息，也可以存储链表的长度等一些附加信息；头结点的指针域指向第一个结点。

无头结点的结构如下：

无头结点.png

有头结点的结构如下：

有头结点.png

其实头结点存在的意义有2点：

便于第一个结点的相关处理
便于空表和⾮空表的统一处理

下面我们来看看单链表结构如何定义

typedef int ElementType;

typedef struct Node{
    ElementType data;   // 数据域
    struct Node *next;  // 指针域
}Node;

typedef struct Node *linkList;

当前元素与下一个元素的关联就在next指针。

单链表结点.png

单链表的操作

初始化单链表

TStatus InitLinkList(linkList *ll) {
    *ll = (linkList)malloc(sizeof(Node));
    if (*ll == NULL) {
        return T_ERROR;
    }
    *ll->data = NULL;
    *ll->next = NULL;
    return T_OK;
}

从单链表获取元素

获取第i个元素：

获取链表的第一个结点p
遍历链表，移动p指针
若链表到结尾了还未找到第i个元素，说明其不存在
反之找到了元素，返回即可

TStatus GetElement2(linkList *ll, int i, ElementType *e) {
    if (*ll == NULL) {
        return T_ERROR;
    }
    linkList p = *ll;
    
    int j = 1;
    // 取到i位置的前一个结点
    while (p && j < i) {
        p = p->next;
        j += 1;
    }
    
    if (p->next == NULL || j > i) {
        return T_ERROR;
    }
    *e = p->next->data;
    return T_OK;
}

单链表的插入

在单链表的第i个位置之后插入新的数据元素。了解了单链表的结构，可以看出，我们只要找到i位置的前一个元素p，让我们的新元素的next指针指向i位置的元素，然后把p的next指针指向新元素即可。如果没有头结点的话，我们需要把链表指针指向改为新元素，而有了头结点，我们只需要将头结点的next指针指向新元素即可，并不用去修改链表指针。

单链表的插入.png

获取链表的第一个结点p，一个待插入的节点q
当j < i时，遍历链表，后移指针p，累加j
若链表到结尾了还未找到第i个元素，说明其不存在
找到之后，将q的next指针指向该元素，将第i个元素的前一个元素的next指针指向q
返回成功

TStatus InsertElement2(linkList *ll, int i, ElementType e) {
    if (*ll == NULL) {
        return T_ERROR;
    }
    linkList p = (*ll);
    int j = 1;
    while (p && j < i) {
        p = p->next;
        j += 1;
    }
    
    if (p == NULL || j > i) {
        return T_ERROR;
    }
    
    linkList q = (linkList)malloc(sizeof(Node));
    if (q == NULL) {
        return T_ERROR;
    }
    q->next = p->next;
    q->data = e;
    p->next = q;
    
    return T_OK;
}

单链表的删除

删除第i个元素，其实就是把第i个元素与前后元素的联系断开，然后将前后元素链接起来。

单链表的删除.png

大概步骤如下：

获取第一个节点p
遍历链表，后移指针
未找到，则说明链表没有这个元素
找到，新建一个结点q，将要删除的结点赋值给q，将q的前一个结点赋值给p
让p结点的next指向q的next即可
返回q结点中的数据

TStatus DeleteElement1(linkList *ll, int i, ElementType *e) {
    if (*ll == NULL) {
        return T_ERROR;
    }
    
    linkList p = *ll;
    int j = 1;
    while (p && j < i) {
        p = p->next;
        j += 1;
    }
    
    if (p == NULL || p->next == NULL || j > i) {
        return T_ERROR;
    }
    
    linkList delQ = p->next;
    *e = delQ->data;
    p->next = delQ->next;
    free(delQ);

    return T_OK;
}

可以看出，对于插入或者删除数据，相比于顺序表，单链表的效率优势还是比较明显的。

单链表的整表创建

单链表也可以在创建的时候就创建出需要的结点，这就相当与将初始化和插入元素一起处理了。只是此时，我们需要确定插入的位置，一般情况下，有两种方式:

头插法：所有元素都插入在第一个结点位置
尾插法：所有元素都插在最后一个位置

头插法

TStatus createLinkListWithHead(linkList *ll, int arr[], int size) {
    *ll = (linkList)malloc(sizeof(Node));
    (*ll)->data = -1;
    (*ll)->next = NULL;
    
    for (int i = 0; i < size; i++) {
        int e = arr[i];
        linkList p = (linkList)malloc(sizeof(Node));
        if (p == NULL) {
            return T_ERROR;
        }
        p->data = e;
        p->next = (*ll)->next;
        (*ll)->next = p;
    }
    
    return T_OK;
}

尾插法

TStatus createLinkListWithTrail(linkList *ll, int arr[], int size) {
    *ll = (linkList)malloc(sizeof(Node));
    (*ll)->data = -1;
    (*ll)->next = NULL;
    
    linkList trail = *ll;    // 最后一个元素
    for (int i = 0; i < size; i++) {
        int e = arr[i];
        linkList p = (linkList)malloc(sizeof(Node));
        if (p == NULL) {
            return T_ERROR;
        }
        p->data = e;
        p->next = NULL;
        trail->next = p;
        trail = p;
    }
    
    return T_OK;
}

单链表的整表删除

单链表的整表删除就需要将链表中的每一个元素都删除，释放。

TStatus destoryLinkList(linkList *ll) {
    linkList p, q;
    p = (*ll)->next;
    
    while (p) {
        q = p;
        free(p);
        p = q->next;
    }
    
    (*ll)->next = NULL;
    return T_OK;
}

单链表与顺序表比较

存储分配方式
- 顺序存储结构用一段连续的存储单元一次存储线性表的数据元素
- 单链表采用链式存储结构，用一组任意的存储单元即可
时间性能
- 查找
  - 顺序存储结构O(1)
  - 单链表O(n)
- 插入和删除
  - 顺序存储结构O(n)
  - 单链表O(1)
空间性能
- 顺序存储结构需要预分配存储空间，分配大了浪费，分配少了容易溢出
- 单链表不需要预分配，而且元素个数不限制

静态链表

使用数组代替指针来描述单链表，让数组的元素由2个数据域组成，data和cur，data用来存储数据元素，cur存放该元素的后继元素在数组中的下标。这种形式的链表就叫做静态链表。

单向循环链表

将单链表中最后一个结点的指针由空指针改为指向头指针，这样链表就形成了一个环，这种头尾相接的单链表就称为单向循环链表。单向循环链表和单链表的区别其实就是看最后一个元素的next指针是否指向头指针(*ll)，当我们的链表存在头结点就会指向头结点，不存在头结点就会指向第一个元素结点。

循环链表.png

初始化单向循环链表

TStatus InitCycleLinkList(linkList *ll) {
    *ll = (linkList)malloc(sizeof(Node));
    if (*ll == NULL) {
        return T_ERROR;
    }
    (*ll)->next = (*ll);
    (*ll)->data = -1;
    return T_OK;
}

单向循环链表插入元素

单向循环链表在第i个位置插入元素，需要注意的是遍历链表的时候，防止当传入的i过大的时候，链表被循环遍历多次。另外，由于我们的链表都存在头结点，链表的头指针是指向头结点，所以就算是插入的位置为第一个结点，也不需要移动头指针的指向。

遍历链表，找出要插入位置的前一个元素p
创建要插入的结点q，将该节点的next指针指向p的next
将p的next指向要插入的新结点

/// 当插入位置超过链表长度则插入到链表末尾
TStatus InsertElement(linkList *ll, int i, ElementType e) {
    if (*ll == NULL || i < 1) {
        return T_ERROR;
    }
    
    linkList p = (*ll);
    int j = 1;
    // p->next != (*ll)防止当传入的数值i过大时，链表多次循环
    while (j < i && p->next != (*ll)) {
        p = p->next;
        j += 1;
    }
    
    linkList insP = (linkList)malloc(sizeof(Node));
    if (insP == NULL) {
        return T_ERROR;
    }
    insP->data = e;
    insP->next = p->next;
    p->next = insP;
    
    return T_OK;
}

单向循环链表删除元素

TStatus DeleteElement(linkList *ll, int i, ElementType *e) {
    if (*ll == NULL) {
        return T_ERROR;
    }
    
    linkList p = (*ll);
    int j = 1;
    while (p && j < i && p->next != (*ll)) {
        p = p->next;
        j += 1;
    }
    
    if (p->next == NULL || j > i) {
        return T_ERROR;
    }
    
    linkList delQ = p->next;
    p->next = delQ->next;
    *e = delQ->data;
    free(delQ);
    
    return T_OK;
}

可以看出存在头结点的单向循环链表和非循环的单向链表操作基本上是一致的，唯一需要注意的就是遍历链表的时候，防止循环链表多次循环遍历整个链表。