您现在的位置是:首页 >技术交流 >C语言单链表网站首页技术交流
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;
}