單鏈表學習（一）
- 2019 年 10 月 3 日
- 筆記
關於鏈表的概念，原理，具備的優點和缺點，以及示意圖等這裡就不過多介紹了。書本上或者百度上，其他博主上都可以了解學習。我主要分享鏈表的一些基礎算法。
直接進入主題吧。
今天分享的是關於鏈表頭節點和數據節點的創建。
我們創建一個鏈表，一般來說都會創建一個頭節點，頭節點裏面不放然後數據，只需要在指針裏面放入下一個數據節點的內存地址就行了，當我們需要訪問數據節點的時候就從頭節點開始依次訪問後面的每一個數據節點。
下面就開始創建頭節點,
創建頭節點
#include<iostream> #include<stdlib.h> //調用malloc函數實現動態地址的分配 using namespace std; struct node //結構體 { int a; //節點用來存放數據 struct node *next; //用來存放下一個節點的地址 }; int main() { node *head; //定義了一個結構體指針始終用來指向頭節點 node *p; //定義了一個結構體指針P用來分配內存空間實現節點的創建 p = (node *)malloc(sizeof(struct node)); //用malloc函數實現節點的創建，其中malloc函數前面需要指明數據類型，結構體是一個數據類型，後面是分配多大的內存，我們通過sizeof計算結構體的大小 p->next = NULL; //我們還沒有創建數據節點，所以頭節點的next不能存放下一個節點的地址，所以賦值NULL head = p;//將頭節點的地址給head,讓頭指針始終指向頭節點 return(0); }
上面的代碼成功的創建了一個頭節點，並且頭節點裏面的next指針為NULL(空），head成功指向了頭節點。如果頭節點裏面放了下一個數據節點的內存地址，可以通過head->next去得到下一個數據節點的內存地址，從而實現訪問下一個數據節點。
頭節點創建好了之後，我們開始創建數據節點。
關於創建數據節點一般有兩種方法。
第一種每次創建一個數據節點的時候都直接在頭節點後面創建，這樣創建出來的鏈表它的數據節點是倒過來的。最後的在最前面，最先建的在最後面，大家可以想想這個畫面。
每次在頭節點後面創建數據節點，我們需要完成的操作有：
1.讓新創建的數據節點指向它後面的數據節點(也就是比他先創建的數據節點）
2.讓頭節點指向新創建的數據節點
這樣就實現了有序的鏈表創建
如下圖所示，首先創建了頭節點，然後再頭節點後面插入數據節點1，然後繼續再頭節點後面插入數據節點2
我將創建節點寫在了函數裏面，當然也可以直接放在主函數裏面，具體需要看你的代碼複雜程度。
void node_creat(node *head,int n) //第一個參數用來接收指向頭節點的head指針來找到頭節點的位置，第二個參數用來接收需要創建多少個數據節點 { node *p; int i; for (i = 1; i <= n; i++) { p = (node *)malloc(sizeof(struct node)); cin >> p->a; //創建的數據節點需要賦值 p->next = head->next; //將頭節點指向的數據節點地址給新節點，讓新節點指向頭節點指向的節點，如果頭節點後面沒有數據節點，則將NULL給創建的節點。 head->next = p;//在將新創建的節點的地址給頭節點，使頭節點指向它 } }
通過上面代碼實現了第一種數據節點的創建。
第二種數據節點的創建不是每次都在頭節點後面創建而是依次創建，如創建了第一個數據節點後，就在第一個數據節點後面繼續創建第二個數據節點，這樣我們的數據節點就不是倒着的了。
實現上面的創建方法也同樣很簡單，但是需要多用一個指針來指向每次創建的數據節點，通過這個指針來賦值內存地址。就好像是在頭節點後面創建的時候，我們都是用head指針實現創建是一樣的。
void node_creat(node *head,int n) { node *p; node *q; //q指針用來指向每次創建的新數據節點 q = head; //首先讓q指針指向頭節點 int i; for (i = 1; i <= n; i++) { p = (node *)malloc(sizeof(struct node)); cin >> p->a; p->next = q->next; //將q指向的數據節點的值給新創建的數據節點，實際上就是將NULL給了新數據節點的next.因為這樣的創建新的數據節點每次都是在最後一個。 q->next = p;//同樣的，讓q指向的數據節點指向新創建的數據節點 q = q->next;//創建好了之後q移到到新創建的數據節點，又開始在它的後面繼續創建 } }
今天分享了關於單鏈表頭節點的創建和數據節點創建的兩種形式，後面將繼續分享單鏈表的其他基礎算法
