线性表—链式存储之单链表

落日映苍穹つ 2021-11-15 12:52 373阅读 0赞

### 线性表—链式存储之单链表 ###

*  1、定义
 *  2、表示方式
 *  3、时间效率
 *  4、相关概念
 *  5、头指针与头结点的异同
 *  6、带头节点的单链表与不带头结点的单链表
 *  7、单链表的优缺点（相比于线性表）
 *  8、带头结点的单链表代码

# 1、定义 #

用一组地址任意的存储单元存放线性表中的数据元素。  
其结构特点：逻辑上相邻的数据元素在物理上不一定相邻。

# 2、表示方式 #

链表中的数据是以结点来表示

# 3、时间效率 #

\*插入和删除一个数据元素的时间复杂度为O(1)  
\*查找的时间复杂度为O(n)

# 4、相关概念 #

数据域

存储数据元素信息的域

指针域

存储后继元素的域

节点

数据域+指针域

头指针

指向链表中第一个结点（或为头结点、或为首元结点）的指针

头结点

在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息，它不计入表长度

首元结点

指链表中存储线性表第一个数据元素a０的结点![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjcwNDA5MA_size_16_color_FFFFFF_t_70]

# 5、头指针与头结点的异同 #

头指针

\*头指针具有标识作用，所以常用头指针冠以链表的名字  
\*头指针必须有。无论链表是否为空，头指针不为空。

头结点

\*头结点不是必需的  
\*头结点的数据域一般无意义（也可存放链表长度）  
\*头结点使得对首元结点的插入与删除与其他节点的操作统一起来了

# 6、带头节点的单链表与不带头结点的单链表 #

带头节点的单链表  
![在这里插入图片描述][20190731165959906.png]  
不带头结点的单链表  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjcwNDA5MA_size_16_color_FFFFFF_t_70 1]

# 7、单链表的优缺点（相比于线性表） #

和顺序表相比，单链表的优点和缺点正好相反  
优点

\*不需要预先确定数据元素的最大个数  
\*插入和删除操作不需要移动数据元素

缺点

\*查找数据元素时需要顺序进行，不能像顺序表那样随机查找任意一个数据元素  
\*每个结点中要有一个指针域，因此空间单元利用率不高，而且单链表操作的算法也较复杂

# 8、带头结点的单链表代码 #

link.h

#ifndef MAINWINDOW_H
    #define MAINWINDOW_H
    
    #include <stdio.h>
    #include <stdlib.h>
    
    #define FALSE 0
    #define TRUE 1
    
    typedef int Status;     //返回状态
    typedef int DataType;   //数据类型
    typedef struct Node
    { 
        DataType data;
        struct Node *next;
    }Link;
    
    int LinkLength(Link *head);                                 //获取链表长度
    void InitiaLink(Link **head);                               //初始化链表
    
    Status CleanLink(Link *head);                               //清空链表
    Status DestroyLink(Link *head);                             //销毁链表
    Status DeleteLinkElem(Link *head, int i);                   //删除链表元素
    Status GetLinkElem(Link *head, int i, DataType *elem);      //获取链表元素
    Status LinkInsertElem(Link *head, int i, DataType elem);    //在链表插入元素
    
    #endif // MAINWINDOW_H

link.c

#include "link.h"
    
    //初始化链表
    void InitiaLink(Link **head)
    { 
        *head = (Link *)malloc(sizeof(Link));
        (*head)->next = NULL;
        (*head)->data = 0;
    }
    
    //获取链表长度
    int LinkLength(Link *head)
    { 
        int length = 0;
        Link *p = head;
    
        if (head == NULL)
        { 
            return length;
        }
    
        while(p->next != NULL)
        { 
            length++;
            p = p->next;
        }
        return length;
    }
    
    //插入元素
    Status LinkInsertElem(Link *head, int i, DataType elem)
    { 
        int j = 0;
        Link *q = NULL;
        Link *p = head;
    
        if (i < 0)
        { 
            printf("Error index!\n");
            return FALSE;
        }
        while (p->next != NULL && j < i - 1)
        { 
            p = p->next;
            j++;
        }
    
        if(j != i - 1)
        { 
            printf("元素位置参数错！\n");
            return FALSE;
        }
        q = (Link *)malloc(sizeof(Link));
        q->data = elem;
        q->next = p->next;
        p->next = q;
    
        return TRUE;
    }
    
    //获取元素
    Status GetLinkElem(Link *head, int i, DataType *elem)
    { 
        int j = 0;
        Link *p = head;
    
        if (i > LinkLength(head) || i < 0)
        { 
            printf("Error index!\n");
            return FALSE;
        }
    
        while (p->next != NULL && j < i)
        { 
            p = p->next;
            j++;
        }
        if(j != i)
        { 
            printf("取元素位置参数错误！\n");
            return FALSE;
        }
        *elem = p->data;
    
        return TRUE;
    }
    
    //删除元素
    Status DeleteLinkElem(Link *head, int i)
    { 
        int j = 0;
        Link *p = head;
        Link *q = NULL;
    
        if (i > LinkLength(head) || i < 0)
        { 
            printf("Error index!\n");
            return FALSE;
        }
    
        while (p->next != NULL && j < i - 1)
        { 
            p = p->next;
            j++;
        }
    
        if(j != i - 1)
        { 
            printf("位置参数错误！\n");
            return FALSE;
        }
    
        q = p->next;
        p->next = p->next->next;
        free(q);
    
        return TRUE;
    }
    
    //销毁链表
    Status DestroyLink(Link *head)
    { 
        Link *q = NULL;
        Link *p = head;
    
        if (p == NULL)
        { 
            printf("Link is empty!\n");
            return FALSE;
        }
    
        while (p != NULL)
        { 
            q = p;
            p = p->next;
            free(q);
        }
        head = NULL;
    
        return TRUE;
    }
    
    //清空链表
    Status CleanLink(Link *head)
    { 
        Link *q = NULL;
        Link *p = head;
    
        if (p->next == NULL)
        { 
            printf("Link has been cleaned!\n");
            return FALSE;
        }
    
        while (p->next != NULL)
        { 
            q = p->next;
            p->next = p->next->next;
            free(q);
        }
    
        return TRUE;
    }

main.c

#include "link.h"
    
    int main()
    { 
        int elem = 0;
        int length = 0;
    
        Link *head;
        InitiaLink(&head);
    
        printf("Insert data:\n");
        for (int i = 1; i <= 10; i++)
        { 
            LinkInsertElem(head, i, i);
        }
    
        printf("Link data:\n");
        for (int i = 1; i <= LinkLength(head); i++)
        { 
            GetLinkElem(head, i, &elem);
            printf("%d\n", elem);
        }
    
        length = LinkLength(head);
        printf("Link length:%d\n", length);
    
        printf("After delete data:\n");
        DeleteLinkElem(head, 4);
        for (int i = 1; i <= LinkLength(head); i++)
        { 
            GetLinkElem(head, i, &elem);
            printf("%d\n", elem);
        }
    
        length = LinkLength(head);
        printf("Link length:%d\n", length);
    
        printf("Clean link:\n");
        CleanLink(head);
        length = LinkLength(head);
        printf("Link length:");
        printf("%d\n", length);
    
        printf("Destory link:\n");
        DestroyLink(head);
        printf("Link has been destoryed!\n");
    
        return 0;
    }

注：清空链表是保留头结点，删除其余的结点。销毁链表是将头结点也一并删除。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjcwNDA5MA_size_16_color_FFFFFF_t_70]: /images/20211115/de819d8907f94592bab2594d1aed9a37.png
[20190731165959906.png]: /images/20211115/412f707b986041fe913239e1116760b4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjcwNDA5MA_size_16_color_FFFFFF_t_70 1]: /images/20211115/33640a7c819d488ab013ece477938059.png