文章目錄
- 1. 鏈表是什么？
- 2. 佇列和堆疊
- 3. 頭插法和尾插法
- 4.實踐創建堆疊和佇列（各部分代碼）
- ??4.1 定義一個鏈表的結構體
- ??4.2 在main函式中定義鏈表的一系類指標
- ??4.3 for回圈實作尾插法建立鏈表
- ??4.4 for回圈實作頭插法建立鏈表
- ??4.5 for回圈實作遍歷鏈表
- 5.實踐創建堆疊和佇列（完整代碼）
1. 鏈表是什么？
??鏈表是一種物理存盤單元上非連續、非順序的存盤結構，資料元素的邏輯順序是通過鏈表中的指標鏈接次序實作的，鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成，每個結點包括兩個部分：一個是存盤資料元素的資料域，另一個是存盤下一個結點地址的指標域，
??畫一張易于理解的簡圖如下，矩形代表存放的是資料，橢圓代表存放的是指標，鏈表的頭必須是一個指標，
??使用鏈表結構可以克服陣列需要預先知道資料大小的缺點，鏈表結構可以充分利用計算機記憶體空間，實作靈活的記憶體動態管理，但是鏈表失去了陣列隨機讀取的優點，同時鏈表由于增加了結點的指標域，空間開銷比較大，鏈表最明顯的好處就是，常規陣列排列關聯專案的方式可能不同于這些資料專案在記憶體或磁盤上順序，資料的存取往往要在不同的排列順序中轉換，鏈表允許插入和移除表上任意位置上的節點，但是不允許隨機存取，
??上面的圖說明了鏈表的原理，下面是鏈表的存盤方式，鏈表在記憶體中是非連續、非順序的，就是說鏈表結點在記憶體中的存放并不是一個接一個，按順序存放的，
??這里我們可以發現，如果想要訪問鏈表中某一結點的話，必須從head開始查找，并不像陣列那樣方便，
2. 佇列和堆疊
?? 佇列是限定只能在表的一端進行插入和在另一端進行洗掉操作的線性表；
??堆疊是限定只能在表的一端進行插入和洗掉操作的線性表，
??簡而言之佇列就是資料先進先出（first in first out,FIFO）;而堆疊則是先進后出（first in last out,FILO）
3. 頭插法和尾插法
??頭插法和尾插法顧名思義，就是在鏈表加入新結點的時候是在頭部插入還是在尾部插入，
??簡易的示意圖如下，黑色箭頭是插入新結點之前的鏈表順序，紅線是插入新結點后的鏈表順序，
??可以看到尾插法不改變鏈表的原本順序，在遍歷鏈表的時候，正好就對應了佇列的先進先出的特性；頭插法會改變鏈表原本的順序，在遍歷鏈表的時候也是正好對應了堆疊的先進后出的特性，
??所以我們就用頭插法的鏈表來實作堆疊；尾插法的鏈表來實作佇列，理論存在，實踐開始！
4.實踐創建堆疊和佇列（各部分代碼）
??4.1 定義一個鏈表的結構體
typedef struct node_s //定義鏈表的結構
{
int data; //資料域
struct node_s *next //指標域
}node_t；
??4.2 在main函式中定義鏈表的一系類指標
node_t *head = NULL; //初始化頭指標為空指標
node_t *new_node; //創建一個新結點的指標
node_t *tail; //創建一個鏈表的尾指標
node_t *front; //創建一個鏈表的頭指標
int count; //計數器
??4.3 for回圈實作尾插法建立鏈表
for(count = 0; count < 10; count++) //用一個for回圈來回圈創建新的結點，
{
new_node = malloc(sizeof(node_t));//malloc申請一塊記憶體給新結點并存在指標中
memset(new_node, 0, sizeof(*new_node));//清理新結點記憶體
new_node->next = NULL; //新結點的指標域設為空
new_node->data = i+1; //新結點的資料域放入數值
/*到這里新結點的建立就完成了，下面是尾插法的邏輯實作*/
if( head == NULL)
{
head = new_node;//若頭指標為空，則是第一個結點，直接用頭指標指向
}
else
{
tail->next = new_node;//否則尾結點的指標域指向新結點
}
tail = new_node; //尾指標指向新插入的結點
}
??4.4 for回圈實作頭插法建立鏈表
for(i = 0; i < 10; i++) //用一個for回圈來回圈創建新的結點，
{
new_node = malloc(sizeof(node_t));//malloc申請一塊記憶體給新結點并存在指標中
memset(new_node, 0, sizeof(*new_node));//清理新結點記憶體
new_node->next = NULL; //新結點的指標域設為空
new_node->data = i+1; //新結點的資料域放入數值
/*到這里新結點的建立就完成了，下面是頭插法的邏輯實作*/
if( head == NULL)
{
head = new_node;//若頭指標為空，則是第一個結點，直接用頭指標指向它
}
else
{
front = head; //用front保留住上一個鏈表的地址
new_node->next = front; //新鏈表的尾部指向上一個鏈表的頭
head = new_node; //head指向新建鏈表的頭
}
}
??4.5 for回圈實作遍歷鏈表
for(prt = head; prt != NULL; prt = prt->next) //回圈實作遍歷
{
printf("%d\n", prt->data); //列印每個節點的資料
}
5.實踐創建堆疊和佇列（完整代碼）
??整合上面各部分的代碼，包含malloc、memset和printf的頭檔案，再用上條件編譯，完整的代碼如下：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define INSERT_BEHIND //定義了這行就用尾插擦，注釋這行就用頭插法
typedef struct node_s //定義鏈表結構
{
int data; //鏈表的資料域
struct node_s *next; //鏈表的指標域
} node_t; //重定義結構體node_s為node_t
int main (int argc, char **argv)
{
node_t *head = NULL; //初始化鏈表的頭指向nowhere
node_t *new_node; //新結點的指標
node_t *tail; //鏈表的尾指標
node_t *front; //鏈表的頭指標
int MagnetoF; // 計數器（author of this passage: MagnetoF）
#ifdef INSERT_BEHIND //條件編譯：定義了INSTER_BEHIND就使用尾插法實作佇列的資料結構
for( MagnetoF = 0; MagnetoF < 8; MagnetoF++) //回圈創建鏈表
{
new_node = malloc(sizeof(node_t) ); //創建一塊記憶體，并用new_node指標標記
memset(new_node, 0, sizeof(*new_node) ); //清空申請的記憶體
new_node->next = NULL; //新鏈表的尾部指向nowhere
new_node->data = MagnetoF+1; //把資料域放入相應的值
if(head == NULL)
{
head = new_node; //若頭指標為空，則是第一個結點，頭指標指向新結點
}
else
{
tail->next = new_node; //非首個結點，尾結點的指標域指向新結點
}
tail = new_node; //尾指標指向新的結點
}
#else //未定義INSERT_BEHIND時，使用頭插法
for( MagnetoF = 0; MagnetoF < 8; MagnetoF++) //這里創建新鏈表的for回圈和尾插法一樣
{
new_node = malloc(sizeof(node_t) );
memset(new_node, 0, sizeof(*new_node) );
new_node->next = NULL;
new_node->data = MagnetoF+1;
if(head == NULL) //這里開始是頭插法的關鍵
{
head = new_node;
}
else
{
front = head; //用front保留住上一個鏈表的地址
new_node->next = front; //新鏈表的尾部指向上一個鏈表的頭
head = new_node; //head指向新建鏈表的頭
}
}
#endif
node_t *prt;
for(prt = head; prt != NULL; prt = prt->next) //回圈實作遍歷
printf("%d\n", prt->data);
return 0;
}
??在Ubuntu18.04下用gcc編譯分別生成“list_FIFO”（尾插法實作佇列）和“list_FILO”（頭插法實作堆疊），兩者運行的結果如下：
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/249797.html
標籤：其他