数据结构与算法⑦(第二章收尾)带头双向循环链表的实现(上)

简介: 数据结构与算法⑦(第二章收尾)带头双向循环链表的实现

1.链表的分类

链表的分类

① 单向或者双向

② 带头或者不带头

③ 循环或者非循环


常用的链表:

根据上面的分类我们可以细分出8种不同类型的链表,这么多链表我们一个个讲解这并没有意义。我们实际中最常用的链表是 "无头单向非循环链表" 和 "带头双向循环链表" ,至于 "无头单项非循环链表" 我们在前面已经讲述过了,我们下面将讲解其反面: "带头双向循环列表" !

解读:

① 无头单向非循环链表:结构简单,一般不会单独用来存储数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等。此外,在笔试中单链表的出现频率较多

② 带头双向循环链表:结构最复杂,但是实现反而简单。一般用来单独存储数据,实际中使用的链表数据结构都是带头双向循环链表。另外,这个结构虽然结构复杂,但是使用代码实现后会发现结构会带来很多优势。双向链表严格来说只需要快速的实现两个接口,insert 和 earse ,头尾的插入和删除就可以搞定了,这就是结构的优势!链表的接口函数

2.双向链表分步实现:

(List.h)

#pragma once
 
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
typedef int DLNodeDataType;
 
typedef struct DoubleListNode 
{
    DLNodeDataType data;
    struct DoubleListNode* next;  // 指向后继节点的指针
    struct DoubleListNode* prev;  // 指向前驱节点的指针
}DLNode;
 
DLNode* DListInit();
void DListPushBack(DLNode* pHead, DLNodeDataType x);
void DListPrint(DLNode* pHead);
void DListPopBack(DLNode* pHead);
void DListPushFront(DLNode* pHead, DLNodeDataType x);
void DListPopFront(DLNode* pHead);
DLNode* DListFind(DLNode* pHead, DLNodeDataType x);
void DListInsert(DLNode* pos, DLNodeDataType x);
void DListEarse(DLNode* pos);

DListInit初始化函数:

DLNode* DListInit()
{
    DLNode* pHead = (DLNode*)malloc(sizeof(DLNode));
    if (pHead == NULL)
    {
        printf("malloc failed!\n");
        exit(-1);
    }
    pHead->next = pHead;
    pHead->prev = pHead;
    return pHead;
    //这里我们使用 malloc 函数开辟一块空间作为 "哨兵位" pHead ,
    //最后将其进行一个初始化。最后再将 pHead 作为结果返回回去,外面就可以接收到了。
    //这就是返回值的方法,当然这里也可以采用二级指针的方法来完成。
}

CreateNewNode创建新节点函数:

DLNode* CreateNewNode(DLNodeDataType x) 
{
    DLNode* newNode = (DLNode*)malloc(sizeof(DLNode));
    if (newNode == NULL) 
    {
        printf("malloc failed!\n");
        exit(-1);
    }
    newNode->data = x;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

DListPushBack尾插函数:

哨兵位头节点的好处:不用分情况处理

//因为不用改变 pList,所以不需要使用二级指针
void DListPushBack(DLNode* pHead, DLNodeDataType x)
{
    assert(pHead != NULL);
    DLNode* tail = pHead->prev;
    DLNode* newNode = CreateNewNode(x);
 
    tail->next = newNode;//原尾指向新尾
    newNode->prev = tail;//新尾指回原尾
    pHead->prev = newNode;//哨兵指到新尾
    newNode->next = pHead;//新尾指回哨兵
}

DListPrint打印函数:

void DListPrint(DLNode* pHead)
{
    //用结构体指针 pHead 接收, 这里的 pHead 表示哨兵位。
    assert(pHead != NULL);
    DLNode* cur = pHead->next;
    //遍历链表就需要从 pHead->next 开始(即第一个有效数据节点)
    //当 cur 等于 pHead 就相当于全部走了一遍了,这时就结束。
    while (cur != pHead)
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

DListPopBack尾删函数:

void DListPopBack(DLNode* pHead)
{
    assert(pHead != NULL);
    assert(pHead->next != pHead);//防止删掉哨兵位头节点
    DLNode* tali = pHead->prev;//记录原尾等下释放
    pHead->prev = pHead->prev->prev;//头链接到新尾
    pHead->prev->next = pHead;//新尾链接到头
    free(tali);
    tali = NULL;//不置空也行
}

测试1

void TestList1() 
{
    DLNode* pList = DListInit();
    DListPushBack(pList, 1);
    DListPushBack(pList, 2);
    DListPushBack(pList, 3);
    DListPushBack(pList, 4);
    DListPrint(pList);
 
    DListPopBack(pList);
    DListPopBack(pList);
    DListPrint(pList);
}

DListPushFront头插函数:

void DListPushFront(DLNode* pHead, DLNodeDataType x)
{
    assert(pHead != NULL);
    DLNode* newNode = CreateNewNode(x);
    pHead->next->prev = newNode;//原一指回新一
    newNode->next = pHead->next;//新一指向原一
    pHead->next = newNode;//哨兵指向新一
    newNode->prev = pHead;//新一指回哨兵
    //只有哨兵位头结点也能头插
}

DListPopFront头删函数:

void DListPopFront(DLNode* pHead)
{
    assert(pHead != NULL);
    assert(pHead->next != pHead);//防止删掉哨兵位头节点
    DLNode* head = pHead->next;//记录原一等下释放
    pHead->next = head->next;//哨兵头指向原二
    head->prev = pHead;//原二指回哨兵头
    free(head);
    head = NULL;//不置空也行
}

测试2

void TestList2()
{
    DLNode* pList = DListInit();
    DListPushFront(pList, 1);
    DListPushFront(pList, 2);
    DListPushFront(pList, 3);
    DListPushFront(pList, 4);
    DListPrint(pList);
 
    DListPopFront(pList);
    DListPopFront(pList);
    DListPrint(pList);
}

DListFind查找函数:

DLNode* DListFind(DLNode* pHead, DLNodeDataType x)
{
    assert(pHead != NULL);
    DLNode* cur = pHead->next;
    //遍历链表就需要从 pHead->next 开始(即第一个有效数据节点)(和打印一样)
    //当 cur 等于 pHead 就相当于全部走了一遍了,这时就结束。
    while (cur != pHead)
    {
        if (cur->data == x)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

DListInsert指定位置之前插入函数:

void DListInsert(DLNode* pos, DLNodeDataType x)//在pos之前插入
{
    assert(pos != NULL);
    DLNode* newNode = CreateNewNode(x);
    DLNode* posPrev = pos->prev;//记录pos前节点
    posPrev->next = newNode;//pos前节点指向新节点
    newNode->prev = posPrev;//新节点指回pos前节点
 
    newNode->next = pos;//新节点指向pos 
    pos->prev = newNode;//pos指回新节点
}

数据结构与算法⑦(第二章收尾)带头双向循环链表的实现(下):https://developer.aliyun.com/article/1513386

目录
相关文章
|
4天前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
8天前
|
存储 缓存 算法
数据结构和算法学习记录——总结顺序表和链表(双向带头循环链表)的优缺点、CPU高速缓存命中率
数据结构和算法学习记录——总结顺序表和链表(双向带头循环链表)的优缺点、CPU高速缓存命中率
11 0
|
8天前
|
算法
数据结构和算法学习记录——线性表之双向链表(上)-结点类型定义、初始化函数、创建新结点函数、尾插函数、打印函数、尾删函数
数据结构和算法学习记录——线性表之双向链表(上)-结点类型定义、初始化函数、创建新结点函数、尾插函数、打印函数、尾删函数
17 0
|
8天前
|
算法
数据结构和算法学习记录——习题-移除链表元素
数据结构和算法学习记录——习题-移除链表元素
7 0
|
19小时前
|
算法
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
|
3天前
|
存储
初阶数据结构 带头双链表
初阶数据结构 带头双链表
5 0
|
3天前
数据结构初阶 链表的补充
数据结构初阶 链表的补充
4 0
|
3天前
|
存储
数据结构初阶 链表详解
数据结构初阶 链表详解
5 0
|
7天前
|
存储 算法
数据结构和算法学习记录——二叉树的存储结构&二叉树的递归遍历(顺序存储结构、链表存储结构、先序中序后序递归遍历)
数据结构和算法学习记录——二叉树的存储结构&二叉树的递归遍历(顺序存储结构、链表存储结构、先序中序后序递归遍历)
8 0
数据结构和算法学习记录——二叉树的存储结构&二叉树的递归遍历(顺序存储结构、链表存储结构、先序中序后序递归遍历)
|
8天前
|
算法
数据结构和算法学习记录——线性表之双向链表(下)-头插函数、头删函数、查找函数、pos位置之前插入结点、pos位置删除结点及其复用、销毁链表函数
数据结构和算法学习记录——线性表之双向链表(下)-头插函数、头删函数、查找函数、pos位置之前插入结点、pos位置删除结点及其复用、销毁链表函数
9 0