1、頭插法:
流程:1 ,判斷傳入數據是否正確 2,如果正確則創建一個新的節點,并判斷節點是否創建成功 3,然后給節點成員變量賦值 4,最后讓新節點變為鏈表的第一個節點。
代碼實現:
// 鏈表的頭插
int Insert_Head(Node** h, LinkData data)
{//判斷傳入數據是否正確if (NULL == h){return FALSE;}// 創建新的節點Node* node = (Node*) malloc(sizeof(Node) / sizeof(char));if (NULL == node) // 判斷節點創建是否成功{return FALSE;}// 給節點成員變量賦值node->data = data;node->next = *h;// 讓新節點變為鏈表的第一個節點*h = node;return TRUE;
}
2、尾插法:
流程:1,首先判斷傳入數據是否正確 2,如果正確則創建一個新的節點并判斷節點是否創建成功 3,然后給成員變量賦值 4,找到最后一個節點(創建一個tmp指向第一個節點,遍歷整個鏈表,最終指向最后一個節點),尋找最后一個節點時要判斷是否為空表。
代碼:
// 鏈表的尾插
int Insert_Last(Node** h, LinkData data)
{if (NULL == h){return FALSE;}// 創建新的節點Node* node = (Node*) malloc(sizeof(Node) / sizeof(char));if (NULL == node) // 判斷節點創建是否成功{return FALSE;}// 給節點成員變量賦值node->data = data;node->next = NULL;// 找到最后一個節點Node* tmp = *h; // 指向第一個節點if (NULL == tmp) // 空表{*h = node;}else {while (tmp->next){tmp = tmp->next;}tmp->next = node;}return TRUE;
}
3、中間插法(在第pos個節點處插入):
流程:1,判斷傳入數據是否正確、pos是否符合題意 2,如果正確則創建新節點 3,給變量成員賦值 4,判斷是否是空表,如果是空表,則只能插在第一個節點處(需判斷pos的值),如果不是空表,需要單獨考慮插到第一節點處,然后判斷pos是否會越界,找到插入位置的前一個節點(利用第三個指針遍歷到pos前一個位置),然后執行插入(插入前要判斷遍歷后的tmp是否為空)。
代碼:
// 在第pos個位置處插入數據
int Insert_Pos (Node** h, int pos, LinkData data)
{// 判斷傳入數據是否正確,插入位置是否大于1if (NULL == h || pos < 1){return FALSE;}// 創建新節點Node* node = (Node*) malloc(sizeof(Node) / sizeof(char));if (NULL == node){return FALSE;}// 給新節點賦值node->data = data;// 判斷是否為空表,如果是空表則插在第一個節點處if (NULL == *h){if (1 != pos) // 空表時判斷pos是否為1{printf ("當前為空表,無法在第%d節點處插入數據\n", pos);free(node);return FALSE;}node->next = NULL; // 插入第一個節點處*h = node;}// 不為空表時else{if (1 == pos){node->next = *h;*h = node;}else{int i;Node* tmp = *h; // tmp 開始的時候指向第一個節點for (i = 0; i < pos - 2; i++){if (NULL == tmp) // 如果pos太大會造成越界{break;}tmp = tmp->next;}if (NULL == tmp){printf ("插入位置越界\n");free(node);return FALSE;}node->next = tmp->next;tmp->next = node;}}return TRUE;
}
最后附上頭文件,宏定義,結構體聲明和主函數:
#include <stdio.h>
#include <stdlib.h>#define TRUE 1
#define FALSE 0typedef int LinkData; // 鏈表的數據類型typedef struct _node
{LinkData data; // 鏈表的數據struct _node* next; // 指向鏈表的下一個指針
}Node;int main()
{Node* head = NULL; //指向鏈表第一個結點的指針(頭指針)int i;for (i = 0; i < 10; i++){Insert_Head(&head, i);//Insert_Last(&head, i);//Insert_Pos (&head, pos, i);}return 0;
}