C語言實現線性表：順序存儲與鏈式存儲完整指南

線性表的兩種存儲結構

線性表是數據結構中最基礎、最常用的結構之一。在C語言中，線性表主要有兩種存儲方式：順序存儲（動態數組）和鏈式存儲（單鏈表）。本文將詳細解析這兩種實現方式的核心操作，並提供完整的C語言代碼示例。

一、 順序存儲結構實現

順序存儲利用一段連續的內存空間依次存放線性表的元素。為了實現動態擴容，我們定義了一個包含數據指針、當前長度和最大容量的結構體：

typedef int elemType;
struct List {
    elemType *list;    // 數據指針
    int size;          // 當前長度
    int maxSize;       // 最大容量
};

核心操作解析

1. 動態擴容機制

當數組空間不足時，againMalloc 函數使用 realloc 將空間擴大為原來的兩倍：

void againMalloc(struct List *L) {
    elemType *p = realloc(L->list, 2 * L->maxSize * sizeof(elemType));
    if (!p) { printf("存儲空間分配失敗！"); exit(1); }
    L->list = p;
    L->maxSize *= 2;
}

2. 基本操作集（16種算法）

• 初始化/銷毀：initList 分配初始空間，clearList 釋放內存並歸零。
• 查詢操作：sizeList 返回長度，emptyList 判空，getElem 按位置取值（下標從1開始），traverseList 遍歷輸出。
• 查找與修改：findList 順序查找返回下標（0-based），updatePosList 按位置修改值。
• 插入操作：inserFirstList（頭插）、insertLastList（尾插）、insertPosList（指定位置插入）、insertOrderList（有序表插入保持有序）。插入前均檢查是否需要擴容。
• 刪除操作：deleteFirstList（刪頭）、deleteLastList（刪尾）、deletePosList（刪指定位置）、deleteValueList（刪第一個值為x的元素）。刪除後元素前移填補空缺。

測試主函數

main 函數演示了初始化容量為5的表，連續尾插10個元素（觸發擴容），頭插、指定位置插入、查找、修改、多種刪除操作，最後清空銷毀。

二、 鏈式存儲結構實現（單鏈表）

單鏈表通過指針鏈接離散的節點，每個節點包含數據域和指向下一節點的指針：

struct sNode {
    elemType data;
    struct sNode *next;
};

核心操作解析

1. 初始化與銷毀

initList 將頭指針置NULL；clearList 遍歷釋放所有節點。

2. 基本操作集（16種算法）

• 屬性查詢：sizeList 遍歷計數，emptyList 判頭指針是否為NULL。
• 元素訪問：getElem 遍歷到第pos個節點返回數據，traverseList 遍歷輸出。
• 查找與修改：findList 返回匹配節點的數據地址，updatePosList 定位第pos個節點修改數據。
• 插入操作：insertFirstList（頭插法）、insertLastList（尾插需遍歷到尾節點）、insetPosList（指定位置插入，處理頭插情況）、insertOrderList（有序插入）。
• 刪除操作：deleteFirstList（刪頭節點）、deleteLastList（刪尾節點，需記錄前驅）、deletePosList（刪指定位置）、deleteValueList（刪第一個值為x的節點）。均需釋放被刪節點內存。

綜合應用示例

main 函數生成隨機數，通過頭插法建立鏈表（逆序），去重（雙重循環刪除後續重複值），最後用有序插入構建有序鏈表，展示了單鏈表的靈活應用。

總結與對比

選擇哪種結構取決於具體應用場景：頻繁隨機訪問選順序表，頻繁插入刪除且長度變化大選鏈表。