【数据结构学习记录3】—— 单链表_数据结构中的单链三表记录了

一.原理

1.简述

因为顺序表是一段固定的空间，所以会存在空间的时候率的一些问题。如果能通过某种方式，动态的将一个又一个的节点串接起来，那就可能会好很多，所以，在这种情况下，我们想出了单链表这种数据结构。

2.分析

对于单链表，我们肯定还是需要有，增删改查这几种基础函数。而且，除了节点的定义，我们除了储存数据，应该还需要包括一个能够“感知”下一个节点的数据结构，那么我们可以用指针来代替。

3.思路图解

1.3.1 节点的定义

我们可以创建一个结构体，包含两个部分：第一个部分是我们的数据；第二个部分就存着我们指向下一个节点的指针，并将*next默认初始化为NULL，后面只要检测到他不为NULL，那么说明他的后面就还存在节点。一旦某个节点指向了NULL，说明这个节点就到此结束了。

1.3.2 链表的定义

因为我们整个链表的结构都是一样的，所以我们可以直接拿一个固定的节点，作为表头。
然后，根据习惯，我们将表头指向的第一个节点序号规定为0。

1.3.3 链表/节点的初始化

因为我们的链表都是由相同的节点组成，所以我们链表的初始化就等于我们节点的初始化。所以我们只需要使用malloc生成一个节点，并将*next指向NULL就可以了。

1.3.4 表的遍历

表的遍历我们可以用while来进行，直到*next == NULL。

1.3.5 表的销毁

对于销毁表，我们可以边遍历，边free，直到结束。

1.3.6 节点插入

我们可以通过遍历+计数的方式，找到要插入的节点的上一个位置，记作LastNode，并执行以下操作：

1. 创建好要插入的节点信息，记为ThisNode，并将ThisNode的*next赋值为 LastNode的 *next。这样，我们插入的节点，就指向我们的下一个节点了。
2. 将LastNode的 *next赋值为ThisNode的地址。这样，表就又完整了。
   比如图中的LastNode 是 0 ThisNode = index 是 1

1.3.7 节点的删除

类似于插入，我们还是要遍历到要删除的节点的上一个位置，然后执行这样的流程：

1. 读取并保存LastNode的*next的地址，这就是我们要删除的ThisNode。
2. 我们把LastNode的*next指向ThisNode的*next。此时，如果我们再遍历列表的话，已经无法遍历到ThisNode了，它被跳过了
3. free掉ThisNode因为它已经没有意义了。这样一个节点的删除了。

1.3.7 节点的修改

修改没有什么好说的，只是修改数据的话，并不会对链表的结构进行改变，所以直接遍历修改data就行。

1.3.8 节点的查询

查询的话，也是遍历即可。

二.代码

自己修改主函数，实现效果

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

#define OK      1
#define ERROR   0

// 定义数据类型
typedef struct elemType {
    int data1;
    int data2;
}data;

//定义节点
typedef struct Node {
    data data;
    struct Node *next;
    //不能写成 Node *next 因为此时还没有typedef成功，只能用结构体嵌套的方式定义
}Node;

Node* ListInit(void);
void ListShow(Node *list);
int ListInsert(Node *list, data data_in, int index);
int ListDelect(Node *list, int index);
int ListModify(Node *List, data data_in, int index);
int ListQuery(Node *list, data data_in);

int main()
{
    Node* List = ListInit();
    data test;
    test.data1 = 1;
    test.data2 = 2;

    ListInsert(List, test, 0);
    test.data1 = 3;
    ListInsert(List, test, 1);
    ListShow(List);
    printf("-------\n");
    //ListDelect(List, 0);
    //ListShow(List);
    //printf("-------\n");
    test.data1 = 5;
    ListModify(List,test,1);
    ListShow(List);
    printf("query get %d\n", ListQuery(List, test));
    test.data1 = 88;
    printf("query get %d\n", ListQuery(List, test));
    return 0;
}

Node* ListInit(void)
{
    Node* list = (Node *)malloc(sizeof(Node));  // 创建节点

    if (list == NULL)
    {
        exit(0);    // 节点创建失败，退出
    }
    else
    {
        list->next = NULL;  // 节点初始化成功，返回节点作为表头
        return list;    
    }
}

void ListShow(Node* list)
{
    int cont = 0;

    while(list->next != NULL)   // 遍历到表末尾
    {
        list = list->next;  // 跳过表头，list变成真第一个节点
        printf("No.%d data is %d %d\n", cont, list->data.data1, list->data.data2);
        ++cont; // 这个节点已输出，cont变成下一个节点的序号
    }

}

int ListInsert(Node *list, data data_in, int index)
{
    int cont = -1;  // 初始化为 -1，简化后面操作
    Node *ThisNode = (Node *)malloc(sizeof(Node));
    
    ThisNode->data = data_in;   // 初始化创建好的节点
    ThisNode->next = NULL;  

    if (list->next == NULL) //  判断这个表是不是空表，空表就特殊处理了
    {
        list->next = ThisNode;
        return OK;
    }

    while(list->next != NULL && cont < index - 1)   //遍历 到插入的前一个节点
    {
        list = list->next; //移动到下一个节点
        ++cont; // 因为list初值是表头，cont初值-1，所以这样操作后，这句话后的list的节点序号和cont对应
    }

    ThisNode->next = list->next;    //更新操作
    list->next = ThisNode;

    return OK;
}

int ListDelect(Node *list, int index)
{
    Node *dNode = NULL;     //声明一下要删除的节点变量
    int cont = -1;  //  同理

    if (list->next == NULL)
    {
        return ERROR;   //空链表，没意义，返回错误
    }
    else
    {
        while(list->next != NULL && cont < index - 1)
        {
            list = list->next;
            ++cont;
            // 和插入一样的解释，遍历。
        }

        dNode = list->next;
        list->next = dNode->next; //    这样就跳过了dNode
        free(dNode);    //释放掉删除的Node

        return OK;
    }
}

int ListModify(Node *list, data data_in, int index)
{
    int cont = -1;

    while(list->next != NULL && cont < index) // 因为要删除，所以要遍历到它本身
    {
        list = list->next;
        ++cont;
    }
    if (cont == index)  // 确定遍历到了它
    {
        list->data = data_in;
        return OK;
    }
    else    // 理论上来说是长度不够 index比表长更长
    {
        return ERROR;
    }
}

int ListQuery(Node *list, data data_ck)
{
    int cont = 0;
    
    while(list->next != NULL)   // 查询同修改
    {
        list = list->next;
        if (list->data.data1 == data_ck.data1 && list->data.data2 == data_ck.data2)
        {
            return cont;
        }
        ++cont;
    }
    return -1;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165