文章目錄1.結(jié)構(gòu)體與接口(SqList.h)2.完整實現(xiàn)(SqList.c)3.測試(test.c)1.結(jié)構(gòu)體與接口(SqList.h)#pragmaonce// SqList.h 一般這些接口函數(shù)聲明放到.h中// 下面的接口函數(shù)的實現(xiàn)放到SqList.cpp中#includestdio.h#includestdlib.h#includestdbool.h#includeassert.hstructSnakeData{introw;intcol;// ...};// typedef是為了方便類型替換//typedef SnakeData SqDataType; // 數(shù)據(jù)元素類型typedefintSqDataType;// 數(shù)據(jù)元素類型// typedef struct SequenceList{typedefstruct{SqDataType*arr;// 存儲數(shù)據(jù)的動態(tài)數(shù)組的指針intsize;// 記錄順序表中已經(jīng)存入的數(shù)據(jù)個數(shù)intcapacity;// 動態(tài)數(shù)組的容量空間的大小}SqList;// 初始化順序表voidSqListInit(SqList*ps);// 有些書本上的用法//void SqListInit(SqList s);// 銷毀順序表voidSqListDestroy(SqList*ps);// 返回順序表中第i個下標位置元素的值SqDataTypeGetElem(SqList*ps,inti);// 返回第一個等于x的數(shù)據(jù)元素的下標若不存在返回-1intLocateElem(SqList*ps,SqDataType x);// 書本i通常是位序位序是從1開始// 我們實現(xiàn)的時候i用的是下標// 在順序表的第i個位置插入元素xvoidSqListInsert(SqList*ps,inti,SqDataType x);// 刪除順序表中第i個元素并返回刪除的值SqDataTypeSqListDelete(SqList*ps,inti);// 打印順序表中的元素voidSqListPrint(SqList*ps);// 檢測順序表是否為空空返回true否則返回falseboolEmptySqList(SqList*ps);// 獲取順序表中有效元素個數(shù)intSqListSize(SqList*ps);// 以下接口復用上面的Insert和Delete即可完成// 頭插尾插voidSqListPushBack(SqList*ps,SqDataType x);voidSqListPushFront(SqList*ps,SqDataType x);// 頭刪尾刪voidSqListPopBack(SqList*ps);voidSqListPopFront(SqList*ps);2.完整實現(xiàn)(SqList.c)/* * SqList.c * 動態(tài)順序表Sequential List各接口函數(shù)的實現(xiàn)。 * * 對應的聲明見 SqList.hSqList 結(jié)構(gòu)體由 arr動態(tài)數(shù)組指針、size有效元素 * 個數(shù)、capacity容量三個成員組成SqDataType 為數(shù)據(jù)元素類型目前是 int。 * * 本文件統(tǒng)一約定 * 1. 參數(shù) i 一律表示“下標”從 0 開始插入時 i 的合法范圍是 [0, size] * 刪除/讀取時是 [0, size-1]注意與書本上從 1 開始的“位序”不同。 * 2. 每個函數(shù)入口都用 assert 檢查 ps 非空便于在調(diào)試期盡早發(fā)現(xiàn)空指針。 * 3. 擴容策略容量不足時按原來的 2 倍申請新空間使連續(xù)插入的均攤復雜度為 O(1)。 * * 說明以下注釋均是在原代碼基礎上新增的原代碼的邏輯與順序沒有做任何改動。 */#define_CRT_SECURE_NO_WARNINGS1// 初始化順序表#includeSqList.h// 初始化與銷毀 /* * SqListInit —— 初始化順序表 * param ps 指向待初始化的順序表 * 初始申請可容納 4 個元素的動態(tài)數(shù)組并把 size 置 0、capacity 置 4。 * 若內(nèi)存申請失敗則打印錯誤信息并直接返回此時 arr 為 NULL。 */voidSqListInit(SqList*ps){assert(ps);// 初始容量為 4申請 4 個 SqDataType 大小的連續(xù)堆空間ps-arr(SqDataType*)malloc(sizeof(SqDataType)*4);if(ps-arrNULL){//申請失敗則退出printf(InitSqList: 內(nèi)申請空間失敗 !!!\n);//exit(-1);return;}// 記錄有效元素個數(shù)與當前容量ps-size0;ps-capacity4;}/* * SqListDestroy —— 銷毀順序表 * 釋放動態(tài)數(shù)組占用的堆空間并把 arr 置為 NULL、size 與 capacity 清零 * 避免留下懸空指針重復調(diào)用本函數(shù)也是安全的。 */voidSqListDestroy(SqList*ps){assert(ps);// arr 非空說明空間申請成功過需要釋放if(ps-arr){free(ps-arr);// 釋放后復位成員避免后續(xù)誤用已釋放的內(nèi)存ps-size0;ps-capacity0;ps-arrNULL;}}/* * SqListInsert —— 在下標 i 處插入元素 x * param ps 指向順序表 * param i 插入位置的下標合法范圍 [0, size]i size 即尾插 * param x 待插入的數(shù)據(jù)元素 * 若容量已滿先按 2 倍擴容再把下標 [i, size-1] 的元素整體后移一位 * 空出下標 i 的位置放入 x最后 size 加 1。時間復雜度 O(n)。 */voidSqListInsert(SqList*ps,inti,SqDataType x){assert(ps);// 下標合法性檢查i 可以等于 size尾插但不能越界assert(i0ips-size);// 容量已滿需要先擴容if(ps-sizeps-capacity){// 用 realloc 把容量擴大為原來的 2 倍結(jié)果先存入 tmp避免丟失原指針SqDataType*tmp(SqDataType*)realloc(ps-arr,sizeof(SqDataType)*ps-capacity*2);// 擴容失敗realloc 返回 NULL原空間仍然有效直接返回if(tmpNULL){printf(SqListInsert:內(nèi)存申請空間失敗!!!\n);return;}// 擴容成功更新數(shù)組指針與容量ps-arrtmp;ps-capacity*2;}// 從后往前把 [i, size-1] 的元素依次后移一位騰出下標 i 的位置for(intjps-size-1;ji;j--){ps-arr[j1]ps-arr[j];}// 在騰出的位置寫入 x并讓有效元素個數(shù)加 1ps-arr[i]x;ps-size;}/* * SqListDelete —— 刪除下標 i 處的元素 * param ps 指向順序表 * param i 待刪除元素的下標合法范圍 [0, size-1] * return 被刪除的元素值 * 先保存被刪元素再把 [i1, size-1] 的元素整體前移一位覆蓋它最后 size 減 1。 * 時間復雜度 O(n)。 */SqDataTypeSqListDelete(SqList*ps,inti){assert(ps);// 下標合法性檢查刪除時 i 必須落在 [0, size-1] 內(nèi)assert(i0ips-size);// 先保存被刪除的元素用于返回SqDataType xps-arr[i];// 把 i 之后的元素依次前移一位覆蓋被刪除的元素for(intji1;jps-size;j){ps-arr[j-1]ps-arr[j];}// 有效元素個數(shù)減 1ps-size--;returnx;}/* * SqListPrint —— 打印順序表中的所有元素 * 按下標從 0 到 size-1 的順序輸出元素之間用空格分隔末尾不換行。 */voidSqListPrint(SqList*ps){assert(ps);// 按下標順序遍歷并輸出每個元素for(inti0;ips-size;i){printf(%d ,ps-arr[i]);}}/* * SqListPushFront —— 頭插在下標 0 處插入元素 x * 相當于 SqListInsert(ps, 0, x)這里單獨實現(xiàn)以便觀察“元素整體后移”的過程。 * 容量不足時同樣按 2 倍擴容。 */voidSqListPushFront(SqList*ps,SqDataType x){assert(ps);// 容量已滿按 2 倍策略擴容與 SqListInsert 中的處理一致if(ps-sizeps-capacity){// realloc 擴容失敗時保留原空間直接返回SqDataType*tmp(SqDataType*)realloc(ps-arr,sizeof(SqDataType)*ps-capacity*2);if(tmpNULL){printf(SqListInsert:內(nèi)存申請空間失敗!!!\n);return;}ps-arrtmp;ps-capacity*2;}// 把所有元素整體后移一位騰出下標 0 的位置for(intjps-size-1;j0;j--){ps-arr[j1]ps-arr[j];}// 下標 0 放入 x并讓有效元素個數(shù)加 1ps-arr[0]x;ps-size;}/* * SqListPushBack —— 尾插在順序表末尾追加元素 x * 相當于 SqListInsert(ps, size, x)不需要移動已有元素時間復雜度 O(1)。 * 容量不足時按 2 倍擴容。 */voidSqListPushBack(SqList*ps,SqDataType x){assert(ps);// 容量已滿按 2 倍策略擴容if(ps-sizeps-capacity){SqDataType*tmp(SqDataType*)realloc(ps-arr,sizeof(SqDataType)*ps-capacity*2);if(tmpNULL){printf(SqListInsert:內(nèi)存申請空間失敗!!!\n);return;}ps-arrtmp;ps-capacity*2;}// 下標 size 正好是末尾的空閑位置寫入 x 后讓 size 加 1ps-arr[ps-size]x;ps-size;}/* * SqListPopFront —— 頭刪刪除下標 0 處的元素 * 把 [1, size-1] 的元素整體前移一位再讓 size 減 1時間復雜度 O(n)。 * 本函數(shù)不檢查順序表是否為空調(diào)用前應保證 size 0。 */voidSqListPopFront(SqList*ps){assert(ps);// 從前往后把后一個元素覆蓋到前一個位置for(intj0;jps-size-1;j){ps-arr[j]ps-arr[j1];}// 有效元素個數(shù)減 1ps-size--;}/* * SqListPopBack —— 尾刪刪除順序表末尾的元素 * 只需把 size 減 1時間復雜度 O(1)被“刪除”的空間會在下次插入時被覆蓋。 */voidSqListPopBack(SqList*ps){assert(ps);// size 減 1 即視為刪除末尾元素底層數(shù)組空間不釋放ps-size--;}/* * LocateElem —— 查找元素 x 第一次出現(xiàn)的下標 * return 找到時返回對應下標不存在時返回 -1 * 采用順序查找時間復雜度 O(n)。 */intLocateElem(SqList*ps,SqDataType x){assert(ps);// 從下標 0 開始逐個比較找到第一個相等的元素就返回其下標for(intj0;jps-size;j){if(xps-arr[j])returnj;}// 遍歷結(jié)束仍未找到返回 -1return-1;}/* * EmptySqList —— 判斷順序表是否為空 * return size 0 時返回 true否則返回 false */boolEmptySqList(SqList*ps){assert(ps);returnps-size0;}/* * SqListSize —— 獲取順序表中有效元素的個數(shù) * return 當前 size 的值 */intSqListSize(SqList*ps){assert(ps);returnps-size;}/* * GetElem —— 獲取下標 i 處的元素值 * param i 下標合法范圍 [0, size-1] * return 下標 i 處的數(shù)據(jù)元素 * 時間復雜度 O(1)。 */SqDataTypeGetElem(SqList*ps,inti){assert(ps);// 下標合法性檢查越界時 assert 會在調(diào)試版中觸發(fā)assert(i0ips-size);returnps-arr[i];}3.測試(test.c)#define_CRT_SECURE_NO_WARNINGS1#includeSqList.hvoidTestSqList1(){SqList L;SqListInit(L);SqListInsert(L,0,9);SqListInsert(L,1,10);SqListInsert(L,2,20);SqListInsert(L,3,30);SqListInsert(L,4,40);SqListInsert(L,5,50);// 擴容SqListPrint(L);// 頭插SqListInsert(L,0,0);SqListPrint(L);// 尾插SqListInsert(L,SqListSize(L),60);SqListPrint(L);// 中間插入SqListInsert(L,2,2);SqListPrint(L);}voidTestSqList2(){SqList L;SqListInit(L);SqListInsert(L,0,9);SqListInsert(L,1,10);SqListInsert(L,2,20);SqListInsert(L,3,30);SqListInsert(L,4,40);SqListInsert(L,5,50);// 擴容SqListPrint(L);// 刪除順序表第1位置上的元素printf(順序表中有效元素個數(shù)為: %d \n,SqListSize(L));// 刪除第一個數(shù)據(jù)printf(刪除的元素是:%d \n,SqListDelete(L,0));// 刪除末尾的數(shù)據(jù)printf(刪除的元素是:%d \n,SqListDelete(L,SqListSize(L)-1));// 刪除中間的數(shù)據(jù)printf(刪除的元素是:%d \n,SqListDelete(L,2));SqListPrint(L);printf(順序表中第%d個元素是: %d\n,1,GetElem(L,1));printf(40 的下標是%d\n,LocateElem(L,40));SqListDestroy(L);}intmain(){TestSqList1();//TestSqList2();return0;}