頭插法和尾插法創建鏈表（有無頭結點）

文章目錄

• 頭插法和尾插法創建鏈表（有無頭結點）
• • 1 頭插法
  • • 1.1頭插法建表規則：
    • 1.2 頭插法建表代碼實現
  • 2 尾插法
  • • 2.1 尾插法建表規則：
    • 2.2 尾插法建表代碼實現：

1 頭插法

1.1頭插法建表規則：

從一個空表開始，讀取字符數組a中的字符，生成新節點，將讀取的數據存放到新節點的數據域中，然后將新節點插入到當前鏈表的表頭上，直到讀完字符數組a的所有元素為止。

頭插法建表簡單，但生成的鏈表中節點的次序和原數組的次序相反，若希望兩者的次序一致，可采用尾插法建立

1.2 頭插法建表代碼實現

/*節點的結構聲明 */ typedef int ElementType;typedef struct Node {ElementType data;struct Node *Next; } *List;/* 建立鏈表 - 頭插法 - 有頭節點 +------+ +------+ +------+ +------+| head | => |node_1| -> |node_2| -> |node_3| -> NULL+------+ +------+ +------+ +------+\ /+------+| p |+------+*/ 思想：將新結點插入到表頭之后，最先得到的是尾結點，將右端固定，不斷向左延伸 List HeadCreate(void) {ElementType x; // 保存 Node 中的 data 數據List p; // 臨時指針，用于保存聲明的節點List head; // 整個鏈表的頭結點;head = (List)malloc(sizeof(struct Node));head->Next = NULL;head->data = 0; // 頭節點的 data 域用于保存鏈表的長度scanf("%d", &x);while (x != -1) { // 當 x 等于 -1 的時候，停止創建鏈表p = (List)malloc(sizeof(struct Node));p->data = x;p->Next = head->Next;head->Next = p;head->data++; // 鏈表的長度加 1scanf("%d", &x); // 讀取下一個節點的數據}return head; }/*建立鏈表 - 頭插法 - 沒有頭節點+------+ +------+ +------+ +------+| head | -> |node_1| -> |node_2| -> |node_3| -> NULL^ +------+ +------+ +------+ +------+|+------+| p |+------+*/ List HeadCreate(void) {ElementType x; // 保存 Node 中的 data 數據List p;List head;head = NULL;scanf("%d", &x);while (x != -1) {p = (List)malloc(sizeof(struct Node));p->data = x;if (head == NULL) { // 若第一次創建節點，則將該點設置為頭節點head = p;p->Next = NULL;} else { // 若不是第一次創建節點，則直接將新節點接到鏈表頭p->Next = head;head = p;}scanf("%d", &x);}return head; }

2 尾插法

2.1 尾插法建表規則：

該算法是將新節點插到當前鏈表的表尾上，為此必須增加一個尾指針rear，使其始終指向當前鏈表的尾節點

2.2 尾插法建表代碼實現：

/* 創建鏈表 - 尾插法 - 有頭節點+------+ +------+ +------+| head | -> |node_1| -> |node_2| ____+------+ +------+ +------+ |v+------+ +------+| rear | -> | p |+------+ +------+*/ 思想：新增一個尾指針rear,將新結點插入到表尾，尾指針始終指向head便于建表 List TailCreate(void) {ElementType x; // 保存 Node 中的 data 數據List p;List head; // 頭結點List rear; // 因為尾插法需要在尾部插入，所以要有個指針來保存尾的位置head = (List)malloc(sizeof(struct Node));head->Next = NULL;head = rear; // 鏈表為空，頭和尾指向同一個位置scanf("%d", &x);while (x != -1) {p = (List)malloc(sizeof(struct Node));p->data = x;rear->Next = p;rear = p;}rear->Next = NULL; // 鏈表建立結束后將最后一個節點指向 NULLreturn head; }/* 創建鏈表 - 尾插法 - 沒有頭節點 +------+ +------+ +------+|node_1| -> |node_2| -> |node_3| ____+------+ +------+ +------+ |v+------+ +------+| rear | -> | p |+------+ +------+*/ List TailCreate(void) {ElementType x;List p;List head;List rear;head = NULL;rear = NULL;scanf(%d, &x);while (x != -1) {p = (List)malloc(sizeof(struct Node));p->data = x;if (head == NULL) { // 創建鏈表的第一個節點head = p;rear = p;p->Next = NULL;} else {rear->Next = p;rear = p;}scanf("%d", &x);}rear->Next = NULL; // 鏈表建立結束后將最后一個節點指向 NULL（尾插法中不要遺漏）return head; }

總結

以上是生活随笔為你收集整理的头插法和尾插法创建链表（有无头结点）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。