学习记录：第二章 线性表的链式存储-单链表的初始化创建（代码、图示、C++）

• 前言
• 一、单链表结点的定义（两种方式）
• 二、头指针L的两种命名方式及区别
• 三、不带头结点的单链表的创建
• 四、带头结点的单链表的创建
• 五、带头结点和不带头结点区别
• 总结（需要注意）

本文给出了单链表的初始化（带头结点、不带头结点）、结点的定义（两种方式）、头指针 L 的两种命名方式及区别，它们的代码及相应图示助于理解，代码实现使用的是C语言在线工具。无概念解释，初学者建议配合书本食用。
【如果图片看不清楚，网页版是很清晰的。】

//方式一
typedef struct LNode{			//定义单链表结点类型
	ElemType data;				//数据域，每个结点存放一个数据元素
	struct LNode *next;			//指针域，指针指向下一个结点
}LNode, *LinkList;

//方式二
struct LNode{					//定义单链表结点类型
	ElemType data;				//数据域，每个结点存放一个数据元素
	struct LNode *next;			//指针域，指针指向下一个结点
};
typedef struct LNode LNode;		//typedef给数据类型struct LNode重命名为LNode
typedef struct LNode *LinkList;	//并且用LinkList表示这是指向struct LNode类型的指针

单链表在内存中是这样的：

可以看出要表示一个单链表时，只需要表示一个头指针L，因为L指向单链表的第一个结点，所以找到头指针L，就找到了整个单链表，因此声明头指针 L 的两种方式：

//方式一
LNode * L;			//声明一个指向单链表第一个结点的指针
//方式二
LinkList L;			//声明一个指向单链表第一个结点的指针，这种方式代码可读性更强

两种命名方式是等价的，但是它们的不同体现在下面这张图片，GetElem操作在后续的文章会讲到。
GetElem：从单链表 L 中的第 i 个结点取出来，并 return 返回。

typedef struct LNode{			//定义单链表结点类型
	ElemType data;				//每个结点存放一个数据元素
	struct LNode *next;			//指针指向下一个结点
}LNode, *LinkList;				

//初始化一个空的单链表（不带头结点）
bool InitList(LinkList &L){		//注意这里传入指针变量L的时候使用的是&L引用类型
	L = NULL;		//空表，暂时没有任何结点
	return true;
}

void test(){
	LinkList L;		//声明一个指向单链表的指针
	InitList(L);	//初始化一个空表
	
}

//判断单链表是否为空（不带头结点）：判断头指针L是否等于NULL
bool Empty(LinkList L){
	if(L == NULL)
		return true;
	else 
		return false;
}

typedef struct LNode{			//定义单链表结点类型
	ElemType data;				//每个结点存放一个数据元素
	struct LNode *next;			//指针指向下一个结点
}LNode, *LinkList;

//初始化一个单链表（带头结点）
bool InitList(LinkList &L){
	L = (LNode *)malloc(sizeof(LNode));	//分配一个头结点，头结点不存储数据
	if(L == NULL)			//内存不足，分配失败
		return false;
	L->next = NULL;			//头结点之后暂时没有结点
	return true;
}

void test(){
	LinkList L;		//声明一个指向单链表的指针
	InitList(L);	//初始化一个空表
	
}

//判断单链表是否为空（带头结点）
bool Empty(LinkList L){
	if(L->next == NULL)
		return true;
	else
		return false;
}

• 不带头结点：写代码更麻烦。对第一个数据结点和后续数据结点的处理需要用不同的代码逻辑；对空表和非空表的处理需要用不同的代码逻辑。
• 带头结点：写代码更方便，据说用过的都说好:-D。

• LinkList 和 LNode * 的区别
• 不带头结点：空表判断条件是 L==NULL，写代码不方便
• 带头结点：空表判断条件是 L->next==NULL，写代码更方便。
• 带头结点的单链表，头结点不存储数据只是为了操作方便。
• 掰掰。