数据结构与算法

2024-02-13 05:26| 来源: 网络整理| 查看: 265

1024G 嵌入式资源大放送！包括但不限于C/C++、单片机、Linux等。关注微信公众号【嵌入式大杂烩】，回复1024，即可免费获取！

上一节分享的是单链表的一些概念及一些单链表的基本操作算法，可移步至【数据结构笔记】单链表进行查看，其中用到的是头插法来创建单链表。除了头插法，还可以使用尾插法来创建单链表。本节分享头插法与尾插法的区别及使用方法。

什么是头插法

首先，头指针L指向头结点，创建第一个结点并插入头结点之后、创建第二个结点插入头结点之后、……、创建第i个结点插入头结点之后。如：

头插法创建链表的代码示例：

LNode *HeadCreateList(void) { int i; LNode *L; // 头结点 LNode *s; // 新结点 L->next = NULL; // 此时链表为空 // 创建链表 for (i = 0; i < 5; i++) { // 创建新结点 s = (LNode*)malloc(sizeof(LNode)); s->data = i; // 使用头插法把新元素插入到链表中 s->next = L->next; // 新结点的next指针指向头结点 L->next = s; // 头结点的next指针指向新结点 } return L; } 什么是尾插法

首先，头指针L指向头结点，创建第一个结点并插入头结点之后、创建第二个结点插入第一个结点之后、……、创建第i个结点插入第i-1个结点之后。如：

尾插法与头插法不同的是：尾插法需要创建一个指针始终指向表尾结点。

尾插法创建链表的代码示例：

LNode *TailCreateList(void) { int i; LNode *L; // 头结点 LNode *s, *r; // s用来指向新生成的节点。r始终指向表尾节点。 r = L; // r指向了头节点，此时的头节点是表尾节点。 for (i = 0; i < 5; i++) { // 创建新结点 s = (LNode*)malloc(sizeof(LNode)); s->data = i; // 使用尾插法把新元素插入到链表中 r->next = s; //用来接纳新结点 r = s; //指向表尾结点 } r->next = NULL; //此刻所有元素已经全装入链表L中，L的表尾结点的指针域置为NULL return L; }

代码中指针变量r始终指向表尾结点，随着新结点的不断插入，表尾结点是会变化的。

完整程序 /*---------------------------------------------------------------------------------------- 程序说明：头插法与尾插法创建单链表微信公众号：嵌入式大杂烩 ----------------------------------------------------------------------------------------*/ #include #include #define SIZE 5 #define ERROR 1 #define OK 0 /* 数据元素类型 */ typedef int ListType; /* 单链表结点定义 */ typedef struct LNode { ListType data; // 数据域 struct LNode *next; // 指针域，指向直接后继元素 }LNode; /* 函数的声明 */ LNode *HeadCreateList(void);// 使用头插法创建一个单链表 LNode *TailCreateList(void);// 使用尾插法创建一个单链表 void PrintfList(LNode *L); // 打印输出链表 /******************************************************************************************************* ** 函数: main，主函数 **------------------------------------------------------------------------------------------------------ ** 参数: void ** 返回: 无 ** 日期: 2019.01.05 by LiZhengNian ********************************************************************************************************/ int main(void) { LNode *L1 = NULL; LNode *L2 = NULL; /* 使用头插法创建单链表 */ L1 = HeadCreateList(); printf("头插法创建的链表为："); PrintfList(L1); /* 使用尾插法创建单链表 */ L2 = TailCreateList(); printf("尾插法创建的链表为："); PrintfList(L2); return 0; } /******************************************************************************************************* ** 函数: HeadCreateList，头插法建立单链表（逆序） **------------------------------------------------------------------------------------------------------ ** 参数: void ** 返回: 创建成功的链表 ** 说明：从一个空表开始，不断读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头结点之后。 ** 日期: 2019.01.05 by LiZhengNian ********************************************************************************************************/ LNode *HeadCreateList(void) { int i; LNode *L; // 头结点 LNode *s; // 新结点 L->next = NULL; // 此时链表为空 // 创建链表 for (i = 0; i < 5; i++) { // 创建新结点 s = (LNode*)malloc(sizeof(LNode)); s->data = i; // 使用头插法把新元素插入到链表中 s->next = L->next; // 新结点的next指针指向头结点 L->next = s; // 头结点的next指针指向新结点 } return L; } /******************************************************************************************************* ** 函数: TailCreateList, 尾插法建立单链表（顺序） **------------------------------------------------------------------------------------------------------ ** 参数: void ** 返回: 创建成功的链表 ** 说明：从一个空表开始，不断读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表尾结点之后。 ** 日期: 2019.01.05 by LiZhengNian ********************************************************************************************************/ LNode *TailCreateList(void) { int i; LNode *L; // 头结点 LNode *s, *r; // s用来指向新生成的节点。r始终指向表尾节点。 r = L; // r指向了头节点，此时的头节点是表尾结点。 for (i = 0; i < 5; i++) { // 创建新结点 s = (LNode*)malloc(sizeof(LNode)); s->data = i; // 使用尾插法把新元素插入到链表中 r->next = s; //用来接纳新结点 r = s; //指向表尾结点 } r->next = NULL; //此刻所有元素已经全装入链表L中，L的表尾结点的指针域置为NULL return L; } /******************************************************************************************************* ** 函数: PrintfList，打印输出链表 **------------------------------------------------------------------------------------------------------ ** 参数: l:链表 ** 返回: void ** 日期: 2019.01.05 by LiZhengNian ********************************************************************************************************/ void PrintfList(LNode *L) { LNode *temp = L; while(temp->next) { temp = temp->next; printf("%d ",temp->data); } printf("\n\n"); }

程序运行结果：

以上就是头插法与尾插法的一些笔记，如有错误欢迎指出！

【本文地址】

公司简介

联系我们