一、概念

可以更合理使用內存
提高程序的執行效率

C語言本質是操作內存

數據對象、數據元素、數據項

（一）數據結構的三元素

1. 邏輯結構

（1）線性結構

一對一的關系
數據連續

（2）非線性結構

樹型：
一對多

圖：
多對多

2. 存儲結構

數據在計算機尤其是內存中的存儲方式

（1）順序存儲

（2）鏈式存儲

（3）索引存儲

3. 運算

算法：有限步驟內解決問題的方法
算法不依賴于編程語言
特點：

1. 有窮性
2. 確定性
3. 可行性
4. 有0個或多個輸入，有一個或多個輸出

標準：

1. 正確性
2. 易讀性
3. 健壯性：對非法數據的處理能力
4. 高效性
5. 低存儲

（二）時間復雜度

算法的時間復雜度定義為算法中可執行語句的頻度之和 記作 T(n)
語句頻度是指同一代碼執行的次數
T(n)是算法所需時間的一種估值，n 表示問題的規模

算法的時間復雜度的表示方式為：
O(頻度); ----------稱為 大 O 表示法

假設有三段代碼：
a 的時間復雜度為 2
b 的時間復雜度為 2n
c 的時間復雜度為2n^2
如果a、b、c組成一段程序，
那么算法的時間復雜度為
T(n) =T (2+2n+2n^2)
業內表示方法 還需T (2+2n+2n^2)要對進行簡化

使用大O表示法的簡化流程：
1.去掉運行時間中的所有常數項。
（例如 2+2n+2n^2，直接變為 2n+2n^2）
2.保留最高次冪項。
（2n^2+2n 變成 2n^2）
3.最高項存在但是系數不是1，則把系數置為1。
（2n^2 系數為2 去掉系數 n^2 ）

所以，最終a、b和c合并而成的代碼的時間復雜度為O(n^2)。

1. 線性階

O(n)

2. 常數階

O(1)

3. 平方階

O(n^2)

4. 三次方階

O(n^3)

5. 對數階

O(logn)

6. 時間復雜度排序

O(1)< O(logn) < O(n) < O(nlogn) < O(n^2) <O(n^3) <O(2^n) <O(n!) < O(n^n)

可以帶一個數測試，如問題規模n是16
1 < 4 < 16 < 64 < 256 < 4096 < 65536 < 16! < 16^16

二、順序表

（一）邏輯結構

線性結構

（二）存儲結構

順序存儲
內存中連續的空間

（三）操作

• 目的：封裝成函數，供他人使用
• 結構體定義：

//節點結構體定義
typedef struct node
{int data; //此處以int為例，可自行添加其他成員
}Nd_t;
//列表結構體定義
typedef struct list
{int count; //記錄當前存入了多少個值Nd_t listArr[MAX_SIZE]; 
}Ls_t;

1. 創建順序表

（1）返回值是創建的順序表

list_t *create_list_1();

（2）參數傳入想要創建的順序表

① 函數聲明

int create_list(Ls_t **list);

② 注意點：

1. 參數必須傳入二級指針（需要改變main函數中的指針的值）
2. 首先需要判定傳入函數的指針是否為一個空指針（因為接下來第一件事是要使用*list來接malloc的返回值，如果傳入的是一個空指針，會報段錯誤，所以需要提前檢查）
3. 需要判定申請空間是否成功（申請失敗會返回NULL）

③代碼實現

//創建順序表并初始化
int create_list(Ls_t **list)
{if(NULL==list)//判定傳入的指針是否是一個空指針{printf("申請空間失敗\n");return -1;}//申請內存空間*list=(Ls_t *)malloc(sizeof(Ls_t));if(NULL==*list)//申請空間失敗{printf("申請空間失敗\n");return -1;}//初始化(*list)->count=0; memset(*list,0,sizeof(Ls_t));return 0;
}

• 補充：memset函數

#include <string.h>
void *memset(void *s, int c, size_t n);
//s 要置值的內存首地址
//c 用于置值的值
//n 置值的大小

2. 插入元素（尾插、任意位置插入）

（1）尾插

① 函數聲明

int insert_list_by_tail(Ls_t *list,int num);

② 注意點：

1. 需要判定傳入的順序表指針是否是空指針
2. 需要判定順序表是否已滿
3. 插入成功后，count++

③代碼實現

//在尾部插入數據
int insert_list_by_tail(Ls_t *list,int num)
{if(NULL == list) {printf("操作的表不存在\n");return -1;}if(MAX_SIZE == list->count){printf("順序表已滿\n");return -1;}//插入數據list->listArr[list->count].data=num;//順序表存入數據的數量+1list->count++;return 0;
}

（2）任意位置插入

① 函數聲明

int insert_list(Ls_t *list,int pos,int num);

② 注意點：

1. 需要判定傳入的順序表指針是否是空指針
2. 需要判定順序表是否已滿
3. 判定插入位置是否合法，需要大于零，且需要保證順序表內存空間連續
4. 插入成功后，count++

③代碼實現

int insert_list(Ls_t *list,int pos,int num)
{if(NULL == list) {printf("操作的表不存在\n");return -1;}if(MAX_SIZE == list->count){printf("順序表已滿\n");return -1;}if(pos < 0 || pos > list->count){printf("插入位置違法\n");return -1;}//從后往前，依次向后移動一位，直到到達插入位置int i=list->count;while(i!=pos){list->listArr[i]=list->listArr[i-1];i--;}//插入數據list->listArr[pos].data=num;//順序表存入數據的數量+1list->count++;return 0;
}

3. 刪除元素（尾刪、任意位置刪除）

（1）尾刪

① 函數聲明

int delete_list_by_tail(Ls_t *list);

② 注意點：

1. 需要判定傳入的順序表指針是否是空指針
2. 需要判定順序表是否已滿
3. 直接count–即可，不必去清空值，此時原來的位置相當于已經聲明可以繼續寫入數據

③代碼實現

int delete_list_by_tail(Ls_t *list)
{if(NULL == list) {printf("操作的表不存在\n");return -1;}if(0==list->count){printf("順序表為空\n");return -1;}list->count--;return 0;
}

（2）任意位置刪除

① 函數聲明

int delete_list(Ls_t *list,int pos);

② 注意點：

1. 需要判定列表指針是否是空指針
2. 判斷表是否為空
3. 判定刪除位置是否合法，需要大于零，且小于順序表當前容納值的數量；
4. 刪除成功后，count需要減一

③代碼實現

int delete_list(Ls_t *list,int pos)
{if(NULL == list) {printf("操作的表不存在\n");return -1;}if(0==list->count){printf("順序表為空\n");return -1;}if(pos<0||pos>=list->count){printf("刪除位置違法\n");return -1;}for(int i=pos;i<list->count;i++){list->listArr[i]=list->listArr[i+1];}list->count--;return 0;
}

4. 修改指定位置

① 函數聲明

int modify_list(Ls_t *list,int pos,int num);

② 注意點：

1. 需要判定列表指針是否是空指針
2. 判斷表是否為空
3. 判定修改位置是否合法，需要大于零，且小于順序表當前容納值的數量；

③代碼實現

int modify_list(Ls_t *list,int pos,int num)
{if(NULL == list) {printf("操作的表不存在\n");return -1;}if(0==list->count){printf("順序表為空\n");return -1;}if(pos<0||pos>=list->count){printf("修改位置違法\n");return -1;}list->listArr[pos].data=num;return 0;
}

5. 查找指定位置

① 函數聲明

int search_list(Ls_t *list,int pos,int *num);

② 注意點：

1. 需要判定列表指針是否是空指針
2. 判定查詢位置是否合法，需要大于零，且小于順序表當前容納值的數量；

③代碼實現

int search_list(Ls_t *list,int pos,int *num)
{if(NULL == list) {printf("操作的表不存在\n");return -1;}if(0==list->count){printf("順序表為空\n");return -1;}if(pos<0||pos>=list->count){printf("查詢位置違法\n");return -1;}*num=list->listArr[pos].data;return 0;
}

6. 清空順序表

① 函數聲明

int clean_list(Ls_t *list);

② 注意點：

1. 需要判定列表指針是否是空指針
2. 只需將count置0即可，各函數都是根據count來進行操作，因此即使原來順序表的值并未清空也不影響

③代碼實現

int clean_list(Ls_t *list)
{if(NULL == list) {printf("操作的表不存在\n");return -1;}list->count=0;return 0;
}

7. 銷毀順序表

① 函數聲明

int destroy_list(Ls_t **list);

② 注意點：

1. 需要先確保傳入的指針并非空指針，再去判斷*list是否為空
2. 釋放完堆區的空間后，再將main函數中的指針置為NULL

③代碼實現

int destroy_list(Ls_t **list)
{if(NULL == list) {printf("操作的指針不存在\n");return -1;}if(NULL == *list) {printf("操作的表不存在\n");return -1;}free(*list);*list=NULL;return 0;
}

8. 排序

① 函數聲明

int sort_list(Ls_t *list,int s);

② 注意點：

1. 先確保傳入的指針并非空指針
2. 判斷表是否為空
3. 第二個參數為0是正序排序，否則倒序排序

③代碼實現

int sort_list(Ls_t *list,int s)
{if(NULL == list) {printf("操作的表不存在\n");return -1;}if(0==list->count){printf("順序表為空\n");return -1;}int flag=0;for(int i=0;i<list->count-1;i++){flag=0;for(int j=0;j<list->count-1-i;j++){if(0==s){ //正序排序if(list->listArr[j].data>list->listArr[j+1].data){Nd_t temp=list->listArr[j];list->listArr[j]=list->listArr[j+1];list->listArr[j+1]=temp;flag=1;}}else{if(list->listArr[j].data<list->listArr[j+1].data){Nd_t temp=list->listArr[j];list->listArr[j]=list->listArr[j+1];list->listArr[j+1]=temp;flag=1;}}}if(0==flag) break;}return 0;
}

9. 翻轉

① 函數聲明

int overturn_list(Ls_t *list);

② 注意點：

1. 先確保傳入的指針并非空指針
2. 判斷表是否為空

③代碼實現

int overturn_list(Ls_t *list){if(NULL == list) {printf("操作的表不存在\n");return -1;}if(0==list->count){printf("順序表為空\n");return -1;}int i=0,j=list->count-1;Nd_t temp;while(i<j){temp=list->listArr[i];list->listArr[i]=list->listArr[j];list->listArr[j]=temp;i++;j--;}printf("翻轉完成\n");return 0;
}

10. 剔重

① 函數聲明

int dedup_list(Ls_t *list);

② 注意點：

1. 先確保傳入的指針并非空指針
2. 判斷表是否為空
3. 兩側遍歷，第一層是從第一個元素遍歷到倒數第二個元素（j=i+1）；第二層是從第i+1個開始遍歷，然后比較與當前第i個元素是否相等，相等就刪除第j個元素，后面的元素依次向前移動一個位置，此時j無需再自加1

③代碼實現

int dedup_list(Ls_t *list)
{if(NULL == list) {printf("操作的表不存在\n");return -1;}if(0==list->count){printf("順序表為空\n");return -1;}int i,j;for(i=0;i<list->count-1;i++){for(j=i+1;j<list->count;j){if(list->listArr[j].data==list->listArr[i].data){for(int k=j;k<list->count-1;k++){list->listArr[k]=list->listArr[k+1];}list->count--;}else{j++;}}}return 0;
}

11. 打印所有元素

① 函數聲明

int show_list(Ls_t *list);

② 注意點：

1. 需要判定列表指針是否是空指針

③代碼實現

int show_list(Ls_t *list)
{if(NULL == list) {printf("操作的表不存在\n");return -1;}for(int i=0;i<list->count;i++){printf("%d ",list->listArr[i].data);}putchar(10);return 0;
}

（四）使用C語言實現的順序表的源代碼已上傳資源