线性表采用带头结点单链表实现,head为头指针_线性表的链式表示和实现[通俗易懂]

学习是一件快乐的事，先上个图片放松一下  

目录

一、前言

二、头指针和头结点

1.头指针 

2.头结点

3.头指针和头结点的关系

三、形象说明

四、为什么要加头结点？ 加了头结点有哪些好处？

五、开发环境  Dev-c++  

六、实际操作

七、测试结果

八、总结

一、前言

在学习链表时，会有头指针和头结点这两个概念，那么这二者的关系是什么？ 为什么要加头结点？ 加了头结点有哪些好处？ 这篇博客是我的一些个人理解，希望能对您有所帮助。

二、头指针和头结点

1.头指针 

头指针唯一代表着一个链表（对于单链表来说），即这个指针是我们访问链表的入口。

2.头结点

头结点是在首元结点（正式存放数据的第一个节点）之前的一个节点。

3.头指针和头结点的关系

头指针指向头结点，头结点指向首元结点。指向的意思是，前者存储后者的地址。

三、形象说明

举个例子，比如有一个小吃街，只有正门，没有侧门和后门，要进来只能从正门进，示意图如下：

1.这个例子中正门就是 “头指针”，我们去小吃街买东西，必须从正门进入才能买，也就是说正门代表了我们这条小吃街。（无头结点）

我们假设小吃街不能一直开着，只有周六日开，万一有人不知道，就从大门向里面看，没看到店铺开门，就代表小吃街今天不营业。（当然大门上也可以粘贴营业信息，这不是我们讨论的重点）。

对应于我们的头指针指向空，即这条链表是空表。L==NULL     （L和上面正门意义相同）

2.随着小吃街的生意不断火爆，可能有人开车来，骑自行车来，为了便于小吃街的管理，小吃街增加了保安室，来管理小吃街，并负责不营业时的卫生打扫，安保工作。（有头结点）

这时的保安室就相当于头结点，此时不营业时大门也开着，如果有人来询问营业等信息，就去保安室问，这时保安人员会回答具体的营业时间，或者店铺的数量等信息。

如果此时不营业，就代表保安室之后的店铺都没开门，对于小吃街来说，大门存储着保安室的地址，保安室存储着第一个店铺的地址

对于链表来说，如果为空  L->next=NULL  ， (L存储着头结点的地址，头结点的next存储着第一个店铺的地址)

四、为什么要加头结点？ 加了头结点有哪些好处？

对于上述例子，我们可以看到，有了保安可以管理之外，还可以记录店铺的数量、营业时间、安保、打扫卫生等等好处，那么对于链表呢？

1.固定L值，增加了头结点，便于我们更好地管理链表，此时不管链表是否为空，L都不为空，指向头结点

2.便于管理，头结点本身也是一个节点，除了指针域能存储首元结点的地址外，数据域还可以存储链表的长度等信息。

3.操作统一，对于插入和删除首元结点，我们只要操作头结点就可以，无需改变头指针L

4.更安全，因为头指针是我们访问单链表的入口，如果不小心改变头指针的指向，那么我们就无法访问该单链表。增加了头结点，此时的增删改查都是相对头结点进行实际操作的。

五、开发环境  Dev-c++  

Dev-C++  下载链接         
提取码：3f00

六、实际操作

#include<cstdio>
#include<cstdlib>
#include<malloc.h>
#include<cstring>
#include<conio.h>
//函数结果状态代码 
#define TRUE  1
#define FALSE 0
#define OK    1
#define ERROR 0 

typedef int Status;  //int 的别名，其值是函数结果状态代码 

typedef struct LNode{
	int            data;
	struct LNode * next; //指向结构体类型的指针，表示下一个结点 
}LNode,* LinkList;

/*  最后一句的等同于下面代码，中括号是我自己加上的，只是提示把他们看作是一个整体
 
typedef  {struct  LNode   }  LNode;      // struct  LNode 的别名是 LNode
 
typedef  {struct  LNode * }  LinkList;   // struct  LNode *  的别名是 LinkList

*/

//无头结点 
Status create_Linked_List(LinkList & L,int n) 
 //逆序输入n个元素的值，建立带表头结点单链线性表L 
 {
 	L = NULL;
	for(int i=0;i<n;i++)
	{
		LinkList  List_Node = (LinkList)malloc(sizeof(LNode));
		scanf("%d",&List_Node->data);
		List_Node->next = L;
		L = List_Node;
	} 
	return OK;
 }
 
 //有头结点 
 Status create_headLinked_List(LinkList & L,int n) 
 //逆序输入n个元素的值，建立带表头结点单链线性表L 
 {
 	LinkList p = (LinkList)malloc(sizeof(LNode));//头结点的存储地址 
 	if(NULL == p) return ERROR;                  //分配空间失败 
 	L = p;                                       //头指针L存储头结点P的地址，即头指针指向头结点 
 	L->data = 0;                                 //用头结点统计元素个数，刚开始为0个 
 	L->next = NULL;                              //此时链表为空 
 	for(int i = 0;i<n;i++)
	 {
 		LinkList List_Node = (LinkList)malloc(sizeof(LNode));
 		scanf("%d",&List_Node->data);
 		L->data++;                               //每插入一个元素，头结点统计链表元素个数加一 
 		List_Node->next = L->next;               //头插法，即链表中的元素顺序与输入相反 
 		L->next = List_Node;
	 } 
	 return OK;
 }
 
 //输出带头结点链表中的元素 
 void headlinked_List_Traverse(LinkList  L)
 {
    printf("该链表的元素个数为：%d \n",L->data);
	LinkList p = L->next;    
 	while(p)
	{    
 	    printf(" %d ",p->data);	
	    p = p->next;	    	
	}
 	
}

//输出不带头结点链表中的元素 
 void linkedListTraverse(LinkList  L)
 {
	LinkList p = L;    
 	while(p)
	{    
 	    printf(" %d ",p->data);	
	    p = p->next;	    	
	}
 	
}


//销毁链表,包括头结点的所有结点全部释放	 
Status destroy_headlinked_list(LinkList  L)	
{
	L->data = 0; 
	LinkList p;
	while(L)
	{   
	    p = L->next;
	    free(L);
	    L = p;			    	
	} 
 	return OK;
} 

/*清空带头结点链表
  1.先保留链表的头结点
  2.然后把头结点后面的所有的都销毁
  3.最后把头结点里指向首元结点的指针设为空 */
Status clear_headlinked_list(LinkList  L)	
{
	L->data = 0; 
	LinkList p,q;
	p = L->next;
	while(L)
	{   
	    q = p->next;
	    free(p);
            p = q;			    	
	} 
	L->next = NULL;
 	return OK;
}  


//销毁不带头结点的链表 

Status destroy_linked_list(LinkList  L)
{
	LinkList p;
	while(L)
	{
	    p = L->next;
	    free(L);
            L = p;
	}
	return OK;
}

int main(void)
{
	LinkList L;//头指针L 
	int n = 0;
	printf("请输入所要创建带头结点链表的元素个数：");
	scanf("%d",&n);
	if(create_headLinked_List( L, n) )
		headlinked_List_Traverse(L);
	if(destroy_headlinked_list(L))
		printf("\n销毁带头结点链表L成功!\n");	
		
	LinkList M;//头指针M 
	int m = 0;
	printf("请输入所要创建不带头结点链表的元素个数：");
	scanf("%d",&m);
	if(create_Linked_List( M, m) )
		linkedListTraverse(M);
	if(destroy_linked_list(M))
		printf("\n销毁不带头结点链表M成功!\n");	
	return 0;
} 
  

七、测试结果

八、总结

1.头指针存储头结点的地址，头结点存储首元结点的地址

2.头结点实质还是一个结点，只不过是位置特殊。

3.加了头结点有很多好处，上面已经给出，这个需要自己进行实际操作来体会。

今天的文章线性表采用带头结点单链表实现,head为头指针_线性表的链式表示和实现[通俗易懂]分享到此就结束了，感谢您的阅读。