C语言数据结构之单链表操作实例分析

C语言数据结构之单链表操作实例分析

目录

1. 引言
2. 单链表的基本概念
3. 单链表的存储结构
4. 单链表的基本操作
   • 创建单链表
   • 插入节点
   • 删除节点
   • 查找节点
   • 遍历单链表
5. 单链表的应用实例
   • 实例1：学生信息管理系统
   • 实例2：多项式相加
6. 单链表的优缺点
7. 总结

引言

在计算机科学中，数据结构是组织和存储数据的方式，以便能够高效地访问和修改数据。单链表是一种常见的数据结构，广泛应用于各种算法和程序中。本文将详细介绍单链表的基本概念、存储结构、基本操作以及应用实例，并通过C语言代码进行实例分析。

单链表的基本概念

单链表（Singly Linked List）是一种线性数据结构，由一系列节点组成，每个节点包含两个部分：数据域和指针域。数据域用于存储数据，指针域用于指向下一个节点。单链表的特点是每个节点只有一个指向下一个节点的指针，因此只能单向遍历。

单链表的存储结构

单链表的存储结构可以用C语言中的结构体来表示：

struct Node { int data; // 数据域 struct Node* next; // 指针域，指向下一个节点 }; 

在这个结构体中，data表示节点存储的数据，next是指向下一个节点的指针。

单链表的基本操作

创建单链表

创建单链表的过程包括初始化头节点和添加新节点。头节点是单链表的起点，通常不存储实际数据。

struct Node* createLinkedList(int data) { struct Node* head = (struct Node*)malloc(sizeof(struct Node)); head->data = data; head->next = NULL; return head; } 

插入节点

在单链表中插入节点有多种方式，包括在链表头部插入、在链表尾部插入以及在指定位置插入。

在链表头部插入节点

void insertAtHead(struct Node** head, int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; newNode->next = *head; *head = newNode; } 

在链表尾部插入节点

void insertAtTail(struct Node** head, int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; newNode->next = NULL; if (*head == NULL) { *head = newNode; return; } struct Node* temp = *head; while (temp->next != NULL) { temp = temp->next; } temp->next = newNode; } 

在指定位置插入节点

void insertAtPosition(struct Node** head, int data, int position) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; if (position == 1) { newNode->next = *head; *head = newNode; return; } struct Node* temp = *head; for (int i = 1; i < position - 1 && temp != NULL; i++) { temp = temp->next; } if (temp == NULL) { printf("Position out of range\n"); return; } newNode->next = temp->next; temp->next = newNode; } 

删除节点

删除节点的操作包括删除头节点、删除尾节点以及删除指定位置的节点。

删除头节点

void deleteAtHead(struct Node** head) { if (*head == NULL) { printf("List is empty\n"); return; } struct Node* temp = *head; *head = (*head)->next; free(temp); } 

删除尾节点

void deleteAtTail(struct Node** head) { if (*head == NULL) { printf("List is empty\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(struct Node** head, int position) { if (*head == NULL) { printf("List is empty\n"); return; } struct Node* temp = *head; if (position == 1) { *head = temp->next; free(temp); return; } for (int i = 1; i < position - 1 && temp != NULL; i++) { temp = temp->next; } if (temp == NULL || temp->next == NULL) { printf("Position out of range\n"); return; } struct Node* nodeToDelete = temp->next; temp->next = nodeToDelete->next; free(nodeToDelete); } 

查找节点

查找节点可以通过遍历链表来实现，找到指定数据的节点并返回其位置。

int searchNode(struct Node* head, int data) { struct Node* temp = head; int position = 1; while (temp != NULL) { if (temp->data == data) { return position; } temp = temp->next; position++; } return -1; // 未找到 } 

遍历单链表

遍历单链表是指依次访问链表中的每个节点，并输出其数据。

void printLinkedList(struct Node* head) { struct Node* temp = head; while (temp != NULL) { printf("%d -> ", temp->data); temp = temp->next; } printf("NULL\n"); } 

单链表的应用实例

实例1：学生信息管理系统

假设我们需要实现一个简单的学生信息管理系统，使用单链表来存储学生的信息。每个学生的信息包括学号、姓名和成绩。

struct Student { int id; char name[50]; float grade; struct Student* next; }; void insertStudent(struct Student** head, int id, char name[], float grade) { struct Student* newStudent = (struct Student*)malloc(sizeof(struct Student)); newStudent->id = id; strcpy(newStudent->name, name); newStudent->grade = grade; newStudent->next = *head; *head = newStudent; } void printStudents(struct Student* head) { struct Student* temp = head; while (temp != NULL) { printf("ID: %d, Name: %s, Grade: %.2f\n", temp->id, temp->name, temp->grade); temp = temp->next; } } int main() { struct Student* head = NULL; insertStudent(&head, 1, "Alice", 95.5); insertStudent(&head, 2, "Bob", 88.0); insertStudent(&head, 3, "Charlie", 92.3); printStudents(head); return 0; } 

实例2：多项式相加

单链表可以用于表示多项式，每个节点存储多项式的一项（系数和指数）。我们可以通过遍历两个多项式链表来实现多项式相加。

struct Term { int coefficient; int exponent; struct Term* next; }; void insertTerm(struct Term** head, int coefficient, int exponent) { struct Term* newTerm = (struct Term*)malloc(sizeof(struct Term)); newTerm->coefficient = coefficient; newTerm->exponent = exponent; newTerm->next = *head; *head = newTerm; } struct Term* addPolynomials(struct Term* poly1, struct Term* poly2) { struct Term* result = NULL; while (poly1 != NULL && poly2 != NULL) { if (poly1->exponent > poly2->exponent) { insertTerm(&result, poly1->coefficient, poly1->exponent); poly1 = poly1->next; } else if (poly1->exponent < poly2->exponent) { insertTerm(&result, poly2->coefficient, poly2->exponent); poly2 = poly2->next; } else { int sum = poly1->coefficient + poly2->coefficient; if (sum != 0) { insertTerm(&result, sum, poly1->exponent); } poly1 = poly1->next; poly2 = poly2->next; } } while (poly1 != NULL) { insertTerm(&result, poly1->coefficient, poly1->exponent); poly1 = poly1->next; } while (poly2 != NULL) { insertTerm(&result, poly2->coefficient, poly2->exponent); poly2 = poly2->next; } return result; } void printPolynomial(struct Term* head) { struct Term* temp = head; while (temp != NULL) { printf("%dx^%d", temp->coefficient, temp->exponent); if (temp->next != NULL) { printf(" + "); } temp = temp->next; } printf("\n"); } int main() { struct Term* poly1 = NULL; insertTerm(&poly1, 5, 2); insertTerm(&poly1, 4, 1); insertTerm(&poly1, 2, 0); struct Term* poly2 = NULL; insertTerm(&poly2, 3, 1); insertTerm(&poly2, 1, 0); struct Term* result = addPolynomials(poly1, poly2); printPolynomial(result); return 0; } 

单链表的优缺点

优点

1. 动态内存分配：单链表可以根据需要动态分配内存，不需要预先分配固定大小的内存空间。
2. 插入和删除操作高效：在单链表中插入和删除节点的操作时间复杂度为O(1)，特别是在链表头部进行操作时。
3. 灵活性：单链表可以轻松地扩展和缩减，适用于频繁插入和删除操作的场景。

缺点

1. 访问效率低：单链表只能单向遍历，访问某个节点需要从头节点开始依次遍历，时间复杂度为O(n)。
2. 内存开销：每个节点需要额外的指针域来存储下一个节点的地址，增加了内存开销。
3. 不支持随机访问：单链表不支持像数组那样的随机访问，无法直接通过索引访问某个节点。

总结

单链表是一种简单而强大的数据结构，适用于需要频繁插入和删除操作的场景。通过本文的介绍，我们了解了单链表的基本概念、存储结构、基本操作以及应用实例。虽然单链表在某些方面存在不足，但其灵活性和动态内存分配的特点使其在许多应用中仍然具有重要价值。掌握单链表的操作和应用，对于理解和实现更复杂的数据结构和算法具有重要意义。