資料結構學習筆記--帶頭結點的單連結清單的多種初始化及銷毀方法（c/c++實作）

資料結構學習--帶頭結點的單連結清單的多種初始化及銷毀方法（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;
}
           

方法三：直接傳傳入連結表指針的位址（C++引用的方法）

// 初始化連結清單，傳回值：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; // 對指針的位址取值，得到指針，将連結清單指針置空。
}
           

方法三：直接傳傳入連結表指針的位址（C++引用的方法）

void DestroyList3(LinkList &L)
{
    // 在本函數中，直接對指針取位址。
	LNode *tmp;
	while(LL!=NULL)
	{
		tmp=LL->next;
		free(LL); // 依次釋放結點。
		LL=tmp;
	}
	
	LL=NULL; // 将連結清單指針置空。
}
           

總結

本知識點主要需要注意的是函數所傳入參數的指針取值與取位址的差別，加深對c語言中指針的了解。

參考學習視訊：資料結構（考研、面試、刷題必學），源代碼可下載下傳