社区 › 安全 › 数据结构-单链表基础2

赘暨逢 发表于 2025-9-22 16:38:58

数据结构-单链表基础2

0.基本结构和函数

前置内容，可以访问数据结构-单链表基础1
点击查看代码typedef int ElemType;
typedef struct LNode {
        ElemType data;
        struct LNode *next;
} LNode, *linkList;
void CreateList_R(linkList *L, int n) {
        *L = (linkList) malloc(sizeof(LNode));
        (*L)->next = NULL;
        linkList lastp = *L;
        for (int i = 0; i < n; i++) {
                LNode *p = (LNode *) malloc(sizeof(LNode));
                scanf("%d", &(p->data));
                p->next = NULL;
                lastp->next = p;
                lastp = p;
        }
}
void PrintList(linkList L) {
        linkList p = L->next;
        while (p) {
                printf("%d ", p->data);
                p = p->next;
        }
        printf("\n");
}1.单链表的逆置

1.1简述

给定一个单链表，要求空间复杂度\({O}(1)\)实现逆置
1.2分析

在单链表建立时，利用头插法可以实现逆序输入，原因是每次输入的结点“都挤进了头结点后面的位置”，我们利用这个思路，遍历单链表，每次都对结点使用头插法，就可以实现逆置
时间复杂度\({O}(n)\)，空间复杂度\({O}(1)\)
1.3代码具体实现

点击查看代码void reverse(linkList *L) {
        linkList p = (*L)->next;
        (*L)->next = NULL;
        while (p) {
                LNode *q = p->next;
                p->next = (*L)->next;
                (*L)->next = p;
                p = q;
        }
}2.单链表的最大值查找

2.1简述

利用单链表表示一个整数序列，在单链表中确定最大值
2.2分析

该问题很简单，一次遍历比较即可
时间复杂度为\({O}(n)\) 空间复杂度为\({O}(1)\)
2.3代码具体实现

点击查看代码int findMax(linkList L) {
    linkList p = L->next;
    int max = p->data;
    while (p){
      max = max > p->data ? max : p->data;
      p = p->next;
    }
    return max;
}3.链表的正负分解

3.1简述

给定\(la\)表示一个非零整数序列，把链表\(la\)分解为两个链表\(lb\)和\(lc\)，其中\(lb\)表的结点为\(la\)表中值小于零的结点，而\(lc\)表的结点为\(la\)表中值大于零的结点。要求空间复杂度为\({O}(1)\)。
3.2分析

这道题目很简单，遍历链表\(la\)后对于正负不同的元素分别使用尾插法插入\(lb\)和\(lc\)即可
时间复杂度为\({O}(n)\) 空间复杂度为\({O}(1)\)
3.3代码具体实现

点击查看代码void fun(linkList *La,linkList *Lb,linkList *Lc) {
        *Lb = (linkList) malloc(sizeof(LNode));
        *Lc = (linkList) malloc(sizeof(LNode));
    linkList pa = (*La)->next,pb = *Lb,pc = *Lc;
    while (pa) {
      linkList temp = pa->next;
      pa->next = NULL;

      if (pa->data < 0) {
            pb->next = pa;
            pb = pa;
      } else {
            pc->next = pa;
            pc = pa;
      }

      pa = temp;
    }
    pb->next = NULL;
    pc->next = NULL;
}4.单链表的区间删除

4.1简述

给定一个有序链表和最小值和最大值，要求删除该链表中在区间[最小值，最大值]的所有结点，如果一个结点都没删或者全删了认为“删除失败”，不保证最小值最大值合法
4.2分析

首先题目不保证合法，还定义了“删除失败”，所以我们的函数需要返回是否合法且删除成功。在c语言中我们的函数需要使用int类型(或者自定义bool类型)。对于\(\)区间内的元素删除即可
时间复杂度为\({O}(n)\) 空间复杂度为\({O}(1)\)
4.3代码具体实现

点击查看代码int Delete(linkList *L,int min,int max,int n) {
    if(min>=max) return 0;
    linkList p = (*L)->next;
    linkList lastp = *L;
    int cnt = 0;
    while (p) {
      if(p->data >= min && p->data <= max) {
            lastp->next = p->next;
            cnt++;
      }else
            lastp = p;
      p = p->next;
    }
    if(cnt == n || cnt == 0) return 0;
    else return 1;
}5.两个有序链表的集合运算

5.1交集

单链表\(la\)和\(lb\)分别示两个递增的整数集合，求出\(la\)和\(lb\)的交集并以同样的形式存储，并存放在\(la\)中。若无交集，输出0。要求空间复杂度为\({O}(1)\)
5.1.2分析

首先题目说了是有序集合，所以没有重复元素，我们使用“快慢指针”法，对于每一个\(la\)的结点，值为\(e\)，我们使用只需要找到\(lb\)中第一个不小于\(e\)的结点，比较此结点的值是否为\(e\)即可，如果不是就删除，这样做看起来复杂度是\({O}(n^2)\)的，但是请注意两个链表均有序，所以\(lb\)不需要每次从头遍历，故最终时间复杂度为\(O(max(lena,lenb))\)，如果遍历结束\(la\)的指针还没有结束，需要赋值\(null\)代表后面的元素均不符合条件
时间复杂度为\({O}(n)\) 空间复杂度为\({O}(1)\)
5.1.3代码具体实现

点击查看代码int fun(linkList *La,linkList *Lb) {
    linkList pa = (*La)->next,pb = (*Lb)->next,pre = *La;
    pre->next = NULL;
    int cnt = 0;
    while(pa){
      while(pb && pb->data < pa->data)
                pb = pb->next;//找到第一个不小于此值的结点
      if(pb && pb->data == pa->data) {
      cnt ++;
      pre -> next = pa;
      pre = pa;//记录上一个符合条件的结点
      pa = pa->next;
      pb = pb->next;
      }else{
      linkList p = pa;
      pre -> next = pa -> next;
      pa = pa -> next;
      free(p);
      }
    }
    pre -> next = NULL;
    return cnt;
}5.2差集

和上一题目类似，所求集合从$ la\cap lb $变成 $ la - lb $
5.2.1分析

不难发现，这道题目的思考逻辑和上一题完全是相对的，我们在求解两个有序集合的交集时，遇见满足条件(在\(la\)中且\(lb\)中第一个不小于的元素和其相等)的元素就加入，否则就删除。不难发现 $ la - lb$ =$ la - (la ∩ lb) $，所以我们在上一题的逻辑下，仅需要调换删除和加入的顺序就能实现，即满足条件就删除，不满足条件就加入，此处所说的条件和前文一致。代码实现上需要注意一些小细节，已经在注释中说明
时间复杂度为\({O}(n)\) 空间复杂度为\({O}(1)\)
5.2.2代码具体实现

点击查看代码int fun(linkList *La,linkList *Lb) {
    linkList pa = (*La)->next,pb = (*Lb)->next,pre = *La;
    pre->next = NULL;
    int cnt = 0;
    while(pa){
      while(pb && pb->data < pa->data) pb = pb->next;
        //读者可以与上一题代码进行比较，仅仅调换了位置
      if(pb && pb->data == pa->data) {
      linkList p = pa;
      pre -> next = pa -> next;
      pa = pa -> next;
      free(p);
      }else{
      cnt ++;
      pre -> next = pa;
      pre = pa;
      pa = pa->next;
        //pb = pb->next;
        /*略微不同的是pb指针不需要后移
        因为此时pa指向的元素小于pb指向的元素，
        pa后移后，元素有可能与pb指向的元素相等也有可能仍然小于，
        所以如果pb后移则会缺少情况*/
      }
    }
    pre -> next = NULL;
    return cnt;
}6.单链表的排序

给定单链表，要求给出排序后的单链表
6.1.冒泡排序

6.1.1分析

排序，是算法/数据结构的基础，可以说很多高阶数据结构都是基于排序的，对于学习过c语言的读者，必然会冒泡排序算法，这里不再赘述原理，直接给出代码
时间复杂度为\({O}(n^2)\) 空间复杂度为\({O}(1)\)
6.1.2代码具体实现

点击查看代码void bubble(linkList L) {
        if (L->next == NULL || L->next->next == NULL) return;
        linkList p, q, tail = NULL;
        int isswap;// 是否发生交换
        do {
                isswap = 0;
                p = L->next;// 从第一个节点开始
                q = p->next;// 第二个结点开始
                // 遍历到tail节点
                while (q != tail) {
                        if (p->data > q->data) {
                                ElemType temp = p->data;
                                p->data = q->data;
                                q->data = temp;
                                isswap = 1;// 标记发生了交换
                        }
                        // 移动到下一对节点
                        p = q;
                        q = q->next;
                }
                // 更新尾指针 下一次不需要处理已排好的尾部
                tail = p;
        } while (isswap);
}6.2.归并排序

6.2.1分析

当然，\({O}(n^2)\)的排序仅仅能应付校内一些基础的任务，在大部分情况下是无法满足我们的性能需求的，我们需要思考更高效的算法。在上一篇文章中，我介绍了两个有序链表的合并，即归并操作，我们可以利用归并来实现高效的排序。我们需要知道基本基本事实：单个元素一定是有序的
请想象一下，我们比较每两个元素，对其归并，这时候长度为 $ {n} $ 的链表变成了 $ \frac{n}{2} $ 个有序的长度为2的链表，然后我们再对相邻的长度为2的链表进行归并......以此类推，最终由2个长度为$ \frac{n}{2} $ 归并，形成了所需要的有序链表。但是我们在代码实现的时候，实现逻辑是反过来的，因为我们不可能先将链表分成$ {n}$ 份，然后再分成$ \frac{n}{2} $ 份。我们反过来利用分治的思想对于排序的算法\({f}(L)\)，我们现把他分成两份，然后分别排序\({f}(L1)\)，\({f}(L2)\)，这样做函数就会递归调用，直到遇到边界情况，即长度为1的情况，此时退出递归。不难发现其时间复杂度由 “分”和“合” 两个阶段共同决定。
a.“分” 阶段：拆分链表

过程：通过快慢指针找到链表的中间节点，将链表拆分为两个子链表(\(L1\)和\(L2\))，递归处理子链表。
时间开销：每次拆分时，快慢指针遍历半个链表(长度为$ \frac{n}{2} $ )，时间复杂度为\({O}(n)\)。
递归结构：对于长度为n的链表，会拆分为两个长度为$ \frac{n}{2} $ 的子链表，以此类推，直到子链表长度为 \(1\)。递归深度为\(log_{2}n\)(二分次数)。
b.“合” 阶段：合并有序链表

过程：Merge函数将两个有序子链表(\(L1\)和\(L2\))合并为一个有序链表(\(L3\))，通过比较节点值依次链接。
时间开销：合并两个总长度为n的链表时，需要遍历所有节点一次，时间复杂度为\({O}(n)\)。
递归结构：每层递归的总合并时间为\({O}(n)\)(所有子链表合并的总长度为n)，共\(log_{2}n\)层。
c.总时间复杂度

分阶段总时间：\({O}(n) + {O}\left(\frac{n}{2}\right) + {O}\left(\frac{n}{4}\right) + \dots + {O}(1) = {O}(n)\)（等比数列求和）。
合阶段总时间：\({O}(n) \times \log_{2}n = {O}(n\log n)\)。
整体时间复杂度：\({O}(n\log n)\)（分阶段时间被合阶段主导）。
时间复杂度为\({O}(n\log n)\)，空间复杂度为\({O}(\log n)\)，此处空间复杂度为递归调用函数导致
6.2.2代码具体实现

点击查看代码void Merge(linkList L1, linkList L2, linkList *L3) {
        *L3 = (linkList) malloc(sizeof(LNode));
        (*L3)->next = NULL;
        linkList p1 = L1->next, p2 = L2->next, lastp = *L3;
        while (p1 && p2) {
                if (p1->data < p2->data)
                        lastp->next = p1, p1 = p1->next;
                else
                        lastp->next = p2, p2 = p2->next;
                lastp = lastp->next;
        }
        lastp->next = (p1) ? p1 : p2;
}

void sort(linkList L) {
        if (L->next == NULL || L->next->next == NULL)        return;
        linkList L1 = (linkList) malloc(sizeof(LNode)), L2 = (linkList) malloc(sizeof(LNode));
        L1->next = NULL, L2->next = NULL;
        linkList slow = L->next, fast = L->next->next; // 快慢指针，找中间值，因为链表不能下标访问data
        while (fast && fast->next) slow = slow->next, fast = fast->next->next;
        L1->next = L->next, L2->next = slow->next, slow->next = NULL;
        sort(L1), sort(L2);
        linkList L3;
        Merge(L1, L2, &L3);
        L->next = L3->next;
        free(L1), free(L2), free(L3);
}
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

馑妣窟 发表于 3 天前

感谢分享，下载保存了，貌似很强大

查看完整版本: 数据结构-单链表基础2