• 周六. 3月 2nd, 2024

    数据结构笔记 3.线性表(2)单链表

    每个数据元素ai与其直接后继数据元素ai+1之前的逻辑关系,对数据元素ai来说,除了存储其本身的信息之外,还需存储一个指示其直接 后继的信息(即直接 后继的存储位置)。我们把存储数据元素信息的域称为数据域,把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素ai的存储映像,称为结点(Node)。

    n个结点(ai的存储映像)链结成一个链表,即为线性表(a1,a2,……an)的链式存储结构,因为此链表的每个结点中只包含一个指针域,所以叫单链表

    链表中第一个结点的存储位置叫做头指针,最后一个结点指针为“空”(通常用NULL 或”^”符号表示)

    有时,我们为了更加方便地对链表进行操作,会在单链表的第一个结点前附设一个结点,称为头结点。

    1. 头指针与头结点的异同

    2. 线性表链式存储结构代码描述

    若线性表为空表,则头结点的指针域为“空”

    若带有头结点的单链表,则如下图

    空链表如下图

    单链表中,我们在C语言中可用结构指针来描述

    /*线性表的单链表存储结构*/
    typedef struct Node 
    {
        ElemType data;
        struct Node *next;
    }Node;
    
    typedef struct Node *LinkList; /*定义LinkList*/

    结点由存放数据元素的数据域和存放后继结点地址的指针域。

    假设p是指向线性表第i个元素的指针,则该结点ai的数据域我们可以用p->data来表示,p->data的值是一个数据元素,结点ai的指针域可以用p->next来表示,p->next的值是一个指针。 p->next指向ai+1的指针。也就是说, 如果p->data = ai, 那么p->next->data = ai+1

    3. 单链表的读取

    获得链表的第i个数据的算法思路

    1. 声明一个结点p指向链表第一个结点,初始化j从1开始;
    2. 当j<i时,就遍历链表,让p的指针向后移动,不断指向下一个结点,j累加1;
    3. 若到链表末尾p为空,则说明第i个元素不存在
    4. 否则查找成功, 返回结点p的数据

    实现代码算法如下:

    /*初始条件: 顺序线性表L已存在,1<=i<=ListLength(L)*/
    /*操作结构:用e返回L中第i个数据元素的值*/
    Status GetElem(LinkList L, int i, ElemType *e) 
    {
        int j;
        LinkList p; /*声明一结点p*/
        p = L->next; /*让p指向链表L的第一个结点*/
        j = 1;  /*j为计数器*/
        while (p && j<i) { /*p不为空或者计数器j还没有等于i时,循环继续*/
            p = p->next;    /*让p指向下一个结点*/
            ++j;
        }
        if (!p || j>i) 
            return ERROR;   //第i个元素不存在
        *e = p->data; //取第i个元素的数据
        return OK;
    }

    说白了,就是从头开始找,直到第i个元素为止。由于这个算法的时间复杂度取决于i的位置, 当i=1时,则不需遍历,第一个就取出数据了,而当i=n时则遍历n-1次才可以。因此最坏的情况的时间复杂度是o(n).

    4. 单链表的插入

    假设存储元素e的结点为s, 要实现结点p, p->next和s之间的逻辑关系的变化,只需将结点s插入到结点p和p->next之间即可。

    只需要让s->next和p->next的指针做一点改变。

    s->next=p->next;
    p->next=s;

    让p的后继结点改成s的后继结点,再把结点s变成p的后继结点

    插入s后

    对于单链表的表头和表尾的特殊性况,操作是相同的

    单链表第i个数据插入结点的算法思路:

    1. 声明一结点p指向链表第一个结点,初始化j从1开始;
    2. 当j<i时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累加1;
    3. 若到链表末尾p为空,则说明第i个元素不存在;
    4. 否则查找成功,在系统中生成一个空结点s;
    5. 将数据元素e赋值给s->data;
    6. 单链表的插入标准语句s->next = p->next; p->next=s;
    7. 返回成功

    代码描述:

    /**
     * @brief 单链表的插入
     * 初始条件,顺序线性表L已经存在, 1<=L<=ListLength(L)
     * 操作结果: 在L中第i个位置之前插入新的数据元素e,L的长度加1
     * 
     */
    Status ListInsert(LinkLit *L, int i, ElemType e) 
    {
        int j;
        LinkList p, s;
        p = *L;
        j = 1;
        while( p && j<i) {//寻找第i个结点
            p = p->next;
            ++j;
        }
        if(!p || j>i)
            return ERROR;   //第i个元素不存在
        s = (LinkList) malloc(sizeof(Node)); //生成新结点(C标准函数)
        s->data = e;
        s->next = p->next;
        p->next = s;
        return OK;
    }

    这里我们用了malloc C语言的标准函数,它作用为生成一个新的结点。其类型与Node一样。

    5. 单链表的删除

    设存储 元素ai的结点为q, 要实现将结点q删除单链表的操作,其实就是将它的前继结点的指针绕过,指向它的后继结点即可。

    实际上就一步, p->next = p->next->next, 用q来取代p->next,即是 q=p->next; p->next = q->next;

    单链表第i个数据删除结点的算法思路:

    1. 声明一结点p指向链表的第一个结点, 初始化j从1开始;
    2. 当j<i时,就遍历链表,让 p的指针向后移动,不断指向下一个结点,累加j
    3. 若到链表末尾p为空,则说明第i个元素不存在
    4. 否则查找成功, 将欲删除的结点p->next赋值给q;
    5. 单链表的删除标准语句:p->next = q->next;
    6. 将q结点中的数据赋值给e, 作为返回;
    7. 释放q结点;
    8. 返回成功

    代码:

    Status ListDelete(LinkList *L, int i, ElemType *e) 
    {
        int j; 
        LinkList p, q;
        p = *L;
        j = 1;
        while (p->next && j<i) {
            p = p->next;
            ++j;
        }
        if (!(p->next) || j>i) {
            return ERROR;
        }
        q = p->next;
        p->next = q->next;
        *e = q->data;
        free(q);
        return OK;
    }

    C语言标准函数free, 作用是让系统回收一个Node结点,释放内存。

    单链表的插入与删除,时间复杂度都是O(n)。

    6. 单链表的整表创建

    顺序存储结构的创建,其实就是一个数组的初始化,即声明一个类型和大小的数组并赋值的过程。单链表则不一样:

    单链表整表创建的算法思路:

    1. 声明一结点p和计数器变量i;
    2. 初始化一空链表L;
    3. 让L的头结点的指针指向NULL, 即建立一个带头结点的单链表;
    4. 循环:
      • 生成一新结点赋值给p;
      • 随机生成一数字赋值给p的数据域p->data;
      • 将p插入到头结点与前一新结点之间。
    /**
     * @brief 单链表创建整表, 头插法
     * 
     */
    void CreateListHead(LinkList *L, int n)
    {
        LinkList p;
        int i; 
        srand(time());
        *L = (LinkList) malloc (sizeof(Node));
        (*L)->next = NULL;
        for (i=0; i<n; i++) {
            p = (LinkLIst) malloc(sizeof(Node)); 
            p->data = rand()%100+1;
            p->next = (*L)->next;
            (*L)->next = p;
        }
    }
    /**
     * @brief 随机产生n个元素的值,建立带表头结点的单链线性表L(尾插法)
     * 
     * @param L 
     * @param n 
     */
    void CreateLIstTail(LinkList *L, int n) 
    {
        LinkList p, r;
        int i;
        srand(time(0)); 
        *L = (LinkList) malloc(sizeof(Node));
        r = *L; //r为指向尾部的结点
        for (i=0; i<n; i++) {
            p = (Node *) moalloc(sizeof(Node));
            p->data = rand()%100 +1;        //随机生成100以内的数字 
            r->next = p;
            r = p;
        }
        r->next = NULL;
    }

    注意:L与r的关系,L是指整个单链表,而r是指向尾结点的变量,r会随着循环不断地变化结点, 而L则是随着循环增长为一个多结点的链表。

    这里需要解释一下,r->next = p;的意思, 其实就是将刚才的表尾终端结点r的指镇里指向新结点p

    r = p是什么意思?

    本来r是在ai-1元素的结点,可现在它已经不是最后的结点了,现在最后的结点是ai,所以应该要让将p结点这个最后的结点赋值给r。此时r又是最终的尾结点了。

    7。 单链表的整表删除

    算法思路:

    1. 声明一个结点p和q;
    2. 将第一结点赋值给p;
    3. 循环:
      • 将下一结点赋值给q;
      • 释放p;
      • 将q赋值给p

    代码:

    Status ClearList(LinkList *L)
    {
        LinkList p, q;
        p = (*L)->next;
        while(p) {
            q = p->next;
            free(p);
            p = q;
        }
        (*L)->next = NULL; //头结点指针域为空
        return OK;
    }

    8. 单链表结构与顺序存储结构优缺点

    结论:

    • 若线性表需要频繁查找,很少进行插入和删除操作时,宜采用顺序存储结构。若要频繁插入和删除时, 宜采用单有结构。
    • 当线性表中的元素个数变化较大或者根本不知道有多大时,最好用单链表结构,这样可以不需要考虑存储空间大小问题。

    root