数据结构学习笔记--带头结点的单链表的多种初始化及销毁方法（c/c++实现）

• 前言
• 定义单链表
• 单链表的初始化
• • 错误示例：传入指针的值
  • 方法一：直接返回一个指向结点的指针
  • 方法二：传入指针的指针(指针变量地址)
  • 方法三：直接传入链表指针的地址（C++引用的方法）
• 单链表的销毁
• • 方法一：传指针的值
  • 方法二：传指针的指针（指针变量地址）
  • 方法三：直接传入链表指针的地址（C++引用的方法）
• 总结

对于一个函数的参数：在c语言中可以传值，也可以传入指针；在c++中，可以是传值，也可以传地址；传值不会改变原来的参数，传指针或者地址则会改变原参数。
在涉及到指针的链表操作中，对于初始化及销毁操作，尤其要注意函数所传入的参数。

typedef int ElemType;     // 自定义链表的数据元素为整数。

typedef struct LNode
{
  ElemType data;       // 存放结点的数据元素。
  struct LNode *next;  // 指向下一个结点的指针。
}LNode,*LinkList;

在链表的初始化中，要先定义一个头结点并给它分配内存，并让链表指针指向这个头结点，也就是说要改变原来的链表指针，而我们知道通过函数传参改变一个变量的值的话是需要传入该变量的地址，即其指针（c语言中传入指针，c++中可以直接传变量地址），因此如果想要改变原来的链表指针，那么则需要传指针的地址，即指针的指针，或者直接传地址（c++）。
这里展示三种链表初始化方法，及一种错误的初始化方法

//对链表进行初始化，成功返回：1，失败返回：0。
//传入指针的值，无法将其返回，即不能改变原指针的值。
int InitList(LinkList L)
{
     LNode *head = (LNode*)malloc(sizeof(LNode)); // 定义头结点并为其分配内存。
     if(head == NULL) return 0; // 分配内存失败。
     
     head-＞next ＝ NULL; // 头结点的next指针置空，即下一结点不存在。
     
     L ＝ head; // 这一步无效，因为L是传指针的值，在这里相当于局部变量，函数外部L指针的值并不会改变。
     
     return 1;
}

// 初始化链表，成功返回：1，失败返回：0。
LNode *InitList1()
{
	LNode *head; //定义头结点。
	head=(LNode*)malloc(sizeof(LNode)); //分配内存。
	if(head==NULL) return NULL; //分配内存失败。
	
	head->next=NULL;
	
	return head;
}

// 初始化链表，返回值：0-失败；1-成功。
int InitList2(LinkList *L)
{
  // 在本函数中，L是指针的指针，用于存放指针的地址。

  if ( *LL != NULL ) { printf("链表LL已存在，在初始化之前请先释放它。n"); return 0; }

  LNode *head = (LNode *)malloc(sizeof(LNode)); // 分配头结点。

  if (head == NULL) return 0; // 分配内存失败。

  head->next=NULL; // 头结点的next指针置空，即下一结点不存在。

  *LL=head; // 指针的地址取值，得到指针。

  return 1;
}

// 初始化链表，返回值：0-失败；1-成功。
int InitList3(LinkList &LL)
{
    // 在本函数中，直接对指针取地址。
	if(LL!=NULL) { printf("链表已存在，请在初始化前释放它！n"); return 0; }
	
	LL=(LNode*)malloc(sizeof(LNode)); // 分配头结点。
	if(LL==NULL) return 0; // 分配内存失败。
	
	LL->next=NULL; //头结点的下一个节点置空。
	
	return 1;
}

链表的销毁是指要将每个节点释放，并且要将链表指针置空；与单链表的初始化一样，需要注意函数是传值还是传地址。

void DestroyList1(LinkList L)
{
	if(L == NULL) return; // 检查是否传入空指针。
	
	LNode *tmp; // 定义一个临时结点指针。
	while(L != NULL)
	{
		tmp = L->next;
		free(L); // 依次释放结点。
		L = tmp;
	}
	
	L = NULL; //链表指针置空，表示不存在了。在这里这句话无效，因为这里的链表指针是传值。
	//因此可以在主函数中添加这句代码。 如DestroyList1(L); L = NULL;
}

void DestroyList2(LinkList *L)
{
    // 在本函数中，L为指针的地址
	LNode *tmp1,*tmp2;
	tmp1 = *L; // 对指针的地址取值，得到指针。
	while(tmp1 != NULL)
	{
		tmp2 = tmp1->next;
		free(tmp1); // 依次释放结点。
		tmp1 = tmp2;
	}
	*L = NULL; // 对指针的地址取值，得到指针，将链表指针置空。
}

void DestroyList3(LinkList &L)
{
    // 在本函数中，直接对指针取地址。
	LNode *tmp;
	while(LL!=NULL)
	{
		tmp=LL->next;
		free(LL); // 依次释放结点。
		LL=tmp;
	}
	
	LL=NULL; // 将链表指针置空。
}

本知识点主要需要注意的是函数所传入参数的指针取值与取地址的区别，加深对c语言中指针的理解。
参考学习视频：数据结构（考研、面试、刷题必学），源代码可下载