数据结构笔记头插法与尾插法创建单链表 [复制链接]

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

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

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

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

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

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

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

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

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

/*----------------------------------------------------------------------------------------程序说明：头插法与尾插法创建单链表创建日期：.01.05byLiZhengNian----------------------------------------------------------------------------------------*/#includestdio.h#includestdlib.h#defineSIZE5#defineERROR1#defineOK0/*数据元素类型*/typedefintListType;/*单链表结点定义*/typedefstructLNode{ListTypedata;//数据域structLNode*next;//指针域，指向直接后继元素}LNode;/*函数的声明*/LNode*HeadCreateList(void);//使用头插法创建一个单链表LNode*TailCreateList(void);//使用尾插法创建一个单链表voidPrintfList(LNode*L);//打印输出链表/*********************************************************************************************************函数:main，主函数**------------------------------------------------------------------------------------------------------**参数:void**返回:无**日期:.01.05byLiZhengNian********************************************************************************************************/intmain(void){LNode*L1=NULL;LNode*L2=NULL;/*使用头插法创建单链表*/L1=HeadCreateList();printf("头插法创建的链表为：");PrintfList(L1);/*使用尾插法创建单链表*/L2=TailCreateList();printf("尾插法创建的链表为：");PrintfList(L2);return0;}/*********************************************************************************************************函数:HeadCreateList，头插法建立单链表（逆序）**------------------------------------------------------------------------------------------------------**参数:void**返回:创建成功的链表**说明：从一个空表开始，不断读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头结点之后。**日期:.01.05byLiZhengNian********************************************************************************************************/LNode*HeadCreateList(void){inti;LNode*L;//头结点LNode*s;//新结点L-next=NULL;//此时链表为空//创建链表for(i=0;i5;i++){//创建新结点s=(LNode*)malloc(sizeof(LNode));s-data=i;//使用头插法把新元素插入到链表中s-next=L-next;//新结点的next指针指向头结点L-next=s;//头结点的next指针指向新结点}returnL;}/*********************************************************************************************************函数ailCreateList,尾插法建立单链表（顺序）**------------------------------------------------------------------------------------------------------**参数:void**返回:创建成功的链表**说明：从一个空表开始，不断读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表尾结点之后。**日期:.01.05byLiZhengNian********************************************************************************************************/LNode*TailCreateList(void){inti;LNode*L;//头结点LNode*s,*r;//s用来指向新生成的节点。r始终指向表尾节点。r=L;//r指向了头节点，此时的头节点是表尾结点。for(i=0;i5;i++){//创建新结点s=(LNode*)malloc(sizeof(LNode));s-data=i;//使用尾插法把新元素插入到链表中r-next=s;//用来接纳新结点r=s;//指向表尾结点}r-next=NULL;//此刻所有元素已经全装入链表L中，L的表尾结点的指针域置为NULLreturnL;}/*********************************************************************************************************函数rintfList，打印输出链表**------------------------------------------------------------------------------------------------------**参数:l:链表**返回:void**日期:.01.05byLiZhengNian********************************************************************************************************/voidPrintfList(LNode*L){LNode*temp=L;while(temp-next){temp=temp-next;printf("%d",temp-data);}printf("\n\n");}

程序运行结果：

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