1024G 嵌入式資源大放送!包括但不限于C/C++、單片機、Linux等。關注微信公衆号【嵌入式大雜燴】,回複1024,即可免費擷取!
上一節分享的是單連結清單的一些概念及一些單連結清單的基本操作算法,可移步至【資料結構筆記】單連結清單進行檢視,其中用到的是頭插法來建立單連結清單。除了頭插法,還可以使用尾插法來建立單連結清單。本節分享頭插法與尾插法的差別及使用方法。
什麼是頭插法
首先,頭指針L指向頭結點,建立第一個結點并插入頭結點之後、建立第二個結點插入頭結點之後、……、建立第i個結點插入頭結點之後。如:
頭插法建立連結清單的代碼示例:
LNode *HeadCreateList(void)
{
int i;
LNode *L; // 頭結點
LNode *s; // 新結點
L->next = NULL; // 此時連結清單為空
// 建立連結清單
for (i = 0; i < 5; i++)
{
// 建立新結點
s = (LNode*)malloc(sizeof(LNode));
s->data = i;
// 使用頭插法把新元素插入到連結清單中
s->next = L->next; // 新結點的next指針指向頭結點
L->next = s; // 頭結點的next指針指向新結點
}
return L;
}
什麼是尾插法
首先,頭指針L指向頭結點,建立第一個結點并插入頭結點之後、建立第二個結點插入第一個結點之後、……、建立第i個結點插入第i-1個結點之後。如:
尾插法與頭插法不同的是:尾插法需要建立一個指針始終指向表尾結點。
尾插法建立連結清單的代碼示例:
LNode *TailCreateList(void)
{
int i;
LNode *L; // 頭結點
LNode *s, *r; // s用來指向新生成的節點。r始終指向表尾節點。
r = L; // r指向了頭節點,此時的頭節點是表尾節點。
for (i = 0; i < 5; i++)
{
// 建立新結點
s = (LNode*)malloc(sizeof(LNode));
s->data = i;
// 使用尾插法把新元素插入到連結清單中
r->next = s; //用來接納新結點
r = s; //指向表尾結點
}
r->next = NULL; //此刻所有元素已經全裝傳入連結表L中,L的表尾結點的指針域置為NULL
return L;
}
代碼中指針變量r始終指向表尾結點,随着新結點的不斷插入,表尾結點是會變化的。
完整程式
/*----------------------------------------------------------------------------------------
程式說明:頭插法與尾插法建立單連結清單
微信公衆号:嵌入式大雜燴
----------------------------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#define SIZE 5
#define ERROR 1
#define OK 0
/* 資料元素類型 */
typedef int ListType;
/* 單連結清單結點定義 */
typedef struct LNode
{
ListType data; // 資料域
struct LNode *next; // 指針域,指向直接後繼元素
}LNode;
/* 函數的聲明 */
LNode *HeadCreateList(void);// 使用頭插法建立一個單連結清單
LNode *TailCreateList(void);// 使用尾插法建立一個單連結清單
void PrintfList(LNode *L); // 列印輸對外連結表
/*******************************************************************************************************
** 函數: main,主函數
**------------------------------------------------------------------------------------------------------
** 參數: void
** 傳回: 無
** 日期: 2019.01.05 by LiZhengNian
********************************************************************************************************/
int main(void)
{
LNode *L1 = NULL;
LNode *L2 = NULL;
/* 使用頭插法建立單連結清單 */
L1 = HeadCreateList();
printf("頭插法建立的連結清單為:");
PrintfList(L1);
/* 使用尾插法建立單連結清單 */
L2 = TailCreateList();
printf("尾插法建立的連結清單為:");
PrintfList(L2);
return 0;
}
/*******************************************************************************************************
** 函數: HeadCreateList,頭插法建立單連結清單(逆序)
**------------------------------------------------------------------------------------------------------
** 參數: void
** 傳回: 建立成功的連結清單
** 說明:從一個空表開始,不斷讀入資料,生成新結點,将讀入資料存放到新
結點的資料域中,然後将新結點插入到目前連結清單的表頭結點之後。
** 日期: 2019.01.05 by LiZhengNian
********************************************************************************************************/
LNode *HeadCreateList(void)
{
int i;
LNode *L; // 頭結點
LNode *s; // 新結點
L->next = NULL; // 此時連結清單為空
// 建立連結清單
for (i = 0; i < 5; i++)
{
// 建立新結點
s = (LNode*)malloc(sizeof(LNode));
s->data = i;
// 使用頭插法把新元素插入到連結清單中
s->next = L->next; // 新結點的next指針指向頭結點
L->next = s; // 頭結點的next指針指向新結點
}
return L;
}
/*******************************************************************************************************
** 函數: TailCreateList, 尾插法建立單連結清單(順序)
**------------------------------------------------------------------------------------------------------
** 參數: void
** 傳回: 建立成功的連結清單
** 說明:從一個空表開始,不斷讀入資料,生成新結點,将讀入資料存放到新
結點的資料域中,然後将新結點插入到目前連結清單的表尾結點之後。
** 日期: 2019.01.05 by LiZhengNian
********************************************************************************************************/
LNode *TailCreateList(void)
{
int i;
LNode *L; // 頭結點
LNode *s, *r; // s用來指向新生成的節點。r始終指向表尾節點。
r = L; // r指向了頭節點,此時的頭節點是表尾結點。
for (i = 0; i < 5; i++)
{
// 建立新結點
s = (LNode*)malloc(sizeof(LNode));
s->data = i;
// 使用尾插法把新元素插入到連結清單中
r->next = s; //用來接納新結點
r = s; //指向表尾結點
}
r->next = NULL; //此刻所有元素已經全裝傳入連結表L中,L的表尾結點的指針域置為NULL
return L;
}
/*******************************************************************************************************
** 函數: PrintfList,列印輸對外連結表
**------------------------------------------------------------------------------------------------------
** 參數: l:連結清單
** 傳回: void
** 日期: 2019.01.05 by LiZhengNian
********************************************************************************************************/
void PrintfList(LNode *L)
{
LNode *temp = L;
while(temp->next)
{
temp = temp->next;
printf("%d ",temp->data);
}
printf("\n\n");
}
程式運作結果:
以上就是頭插法與尾插法的一些筆記,如有錯誤歡迎指出!