数据结构 | 链表（C语言）

大大源码 • 2023年4月24日 pm11:32 • 未分类

一、前言

以下操作的都是非空链表

下列四种链表主函数操作一致，故放在最后

参考视频：【UP从0到1带你手撕数据结构全集(C语言版)】 https://www.bilibili.com/video/BV1W64y1z7jh/?share_source=copy_web&vd_source=646c00b8c2f1a1aea167f68899ff0631

二、代码实现

1、头文件 / 宏定义

#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
#define TRUE 1
#define FALSE 0

2、单链表

(1) 结构体

typedef struct node
{
    DataType data;
    struct node *next;
} Node;

(2) 链表操作

// 初始化链表(头结点)
Node *initLinkList()
{
    Node *list = (Node *)malloc(sizeof(Node));
    list->data = 0; // 记录结点个数
    list->next = NULL;

    return list;
}

// 插入结点（头插法）
void headInsert(Node *list, DataType data)
{
    Node *node = (Node *)malloc(sizeof(Node));
    node->data = data;
    node->next = list->next;
    list->next = node;
    list->data++;
}

// 插入结点（尾插法）
void tailInsert(Node *list, DataType data)
{
    Node *p = list;
    Node *node = (Node *)malloc(sizeof(Node));

    while (p->next != NULL)
    {
        p = p->next;
    }
    node->data = data;
    node->next = NULL;
    p->next = node;
    list->data++;
}

// 删除结点
int deleteNode(Node *list, DataType data)
{
    Node *pre = list;
    Node *p = list->next;

    while (p->next != NULL)
    {
        if (p->data == data)
        {
            pre->next = p->next;
            p->next = NULL;
            list->data--;
            free(p);
            return TRUE;
        }
        pre = p;
        p = p->next;
    }
    return FALSE;
}

// 遍历链表
void traverseLinkList(Node *list)
{
    Node *L = list->next;
    while (L != NULL)
    {
        printf("%d->", L->data);
        L = L->next;
    }
    printf("NULL\n");
}

3、单循环链表

(1) 结构体

typedef struct node
{
    DataType data;
    struct node *next;
} Node;

(2) 链表操作

// 初始化链表（循环链表）
Node *initLinkList()
{
    Node *list = (Node *)malloc(sizeof(Node));
    list->data = 0;
    list->next = list;

    return list;
}

// 插入结点（头插法）
void headInsert(Node *list, DataType data)
{
    Node *node = (Node *)malloc(sizeof(Node));
    node->data = data;
    node->next = list->next;
    list->next = node;
    list->data++;
}

// 插入结点（尾插法）
void tailInsert(Node *list, DataType data)
{
    Node *p = list;
    Node *node = (Node *)malloc(sizeof(Node));

    while (p->next != list)
    {
        p = p->next;
    }
    node->data = data;
    p->next = node;
    node->next = list;
    list->data++;
}

// 删除结点
int deleteNode(Node *list, DataType data)
{
    Node *pre = list;
    Node *p = list->next;
    while (p != list)
    {
        if (p->data == data)
        {
            pre->next = p->next;
            p->next = NULL;
            list->data--;
            free(p);
            return TRUE;
        }
        pre = p;
        p = p->next;
    }
    return FALSE;
}

// 遍历链表
void traverseLinkList(Node *list)
{
    Node *p = list->next;
    while (p != list)
    {
        printf("%d->", p->data);
        p = p->next;
    }
    printf("list\n");
}

4、双链表

(1) 结构体

typedef struct node
{
    DataType data;
    struct node *pre;
    struct node *next;
} Node;

(2) 链表操作

// 初始化链表（双链表）
Node *initLinkList()
{
    Node *list = (Node *)malloc(sizeof(Node));
    list->data = 0;
    list->pre = NULL;
    list->next = NULL;

    return list;
}

// 插入结点（头插法）
void headInsert(Node *list, DataType data)
{
    Node *node = (Node *)malloc(sizeof(Node));

    node->data = data;
    if (list->data == 0)
    {
        node->next = NULL;
    }
    else
    {
        node->next = list->next;
        list->next->pre = node;
    }
    // 结点与头结点的指针操作
    list->next = node;
    node->pre = list;
    list->data++;
}

// 插入结点（尾插法）
void tailInsert(Node *list, DataType data)
{
    Node *node = (Node *)malloc(sizeof(Node));

    Node *p = list->next;

    while (p->next != NULL)
    {
        p = p->next;
    }
    node->data = data;
    p->next = node;
    node->pre = p;
    node->next = NULL;
    list->data++;
}

// 删除结点
int deleteNode(Node *list, DataType data)
{
    Node *p = list->next;
    Node *pre = NULL;
    Node *next = NULL;

    while (p != NULL)
    {
        if (p->data == data)
        {
            if (p->next == NULL)
            {
                p->pre->next = NULL;
                p->pre = NULL;
            }
            else
            {
                p->pre->next = p->next;
                p->next->pre = p->pre;
            }
            list->data--;
            free(p);
            return TRUE;
        }
        p = p->next;
    }

    return FALSE;
}

// 遍历链表
void traverseLinkList(Node *list)
{
    Node *p = list->next;

    while (p != NULL)
    {
        printf("%d->", p->data);
        p = p->next;
    }
    printf("NULL\n");
}

5、双循环链表

(1) 结构体

typedef struct node
{
    DataType data;
    struct node *pre;
    struct node *next;
} Node;

(2) 链表操作

// 初始化链表（循环双链表）
Node *initLinkList()
{
    Node *list = (Node *)malloc(sizeof(Node));
    list->data = 0;
    list->pre = list;
    list->next = list;

    return list;
}

// 插入结点（头插法）
void headInsert(Node *list, DataType data)
{
    Node *node = (Node *)malloc(sizeof(Node));

    node->data = data;
    if (list->next == list)
    {
        node->next = list;
        list->pre = node;
    }
    else
    {
        node->next = list->next;
        list->next->pre = node;
    }
    list->next = node;
    node->pre = list;
    list->data++;
}

// 插入结点（尾插法）
void tailInsert(Node *list, DataType data)
{
    Node *p = list->next;
    Node *node = (Node *)malloc(sizeof(Node));

    node->data = data;
    while (p->next != list)
    {
        p = p->next;
    }
    p->next = node;
    node->pre = p;
    node->next = list;
    list->pre = node;
    list->data++;
}

// 删除结点
int deleteNode(Node *list, DataType data)
{
    Node *p = list->next;

    while (p != list)
    {
        if (p->data == data)
        {
            p->pre->next = p->next;
            p->next->pre = p->pre;
            list->data--;
            free(p);
            return TRUE;
        }
        p = p->next;
    }

    return FALSE;
}

// 遍历链表
void traverseLinkList(Node *list)
{
    Node *p = list->next;

    while (p != list)
    {
        printf("%d->", p->data);
        p = p->next;
    }
    printf("NULL\n");
}

6、主函数

int main()
{
    int n, flag;
    DataType data = 0;
    Node *list = initLinkList();

    // 插入结点
    printf("请输入要插入的结点个数：");
    scanf("%d", &n);
    printf("1 -- 头插法\n");
    printf("2 -- 尾插法\n");
    printf("请选择插入方式：");
    scanf("%d", &flag);
    for (int i = 1; i <= n; i++)
    {
        flag == 1 ? headInsert(list, i) : tailInsert(list, i);
    }

    // 遍历链表
    traverseLinkList(list);

    printf("链表结点个数为%d\n", list->data);

    // 删除结点
    printf("请输入想删除的数据:");
    scanf("%d", &data);
    if (deleteNode(list, data) == 1)
    {
        printf("删除成功！\n");
        // 遍历删除结点后的链表
        traverseLinkList(list);
        printf("链表结点个数为%d\n", list->data);
    }
    else
    {
        printf("删除失败！\n");
    }

    return 0;
}

原文链接：https://blog.csdn.net/eu8189/article/details/128983624

THE END

计算属性

< <上一篇

npm webstorm配置_webstorm中配置nodejs环境及npm的实例

下一篇>>

大大搜源码

搜索内容

数据结构 | 链表（C语言）