⼆、单链表的头插法建表和尾插法建表
链式存储结构：
⽤⼀组不⼀定连续的存储单元存储逻辑上相邻的元素，元素间的逻辑关系是由附加的指针域表⽰的，由此得到的存储结构称为链式存储结构。
sizeof 指针单链表(线性链表)使⽤链式存储结构表⽰每个数据元素 a  时，除了存储
a  本⾝信息之外，还需要⼀个存储指⽰其后继元素 a  存储位置的指针。由这两部分组成元素 a  的存储映像称为 结点。它包括两个域：存储数据元素的域称为数据域，存储直接后继存储地址的域称为指针域。利⽤这种存储⽅式表⽰的线性表称为链表，n个结点链成⼀个链表，即为线性表的链式存储结构。由于这种链表的每个结点中只包含⼀个指针域，因此⼜称为单链表。
⼀个单链表可由头指针唯⼀确定，因此单链表可以⽤头指针的名字来命名。
链式存储结构如下：
typedef  int  DataType ;  //定义数据类型
typedef  struct  node    //结点类型定义
{
DataType data ;      //结点的数据域
struct  node * next ; //结点的指针域，存储下⼀个结点的地址
}ListNode ;
typedef  ListNode * LinkList ; //定义⼀个指针类型
头插法建表
头插法建表是从⼀个空表开始，重复读⼊数据，⽣成新节点，将读⼊的数据存放到新节点的数据域中，然后将新节点插⼊到当前链表的表头上，直到读⼊结束标志为⽌。
i i i+1i
/*
头插法建表，并返回头指针
*/
LinkList CreateListF(int arr[],int length)
{
LinkList head;//声明指向单链表的头指针
ListNode * p;//定义⼀个指向结点的指针变量
head =NULL;//置空单链表
for(int i =0; i < length; i++)
{
p =(ListNode *)malloc(sizeof(ListNode));//申请⼀个新的结点
p->data = arr[i];//数据域复制
p->next = head;//指针域赋值
head = p;//头指针指向新的结点
printf("data=%d p=%p\n",p->data,p);
}
return head;
}
头插法建⽴的链表是将新结点插⼊在表头，算法⽐较简单，但新建链表中的结点次序和数组顺序相反。如果想要和数组顺序⼀致，可以使⽤尾插法建表。
尾插法建表
将新节点插⼊当前链表的表尾上，因此需要增设⼀个尾指针near，使其始终指向链表的尾节点。
/*
尾插法建表，并返回头指针
*/
LinkList CreateListR(int arr[],int length){
LinkList head,rear;
ListNode *p;
head =NULL; rear =NULL;//置空单链表
for(int i =0; i < length; i++)
{
p =(ListNode *)malloc(sizeof(ListNode));//申请新节点
p->data = arr[i];//数据域赋值
if(head ==NULL){
head = p;//新节点*p插⼊空表
}else{
rear->next = p;//新节点*p插⼊到⾮空表的表尾节点*rear之后
}
rear = p;//表尾指针指向新的表尾指针
printf("data=%d p=%p\n",p->data,p);
}
if(rear !=NULL){
rear->next =NULL;//终端结点的指针域置空
}
return head;
}
主程序代码：
#include<stdio.h>
#include"E:/Dev/C/DataStructure/chapter2/LinkList.c"
void printLink();
int main(){
int arr[]={1,2,3};
LinkList head =NULL;
printf("头插法\n");
head =CreateListF(arr,3);
printf("head= %p\n",head);
printLink(head);
printf("尾插法\n");
head =CreateListR(arr,3);
printf("head= %p\n",head);
printLink(head);
return0;
}
/*
打印输出链表
*/
void printLink(LinkList head){
printf("输出：");
LinkList temp = head;
while(temp !=NULL){
printf("%d ",temp->data);
temp = temp->next;
}
printf("\n");
}
编译运⾏，输出结果：
可以看出头插法输⼊123，输出321。尾插法输⼊123，输出123。
头插法新建链表节点的次序和输⼊时的顺序相反，尾插法新建链表节点次序和输⼊次序相同。引⼊带头节点
为了简化算法，⽅便操作，在链表开始结点前附加⼀个结点，称为头结点。如下
尾插法建⽴单链表算法可简化：
/*
尾插法建⽴带头节点的单链表算法
*/
LinkList CreateListR1(int arr[],int length){
LinkList head =(ListNode *)malloc(sizeof(ListNode));//申请头结点
ListNode *p,*r;
r = head;//尾指针初始指向头结点
for(int i =0; i < length; i++)
{
p =(ListNode *)malloc(sizeof(ListNode));//申请新节点
p->data = arr[i];
r->next = p;//新节点连接到尾结点之后
r = p;//尾结点指向新节点
printf("data=%d p=%p\n",p->data,p);
}
r->next =NULL;//终端结点指针域置空
return head;
}
输出结果
尾插法建⽴带头结点单链表
data=1 p=0000000000176CF0
data=2 p=0000000000176D10
data=3 p=0000000000176D30
输出：1512480 1 2 3
因为增加了头结点，所以输出也就多了⼀位。因为头结点没有赋值，所以值是没有意义的。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。