您好,登录后才能下订单哦!
链表是一种常见的数据结构,它由一系列节点组成,每个节点包含数据和指向下一个节点的指针。与数组不同,链表的内存空间是动态分配的,因此可以灵活地增加或删除节点。本文将介绍如何使用C语言实现一个线性动态单向链表。
链表的每个节点通常包含两个部分: - 数据域:存储节点的数据。 - 指针域:指向下一个节点的指针。
在C语言中,我们可以使用结构体来定义一个节点:
struct Node {
int data; // 数据域
struct Node* next; // 指针域,指向下一个节点
};
链表的头指针指向链表的第一个节点。如果链表为空,头指针为NULL
。
struct Node* head = NULL; // 初始化头指针为空
创建一个新节点并初始化其数据域和指针域。
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("内存分配失败\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
在链表中插入节点有多种方式,常见的有: - 在链表头部插入 - 在链表尾部插入 - 在指定位置插入
将新节点插入到链表的头部,使其成为新的头节点。
void insertAtHead(int data) {
struct Node* newNode = createNode(data);
newNode->next = head;
head = newNode;
}
将新节点插入到链表的尾部。
void insertAtTail(int data) {
struct Node* newNode = createNode(data);
if (head == NULL) {
head = newNode;
return;
}
struct Node* temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
在链表的指定位置插入新节点。
void insertAtPosition(int data, int position) {
if (position < 1) {
printf("无效的位置\n");
return;
}
if (position == 1) {
insertAtHead(data);
return;
}
struct Node* newNode = createNode(data);
struct Node* temp = head;
for (int i = 1; i < position - 1 && temp != NULL; i++) {
temp = temp->next;
}
if (temp == NULL) {
printf("位置超出链表长度\n");
return;
}
newNode->next = temp->next;
temp->next = newNode;
}
删除链表中的节点也有多种方式: - 删除头节点 - 删除尾节点 - 删除指定位置的节点
删除链表的头节点。
void deleteAtHead() {
if (head == NULL) {
printf("链表为空,无法删除\n");
return;
}
struct Node* temp = head;
head = head->next;
free(temp);
}
删除链表的尾节点。
void deleteAtTail() {
if (head == NULL) {
printf("链表为空,无法删除\n");
return;
}
if (head->next == NULL) {
free(head);
head = NULL;
return;
}
struct Node* temp = head;
while (temp->next->next != NULL) {
temp = temp->next;
}
free(temp->next);
temp->next = NULL;
}
删除链表中指定位置的节点。
void deleteAtPosition(int position) {
if (head == NULL) {
printf("链表为空,无法删除\n");
return;
}
if (position < 1) {
printf("无效的位置\n");
return;
}
if (position == 1) {
deleteAtHead();
return;
}
struct Node* temp = head;
for (int i = 1; i < position - 1 && temp != NULL; i++) {
temp = temp->next;
}
if (temp == NULL || temp->next == NULL) {
printf("位置超出链表长度\n");
return;
}
struct Node* nodeToDelete = temp->next;
temp->next = temp->next->next;
free(nodeToDelete);
}
遍历链表并打印每个节点的数据。
void printList() {
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
释放链表占用的内存,防止内存泄漏。
void freeList() {
struct Node* temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp);
}
}
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Node* head = NULL;
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("内存分配失败\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
void insertAtHead(int data) {
struct Node* newNode = createNode(data);
newNode->next = head;
head = newNode;
}
void insertAtTail(int data) {
struct Node* newNode = createNode(data);
if (head == NULL) {
head = newNode;
return;
}
struct Node* temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
void insertAtPosition(int data, int position) {
if (position < 1) {
printf("无效的位置\n");
return;
}
if (position == 1) {
insertAtHead(data);
return;
}
struct Node* newNode = createNode(data);
struct Node* temp = head;
for (int i = 1; i < position - 1 && temp != NULL; i++) {
temp = temp->next;
}
if (temp == NULL) {
printf("位置超出链表长度\n");
return;
}
newNode->next = temp->next;
temp->next = newNode;
}
void deleteAtHead() {
if (head == NULL) {
printf("链表为空,无法删除\n");
return;
}
struct Node* temp = head;
head = head->next;
free(temp);
}
void deleteAtTail() {
if (head == NULL) {
printf("链表为空,无法删除\n");
return;
}
if (head->next == NULL) {
free(head);
head = NULL;
return;
}
struct Node* temp = head;
while (temp->next->next != NULL) {
temp = temp->next;
}
free(temp->next);
temp->next = NULL;
}
void deleteAtPosition(int position) {
if (head == NULL) {
printf("链表为空,无法删除\n");
return;
}
if (position < 1) {
printf("无效的位置\n");
return;
}
if (position == 1) {
deleteAtHead();
return;
}
struct Node* temp = head;
for (int i = 1; i < position - 1 && temp != NULL; i++) {
temp = temp->next;
}
if (temp == NULL || temp->next == NULL) {
printf("位置超出链表长度\n");
return;
}
struct Node* nodeToDelete = temp->next;
temp->next = temp->next->next;
free(nodeToDelete);
}
void printList() {
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
void freeList() {
struct Node* temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp);
}
}
int main() {
insertAtHead(10);
insertAtHead(20);
insertAtTail(30);
insertAtPosition(15, 2);
printList(); // 输出: 20 -> 15 -> 10 -> 30 -> NULL
deleteAtHead();
deleteAtTail();
deleteAtPosition(2);
printList(); // 输出: 15 -> 10 -> NULL
freeList();
return 0;
}
本文介绍了如何使用C语言实现一个线性动态单向链表,包括节点的创建、插入、删除、遍历和释放等操作。链表是一种灵活的数据结构,适用于需要频繁插入和删除操作的场景。通过掌握链表的基本操作,可以更好地理解和应用其他复杂的数据结构。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。