【数据结构】线性表-单链表

server/2025/1/19 1:58:42/

线性表-单链表

  • 顺序表
  • 链表存储结构
  • 单链表
    • 初始化
    • 插入数据
      • 头插法
      • 尾插法
      • 在指定位置插入数据
    • 遍历链表
    • 删除节点
    • 获取链表长度
    • 释放链表

顺序表

上一篇文章

链表介绍：
在这里插入图片描述

  • 线性表链式存储结构的特点是：用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的，也可以是不连续的)。

  • 为了表示每个数据元素 Ai 与其直接后继数据元素 Ai+1之间的逻辑关系，对数据元素Ai来说，除了其本身的信息之外，还需要存储一个指示其直接后继的信息(直接后继的存储位置)。这两部分信息组成数据元素Ai的存储映像，称为节点(node)。

  • 结点包括两个域:其中存储数据元素信息的称为数据域;存储直接后继存储位置有域称为指针域。指针域中存储的信息称作指针或链。

  • n个结点 [ A(1 ≤ i ≤ n)的存储映像 ] 链接成一个链表，即为线性表(A1,A2,…,An)。

链表存储结构

在这里插入图片描述

#include <stdio.h>
#include <stdlib.h>typedef int ElemType; // 定义元素类型typedef struct node // 定义节点类型
{ElemType data;struct node *next;
} Node;

单链表

初始化

注意：
头节点：最开始的头节点
第一个节点：头节点指向的节点叫做第一个节点

在这里插入图片描述

对照这个图，完成单链表的初始化

#include <stdio.h>
#include <stdlib.h>typedef int ElemType; // 定义元素类型typedef struct node // 定义节点类型
{ElemType data;struct node *next;
} Node;/* 初始化一个单链表-造一个头节点 */
Node *InitList()
{Node *head = (Node *)malloc(sizeof(Node)); // 为头节点分配内存head->data = 0;                            // 头节点的数据域为0head->next = NULL;                         // 头节点的指针域为空return head;                               // 返回头节点
}int main()
{Node *list = InitList(); // 初始化一个单链表printf("Hello World!\n");return 0;
}

插入数据

链表的插入数据有两种方式：头插法和尾插法

头插法

每次都在头节点后面插入数据

第一次插入数据
在这里插入图片描述

第二次插入数据

在这里插入图片描述
可以看到：每次都在头节点后面插入数据

讲解视频，演示动画：【《数据结构（C 语言描述）》也许是全站最良心最通俗易懂最好看的数据结构课（最迟每周五更新~~）】 【精准空降到 1:31:50】 https://www.bilibili.com/video/BV1tNpbekEht/?p=3&share_source=copy_web&vd_source=8af85e60c2df9af1f0fd23935753a933&t=5510

头插法的步骤：

  1. 创建一个新的节点
  2. 在新节点的数据域存入数据e
  3. 新节点的指针域指向头节点的下一个节点(把L的NULL复制给新节点)
  4. 头节点的指针域指向新节点
/*单链表 - 头插法*/
int InsertHead(Node *L, ElemType e)
{Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点p->data = e;                            // 在新节点的数据域存入数据ep->next = L->next;                      // 新节点的指针域指向头节点的下一个节点(把L的NULL复制给新节点)L->next = p;                            // 头节点的指针域指向新节点return 1;                               // 返回1表示成功
}

如果后面已经有了数据，那么头插法的演示效果如下，先让新节点指向第一个节点，再让头节点指向新节点（这样就能防止后面的数据丢失）

在这里插入图片描述

  • 对比：顺序表的插入是在数组里插入，每个元素都往后移动，链表的插入不是这样的，只改变节点之间的指向关系即可实现！！！

单链表：单个方向的链表
双向链表：知道下一个，也知道上一个
循环链表：构成一个环的链表

尾插法

找到尾NULL，尾节点地址，根据这个地址再插入数据。

在这里插入图片描述

/* 单链表 - 尾插法 */
// 获取尾节点地址
Node *GetTail(Node *List)
{Node *p = List;         // 从头节点开始遍历while (p->next != NULL) // 遍历到链表末尾{p = p->next; // 移动到下一个节点}return p; // 返回尾节点
}
// 尾插法插入数据
Node *InsertTail(Node *tail, ElemType e)
{Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点p->data = e;                            // 在新节点的数据域存入数据etail->next = p;                         // 尾节点的指针域指向新节点p->next = NULL;                         // 新节点的指针域为空return p;                               // 返回新的尾节点
}

完整的尾插法代码

#include <stdio.h>
#include <stdlib.h>typedef int ElemType; // 定义元素类型typedef struct node // 定义节点类型
{ElemType data;struct node *next;
} Node;/* 初始化一个单链表-造一个头节点 */
Node *InitList()
{Node *head = (Node *)malloc(sizeof(Node)); // 为头节点分配内存head->data = 0;                            // 头节点的数据域为0head->next = NULL;                         // 头节点的指针域为空return head;                               // 返回头节点
}
/*单链表 - 头插法*/
int InsertHead(Node *L, ElemType e)
{Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点p->data = e;                            // 在新节点的数据域存入数据ep->next = L->next;                      // 新节点的指针域指向头节点的下一个节点(把L的NULL复制给新节点)L->next = p;                            // 头节点的指针域指向新节点return 1;                               // 返回1表示成功
}
/* 单链表 - 遍历 */
void TraverseList(Node *L)
{Node *p = L->next; // 从头节点的下一个节点开始遍历while (p != NULL)  // 遍历到链表末尾{printf("%d ", p->data); // 输出节点的数据域p = p->next;            // 移动到下一个节点}printf("\n"); // 换行
}/* 单链表 - 尾插法 */
// 获取尾节点地址
Node *GetTail(Node *List)
{Node *p = List;         // 从头节点开始遍历while (p->next != NULL) // 遍历到链表末尾{p = p->next; // 移动到下一个节点}return p; // 返回尾节点
}
// 尾插法插入数据
Node *InsertTail(Node *tail, ElemType e)
{Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点p->data = e;                            // 在新节点的数据域存入数据etail->next = p;                         // 尾节点的指针域指向新节点p->next = NULL;                         // 新节点的指针域为空return p;                               // 返回新的尾节点
}int main()
{Node *list = InitList(); // 初始化一个单链表printf("头插法插入数据1 2 3\n");InsertHead(list, 1); // 头插法插入数据1InsertHead(list, 2); // 头插法插入数据2InsertHead(list, 3); // 头插法插入数据3printf("遍历-链表中的元素为：");TraverseList(list); // 遍历单链表printf("\n");       // 换行printf("\n尾插法插入数据4 5 6\n");Node *tail = GetTail(list); // 获取尾节点地址tail = InsertTail(tail, 4); // 尾插法插入数据4tail = InsertTail(tail, 5); // 尾插法插入数据5tail = InsertTail(tail, 6); // 尾插法插入数据6printf("遍历-链表中的元素为：");TraverseList(list); // 遍历单链表return 0;
}

输出结果如下：

头插法插入数据1 2 3
遍历-链表中的元素为：3 2 1尾插法插入数据4 5 6
遍历-链表中的元素为：3 2 1 4 5 6请按任意键继续. . .

可以看到尾插法的数据是正确的！

在指定位置插入数据

在70和80中间插入一个new

在这里插入图片描述
一定要注意这个顺序，不能颠倒

*** @Description:单链表 - 在指定位置插入数据* @param {Node} *L     单链表的头节点* @param {int} pos     位置* @param {ElemType} e  插入的数据* @return {*}*/
int InsertPosNode(Node *L, int pos, ElemType e)
{// 用来保存插入位置的前驱节点Node *p = L; // 从头节点开始遍历int i = 0;// 遍历链表-找到插入位置的前驱节点while (i < pos - 1) // 遍历到插入位置的前驱节点{p = p->next; // 移动到下一个节点i++;if (p == NULL) // 判断是否到达链表末尾{printf("插入位置不合法\n");return 0;}}Node *newnode = (Node *)malloc(sizeof(Node)); // 创建一个新的节点newnode->data = e;                            // 在新节点的数据域存入数据enewnode->next = p->next;                      // 新节点的指针域指向插入位置的前驱节点的下一个节点p->next = newnode;                            // 插入位置的前驱节点的指针域指向新节点return 1;
}

完整的演示代码：

#include <stdio.h>
#include <stdlib.h>typedef int ElemType; // 定义元素类型typedef struct node // 定义节点类型
{ElemType data;struct node *next;
} Node;/* 初始化一个单链表-造一个头节点 */
Node *InitList()
{Node *head = (Node *)malloc(sizeof(Node)); // 为头节点分配内存head->data = 0;                            // 头节点的数据域为0head->next = NULL;                         // 头节点的指针域为空return head;                               // 返回头节点
}
/*单链表 - 头插法*/
int InsertHead(Node *L, ElemType e)
{Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点p->data = e;                            // 在新节点的数据域存入数据ep->next = L->next;                      // 新节点的指针域指向头节点的下一个节点(把L的NULL复制给新节点)L->next = p;                            // 头节点的指针域指向新节点return 1;                               // 返回1表示成功
}
/* 单链表 - 遍历 */
void TraverseList(Node *L)
{Node *p = L->next; // 从头节点的下一个节点开始遍历while (p != NULL)  // 遍历到链表末尾{printf("%d ", p->data); // 输出节点的数据域p = p->next;            // 移动到下一个节点}printf("\n"); // 换行
}/* 单链表 - 尾插法 */
// 获取尾节点地址
Node *GetTail(Node *List)
{Node *p = List;         // 从头节点开始遍历while (p->next != NULL) // 遍历到链表末尾{p = p->next; // 移动到下一个节点}return p; // 返回尾节点
}/*** @Description:单链表 - 尾插法插入数据* @param {Node} *tail   尾节点* @param {ElemType} e   插入的数据* @return {*}           返回新的尾节点*/
Node *InsertTail(Node *tail, ElemType e)
{Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点p->data = e;                            // 在新节点的数据域存入数据etail->next = p;                         // 尾节点的指针域指向新节点p->next = NULL;                         // 新节点的指针域为空return p;                               // 返回新的尾节点
}/*** @Description:单链表 - 在指定位置插入数据* @param {Node} *L     单链表的头节点* @param {int} pos     位置* @param {ElemType} e  插入的数据* @return {*}*/
int InsertPosNode(Node *L, int pos, ElemType e)
{// 用来保存插入位置的前驱节点Node *p = L; // 从头节点开始遍历int i = 0;// 遍历链表-找到插入位置的前驱节点while (i < pos - 1) // 遍历到插入位置的前驱节点{p = p->next; // 移动到下一个节点i++;if (p == NULL) // 判断是否到达链表末尾{printf("插入位置不合法\n");return 0;}}Node *newnode = (Node *)malloc(sizeof(Node)); // 创建一个新的节点newnode->data = e;                            // 在新节点的数据域存入数据enewnode->next = p->next;                      // 新节点的指针域指向插入位置的前驱节点的下一个节点p->next = newnode;                            // 插入位置的前驱节点的指针域指向新节点return 1;
}int main()
{Node *list = InitList(); // 初始化一个单链表printf("头插法插入数据1 2 3\n");InsertHead(list, 1); // 头插法插入数据1InsertHead(list, 2); // 头插法插入数据2InsertHead(list, 3); // 头插法插入数据3printf("遍历-链表中的元素为：");TraverseList(list); // 遍历单链表printf("\n");       // 换行printf("\n尾插法插入数据4 5 6\n");Node *tail = GetTail(list); // 获取尾节点地址tail = InsertTail(tail, 4); // 尾插法插入数据4tail = InsertTail(tail, 5); // 尾插法插入数据5tail = InsertTail(tail, 6); // 尾插法插入数据6printf("遍历-链表中的元素为：");TraverseList(list); // 遍历单链表printf("\n在指定位置3插入数据7\n");InsertPosNode(list, 3, 7); // 在指定位置3插入数据7printf("遍历-链表中的元素为：");TraverseList(list); // 遍历单链表return 0;
}

输出结果

头插法插入数据1 2 3
遍历-链表中的元素为：3 2 1尾插法插入数据4 5 6
遍历-链表中的元素为：3 2 1 4 5 6在指定位置3插入数据7
遍历-链表中的元素为：3 2 7 1 4 5 6请按任意键继续. . .

在指定位置3插入数据7，插入数据成功！

遍历链表

传入头节点的下一个节点，然后再while循环里遍历，直到指向NULL为止，输出链表的数据域内容即可

/* 单链表 - 遍历 */
void TraverseList(Node *L)
{Node *p = L->next; // 从头节点的下一个节点开始遍历while (p != NULL)  // 遍历到链表末尾{printf("%d ", p->data); // 输出节点的数据域p = p->next;            // 移动到下一个节点}printf("\n"); // 换行
}

完整代码如下：

#include <stdio.h>
#include <stdlib.h>typedef int ElemType; // 定义元素类型typedef struct node // 定义节点类型
{ElemType data;struct node *next;
} Node;/* 初始化一个单链表-造一个头节点 */
Node *InitList()
{Node *head = (Node *)malloc(sizeof(Node)); // 为头节点分配内存head->data = 0;                            // 头节点的数据域为0head->next = NULL;                         // 头节点的指针域为空return head;                               // 返回头节点
}
/*单链表 - 头插法*/
int InsertHead(Node *L, ElemType e)
{Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点p->data = e;                            // 在新节点的数据域存入数据ep->next = L->next;                      // 新节点的指针域指向头节点的下一个节点(把L的NULL复制给新节点)L->next = p;                            // 头节点的指针域指向新节点return 1;                               // 返回1表示成功
}
/* 单链表 - 遍历 */
void TraverseList(Node *L)
{Node *p = L->next; // 从头节点的下一个节点开始遍历while (p != NULL)  // 遍历到链表末尾{printf("%d ", p->data); // 输出节点的数据域p = p->next;            // 移动到下一个节点}printf("\n"); // 换行
}int main()
{Node *list = InitList(); // 初始化一个单链表InsertHead(list, 1); // 头插法插入数据1InsertHead(list, 2); // 头插法插入数据2InsertHead(list, 3); // 头插法插入数据3printf("遍历-链表中的元素为：");TraverseList(list); // 遍历单链表return 0;
}

输出：

遍历-链表中的元素为：3 2 1请按任意键继续. . .

按照头插法，依次插入 1 2 3，遍历链表输出 3 2 1，这是正确的！

删除节点

找到被删除节点的前驱节点p
用指针q记录被删除的节点
通过改变p的后继节点实现删除
释放删除节点的空间

删除操作：

/*** @Description:单链表 - 删除指定位置的节点* @param {Node} *L 单链表的头节点* @param {int} pos 位置* @return {*}       返回1表示成功*/
int DeletePosNode(Node *L, int pos)
{// 用来保存删除位置的前驱节点Node *p = L; // 从头节点开始遍历int i = 0;// 遍历链表-找到删除节点的前驱节点while (i < pos - 1) // 遍历到删除位置的前驱节点{p = p->next; // 移动到下一个节点i++;if (p == NULL) // 判断是否到达链表末尾{printf("删除位置不合法\n");return 0;}}if (p->next == NULL) // 判断删除位置是否合法{printf("删除位置不合法\n");return 0;}Node *q = p->next; // 保存要删除的节点的地址p->next = q->next; // 删除节点的前驱节点的指针域 指向 删除节点的下一个节点free(q);           // 释放删除节点的内存return 1; // 返回1表示成功
}

完整的删除节点代码：

#include <stdio.h>
#include <stdlib.h>typedef int ElemType; // 定义元素类型typedef struct node // 定义节点类型
{ElemType data;struct node *next;
} Node;/* 初始化一个单链表-造一个头节点 */
Node *InitList()
{Node *head = (Node *)malloc(sizeof(Node)); // 为头节点分配内存head->data = 0;                            // 头节点的数据域为0head->next = NULL;                         // 头节点的指针域为空return head;                               // 返回头节点
}
/*单链表 - 头插法*/
int InsertHead(Node *L, ElemType e)
{Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点p->data = e;                            // 在新节点的数据域存入数据ep->next = L->next;                      // 新节点的指针域指向头节点的下一个节点(把L的NULL复制给新节点)L->next = p;                            // 头节点的指针域指向新节点return 1;                               // 返回1表示成功
}
/* 单链表 - 遍历 */
void TraverseList(Node *L)
{Node *p = L->next; // 从头节点的下一个节点开始遍历while (p != NULL)  // 遍历到链表末尾{printf("%d ", p->data); // 输出节点的数据域p = p->next;            // 移动到下一个节点}printf("\n"); // 换行
}/* 单链表 - 尾插法 */
// 获取尾节点地址
Node *GetTail(Node *List)
{Node *p = List;         // 从头节点开始遍历while (p->next != NULL) // 遍历到链表末尾{p = p->next; // 移动到下一个节点}return p; // 返回尾节点
}/*** @Description:单链表 - 尾插法插入数据* @param {Node} *tail   尾节点* @param {ElemType} e   插入的数据* @return {*}           返回新的尾节点*/
Node *InsertTail(Node *tail, ElemType e)
{Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点p->data = e;                            // 在新节点的数据域存入数据etail->next = p;                         // 尾节点的指针域指向新节点p->next = NULL;                         // 新节点的指针域为空return p;                               // 返回新的尾节点
}/*** @Description:单链表 - 在指定位置插入数据* @param {Node} *L     单链表的头节点* @param {int} pos     位置* @param {ElemType} e  插入的数据* @return {*}*/
int InsertPosNode(Node *L, int pos, ElemType e)
{// 用来保存插入位置的前驱节点Node *p = L; // 从头节点开始遍历int i = 0;// 遍历链表-找到插入位置的前驱节点while (i < pos - 1) // 遍历到插入位置的前驱节点{p = p->next; // 移动到下一个节点i++;if (p == NULL) // 判断是否到达链表末尾{printf("插入位置不合法\n");return 0;}}Node *newnode = (Node *)malloc(sizeof(Node)); // 创建一个新的节点newnode->data = e;                            // 在新节点的数据域存入数据enewnode->next = p->next;                      // 新节点的指针域指向插入位置的前驱节点的下一个节点p->next = newnode;                            // 插入位置的前驱节点的指针域指向新节点return 1;
}/*** @Description:单链表 - 删除指定位置的节点* @param {Node} *L 单链表的头节点* @param {int} pos 位置* @return {*}       返回1表示成功*/
int DeletePosNode(Node *L, int pos)
{// 用来保存删除位置的前驱节点Node *p = L; // 从头节点开始遍历int i = 0;// 遍历链表-找到删除节点的前驱节点while (i < pos - 1) // 遍历到删除位置的前驱节点{p = p->next; // 移动到下一个节点i++;if (p == NULL) // 判断是否到达链表末尾{printf("删除位置不合法\n");return 0;}}if (p->next == NULL) // 判断删除位置是否合法{printf("删除位置不合法\n");return 0;}Node *q = p->next; // 保存要删除的节点的地址p->next = q->next; // 删除节点的前驱节点的指针域 指向 删除节点的下一个节点free(q);           // 释放删除节点的内存return 1; // 返回1表示成功
}int main()
{Node *list = InitList(); // 初始化一个单链表printf("头插法插入数据1 2 3\n");InsertHead(list, 1); // 头插法插入数据1InsertHead(list, 2); // 头插法插入数据2InsertHead(list, 3); // 头插法插入数据3printf("遍历-链表中的元素为：");TraverseList(list); // 遍历单链表printf("\n");       // 换行printf("\n尾插法插入数据4 5 6\n");Node *tail = GetTail(list); // 获取尾节点地址tail = InsertTail(tail, 4); // 尾插法插入数据4tail = InsertTail(tail, 5); // 尾插法插入数据5tail = InsertTail(tail, 6); // 尾插法插入数据6printf("遍历-链表中的元素为：");TraverseList(list); // 遍历单链表printf("\n在指定位置3插入数据7\n");InsertPosNode(list, 3, 7); // 在指定位置3插入数据7printf("遍历-链表中的元素为：");TraverseList(list); // 遍历单链表printf("\n删除指定位置3的节点\n");DeletePosNode(list, 3); // 删除指定位置3的节点printf("遍历-链表中的元素为：");TraverseList(list); // 遍历单链表return 0;
}

输出结果：

头插法插入数据1 2 3
遍历-链表中的元素为：3 2 1尾插法插入数据4 5 6
遍历-链表中的元素为：3 2 1 4 5 6在指定位置3插入数据7
遍历-链表中的元素为：3 2 7 1 4 5 6删除指定位置3的节点
遍历-链表中的元素为：3 2 1 4 5 6请按任意键继续. . .

获取链表长度

int GetListLength(Node *L)
{int length = 0;Node *p = L->next; // 从头节点的下一个节点开始遍历,头节点不算在内while (p != NULL){p = p->next;length++;}return length;
}

从头节点的下一个节点开始遍历,头节点不算在内

释放链表

保存头节点，把剩下的每一个节点的内存都释放掉

  • 指针p指向头节点后的第一个节点
  • 判断指针p是否指向NULL
  • 如果p不为NULL，用指针q记录指针p的后继结点
  • 释放指针p指向的节点
  • 指针p和指针q指向同一个节点，循环上面的操作

释放链表代码

void FreeList(Node *L)
{Node *p = L->next; // 从头节点的下一个节点开始遍历,头节点不需要释放Node *q = NULL;    // 用来保存下一个节点的地址,q能掌握下一个节点的地址，这是灵魂所在while (p != NULL){q = p->next; // 保存下一个节点的地址free(p);     // 释放当前节点的内存p = q;       // 移动到下一个节点}L->next = NULL; // 头节点的指针域为空
}

完整代码如下：

#include <stdio.h>
#include <stdlib.h>typedef int ElemType; // 定义元素类型typedef struct node // 定义节点类型
{ElemType data;struct node *next;
} Node;/* 初始化一个单链表-造一个头节点 */
Node *InitList()
{Node *head = (Node *)malloc(sizeof(Node)); // 为头节点分配内存head->data = 0;                            // 头节点的数据域为0head->next = NULL;                         // 头节点的指针域为空return head;                               // 返回头节点
}
/*单链表 - 头插法*/
int InsertHead(Node *L, ElemType e)
{Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点p->data = e;                            // 在新节点的数据域存入数据ep->next = L->next;                      // 新节点的指针域指向头节点的下一个节点(把L的NULL复制给新节点)L->next = p;                            // 头节点的指针域指向新节点return 1;                               // 返回1表示成功
}
/* 单链表 - 遍历 */
void TraverseList(Node *L)
{Node *p = L->next; // 从头节点的下一个节点开始遍历while (p != NULL)  // 遍历到链表末尾{printf("%d ", p->data); // 输出节点的数据域p = p->next;            // 移动到下一个节点}printf("\n"); // 换行
}/* 单链表 - 尾插法 */
// 获取尾节点地址
Node *GetTail(Node *List)
{Node *p = List;         // 从头节点开始遍历while (p->next != NULL) // 遍历到链表末尾{p = p->next; // 移动到下一个节点}return p; // 返回尾节点
}/*** @Description:单链表 - 尾插法插入数据* @param {Node} *tail   尾节点* @param {ElemType} e   插入的数据* @return {*}           返回新的尾节点*/
Node *InsertTail(Node *tail, ElemType e)
{Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点p->data = e;                            // 在新节点的数据域存入数据etail->next = p;                         // 尾节点的指针域指向新节点p->next = NULL;                         // 新节点的指针域为空return p;                               // 返回新的尾节点
}/*** @Description:单链表 - 在指定位置插入数据* @param {Node} *L     单链表的头节点* @param {int} pos     位置* @param {ElemType} e  插入的数据* @return {*}*/
int InsertPosNode(Node *L, int pos, ElemType e)
{// 用来保存插入位置的前驱节点Node *p = L; // 从头节点开始遍历int i = 0;// 遍历链表-找到插入位置的前驱节点while (i < pos - 1) // 遍历到插入位置的前驱节点{p = p->next; // 移动到下一个节点i++;if (p == NULL) // 判断是否到达链表末尾{printf("插入位置不合法\n");return 0;}}Node *newnode = (Node *)malloc(sizeof(Node)); // 创建一个新的节点newnode->data = e;                            // 在新节点的数据域存入数据enewnode->next = p->next;                      // 新节点的指针域指向插入位置的前驱节点的下一个节点p->next = newnode;                            // 插入位置的前驱节点的指针域指向新节点return 1;
}/*** @Description:单链表 - 删除指定位置的节点* @param {Node} *L 单链表的头节点* @param {int} pos 位置* @return {*}       返回1表示成功*/
int DeletePosNode(Node *L, int pos)
{// 用来保存删除位置的前驱节点Node *p = L; // 从头节点开始遍历int i = 0;// 遍历链表-找到删除节点的前驱节点while (i < pos - 1) // 遍历到删除位置的前驱节点{p = p->next; // 移动到下一个节点i++;if (p == NULL) // 判断是否到达链表末尾{printf("删除位置不合法\n");return 0;}}if (p->next == NULL) // 判断删除位置是否合法{printf("删除位置不合法\n");return 0;}Node *q = p->next; // 保存要删除的节点的地址p->next = q->next; // 删除节点的前驱节点的指针域 指向 删除节点的下一个节点free(q);           // 释放删除节点的内存return 1; // 返回1表示成功
}int GetListLength(Node *L)
{int length = 0;Node *p = L; // 从头节点开始遍历,头节点算在内while (p != NULL){p = p->next;length++;}return length;
}void FreeList(Node *L)
{Node *p = L->next; // 从头节点的下一个节点开始遍历,头节点不需要释放Node *q = NULL;    // 用来保存下一个节点的地址,q能掌握下一个节点的地址，这是灵魂所在while (p != NULL){q = p->next; // 保存下一个节点的地址free(p);     // 释放当前节点的内存p = q;       // 移动到下一个节点}L->next = NULL; // 头节点的指针域为空
}int main()
{Node *list = InitList(); // 初始化一个单链表printf("头插法插入数据1 2 3\n");InsertHead(list, 1); // 头插法插入数据1InsertHead(list, 2); // 头插法插入数据2InsertHead(list, 3); // 头插法插入数据3printf("尾插法插入数据4 5 6\n");Node *tail = GetTail(list); // 获取尾节点地址tail = InsertTail(tail, 4); // 尾插法插入数据4tail = InsertTail(tail, 5); // 尾插法插入数据5tail = InsertTail(tail, 6); // 尾插法插入数据6printf("在指定位置3插入数据7\n");InsertPosNode(list, 3, 7); // 在指定位置3插入数据7printf("删除指定位置3的节点\n");DeletePosNode(list, 3); // 删除指定位置3的节点printf("遍历-链表中的元素为：");TraverseList(list); // 遍历单链表printf("链表长度为%d\n", GetListLength(list));printf("释放链表\n");FreeList(list); // 释放链表的内存printf("链表长度为%d\n", GetListLength(list));return 0;
}

输出

头插法插入数据1 2 3
尾插法插入数据4 5 6
在指定位置3插入数据7
删除指定位置3的节点
遍历-链表中的元素为：3 2 1 4 5 6
链表长度为7
释放链表
链表长度为1请按任意键继续. . .

http://www.ppmy.cn/server/159509.html

相关文章

如何在亚马逊云科技上大幅降低无服务器网页应用冷启动时间（上篇）

如何在亚马逊云科技上大幅降低无服务器网页应用冷启动时间（上篇）

背景 我们在云端搭建无服务器&#xff08;serverless&#xff09;开发架构时&#xff0c;经常会被冷启动&#xff08;cold start&#xff09;带来的应用延迟所困扰。冷启动是指当无服务器资源在一段时间内未被调用&#xff0c;或需要扩展以处理新请求时&#xff0c;系统需要初…
阅读更多...
Tabby - 开源的自托管 AI 编码助手

Tabby - 开源的自托管 AI 编码助手

Tabby 是一个开源的自托管 AI 编码助手。使用 Tabby&#xff0c;每个团队都可以轻松设置自己的 LLM 驱动的代码完成服务器。独立式&#xff0c;无需 DBMS 或云服务。OpenAPI 接口&#xff0c;易于与现有基础设施&#xff08;例如 Cloud IDE&#xff09;集成。 支持消费级 GPU。…
阅读更多...
vue编写一个可拖动的模块，并可以和任何其他组件组合使用

vue编写一个可拖动的模块，并可以和任何其他组件组合使用

实现思路&#xff1a; 使用 Vue 的自定义指令&#xff08;directive&#xff09;来处理拖动逻辑。在 mounted 钩子中添加鼠标事件监听器&#xff0c;以实现拖动功能。在 unmounted 钩子中移除鼠标事件监听器&#xff0c;防止内存泄漏。 代码示例&#xff1a; <template&g…
阅读更多...
前端小知识 鼠标穿透 pointer-events: none；

前端小知识 鼠标穿透 pointer-events: none；

为什么会说到这个呢&#xff1f;是我觉得没有识别出来&#xff0c;然后就导致了这样的问题&#xff0c;这种情况不应该发生。我写了如下这样一段代码&#xff0c;但是发现当自己选择时间的时候无法选择。然后就发现变成了光标在闪烁。这样其实就是因为我选择到了这个input框的鼠…
阅读更多...
STM32--定时器输出pwm知识点_stm32 pwm-CSDN博客

STM32--定时器输出pwm知识点_stm32 pwm-CSDN博客

1. 选择TIM_OCMode_Toggle电平翻转模式&#xff0c; TIM_TimeBaseInitStruct.TIM_Period PWM_1_TIM_Period; 要设置成PWM_1_TIM_Period设置成0xffff - 1&#xff0c;设置成其他数值会出现脉冲一会有一会咩有。 资料&#xff1a;一文搞懂STM32定时器翻转模式&#xff08;产生…
阅读更多...
SQL Server 导入Excel数据

SQL Server 导入Excel数据

1、选中指定要导入到哪个数据库&#xff0c;右键选择 》任务 》导入数据 2、数据源 选择Excel&#xff0c;点击 下一步(Next) 3、目前 选择OLE DB Provider &#xff0c;点击 下一步&#xff08;Next&#xff09; 4、默认 &#xff0c;点击 下一步&#xff08;Next&#xff09;…
阅读更多...
JAVA-Exploit编写(3)--httpcomponents库使用文件上传

JAVA-Exploit编写(3)--httpcomponents库使用文件上传

目录 1.依赖安装 2. upload文件代码 3.文件上传代码 1.依赖安装 文件上传处需要使用httpcomponents库,需要在Maven的pom.xml文件中导入依赖 <dependency><groupId>org.apache.httpcomponents</groupId><artifactId>httpmime</artifactId>&l…
阅读更多...
用LLM做测试驱动开发：有趣又高效的尝试

用LLM做测试驱动开发：有趣又高效的尝试

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…
阅读更多...
最新文章

Copyright @ 2022~2023