您现在的位置是:首页 >技术交流 >C语言单链表网站首页技术交流

C语言单链表

knighthood2001 2024-05-30 13:36:12
简介C语言单链表

本节目标:

①定义单链表结构体

②初始化单链表

③单链表增加结点(头插法尾插法

④删除指定结点

⑤打印输出

目录

导入头文件

定义单链表结构体

初始化单链表

头插法

尾插法插入

删除指定结点

打印单链表

全部代码展示


导入头文件

#include <stdio.h>
#include <stdlib.h>

        <stdlib.h>中有我们需要动态分配内存的malloc()函数。

定义单链表结构体

typedef struct Node {
    int data;
    struct Node* next;
} Node;

这里我们使用typedef将struct Node命名为Node。

当然很多书以及代码中会使用到如下的

typedef struct Node {
    int data;
    struct Node* next;
} Node, *LinkList;

 这里它还定义了一个指向这个结点的指针,当然对于初学者(笔者也是初学者)来说。

使用*LinkList后,不太好理解,这里笔者就使用上述Node的版本。

初始化单链表

Node* initList() {
    //定义头结点
    Node* L = (Node*)malloc(sizeof(Node));
    L->data = 0;
    L->next = NULL;
    return L;

这里我们使用Node* initList()作为初始化的函数,返回的是Node类型。

首先使用malloc函数分配结点内存,sizeof表示将Node转化为对应的大小。

这样就 定义了L,当然你可以加个判断,看内存分配是否成功

接着将L的data域设置为0(这里没有明确规定需要,因为头结点的数据域可存可不存内容),L的指针域设置为NULL,最后返回L,最终初始化好了单链表。

头插法

void headInsert(Node* L, int data) {
    //1创建空间
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = L->next;
    L->next = node;
    //表示插入一个结点
    L->data++;
}

 对于初学者,可以记住传入的参数是Node* L,这里指的是传入头结点。

首先创建一个结点node;然后如下图操作

        首先将data赋值到结点中,将结点指向L的下一个结点,当然这下一个结点可以为NULL,因此不用分类讨论。最后将L指向新生成的结点,最后这步L->data++可以表示插入了一个结点。

尾插法插入

void tailInsert(Node* L, int data) {
    //定义头结点
    Node* head = L;
    //创建空间
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    //指针先移到第一个结点上,因为第一个是头结点
    L = L->next;
    //如果next指向存在,就说明不是最后一个结点
    while (L->next) {
        L = L->next;
    }
    L->next = node;
    head->data++;
}

上图下面的是尾插法:  

①由于尾插法,本文没有设置尾指针,是通过遍历的方法找到最后一个结点(L=L->next),且由于这里head->data++,因此需要在搞一个变量存头结点;

②先创建node结点,将data赋值进去,next指向NULL;

③由于第一个是头结点,我们需要L=L->next,然后在进行遍历找最后一个结点,找到后将L的next指向新生成的node结点,最后head++。

删除指定结点

void delete(Node* L, int data) {
    //头结点
    Node* pre = L;
    //第一个结点
    Node* current = L->next;
    while (current) {
        if (current->data == data) {
            pre->next = current->next;
            free(current);
            break;
        }
        pre = current;
        current = current -> next;
    }
    //头结点的数据域用来计数
    L->data--;
}

①首先删除结点需要找到被删除结点的前一个结点,因此我们定义一个pre;

②然后我们定义一个current,指向L的next;

③判断current是否为空,如果不为空的话,pre和current往后指向一个;

④判断结点的data是否和函数的data相同,如果相同的话,将pre的next指针指向current的下一个结点,然后将current结点释放。

⑤最后头结点的data减一。

打印单链表

void printflist(Node* L) {
    L = L->next;
    while (L) {
        printf("%d ", L->data);
        L = L->next;
    }
    printf("
");
}

全部代码展示

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
    int data;
    struct Node* next;
} Node;

Node* initList() {
    //定义头结点
    Node* L = (Node*)malloc(sizeof(Node));
    L->data = 0;
    L->next = NULL;
    return L;
}
void headInsert(Node* L, int data) {
    //1创建空间
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = L->next;
    L->next = node;
    //表示插入一个元素
    L->data++;
}
void tailInsert(Node* L, int data) {
    //定义头结点
    Node* head = L;
    //创建空间
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    //指针先移到第一个结点上,因为第一个是头结点
    L = L->next;
    //如果next指向存在,就说明不是最后一个结点
    while (L->next) {
        L = L->next;
    }
    L->next = node;
    head->data++;
}
void delete(Node* L, int data) {
    //头结点
    Node* pre = L;
    //第一个结点
    Node* current = L->next;
    while (current) {
        if (current->data == data) {
            pre->next = current->next;
            free(current);
            break;
        }
        pre = current;
        current = current -> next;
    }
    //头结点的数据域用来计数
    L->data--;
}
void printflist(Node* L) {
    L = L->next;
    while (L) {
        printf("%d ", L->data);
        L = L->next;
    }
    printf("
");
}
int main(){
    Node* L = initList();
    headInsert(L, 1);
    headInsert(L, 2);
    headInsert(L, 3);
    headInsert(L, 4);
    headInsert(L, 5);
    headInsert(L, 6);
    headInsert(L, 7);
    tailInsert(L, 8);
    tailInsert(L, 9);
    tailInsert(L, 10);
    printflist(L);
    delete(L, 5);
    delete(L, 1);
    delete(L, 10);
    printflist(L);
    return 0;
}

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。