当前位置：首页 > news >正文

c 语言链表的简单使用

news 2024/11/6 6:39:53

一、链表介绍

在 C 语言中，链表是一种常用的数据结构，用于动态地存储数据。链表中的每个元素称为节点，每个节点包含数据部分和指向下一个节点的指针。

1.1 链表的基本概念

定义：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
组成部分：链表由一系列节点（链表中每一个元素称为节点）组成，节点可以在运行时动态生成。每个节点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域。

1.2 链表的类型

单向链表：每个节点只有一个指向下一个节点的指针。
双向链表：每个节点有两个指针，一个指向下一个节点，一个指向上一个节点。
循环链表：链表的尾节点指向链表的头节点，形成一个环。

1.3 链表的基本操作

节点创建：为链表分配新的节点，并初始化节点的数据和指针。
节点插入：将新节点插入到链表的指定位置，包括在头部插入、在尾部插入和在中间插入。
节点删除：从链表中删除指定节点，需要调整相关节点的指针。
查找节点：在链表中查找具有指定值的节点，需要遍历链表。
链表遍历：从头节点开始，逐个访问链表中的每个节点，直到到达链表末尾。
链表长度计算：遍历链表，同时维护一个计数器来记录访问的节点数。
链表反转：通过改变节点之间的指针方向来实现链表的反转。
链表排序：使用排序算法（如归并排序、插入排序等）对链表进行排序。
链表合并：将两个或多个链表合并成一个链表。
链表清空：删除链表中的所有节点，并释放它们所占用的内存。

1.4链表的优缺点

优点：链表克服了数组需要预先知道数据大小的缺点，可以充分利用计算机内存空间，实现灵活的内存动态管理。链表允许插入和移除表上任意位置上的节点，但不允许随机存取。
缺点：链表失去了数组随机读取的优点，同时链表由于增加了节点的指针域，空间开销比较大。

二、单链表的实现

链表的基本实现，包括创建节点、添加节点、打印链表和释放链表内存。

2.1 定义节点结构

定义一个节点结构，每个节点包含一个整数数据和一个指向下一个节点的指针。

#include <stdio.h>  
#include <stdlib.h>  // 定义节点结构  
struct Node{  int data;  struct Node* next;  
};

2.2 创建新节点

定义一个函数来创建新节点

// 创建新节点  
struct Node* createNode(int data){  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));  if (!newNode){  printf("内存分配失败\n");  exit(1);  }  newNode->data = data;  newNode->next = NULL;  return newNode;  
}

2.3 添加节点到链表

定义一个函数来在链表的头部或尾部添加新节点。比如在头部添加节点。

// 在链表头部添加节点  
void appendNodeAtHead(struct Node** head, int data) 
{  struct Node* newNode = createNode(data);  newNode->next = *head;  *head = newNode;  
}

2.4 打印链表

定义一个函数来打印链表中的所有节点

// 打印链表  
void printList(struct Node* head) 
{  struct Node* temp = head;  while (temp != NULL) {  printf("%d -> ", temp->data);  temp = temp->next;  }  printf("NULL\n");  
}

2.5 释放链表内存

定义一个函数来释放链表占用的内存，防止内存泄漏。

// 释放链表内存  
void freeList(struct Node* head) 
{  struct Node* temp;  while (head != NULL) {  temp = head;  head = head->next;  free(temp);  }  
}

三、测试代码

编写代码，创建一个链表，并在链表的头部依次添加 10、20 和 30 三个节点，然后打印链表内容，最后释放链表占用的内存。
示意图：
在这里插入图片描述

#include <stdio.h>  
#include <stdlib.h>  // 定义节点结构  
struct Node 
{  int data;  struct Node* next;  
};  // 创建新节点  
struct Node* createNode(int data) 
{  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));  if (!newNode) {  printf("内存分配失败\n");  exit(1);  }  newNode->data = data;  newNode->next = NULL;  return newNode;  
}  // 在链表头部添加节点  
void appendNodeAtHead(struct Node** head, int data) 
{  struct Node* newNode = createNode(data);  newNode->next = *head;  *head = newNode;  
}  // 打印链表  
void printList(struct Node* head) 
{  struct Node* temp = head;  while (temp != NULL) {  printf("%d -> ", temp->data);  temp = temp->next;  }  printf("NULL\n");  
}  // 释放链表内存  
void freeList(struct Node* head) 
{  struct Node* temp;  while (head != NULL) {  temp = head;  head = head->next;  free(temp);  }  
}  int main() 
{  struct Node* head = NULL;  // 添加节点到链表  appendNodeAtHead(&head, 10);  appendNodeAtHead(&head, 20);  appendNodeAtHead(&head, 30);  // 打印链表  printList(head);  // 释放链表内存  freeList(head);  return 0;  
}

在这里插入图片描述