说在前面

这是一个绝望的女大学生学习数据结构的笔记，参考了B站up主秒懂算法大佬的数据结构教程，只是留着以后复习用，接下来是我的笔记啦！😋

ADT

抽象数据类型（Abstract Data Type，ADT）是计算机科学中具有类似行为的特定类别的数据结构的数学模型；或者具有类似语义的一种或多种程序设计语言的数据类型。抽象数据类型是描述数据结构的一种理论工具，其目的是使人们能够独立于程序的实现细节来理解数据结构的特性。抽象数据类型的定义取决于它的一组逻辑特性，而与计算机内部如何表示无关。

链表

概念理解：前驱，后继，指针域，数据域
链表由一系列不必在内存中相连的结构组成（与数组有区别），每一个结构都含有表元素和指向包含该元素后继元的结构的指针，我们称之为Next指针，最后一个Next指针指向NULL。了解定义之后，就开始学习插入删除的方法吧。

初始化链表

首先，我们要初始化一个链表，创建一个结构体，定义其中的数据域、指针域。

1
2
3
4
typedef struct Node {
    int data;//数据域
    struct Node* next;//下一节点地址
} Node;   //初始化链表，相当于创建一个头节点

头节点初始化函数

然后，我们要对头节点进行初始化，在堆内存中分配node节点，将数据域初始化为0，next指针指向NULL。

1
2
3
4
5
6
7
8
9
10
Node* initializeHeadNode() {
    Node* newNode = (Node*)malloc(sizeof(Node));//在堆内存分配node节点
    if (newNode == NULL) {
        printf("内存分配失败\n");
        return NULL;//分配失败，返回NULL
    }
    newNode->data = 0;//数据域初始化为0
    newNode->next = NULL;//next空指针初始化为空
    return newNode;//返回头节点地址
}

插入方法

在课程中，我学习到了三种插法

头插法

头插法，就是在链表的开头插入新元素，但是一般新元素要在头节点的后面。
下面来看代码,代码中我们可以看到，在insertAtHead函数中，有两个参数，Node* head是指向链表头节点的指针，int value是要插入的新节点的数据值。第一行代码，首先声明一个Node类型的指针newNode，用于指向新创建的节点*调用malloc函数分配一块内存，大小为Node结构体的大小（即一个节点所需的内存空间）
需要注意的是：(Node*)是强制类型转换，将malloc返回的void指针转换为Node类型，以便正确指向节点结构体。
这一步的目的是为新节点申请内存空间。

1
2
3
4
5
6
7
8
9
10
11
void insertAtHead(Node* head, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));//
    if (newNode == NULL) {
        printf("failure\n");
        return;
    }
    newNode->data = value;//内存分配成功就将传入的value赋值给新节点的data成员
    newNode->next = head->next;//新节点指向原来的第一个节点
    head->next = newNode;//头节点指向新节点
    printf("success,data is:%d\n", value);
}

尾插法

其余详细解释在头插法已经说过，此处不再赘述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void insertAtTail(Node* head, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        return;
    }
    newNode->data = value;
    newNode->next = NULL;//新节点成为尾节点，next指向空

    Node* current = head;
    while (current->next != NULL) {
        current = current->next;//找到最后一个节点
    }

    //将新节点插入链表尾部
    current->next = newNode;
    printf("成功在尾部插入节点，数据为： %d\n", value);
}

指定位置插入节点

和前面两个插入方法差不多，但是这里要注意顺序不能写反，这里面还需要注意的是，我们需要确定插入的位置，因此此处增加了一个参数position，函数中增加一个循环，没有找到制定的位置时，此时的current就会指向自己的next，直到倒找要插入的元素前一位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void insertAtPosition(Node* head, int value, int position) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    //找到要插入位置的前一个结点
    Node* current = head;
    int count = 0;
    while (count < position - 1) {
        current = current->next;
        count++;
    }
    //插入新节点
    newNode->next = current->next;
    current->next = newNode;//顺序不可以写反
}