C語言數據結構基礎：線性表詳解

線性表是數據結構中最基礎、最常用的形式，就像一列整齊排隊的游客：每個元素有固定位置（前驅和后繼），長度可動態變化。在C語言中，它主要通過順序表（數組實現）和鏈表（指針實現）兩種方式構建。理解線性表是掌握棧、隊列等高級結構的基石。本文將深入解析兩者的實現、優缺點及實際應用場景，幫助讀者打下扎實的數據結構基礎。

---

一、順序表：像火車車廂一樣緊密排列

順序表使用連續內存空間存儲元素，類似火車車廂——知道第一節車廂位置，就能快速定位所有車廂。

• 核心特點：地址連續、依次存放、支持隨機存取、所有元素類型相同。
• 代碼實現：使用數組和長度變量管理。

#include <stdio.h>
#define MAX_SIZE 100  // 最大容量typedef struct {int data[MAX_SIZE];  // 存儲數據的數組int length;          // 當前元素數量
} SeqList;// 初始化順序表
void InitList(SeqList *L) {L->length = 0;  // 初始長度為0
}// 插入元素（在位置i插入e）
int Insert(SeqList *L, int i, int e) {if (i < 1 || i > L->length + 1) return 0;  // 位置不合法if (L->length >= MAX_SIZE) return 0;        // 空間已滿// 將i之后的元素后移（從最后一個元素開始移動）for (int j = L->length; j >= i; j--) {L->data[j] = L->data[j-1];}L->data[i-1] = e;  // 插入新元素（索引從0開始）L->length++;       // 長度增加return 1;
}

• 案例演示：假設順序表存儲學生成績 [85, 92, 78]，在位置2插入新成績90：
  1. 位置2及之后的元素后移：[85, _, 92, 78]（空出位置）。
  2. 插入新元素：[85, 90, 92, 78]。
• 優缺點分析：
  • ? 隨機訪問快：通過下標直接定位元素，時間復雜度 $O(1)$。
  • ? 插入/刪除慢：需移動大量元素，時間復雜度 $O(n)$。

---

二、鏈表：像尋寶游戲一樣按線索連接

鏈表元素分散存儲，通過指針連接，類似尋寶地圖——每個地點標注下一個地點的位置。

• 核心特點：元素不連續、通過指針鏈接、支持動態擴展。
• 代碼實現：使用節點結構體管理。

#include <stdlib.h>
typedef struct Node {int data;           // 數據域struct Node *next;  // 指針域（指向下一個節點）
} Node, *LinkList;// 創建新節點
Node* CreateNode(int e) {Node *n = (Node*)malloc(sizeof(Node));n->data = e;n->next = NULL;return n;
}// 在鏈表頭部插入元素
void InsertAtHead(LinkList *L, int e) {Node *newNode = CreateNode(e);newNode->next = *L;  // 新節點指向原頭節點*L = newNode;        // 更新鏈表頭指針
}// 遍歷鏈表
void PrintList(LinkList L) {Node *p = L;while (p != NULL) {printf("%d -> ", p->data);p = p->next;  // 移動到下一個節點}printf("NULL\n");
}

• 案例演示：鏈表存儲任務清單：
  • 初始狀態：買菜 -> 做飯 -> NULL。
  • 頭部插入“取快遞”：取快遞 -> 買菜 -> 做飯 -> NULL。
• 優缺點分析：
  • ? 插入/刪除快：只需修改指針，時間復雜度 $O(1)$。
  • ? 訪問元素慢：需從頭遍歷，時間復雜度 $O(n)$。

---

三、順序表與鏈表的對比與應用場景

下表總結關鍵差異，幫助選擇合適結構：

特性	順序表	鏈表
內存占用	連續緊湊，無額外開銷	分散存儲，有指針開銷
訪問速度	極快（隨機訪問）$O(1)$	慢（順序訪問）$O(n)$
增刪效率	慢（需移動元素）$O(n)$	快（僅改指針）$O(1)$
典型應用	數組計算、矩陣運算	文件系統、瀏覽器歷史記錄

選擇建議：

• 需要頻繁訪問元素（如數據查詢） ? 順序表。
• 需要頻繁插入/刪除（如動態列表管理） ? 鏈表。

---

總結

通過本文，你已掌握線性表的核心：順序表和鏈表各有優勢，是數據結構大廈的基石。實際開發中，結合場景選擇：順序表適合快速訪問，鏈表適合動態操作。后續的棧、隊列等結構均基于此衍生。動手實踐代碼案例，加深理解——數據結構的學習，從線性表開始，步步為營！