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