目錄
1.?線性表
2. 順序表概念及分類
2.1 順序表的概念
2.2 順序表分類
2.3 動靜態順序表對比
3. 順序表的實現（附完整版代碼）
3.1 順序表結構體聲明
3.2?初始化&銷毀
3.3?插入（尾插、頭插、指定位置之前插入）
3.4?擴容
3.5?刪除（尾刪、頭刪、指定位置刪除）
3.6?查找（查找數據下標）
4. 順序表實現通訊錄（附完整版代碼）
4.1?前向聲明
4.2 通訊錄結構體聲明&順序表結構體修改
4.3 初始化&銷毀（直接調用順序表）
4.4 添加聯系人（直接調用順序表）
4.5 刪除聯系人
4.6 修改聯系人信息
4.7 查找聯系人
5. 通訊錄保存到文件
5.1 保存函數和加載函數
5.2 通訊錄初始化和銷毀函數修改
1.?線性表
????????線性表（linear list）是n個具有相同特性的數據元素的有限序列。 線性表是一種在實際中廣泛使用的數據結構，常見的線性表：順序表、鏈表、棧、隊列、字符串...
????????線性表在邏輯上是線性結構，也就說是連續的一條直線。但是在物理結構上并不一定是連續的，線性表在物理上存儲時，通常以數組和鏈式結構的形式存儲。（物理結構就是物理上的存儲結構）
????????案例：蔬菜分為綠葉類、瓜類、菌菇類。線性表指的是具有部分相同特性的一類數據結構的集合如何理解邏輯結構和物理結構？
2. 順序表概念及分類
2.1 順序表的概念
????????順序表和數組的區別：順序表的底層結構是數組，對數組的封裝，實現了常用的增刪改查等接口。
? ? ? ? 順序表的特性：邏輯結構是連續的，物理結構是連續的（順序表底層是數組，數組是連續的）。
2.2 順序表分類
????????順序表分為靜態順序表和動態順序表。
????????靜態順序表：使用定長數組存儲元素
struct SeqList
{int arr[100];// 定長數組int size; // 順序表當前有效的數據個數
};????????動態順序表：動態內存開啟，數組大小可以動態調整。
struct SeqList
{int* arr; // 指向動態內存開辟的空間int size; // 順序表當前有效的數據個數int capacity;// 動態申請的空間大小
};2.3 動靜態順序表對比
| 靜態順序表 | 動態順序表 |
| 數組給小了，空間不夠用；數組給大了，空間浪費。 | 動態增容 |
? ? ? ? 動態順序表相比于靜態順序表有很大優勢。
3. 順序表的實現（附完整版代碼）
? ? ? ? 完整版順序表實現代碼：【免費】順序表-C語言實現代碼資源-CSDN下載
3.1 順序表結構體聲明
? ? ? ? 順序表的結構體一般有三個成員變量：存儲的數據的類型的指針（重定義以下，方便以后對其他類型使用）、順序表當前有效數據的個數、動態申請的空間的大小。
? ? ? ? 同時可以給順序表結構體重定義，方便以后使用。
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLDataType; // 類型重定義，方便以后修改為其他類型的數據typedef struct SeqList
{SLDataType* arr;// 指向動態內存開辟的空間int size; // 順序表當前有效的數據個數int capacity; // 動態申請的空間大小
}SL; // 重定義結構體類型名，方便以后使用3.2?初始化&銷毀
// 順序表初始化
void SLInit(SL* ps)
{ps->arr = NULL;ps->size = ps->capacity = 0;
}// 順序表銷毀
void SLDestory(SL* ps)
{if (ps->arr){free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;
}3.3?插入（尾插、頭插、指定位置之前插入）
? ? ? ? 順序表插入分為：尾插、頭插、指定位置之前插入。
? ? ? ? 每次插入之前要判斷現有空間是否足夠，不夠時要進行擴容，見3.4節。
? ? ? ? 實現了SLInsert指定位置之前插入之后，可以直接復用到尾插、頭插中。
注意：
? ? ? ? 1. 插入時要對傳入的指針判斷，避免傳入指針為空指針，可以用assert斷言。
? ? ? ? 2. 指定位置之前插入的形參pos要進行判斷，插入的位置是否在順序表內部。如果不在內部執行插入時可能會越界訪問導致程序出錯。
//順序表尾插
void SLPushBack(SL* ps, SLDataType x)
{assert(ps); // 避免這種情況的發生SLPushBack(NULL, 2);SLCheckCapacity(ps);ps->arr[ps->size++] = x;
}//順序表頭插
void SLPushFront(SL* ps, SLDataType x)
{assert(ps); // 避免這種情況的發生SLPushBack(NULL, 2);SLCheckCapacity(ps);// 順序表中的內容整體往后挪動一位for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;ps->size++;//SLInsert(ps, 0, x);
}//指定位置之前插入數據
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps); // 避免這種情況的發生SLPushBack(NULL, 2);assert(pos >= 0 && pos <= ps->size); // 確保pos在ps->arr的里面SLCheckCapacity(ps);for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;
}3.4?擴容
? ? ? ? 在順序表空間不夠時需要擴容，每一種插入都要判斷擴容，所以將擴容單獨寫成一個函數。
? ? ? ? 擴容的規則：動態增容，一般以2倍或3倍的形式增加。
// 擴容
void SLCheckCapacity(SL* ps)
{if (ps->size == ps->capacity){ // 申請空間int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;int* tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * newCapacity);if (tmp == NULL){perror("realloc");exit(1); // 直接退出程序，不在繼續執行}ps->arr = tmp;ps->capacity = newCapacity;}
}3.5?刪除（尾刪、頭刪、指定位置刪除）
? ? ? ? 順序表的刪除分為：尾刪、頭刪、指定位置刪除。
注意：
? ? ? ? 1. 頭刪、尾刪要保證順序表不為空。
? ? ? ? 2. 指定位置刪除，要保證pos在順序表內部，否則可能出現越界訪問導致程序運行出錯。
// 尾刪
void SLPopBack(SL* ps)
{assert(ps);assert(ps->size);//保證順序表不為空ps->size--;
}// 頭刪
void SLPopFront(SL* ps)
{assert(ps);assert(ps->size);//保證順序表不為空for (int i = 0; i < ps->size-1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}//指定位置刪除數據
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >=0 && pos < ps->size);for (int i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}3.6?查找（查找數據下標）
? ? ? ? 沒查找到時，確保返回值不在ps->size內部。
// 查找數據的位置
int SLFind(SL* ps, SLDataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x)return i;}return -1;
}4. 順序表實現通訊錄（附完整版代碼）
? ? ? ? 完整通訊錄實現代碼：【免費】通訊錄程序實現-C語言順序表實現資源-CSDN下載
4.1?前向聲明
4.1.1 前向聲明是什么？
????????定義：在類型完整定義出現之前，先聲明其存在的機制
????????本質：告訴編譯器"這個類型存在，具體細節稍后提供"
????????前向聲明是C/C++解決類型聲明與定義分離的核心機制，通過允許"先聲明后定義"：
????????????????1. 解決了頭文件循環依賴問題
????????????? ? 2. 實現了接口與實現的分離
? ? ? ? ? ? ? ? 3. 提高了編譯效率和代碼可維護性
C 語言允許 只聲明一個結構體類型而不提供完整定義（稱為“不完全類型”或“前向聲明”）。typedef struct SeqList Contact; 只是告訴編譯器：struct SeqList 是一個合法的類型（但暫時不知道它的具體內容）。Contact 是它的別名。編譯器不需要知道 struct SeqList 的完整定義，只要知道它是一個有效的類型名即可。4.1.2 前向聲明的關鍵特性
| 特性 | 說明 | 示例 |
| 不完整類型 | 編譯器知道類型存在，但不知道其大小和結構 | struct SeqList; |
| 延遲定義 | 具體定義可以稍后提供 | Contact.h聲明→SeqList.h定義 |
| 指針友好 | 可以創建指向該類型的指針 | Contact* ptr; |
| 成員不可訪問 | 不能訪問結構體成員 | c.size = 10; // 會報錯 |
4.1.3?為什么這種設計有效？
????????單向依賴：
????????????????SeqList.h → 需要 Contact.h（因使用 peoInfo）
????????????????Contact.h → 不需要 SeqList.h（只需聲明 struct SeqList 存在）
????????編譯過程：
????????????????編譯 Contact.h 時：知道 struct SeqList 是合法類型名
????????????????編譯 SeqList.h 時：已獲得 peoInfo 的完整定義
????????????????最終使用者（如 main.c）同時包含兩者，獲得完整信息
4.1.4 前向聲明使用規則
? ? ? ? 1. 允許的操作
????????????????? 僅需類型名（不訪問成員）
????????????????? 定義類型別名：typedef struct S T;
????????????????? 函數參數/返回值：void func(struct S*);
????????????????? 聲明指針/引用：struct S* p;
? ? ? ? 2. 禁止的操作
????????????????? 實例化對象：struct S obj;
????????????????? 訪問成員：p->member = 0;
????????????????? 計算大小：sizeof(struct S)
????????????????? 非指針類型成員：struct X { struct S s; };
????????3. 核心原則
????????????????只聲明類型存在，不提供結構細節
????????????????必須在使用前提供完整定義
????????????????主要用于打破頭文件循環依賴
????????4. 典型用途
????????????????解決相互依賴：A.h 和 B.h 互相引用時
????????????????隱藏實現：接口聲明指針，實現文件定義結構體
????????????????減少編譯依賴：避免不必要頭文件包含
4.1.5?Contach.h 和 SeqList.h 頭文件包含問題
? Contact.h 不需要包含 SeqList.h
????????因為 typedef struct SeqList Contact; 只是聲明，不涉及 struct SeqList 的成員訪問。
? SeqList.h 必須包含 Contact.h
????????因為它用到了 peoInfo 的具體定義（typedef peoInfo SLDataType;）。
4.2 通訊錄結構體聲明&順序表結構體修改
1. 順序表頭文件修改（arr數組修改為存入數據的類型即可）
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include"Contact.h"//typedef int SLDataType; // 類型重定義，方便以后修改為其他類型的數據
typedef peoInfo SLDataType;
// 動態順序表
typedef struct SeqList
{SLDataType* arr;// 指向動態內存開辟的空間int size; // 順序表當前有效的數據個數int capacity; // 動態申請的空間大小
}SL; // 重定義結構體類型名，方便以后使用2.通訊錄結構體聲明（注意前向聲明，見4.1詳解）
// 宏定義通訊錄成員數組的最大長度
#define NAME_MAX 20
#define GENDER_MAX 10
#define TEL_MAX 20
#define ADDR_MAX 100// 通訊錄結構體聲明
typedef struct personInfo
{char name[NAME_MAX];char gender[GENDER_MAX];int age;char tel[TEL_MAX];char addr[ADDR_MAX];
}peoInfo;// 要用到順序表相關的方法，對通訊錄的實際操作就是對順序表進行操作
// 給順序表起個名字，叫做通訊錄
// 前向聲明
typedef struct SeqList Contact;4.3 初始化&銷毀（直接調用順序表）
//初始化通訊錄
void ContactInit(Contact* con)
{// 實際上要進行的是順序表的初始化// 順序表的初始化已經實現好了，直接調用即可SLInit(con);
}//銷毀通訊錄數據
void ContactDestroy(Contact* con)
{SLDestory(con);
}4.4 添加聯系人（直接調用順序表）
//添加通訊錄數據
void ContactAdd(Contact* con)
{peoInfo info;printf("請輸入要添加的聯系人姓名:");scanf("%s", info.name);printf("請輸入要添加的聯系人性別:");scanf("%s", info.gender);printf("請輸入要添加的聯系人年齡:");scanf("%d", &info.age);printf("請輸入要添加的聯系人電話:");scanf("%s", info.tel);printf("請輸入要添加的聯系人地址:");scanf("%s", info.addr);// 往通訊錄中添加數據SLPushBack(con, info);printf("添加成功\n\n");
}4.5 刪除聯系人
? ? ? ? 需要確定：按照什么方式查找要刪除的數據（此處按照姓名查找，字符串比較要用strcmp，調用FindByName函數找到對應姓名的下標）
? ? ? ? 找到下標后，調用順序表的指定位置刪除函數。
int FindByName(Contact* con, char* name)
{for (int i = 0; i < con->size; i++){if (strcmp(con->arr[i].name, name) == 0)return i;}return -1;
}//刪除通訊錄數據
void ContactDel(Contact* con)
{// 要刪除的數據必須存在才可以執行刪除操作char name[NAME_MAX];printf("請輸入要刪除的數據的姓名：");scanf("%s", name);int find = FindByName(con, name);if (find == -1){printf("要刪除的數據的姓名不存在!!\n\n");return;}SLErase(con, find);printf("刪除成功！\n\n");
}4.6 修改聯系人信息
? ? ? ? 通過FindByName()查找到要修改的聯系人姓名的下標之后，直接scanf修改。
//修改通訊錄數據
void ContactModify(Contact* con)
{char name[NAME_MAX];printf("請輸入要修改的數據的姓名：");scanf("%s", name);int find = FindByName(con, name);if (find == -1){printf("要修改的數據的姓名不存在!!\n\n");return;}printf("請輸入新的姓名：");scanf("%s", con->arr[find].name);printf("請輸入新的性別：");scanf("%s", con->arr[find].gender);printf("請輸入新的年齡：");scanf("%d", &con->arr[find].age);printf("請輸入新的電話：");scanf("%s", con->arr[find].tel);printf("請輸入新的住址：");scanf("%s", con->arr[find].addr);printf("修改成功！\n\n");
}4.7 查找聯系人
????????調用FindByName函數，找到下標后打印對應的聯系人信息。
//查找通訊錄數據
void ContactFind(Contact* con)
{char name[NAME_MAX];printf("請輸入要查找的數據的姓名：");scanf("%s", name);int find = FindByName(con, name);if (find == -1){printf("要查找的數據的姓名不存在!!\n\n");return;}// 姓名 性別 年齡 電話 地址printf("找到了！！\n");printf("%5s %5s %5s %5s %5s\n", "姓名", "性別", "年齡", "電話", "地址");printf("%4s %5s %5d %5s %5s\n\n",con->arr[find].name,con->arr[find].gender,con->arr[find].age,con->arr[find].tel,con->arr[find].addr);
}
5. 通訊錄保存到文件
5.1 保存函數和加載函數
? ? ? ? 注意，加載函數中的添加通訊錄數據是用的 SLPushBack() 函數。
//保存通訊錄
void ContactSave(Contact* con)
{FILE* pf = fopen("contact.txt", "wb");if (pf == NULL){perror("fopen");return;}// 將通訊錄數據寫入文件for (int i = 0; i < con->size; i++){// 此處用二進制寫入fwrite(con->arr + i, sizeof(peoInfo), 1, pf);printf("寫入第%d個數據\n", i + 1);}printf("通訊錄數據保存成功！\n");
}//加載通訊錄數據
void ContactLoad(Contact* con)
{FILE* pf = fopen("contact.txt", "rb");if (pf == NULL){perror("fopen");return;}peoInfo info;while (fread(&info, sizeof(peoInfo), 1, pf)){SLPushBack(con, info);}printf("歷史數據導入成功\n");
}
5.2 通訊錄初始化和銷毀函數修改
? ? ? ? 初始化需要讀取文件中的數據，銷毀前需要保存修改后的通訊錄數據。
//初始化通訊錄
void ContactInit(Contact* con)
{// 實際上要進行的是順序表的初始化// 順序表的初始化已經實現好了，直接調用即可SLInit(con);ContactLoad(con); // 讀取文件中的通訊錄數據
}//銷毀通訊錄數據
void ContactDestroy(Contact* con)
{ContactSave(con); // 保存修改后的通訊錄數據到文件中SLDestory(con);
}
