高明网站设计服务_创建软件的步骤_网络营销策略是什么_重庆seo公司

在C语言中，链表是一种常见的数据结构，用于存储一系列的元素，但不同于数组，链表中的元素在内存中不是连续存储的，而是通过指针将这些元素链接起来。链表具有动态大小的特点，可以方便地进行插入和删除操作。

链表的基本结构通常包括节点（Node）和头指针（Head Pointer）。每个节点包含两部分：一部分是存储数据的域（Data Field），另一部分是存储指向下一个节点的指针（Pointer Field）。

链表具有几个显著的特点：

1. 动态大小：链表可以根据需要动态地增加或减少节点，这使得链表在处理未知大小的数据集时非常有用。
2. 高效的插入和删除：在链表中插入或删除节点通常只需要改变相关节点的指针，而不需要移动大量的数据。
3. 内存使用：由于链表中的节点是单独分配的，因此可能存在内存碎片的问题。同时，每个节点都需要额外的指针存储空间。

链表类型

在C语言中，链表可以分为单向链表（Singly Linked List）和双向链表（Doubly Linked List）等类型。

• 单向链表：每个节点只包含一个指向下一个节点的指针。
• 双向链表：每个节点包含两个指针，一个指向下一个节点，另一个指向前一个节点。这使得在双向链表中向任意方向遍历都变得容易。

链表操作

下面是一个简单的单向链表（Singly Linked List）的实现示例：

1. 定义节点结构

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

2. 创建新节点

使用malloc或calloc等内存分配函数为节点分配内存，并初始化节点的数据域和指针域。

// 创建新节点并返回其指针  
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;  
}

3. 插入节点

在链表头部插入节点

创建一个新节点，将其指针域指向当前的头节点，然后更新头指针指向新节点。

// 在链表头部插入新节点  
void insertAtHead(struct Node** head, int data) {  struct Node* newNode = createNode(data);  newNode->next = *head;  *head = newNode;  
}

在链表尾部插入节点

遍历链表找到最后一个节点，将其指针域指向新节点。如果链表为空，则新节点成为头节点。

// 在链表尾部插入新节点  
void insertAtTail(struct Node** head, 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 insertFromBehind(struct Test *head,int data,struct Test *new)
{struct Test *p = head;while(1){if(p != NULL){if(p->data == data){new->next = p->next;p->next = new;}p = p->next;}else{break;}}
}

在指定节点前面插入节点

在指定节点前面插入节点时，我们要拿当前节点的下一个节点的数据作为判断条件，这样才能保证插入新的节点时，新的节点前面的那个节点可以指向新的节点。而新的节点是插在指定节点的前面，新的节点可以直接指向指定节点，这样链表就前后连接起来了。

struct Test* insertFromForward(struct Test *head,int data,struct Test *new)
{struct Test *p = head;if(data == p->data){new->next = p;return new;}while(p->next != NULL){if(p->next->data == data){new->next = p->next;p->next = new;return head;}else{p = p->next;}}return 0;
}

4. 删除节点

删除头部节点

更新头指针指向当前头节点的下一个节点，并释放头节点的内存。

// 删除链表头部节点  
struct Test* delteNode(struct Test* head,int data)
{struct Test *p = head;if(p->data == data){head = head->next;//      free(p);return head;}}

删除指定值的节点

遍历链表找到要删除的节点的前一个节点，然后更新其指针域跳过要删除的节点，并释放该节点的内存。

// 删除链表中第一个值为key的节点  
void deleteNode(struct Node** head, int key) {  struct Node* temp = *head;  struct Node* prev = NULL;  // 如果头节点就是要删除的节点  if (temp != NULL && temp->data == key) {  *head = temp->next;  free(temp);  return;  }  // 查找要删除的节点  while (temp != NULL && temp->data != key) {  prev = temp;  temp = temp->next;  }  // 如果没有找到  if (temp == NULL) return;  // 解除节点并释放内存  prev->next = temp->next;  free(temp);  
}

struct Test* delteNode(struct Test* head,int data)
{struct Test *p = head;//删除头节点if(p->data == data){head = head->next;//      free(p);return head;}//查找要删除的节点while(p->next != NULL){//找到后进行删除if(p->next->data == data){//struct Test *temp = p;p->next = p->next->next;//free(temp);释放配p以避免内存泄漏return head;}//没找到继续往下找p = p->next;}//遍历完整个链表找不到后返回头节点return head;
}

5. 遍历链表

从头节点开始，使用指针域依次访问每个节点，直到达到链表的末尾（即指针域为NULL的节点）。

// 打印链表中的所有元素  
void printLink(struct Test *head)
{while(1){if(head != NULL){printf("%d  ",head->data);head = head->next;}else{putchar('\n');break;}}
}

6. 释放链表内存

遍历链表，逐个释放每个节点的内存。这是防止内存泄漏的重要步骤。

// 释放链表的所有节点  
void freeList(struct Node* head) {  struct Node* temp;  while (head != NULL) {  temp = head;  head = head->next;  free(temp);  }  
}