AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

《C语言数据结构》———链表进阶之双向链表

2022-11-26 142
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 《C语言数据结构》———链表进阶之双向链表

一、双向链表的概念


1、概念：概念：双向链表是每个结点除后继指针外还有⼀个前驱指针。双向链表也有带头结点结构和不带头结点结构两种，带头结点的双向链表更为常用；另外，双向链表也可以有循环和非循环两种结构，循环结构的双向链表更为常用。

1669438806009.jpg


二、双向链表的实现


头文件List.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int LTDateType;
typedef struct ListNode
{
  LTDateType date;
  struct ListNode* next;
  struct ListNode* prev;
}LTNode;
//void ListInit(LTNode** pphead)；
void ListPrint(LTNode* phead);
void ListPopBack(LTNode* phead);
LTNode* ListInit();//初始化
LTNode* BuyLTNode(LTDateType x);
void ListPushBack(LTNode* phead, LTDateType x);
void ListPushFront(LTNode* phead, LTDateType x);
void ListPopFront(LTNode* phead);
LTNode* ListFind(LTNode* phead, LTDateType x);
//在pos前插入
void ListInsert(LTNode* pos, LTDateType x);
//删除pos位置的节点
void ListErease(LTNode* pos);
void ListDestory(LTNode* phead);


源文件List.C


#include"List.h"
LTNode* BuyLTNode(LTDateType x)
{
  LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
  if (newnode == NULL)
  {
  printf("malloc fail\n");
  exit(-1);
  }
  newnode->date = x;
  newnode->next = NULL;
  newnode->prev = NULL;
  return newnode;
}
//void ListInit(LTNode** pphead)
//{
//  assert(pphead);
//  *pphead = BuyLTNode(0);
//  (*pphead)->next = *pphead;
//  (*pphead)->prev = *pphead;
//}
LTNode* ListInit()
{
  LTNode* phead = BuyLTNode(0);
  phead->next = phead;
  phead->prev = phead;
  return phead;
}
void ListPrint(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
  printf("%d ", cur->date);
  cur = cur->next;
  }
  printf("\n");
}
void ListPushBack(LTNode* phead, LTDateType x)
{
  assert(phead);
  LTNode* tail = phead->prev;
  LTNode* newnode = BuyLTNode(x);
  tail->next = newnode;
  newnode->prev = tail;
  newnode->next = phead;
  phead->prev = newnode;
}
void ListPushFront(LTNode* phead, LTDateType x)
{
  assert(phead);
  ListInsert(phead->next, x);
}
void ListPopBack(LTNode* phead)//尾删
{
  assert(phead);
  assert(phead->next != phead);//说明传进来的不只有phead,不然phead被free掉了。
  //LTNode* tail = phead->prev;
  //LTNode* tailPrev = tail->prev;
  //free(tail);
  //tail = NULL;
  //tailPrev->next = phead;
  //phead->prev = tailPrev;
  ListErease(phead->prev);
}
void ListPopFront(LTNode* phead)//头删
{
  assert(phead);
  assert(phead->next != phead);
  ListErease(phead->next);
}
LTNode* ListFind(LTNode* phead, LTDateType x)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
  if (cur->date == x)
  {
    return cur;
  }
  cur = cur->next;
  }
  return NULL;
}
//void ListInsert(LTNode* pos, LTDateType x)
//{
//  assert(pos);
//  LTNode* newnode = BuyLTNode(x);
//  pos->prev->next = newnode;
//  newnode->prev = pos->prev;
//
//  pos->prev = newnode;
//  newnode->next = pos;
//
//}
//更好的写法
void ListInsert(LTNode* pos, LTDateType x)
{
  assert(pos);
  //无关写的顺序
  LTNode* newnode = BuyLTNode(x);
  LTNode* posPrev = pos->prev;
  newnode->next = pos;
  pos->prev = newnode;
  posPrev->next = newnode;
  newnode->prev = posPrev;
}
// 驼峰法
//函数和类型所以单词首字母大写
//变量：第一个单词小写后续单词首字母大写
void ListErease(LTNode* pos)
{
  assert(pos);
  LTNode* prev = pos->prev;
  LTNode* next = pos->next;
  free(pos);
  //此时要把pos置成空，不然pos就是野指针了
  pos = NULL;
  prev->next = next;//LT的新的prev指向pos->next;
  next->prev = prev;//LT的新的next的prev指向prev;
}
void ListDestory(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead->next;//从头结点的下一个位置开始。
  while (cur != phead)
  {
  LTNode* next = cur->next;//先记录，再free
  //ListErease(cur);//副用Erease函数实现destory
  free(cur);//
  cur = next;
  }
  free(phead);
  //phead = NULL;形参的改变不影响实参
}


三、链表与顺序表的差别

不同点 顺序表 链表
存储空间上 物理上一定连续 逻辑上连续，但物理上不一定连 续
随机访问 支持O(1) 不支持：O(N）
任意位置插入或者删除元 素 可能需要搬移元素，效率低O(N) 只需修改指针指向
插入 动态顺序表，空间不够时需要扩容 没有容量的概念
应用场景 元素高效存储+频繁访问 任意位置插入和删除频繁
缓存利用率 高 低


四、链表oj


1、链表中倒数第k个结点_牛客题霸_牛客网（链接）


思路：快慢指针法，fast先走k步， slow和fast同时走， fast走到尾时，slow就是倒数第k个


代码示例：

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    struct ListNode* slow, *fast;
    slow = fast = pListHead;
    while(k --)//走k步
    {
        //判断K是否大于链表的长度。
        if(fast == NULL) return NULL;
        fast = fast->next;
    }
    while(fast)//当fast 指针走到尾时
    {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

第二种写法：

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
{
    struct ListNode* p1 = NULL, *p2 = NULL;
    p1 = pListHead;
    p2 = pListHead;
    int a = k;
    int c = 0;//记录节点个数
      //p1指针先跑，并且记录节点数，当p1指针跑了k-1个节点后，p2指针开始跑，
        //当p1指针跑到最后时，p2所指指针就是倒数第k个节点
    while(p1)//当p1 不为空时
    {
        p1 = p1->next;
        c ++;//节点个数增加
        if(k < 1) p2 = p2->next;
        k --;    
    }
    if(c < a) return NULL;
    return p2;
}

 2、21. 合并两个有序链表（链接）

思路：归并的思想，将小的值尾插到新链表。时间复杂度为n^2;如果再定义一个尾指针， 每次记录尾。

1669438935656.jpg

1669438945622.jpg

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    if(list1 == NULL)//list1和list2分别是两个链表的头指针
        return list2;
    if(list2 == NULL)
        return list1;
    struct ListNode* head = NULL, *tail = NULL;//head是新链表的头指针，tail是新链表的尾指针
    while(list1 && list2)
    {
            if(list1->val < list2->val)
            {
                if(tail == NULL)//这一步不太理解
                {
                    head = tail = list1;
                }
                else
                {
                    tail->next = list1;//先传指针指向
                    tail = list1;//再把list 的地址传给tail，相当于tail往前挪了一步。
                }
                list1 = list1->next;
            }
            else
            {
                if(tail == NULL)
                {
                    head = tail = list2;
                }
                else
                {
                    tail->next = list2;
                    tail = list2;//传地址
                }
                 list2 = list2->next;
            }
    }
    if(list1)
    {
        tail->next = list1;//如果链表1不为空，而此时链表二为空，则直接把链表二的值连接过去就好了。
    }
    if(list2)
    {
        tail->next = list2;
    }
    return head;
}

方法二：设置一个哨兵位头结点

head存随机值， head->next存第一个链表的值。起到简化代码的作用。

一般的链表没有设置哨兵位头结点。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    struct ListNode* head = NULL, *tail = NULL;
    head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->next = NULL;
    while(list1 && list2)
    {
            if(list1->val < list2->val)
            {
                    tail->next = list1;//先传指针指向
                    tail = list1;//再把list 的地址传给tail，相当于tail往前挪了一步。
                list1 = list1->next;
            }
            else
            {
                    tail->next = list2;
                    tail = list2;//传地址
                    list2 = list2->next;
            }
    }
    if(list1)
    {
        tail->next = list1;//如果链表1不为空，而此时链表二为空，则直接把链表二的值连接过去就好了。
    }
    if(list2)
    {
        tail->next = list2;
    }
    //解决内存泄漏问题；
    struct ListNode* list = head->next;
    free(head);
    return list;
}


3、链表分割_牛客题霸_牛客网（链接）


思路：新设置两个链表，小于x的插到第一个链表，大于x的插到第二个链表。


1669438988352.jpg

定义四个指针：LessHead, LessTail,GreatHead, GreatTail.


原链表的值分别尾插到这两个链表， 然后分别更新LessTail,和GreatTail;


最后LessTail的指针再指向GreatHead。完成两个链表的连接。


想极端场景：


1、所有值比x小


2、所有值比x大


3、比x大和小都有，最后一个值是比x小


4、比x大和小都有，最后一个值是比x大


1669438999035.jpg


构成环链表，造成死循环。

//设置哨兵位
class Partition {
  public:
    ListNode* partition(ListNode* pHead, int x) {
        struct ListNode* lessHead, *lessTail, *greatHead, *greatTail;
        lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));
        greatHead = greatTail = (struct ListNode*)malloc(sizeof(struct ListNode));
        lessTail->next = greatTail->next = NULL;
        struct ListNode* cur = pHead;
        while (cur) {
            if (cur->val < x) {
                lessTail->next = cur;
                lessTail = lessTail->next;
            } else {
                greatTail->next = cur;
                greatTail = greatTail->next;
            }
            cur = cur->next;
        }
        //完成链接工作
        lessTail->next = greatHead->next;
        greatTail->next = NULL;//切断greetTail的最后与greetHead的链接
        struct ListNode* list = lessHead->next;
        free(lessHead);
        free(greatHead);
        return list;
    }
};

4、链表的回文结构_牛客题霸_牛客网 （链接）


思路：找出链表的中间节点， 然后逆置，判断前后链表是否一致，若一致，则说明该链表是回文结构。


1669439031231.jpg


为什么奇数个时也能过，


例如：1 2 3 2 1


逆置完变为了 1 2  1 2  3 ；


当A走到2的位置时2->next = 3, rHead走到的 2->next = 3， 相等。

class PalindromeList {
public:
    struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* slow, * fast;
    slow = fast = head;
    while(fast && fast->next) //想的是结束的条件，写的是继续的条件
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
    struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* NewHead = NULL;
    struct ListNode* cur = head;
    while(cur)
    {
        struct ListNode* next = cur->next;
        //头插
        cur->next = NewHead;//更多代表链表的指向方向。
        NewHead = cur;//接着把地址传过来(更新)
        cur = next;//（更新）
    }
    return NewHead;
    }
    bool chkPalindrome(ListNode* A) {
        struct ListNode* mid = middleNode(A);
        struct ListNode*rHead = reverseList(mid);//应该逆置mid，中间结点。
        while(A && rHead)
        {
            if(A->val == rHead->val)
            {
                A = A->next;
                rHead = rHead->next;
            }
            else
            {
                return false;
            }
        }
        return true;
    }
};

5、力扣相交链表（链接）


思路1：A链表每个节点B跟链表依次比较，如果有相等，就是相交，第一个相等就是交点。


时间复杂度：o(N*M);


思路二：如果两个链表相交，则这两个链表的最后一个元素的地址相同。


包含思路二三：


1669439059018.jpg


代码示例：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    struct ListNode* tailA, *tailB;//因为之后还要用到headA,和headB,所以要用tail来进行迭代。
    tailA = headA, tailB = headB;
    int lenA = 1, lenB = 1;
    while(tailA)//求出A的尾
    {
        tailA = tailA->next;
        ++lenA;//求出A的长度
    }   
    while(tailB)//求出链表B的尾
    {
        tailB = tailB->next;
        ++lenB;//求出B的长度
    }
    if(tailA != tailB)//如果两个链表的尾不相等，则返回空
    {
        return NULL;
    }
    //相交，求交点，长的先走差距步，再同时找交点。
    struct ListNode* shortList = headA, *longList = headB;//默认A短B长
    if(lenA > lenB)
    {
        shortList = headB;
        longList = headA;
    }
    int gap = abs(lenA - lenB);//求出差距
    while(gap--)//减gap次，若是--gap,就是减了gap - 1次
    {
        longList = longList->next;
    }
    while(shortList && longList)
    {
        if(shortList == longList)
        return shortList;//此时shortList == longList;
        longList = longList->next;
        shortList = shortList->next;
    }
    //最最关键的一步：就是要在外面返回一个值，因为编译器不会判断代码在哪返回，只会检查你的代码的语法问题。
    return NULL;
}
文章标签：
C语言
缓存
存储
关键词：
C语言链表
C语言数据结构
数据结构链表
C语言数据结构链表
数据结构c语言
披星戴月的贾维斯
目录
相关文章
ephemerals__
|
1月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
186 9
XIAZHI
|
1月前
|
存储 算法 Perl
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法，并分析时间复杂度，理解链表特点。实验内容包括循环链表应用（约瑟夫回环问题）、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践，加深对链表数据结构的理解和应用能力。
XIAZHI
54 4
LuckiBit
|
20天前
|
存储 算法 C语言
【C语言】深入浅出：C语言链表的全面解析
链表是一种重要的基础数据结构，适用于频繁的插入和删除操作。通过本篇详细讲解了单链表、双向链表和循环链表的概念和实现，以及各类常用操作的示例代码。掌握链表的使用对于理解更复杂的数据结构和算法具有重要意义。
LuckiBit
153 6
龙大吉
|
23天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
44 5
XIAZHI
|
1月前
|
存储 人工智能 算法
数据结构实验之C 语言的函数数组指针结构体知识
本实验旨在复习C语言中的函数、数组、指针、结构体与共用体等核心概念，并通过具体编程任务加深理解。任务包括输出100以内所有素数、逆序排列一维数组、查找二维数组中的鞍点、利用指针输出二维数组元素，以及使用结构体和共用体处理教师与学生信息。每个任务不仅强化了基本语法的应用，还涉及到了算法逻辑的设计与优化。实验结果显示，学生能够有效掌握并运用这些知识完成指定任务。
XIAZHI
51 4
ephemerals__
|
1月前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
76 16
ephemerals__
|
1月前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
131 8
ephemerals__
|
1月前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
85 4
XIAZHI
|
1月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能，支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构，并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示，系统在处理小规模购物车时表现良好，但在大规模购物车操作下可能存在性能瓶颈。
XIAZHI
48 0
ephemerals__
|
1月前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
57 0