详解C语言之单链表
什么是单链表
单链表是一种数据结构，将数据存储在一系列的节点(Node)中。每个节点包含两部分：数据(Datum)和指向下一个节点的指针(Pointer)。节点之间通过指针连接起来，形成链表。单链表只能从头节点一直访问到尾节点，不能随机访问。
单链表的操作
单链表的常见操作有以下几个：
链表的创建
创建一个链表需要两个步骤：先创建头节点，再通过头节点逐个添加下一个节点。
typedef struct node *ptr;
typedef struct node {
int data; //数据
ptr next; //指向下一个节点的指针
} Node;
ptr create_list(int n) {
ptr head; //头节点
ptr tail; //尾节点
int data;
//创建头节点
head = (ptr)malloc(sizeof(Node));
if (head == NULL) {
printf("Memory allocation failed.\n");
return NULL;
}
head->data = 0;
head->next = NULL;
//逐个添加节点
tail = head;
while (n--) {
printf("Enter data: ");
scanf("%d", &data);
//创建新节点
ptr new_node = (ptr)malloc(sizeof(Node));
if (new_node == NULL) {
printf("Memory allocation failed.\n");
return NULL;
}
new_node->data = data;
new_node->next = NULL;
//添加节点到链表尾部
tail->next = new_node;
tail = new_node;
head->data++; //节点数+1
}
return head;
}
链表的输出
输出链表需要遍历链表中的每一个节点。
void print_list(ptr head) {
ptr p;
p = head->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
链表的插入
插入操作有两种情况：在链表的头部插入一个新节点和在链表的中间插入一个新节点。
void insert_first(ptr head, int data) {
//创建新节点
ptr new_node = (ptr)malloc(sizeof(Node));
if (new_node == NULL) {
printf("Memory allocation failed.\n");
return;
}
new_node->data = data;
new_node->next = head->next;
//插入新节点到头部
head->next = new_node;
head->data++; //节点数+1
}
void insert_node(ptr head, int x, int data) {
int i;
ptr p;
p = head->next;
for (i = 1; i < x; i++) {
p = p->next;
if (p == NULL) {
printf("Invalid position.\n");
return;
}
}
//创建新节点
ptr new_node = (ptr)malloc(sizeof(Node));
if (new_node == NULL) {
printf("Memory allocation failed.\n");
return;
}
new_node->data = data;
new_node->next = p->next;
//插入新节点到中间
p->next = new_node;
head->data++; //节点数+1
}
链表的删除
删除操作也分为两种情况：从链表的头部删除一个节点和从链表的中间删除一个节点。
void delete_first(ptr head) {
ptr p;
if (head->next == NULL) {
printf("List is already empty.\n");
return;
}
p = head->next;
head->next = p->next;
free(p);
head->data--; //节点数-1
}
void delete_node(ptr head, int x) {
int i;
ptr p, q;
p = head->next;
for (i = 1; i < x; i++) {
q = p;
p = p->next;
if (p == NULL) {
printf("Invalid position.\n");
return;
}
}
q->next = p->next;
free(p);
head->data--; //节点数-1
}
示例说明
示例一
用户需要输入5个整数创建一个链表，然后依次输出链表中的内容。最后在链表的第3个位置插入一个新节点，然后删除链表的第4个节点。
#include <stdio.h>
#include <stdlib.h>
typedef struct node *ptr;
typedef struct node {
int data; //数据
ptr next; //指向下一个节点的指针
} Node;
ptr create_list(int n) {
ptr head; //头节点
ptr tail; //尾节点
int data;
//创建头节点
head = (ptr)malloc(sizeof(Node));
if (head == NULL) {
printf("Memory allocation failed.\n");
return NULL;
}
head->data = 0;
head->next = NULL;
//逐个添加节点
tail = head;
while (n--) {
printf("Enter data: ");
scanf("%d", &data);
//创建新节点
ptr new_node = (ptr)malloc(sizeof(Node));
if (new_node == NULL) {
printf("Memory allocation failed.\n");
return NULL;
}
new_node->data = data;
new_node->next = NULL;
//添加节点到链表尾部
tail->next = new_node;
tail = new_node;
head->data++; //节点数+1
}
return head;
}
void print_list(ptr head) {
ptr p;
p = head->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
void insert_node(ptr head, int x, int data) {
int i;
ptr p;
p = head->next;
for (i = 1; i < x; i++) {
p = p->next;
if (p == NULL) {
printf("Invalid position.\n");
return;
}
}
//创建新节点
ptr new_node = (ptr)malloc(sizeof(Node));
if (new_node == NULL) {
printf("Memory allocation failed.\n");
return;
}
new_node->data = data;
new_node->next = p->next;
//插入新节点到中间
p->next = new_node;
head->data++; //节点数+1
}
void delete_node(ptr head, int x) {
int i;
ptr p, q;
p = head->next;
for (i = 1; i < x; i++) {
q = p;
p = p->next;
if (p == NULL) {
printf("Invalid position.\n");
return;
}
}
q->next = p->next;
free(p);
head->data--; //节点数-1
}
int main() {
ptr list_head;
list_head = create_list(5);
printf("List content: ");
print_list(list_head);
insert_node(list_head, 3, 10);
printf("List content after insertion: ");
print_list(list_head);
delete_node(list_head, 4);
printf("List content after deletion: ");
print_list(list_head);
return 0;
}
输出结果：
Enter data: 1
Enter data: 2
Enter data: 3
Enter data: 4
Enter data: 5
List content: 1 2 3 4 5
List content after insertion: 1 2 3 10 4 5
List content after deletion: 1 2 3 10 5
示例二
程序先创建一个空链表，然后依次在链表的头部插入5个新节点，最后逐个删除链表中的所有节点。
#include <stdio.h>
#include <stdlib.h>
typedef struct node *ptr;
typedef struct node {
int data; //数据
ptr next; //指向下一个节点的指针
} Node;
ptr create_list(int n) {
ptr head; //头节点
ptr tail; //尾节点
int data;
//创建头节点
head = (ptr)malloc(sizeof(Node));
if (head == NULL) {
printf("Memory allocation failed.\n");
return NULL;
}
head->data = 0;
head->next = NULL;
//逐个添加节点
tail = head;
while (n--) {
printf("Enter data: ");
scanf("%d", &data);
//创建新节点
ptr new_node = (ptr)malloc(sizeof(Node));
if (new_node == NULL) {
printf("Memory allocation failed.\n");
return NULL;
}
new_node->data = data;
new_node->next = NULL;
//添加节点到链表尾部
tail->next = new_node;
tail = new_node;
head->data++; //节点数+1
}
return head;
}
void print_list(ptr head) {
ptr p;
p = head->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
void insert_first(ptr head, int data) {
//创建新节点
ptr new_node = (ptr)malloc(sizeof(Node));
if (new_node == NULL) {
printf("Memory allocation failed.\n");
return;
}
new_node->data = data;
new_node->next = head->next;
//插入新节点到头部
head->next = new_node;
head->data++; //节点数+1
}
void delete_first(ptr head) {
ptr p;
if (head->next == NULL) {
printf("List is already empty.\n");
return;
}
p = head->next;
head->next = p->next;
free(p);
head->data--; //节点数-1
}
int main() {
ptr list_head;
list_head = create_list(0);
insert_first(list_head, 1);
insert_first(list_head, 2);
insert_first(list_head, 3);
insert_first(list_head, 4);
insert_first(list_head, 5);
printf("List content after insertions: ");
print_list(list_head);
while (list_head->next != NULL) {
delete_first(list_head);
printf("List content after deletion: ");
print_list(list_head);
}
return 0;
}
输出结果：
Enter data: 1
Enter data: 2
Enter data: 3
Enter data: 4
Enter data: 5
List content after insertions: 5 4 3 2 1
List content after deletion: 4 3 2 1
List content after deletion: 3 2 1
List content after deletion: 2 1
List content after deletion: 1
List content after deletion:
本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：详解C语言之单链表 - Python技术站
微信扫一扫 
支付宝扫一扫 