C語(yǔ)言?超詳細(xì)順序表的模擬實(shí)現(xiàn)實(shí)例建議收藏
概念及結(jié)構(gòu)
順序表是用一段物理地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線(xiàn)性結(jié)構(gòu)，一般情況下采用數(shù)組存儲(chǔ)。在數(shù)組 上完成數(shù)據(jù)的增刪查改。
順序表一般可以分為：
靜態(tài)順序表：使用定長(zhǎng)數(shù)組存儲(chǔ)元素，元素的數(shù)目無(wú)法進(jìn)行修改。
//順序表的靜態(tài)存儲(chǔ)
#define N 7
typedef int SLDataType;
typedef struct SeqList
{
SLDataType array[N];//定長(zhǎng)數(shù)組
size_t size;//有效數(shù)據(jù)的個(gè)數(shù)
}SeqList;動(dòng)態(tài)順序表
//順序表的動(dòng)態(tài)存儲(chǔ)
typedef struct SeqList
{
SLDataType* array;//指向動(dòng)態(tài)開(kāi)辟的數(shù)組，空間不夠可以增容
size_t size;//有效數(shù)據(jù)的個(gè)數(shù)
size_t capacity;//容量空間的大小
};接口實(shí)現(xiàn)
靜態(tài)順序表只適用于確定知道需要存多少數(shù)據(jù)的場(chǎng)景。靜態(tài)順序表的定長(zhǎng)數(shù)組導(dǎo)致N定大了，空間開(kāi)多了浪 費(fèi)，開(kāi)少了不夠用。所以現(xiàn)實(shí)中基本都是使用動(dòng)態(tài)順序表，根據(jù)需要?jiǎng)討B(tài)的分配空間大小，所以下面我們實(shí)現(xiàn)動(dòng)態(tài)順序表。
1 順序表的動(dòng)態(tài)存儲(chǔ)
typedef int SLDataType;//順序表中存儲(chǔ)的數(shù)據(jù)，此處假設(shè)是int型
typedef struct SeqList
{
int* a;//指向動(dòng)態(tài)開(kāi)辟的數(shù)組空間，空間可以隨時(shí)增容
int size;//存儲(chǔ)數(shù)據(jù)個(gè)數(shù)
int capacity;//存儲(chǔ)空間大小
}SL,SeqList;2 順序表初始化
void SeqListInit(SeqList* psl);//聲明
void SeqListInit(SeqList* psl)
{
assert(psl);//進(jìn)行斷言是因?yàn)楫?dāng)psl為NULL時(shí)，下面的操作將無(wú)法進(jìn)行，因?yàn)榭罩羔樖菬o(wú)法進(jìn)行解引用的。
psl->a = NULL;
psl->size = 0;
psl->capacity = 0;
}//函數(shù)實(shí)現(xiàn)注意：進(jìn)行斷言是因?yàn)楫?dāng)psl為NULL時(shí)，下面的操作將無(wú)法進(jìn)行，因?yàn)榭罩羔樖菬o(wú)法進(jìn)行解引用的，后面也是如此。
3 順序表的銷(xiāo)毀
void SeqListDestroy(SeqList* psl);
void SeqListDestroy(SeqList* psl)
{
assert(psl);
free(psl->a);
psl->a = NULL;
psl->capacity = psl->size = 0;
}注意：free后面括號(hào)中的指針必須是malloc開(kāi)辟出來(lái)的那塊空間，且不能有任何的偏差（即指針不能發(fā)生移動(dòng)）。
下面進(jìn)行舉例：
像上面這樣使用是完全沒(méi)有問(wèn)題的，但是像下面這樣進(jìn)行使用就出現(xiàn)了問(wèn)題：
tmp進(jìn)行自增操作后，就指向了下圖所示位置：
free的位置是tmp++后的位置，這不符合C語(yǔ)言的規(guī)定，且即使正常的釋放掉了，前面的那一塊int空間也將引起內(nèi)存泄漏問(wèn)題，即動(dòng)態(tài)開(kāi)辟的內(nèi)存忘記釋放。
4 順序表的尾插
void SeqListPushBack(SeqList* psl,SLDataType x);//聲明
void SeqListPushBack(SeqList* psl, SLDataType x)
{
assert(psl);
//如果滿(mǎn)了，就進(jìn)行擴(kuò)容
SeqListCheckCapacity(psl);
psl->a[psl->size] = x;
psl->size++;
}
5 順序表的尾刪
void SeqListPopBack(SeqList* psl);
void SeqListPopBack(SeqList* psl)
{
assert(psl);
if(psl->size > 0)
{
psl->size -= 1;
}
}6 順序表的頭插
void SeqListPushFront(SeqList* psl, SLDataType x);
void SeqListPushFront(SeqList* psl, SLDataType x)
{
assert(psl);
SeqListCheckCapacity(psl);
int end = psl->size - 1;
while (end >= 0)
{
psl->a[end+1] = psl->a[end];
--end;
}
psl->a[0] = x;
psl->size++;
}順序表的頭插會(huì)涉及到后續(xù)元素的移動(dòng)，頭插時(shí)要將順序表中的元素從后面開(kāi)始進(jìn)行移動(dòng)，因?yàn)閺那懊骈_(kāi)始移動(dòng)的話(huà)會(huì)出現(xiàn)覆蓋現(xiàn)象。下面是圖示：
7 順序表的頭刪
同理，如果想要元素不被覆蓋，就只能從前向后進(jìn)行移動(dòng)。
void SeqListPopFront(SeqList* psl);
void SeqListPopFront(SeqList* psl)
{
//挪出數(shù)據(jù)，騰出頭部空間
//方法一：從1開(kāi)始移動(dòng)
/*assert(psl);
if (psl->size > 0)
{
int begin = 1;
while (begin < psl->size)
{
psl->a[begin - 1] = psl->a[begin];
begin++;
}
psl->size--;
}*/
//方法二：從0開(kāi)始移動(dòng)
assert(psl);
if (psl->size > 0)
{
int begin = 0;
while (begin < psl->size - 1)
{
psl->a[begin] = psl->a[begin + 1];
begin++;
}
psl->size--;
}
}下圖是兩種移動(dòng)方式的區(qū)別：
問(wèn)：為什么不可以直接將指針進(jìn)行加1操作？
- free釋放空間時(shí)的指針和malloc開(kāi)辟空間的指針必須相同
- mallo開(kāi)辟的空間存在浪費(fèi)，即0的那塊空間被浪費(fèi)，無(wú)法進(jìn)行使用，因?yàn)槟菈K空間是被合法申請(qǐng)的。
8 順序表容量的檢查與擴(kuò)容
void SeqListCheckCapacity(SeqList* psl);
void SeqListCheckCapacity(SeqList* psl)
{
assert(psl);
if (psl->capacity == psl->size)
{
size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
SLDataType* tmp = (SLDataType*)realloc(psl->a, sizeof(SLDataType) * newCapacity);
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
else
{
psl->a = tmp;
psl->capacity *= 2;
}
}
}注意點(diǎn)1：此處考慮使用的是如果容量不夠，就將容量擴(kuò)容為原容量的兩倍，但是最開(kāi)始的容量是0，所以要考慮到最開(kāi)始為0的情況。
注意點(diǎn)2：要對(duì)擴(kuò)容是否成功進(jìn)行檢測(cè)，即判斷剛申請(qǐng)的空間是否為空。
9 順序表任意位置的插入
void SeqListInsert(SeqList* psl,size_t pos,SLDataType x);
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
assert(psl);
//較為溫和的檢查方式
/*if (pos > psl->size)
{
exit(-1);
}*/
assert(pos <= psl->size);//較為暴力的檢查方式
SeqListCheckCapacity(psl);
size_t end = psl->size;
while (end > pos)
{
psl->a[end] = psl->a[end-1];
--end;
}
psl->a[pos] = x;
psl->size++;
}注意：
問(wèn)：為什么end從psl->size開(kāi)始？
答：此處需要注意的是pos和end的類(lèi)型，為什么呢？因?yàn)閮烧叨际菬o(wú)符號(hào)類(lèi)型，所以尤其注意當(dāng)end到了-1的時(shí)候，就會(huì)變成一個(gè)很大的數(shù)字，此時(shí)如果以此作為下標(biāo)進(jìn)行訪(fǎng)問(wèn)，一定會(huì)出現(xiàn)越界訪(fǎng)問(wèn)內(nèi)存的情況，考慮一種極端情況，當(dāng)pos為0的時(shí)候，end最小的時(shí)候就是為0，所以此時(shí)不會(huì)出現(xiàn)越界的情況，但是如果end是從psl->size - 1開(kāi)始的話(huà)，那么while循環(huán)體內(nèi)的語(yǔ)句就變成下面這樣：
while(end > pos)
{
psl->a[end+1] = psl->a[end];
--end;
}最后end的最小值會(huì)變成-1，但是因?yàn)閑nd是size_t類(lèi)型，所以會(huì)變成一個(gè)很大的數(shù)字，在whle()循環(huán)條件判定時(shí)條件始終是滿(mǎn)足的，同時(shí)在進(jìn)入循環(huán)體內(nèi)之后，會(huì)出現(xiàn)越界訪(fǎng)問(wèn)內(nèi)存的操作。所以?xún)煞N情況的圖如下所示：
10 順序表任意位置的刪除
void SeqListErase(SeqList* psl, size_t pos);
void SeqListErase(SeqList* psl, size_t pos)
{
assert(psl);
assert(pos <= psl->size);
size_t begin = pos+1;
while (begin < psl->size)
{
psl->a[begin-1] = psl->a[begin];
++begin;
}
psl->size--;
}11 順序表的打印
void SeqListPrint(SeqList* psl);
void SeqListPrint(SeqList* psl)
{
assert(psl);
for (int i = 0; i < psl->size; i++)
{
printf("%d ", psl->a[i]);
}
printf("\n");
}12 順序表元素的查找
int SeqListFind(SeqList* psl,SLDataType x);
int SeqListFind(SeqList* psl, SLDataType x)
{
assert(psl);
for (int i = 0; i < psl->size; i++)
{
if (psl->a[i] == x)
return i;//找到了對(duì)應(yīng)元素，返回相應(yīng)的下標(biāo)
}
return -1;//說(shuō)明沒(méi)有找到對(duì)應(yīng)的元素
}13 順序表元素的修改
void SeqListModify(SeqList* psl, size_t pos, SLDataType x);
void SeqListModify(SeqList* psl, size_t pos, SLDataType x)
{
assert(psl);
assert(pos < psl->size);
psl->a[pos] = x;
}到此這篇關(guān)于C語(yǔ)言 超詳細(xì)順序表的模擬實(shí)現(xiàn)實(shí)例建議收藏的文章就介紹到這了,更多相關(guān)C語(yǔ)言 順序表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
QPainter是Qt的一個(gè)繪圖類(lèi)，它的主要任務(wù)是在繪圖設(shè)備上進(jìn)行2D圖形渲染，這篇文章主要介紹了qt中 painter 的用法以及原理,需要的朋友可以參考下2023-07-07
C++用opengl繪制出的二維坐標(biāo),簡(jiǎn)單明了,很容易理解,下面這篇文章主要給大家介紹了關(guān)于如何利用OpenGL畫(huà)坐標(biāo)軸指示圖的相關(guān)資料,需要的朋友可以參考下2022-01-01
C語(yǔ)言的數(shù)據(jù)結(jié)構(gòu)之樹(shù)、森連、二叉樹(shù)之間的轉(zhuǎn)換圖解
這篇文章主要介紹了C語(yǔ)言的數(shù)據(jù)結(jié)構(gòu)之樹(shù)、森連、二叉樹(shù)之間的轉(zhuǎn)換詳解,數(shù)據(jù)是信息的載體，是描述客觀(guān)事物屬性的數(shù)、字符以及所有能輸入到計(jì)算機(jī)中并被程序識(shí)別和處理的符號(hào)的集合,需要的朋友可以參考下2023-07-07
Linux頁(yè)面置換算法的C語(yǔ)言實(shí)現(xiàn)
這篇文章主要為大家詳細(xì)介紹了Linux頁(yè)面置換算法的C語(yǔ)言實(shí)現(xiàn)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-12-12
VSCode無(wú)法打開(kāi)源文件及無(wú)法打開(kāi)鏈接庫(kù)文件的解決方法
本文主要介紹了VSCode無(wú)法打開(kāi)源文件及無(wú)法打開(kāi)鏈接庫(kù)文件的解決方法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2022-06-06
這篇文章主要介紹了C++(STL庫(kù))之順序容器vector的使用，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-02-02
這篇文章主要介紹了C++ string字符串類(lèi)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-03-03
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)圖的鄰接矩陣表示，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-04-04
本文詳細(xì)講解了C語(yǔ)言Make命令用法，文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-01-01
俄羅斯方塊寫(xiě)過(guò)好幾次了，每次的感覺(jué)都不一樣，都有新的收獲。就像達(dá)芬奇畫(huà)雞蛋一樣，雖然都是畫(huà)同樣的雞蛋，但是每次都有不同的收獲。 2016-05-05