c语言之单链表的基础操作（插入删除查找头插尾插）_c语言插入删除

c语言之单链表的基础操作（插入删除查找头插尾插）

有头结点

#include <stdio.h>
#include <stdlib.h> //malloc函数所需要的
struct Node
{
    // 定义一个结构体
    int data;          // 数据域
    struct Node *next; // 指针：指向node节点的指针，叫next，此处struct意为这是一个结构体，可以省略掉
};
typedef struct Node Node;      // 将结构体Node取了个名字叫做Node
typedef struct Node *Linklist; // 为这个单链表结构取了个名字叫做LinkList

// 初始化一个单链表，因为他有头结点，所以需要为头结点开辟一片空间
bool InitLinkList(Linklist &L)
{
    L = (Node *)malloc(sizeof(Node)); // 为头结点分配空间
    if (L == NULL)
    {
        // 用于检测是否分配成功
        return false;
    }
    L->next = NULL; // 头结点之后暂时还没有节点

    return true;
}

// 判断单链表是否为空
bool Empty(Linklist &L)
{
    return (L->next == NULL);
}

// 按位序插入,在表中L的第i个位置上面插入指定元素e
bool LinkInsert(Linklist &L, int i, int e)
{
    // 找到第i-1个节点，将新节点插入其后面
    Node *p = GetNum(L, e);
    return InsertNextNode(p, e);
}

// 给定节点的后插操作
bool InsertNextNode(Node *p, int e)
{
    if (p == NULL)
    {
        return false;
    }
    Node *s = (Node *)malloc(sizeof(Node));
    if (s == NULL)
    {
        return false; // 内存分配失败
    }
    s->data = e; // 将数据e保存到节点s中
    s->next = p->next;
    p->next = s; // 将节点s连接到p之后
    return true;
}

// 指定节点的前插操作
bool InsertPriorNode(Node *p, int e)
{
    if (p == NULL)
    {
        return false;
    }
    Node *s = (Node *)malloc(sizeof(Node *));
    if (s = NULL)
    {
        return false;
    }
    s->next = p->next;
    p->next = s;       // 新节点s连到p之后
    s->data = p->data; // 将p中的元素复制到s中
    p->data = e;       // p中元素覆盖为e
    return true;
}

// 按位序删除
bool ListDelete(Linklist &L, int i, int &e)
{
    Node *p = GetNum(L, e);
    if (p == NULL) // i值不合法
    {
        return false;
    }
    if (p->next == NULL) // 第i-1个节点之后已经没有节点了
    {
        return false;
    }
    Node *q = q->next; // 让q指向被删除节点
    e = q->data;       // 用e返回节点数据值
    p->next = q->next; // 将*q节点从链中断开
    free(q);           // 释放节点的存储空间
    return true;       // 删除成功
}

// 删除指定节点
bool DeleteNode(Node *p)
{
    // 如果p是最后一个节点，有bug，可能会扣分
    if (p == NULL)
    {
        return false;
    }
    Node *q = p->next;       // 令指针*q指向p的后继指针
    p->data = p->next->data; // 和后继节点交换数据域
    p->next = q->next;       // 将q节点从链中断开
    free(q);                 // 释放后继节点的存储空间
    return true;
}

// 按位查找，返回第i个元素
Node *GetNum(Linklist L, int i)
{
    if (i < 1)
    { // 传入的参数不合法
        return NULL;
    }
    Node *p;                       // 指针p指向当前扫描到的节点
    int j = 0;                     // 当前p指向的第几个节点
    p = L;                         // L指向节点，头结点是第0个节点
    while (p != NULL && j < i - 1) // 循环找到第i个节点
    {
        p = p->next;
        j++;
    }
    return p;
}

// 按值查找
Node *LocatNum(Linklist L, int e)
{
    Node *p = L->next;
    // 从第一个节点开始查找数据域为e的节点
    while (p != NULL && p->data != e)
    {
        p = p->next;
    }
    return p;
}

// 求表的长度
int Length(Linklist L)
{
    int len = 0;
    Node *p = L;
    while (p->next != NULL)
    {
        p = p->next;
        len++;
    }
    return len;
}


//尾插法建立单链表
Linklist List_TailInsert(Linklist &L){
    //正向建立单链表
    int x;
    L=(Linklist)malloc(sizeof(Node));//建立头结点,初始化空表
    Node *s,*r=L;//r为尾指针
    scanf("%d",&x);
    while (x!=9999)//输入9999表示结束
    {
        s=(Node *)malloc(sizeof(Node));
        s->data=x;
        r->data=x;
        r=s;
        scanf("%d",&x);
    }
    r->next=NULL;//尾节点指针置空
    return L;
}

//头插法建立单链表
Linklist List_HeadInsert(Linklist &L){
    //反向建立单链表
    Node *s;
    int x;
    L=(Linklist)malloc(sizeof(Node));//建立头结点
    L->next=NULL;//初始化空表
    scanf("%d",&x);
    while (x!=9999)//输入9999表示结束
    {
        s=(Node *)malloc(sizeof(Node));
        s->data=x;
        s->next=L->next;
        L->next=s;
        scanf("%d",&x);
    }
    return L;
}

void test()
{
    Linklist L; // 创建一个单链表
    InitLinkList(L);
}
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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197

无头结点

#include <stdio.h>
#include <stdlib.h> //malloc函数所需要的
struct Node
{
    // 定义一个结构体
    int data;          // 数据域
    struct Node *next; // 指针：指向node节点的指针，叫next，此处struct意为这是一个结构体，可以省略掉
};
typedef struct Node Node;      // 将结构体Node取了个名字叫做Node
typedef struct Node *Linklist; // 为这个单链表结构取了个名字叫做LinkList

// 初始化一个单链表
bool InitLinkList(Linklist &L)
{
    L = NULL;
    // 将其置为空表，防止脏数据
    return true;
}

// 判断单链表是否为空
bool Empty(Linklist &L)
{
    return (L == NULL);
}

// 按位序插入,在表中L的第i个位置上面插入指定元素e
bool LinkInsert(Linklist &L, int i, int e)
{
    // 找到第i-1个节点，将新节点插入其后面
    // 因为不带头结点，所以插入第一个节点的操作与其他节点操作不同
    if (i == 1)
    {
        Node *s = (Node *)malloc(sizeof(Node));
        s->next = NULL;
        s->data = e;
        L = s; // 头指针指向新节点
        return true;
    }
    Node *p = GetNum(L, e);
    return InsertNextNode(p, e);
}

// 给定节点的后插操作
bool InsertNextNode(Node *p, int e)
{
    if (p == NULL)
    {
        return false;
    }
    Node *s = (Node *)malloc(sizeof(Node));
    if (s == NULL)
    {
        return false; // 内存分配失败
    }
    s->data = e; // 将数据e保存到节点s中
    s->next = p->next;
    p->next = s; // 将节点s连接到p之后
    return true;
}

// 指定节点的前插操作
bool InsertPriorNode(Node *p, int e)
{
    if (p == NULL)
    {
        return false;
    }
    Node *s = (Node *)malloc(sizeof(Node *));
    if (s = NULL)
    {
        return false;
    }
    s->next = p->next;
    p->next = s;       // 新节点s连到p之后
    s->data = p->data; // 将p中的元素复制到s中
    p->data = e;       // p中元素覆盖为e
    return true;
}

// 按位序删除
bool ListDelete(Linklist &L, int i, int &e)
{

    if (L == NULL)
    {
        return false;
    }
    if (i = 1)
    {
        e = L->data;
        Node *a = L;
        L = L->next;
        free(a);
        return true;
    }
    Node *p = GetNum(L, e); // 指针p指向当前扫描到的节点
    if (p == NULL)          // i值不合法
    {
        return false;
    }
    if (p->next == NULL) // 第i-1个节点之后已经没有节点了
    {
        return false;
    }
    Node *q = q->next; // 让q指向被删除节点
    e = q->data;       // 用e返回节点数据值
    p->next = q->next; // 将*q节点从链中断开
    free(q);           // 释放节点的存储空间
    return true;       // 删除成功
}

// 删除指定节点
bool DeleteNode(Node *p)
{
    // 如果p是最后一个节点，有bug，可能会扣分
    if (p == NULL)
    {
        return false;
    }
    Node *q = p->next;       // 令指针*q指向p的后继指针
    p->data = p->next->data; // 和后继节点交换数据域
    p->next = q->next;       // 将q节点从链中断开
    free(q);                 // 释放后继节点的存储空间
    return true;
}

// 按位查找，返回第i个元素
Node *GetNum(Linklist L, int i)
{
    Node *p;                       // 指针p指向当前扫描到的节点
    int j = 1;                     // 当前p指向的第几个节点
    p = L;                         // L指向节点，头结点是第0个节点
    while (p != NULL && j < i - 1) // 循环找到第i个节点
    {
        p = p->next;
        j++;
    }
    return p;
}

// 按值查找
Node *LocatNum(Linklist L, int e)
{
    Node *p = L->next;
    // 从第一个节点开始查找数据域为e的节点
    while (p != NULL && p->data != e)
    {
        p = p->next;
    }
    return p;
}

// 求表的长度
int Length(Linklist L)
{
    int len = 0;
    Node *p = L;
    while (p->next != NULL)
    {
        p = p->next;
        len++;
    }
    return len + 1;
}

// 头插法插入节点
bool HeadInsert(Linklist &L, int e)
{
    Node *s = (Node *)malloc(sizeof(Node));
    if (s == NULL)
    {
        return false; // 内存分配失败
    }
    s->data = e;
    s->next = L; // 将新节点s插入到链表头部
    L = s;       // 更新链表头指针
    return true;
}

// 尾插法插入节点
bool TailInsert(Linklist &L, int e)
{
    Node *s = (Node *)malloc(sizeof(Node));
    if (s == NULL)
    {
        return false; // 内存分配失败
    }
    s->data = e;
    s->next = NULL; // 尾部插入新节点时，将其next指针置空
    if (L == NULL)
    {
        L = s; // 空链表时直接将新节点作为头节点
    }
    else
    {
        Node *p = L;
        while (p->next != NULL)
        {
            p = p->next; // 找到尾节点
        }
        p->next = s; // 将新节点连接到尾节点后
    }
    return true;
}

void test()
{
    Linklist L; // 创建一个单链表
    InitLinkList(L);
}
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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210