C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)深入探索順序表
1.順序表的概念及結(jié)構(gòu)
順序表是使用一段連續(xù)物理地址的單元來(lái)依次儲(chǔ)存數(shù)據(jù)的線性結(jié)構(gòu)，一般采用數(shù)組存儲(chǔ)。在數(shù)組上完成增刪查改。
順序表分為兩類：
靜態(tài)順序表：使用定長(zhǎng)數(shù)組儲(chǔ)存元素
struct SeqList
{
int data;//存儲(chǔ)的數(shù)據(jù)
int size;//記錄數(shù)據(jù)個(gè)數(shù)
int 1000;//給定當(dāng)前順序表的總?cè)萘繛?000
};動(dòng)態(tài)順序表：使用動(dòng)態(tài)開(kāi)辟的數(shù)組存儲(chǔ)
struct SeqList
{
int data;//存儲(chǔ)的數(shù)據(jù)
int size;//記錄數(shù)據(jù)個(gè)數(shù)
int capacity;//順序表的總?cè)萘?
};2.增刪查改的實(shí)現(xiàn)
當(dāng)我們需要儲(chǔ)存的數(shù)據(jù)數(shù)目不確定時(shí)我們使用動(dòng)態(tài)順序表更佳，所以下面就用動(dòng)態(tài)順序表來(lái)實(shí)現(xiàn)增刪查改。
2.1擴(kuò)容
首先我們動(dòng)態(tài)順序表想要實(shí)現(xiàn)自動(dòng)擴(kuò)容，當(dāng)當(dāng)前數(shù)據(jù)量size等于總?cè)萘縞apacity時(shí)我們就需要自動(dòng)增容，具體就是使用malloc函數(shù)開(kāi)辟一定數(shù)量的空間，假如我們?cè)O(shè)定每次擴(kuò)充二倍，代碼如下：
//增容
void SLCheckcapacity(SL* pc)
{
assert(pc != NULL);
//檢查容量，滿了就擴(kuò)容
if (pc->sz == pc->capacity)
{
//一次擴(kuò)容二倍，如果初始為0就先擴(kuò)容到4
int newcapacity = pc->capacity == 0 ? 4 : pc->capacity * 2;
//注意類型轉(zhuǎn)換
SLDatatype* tmp = (SLDatatype*)realloc(pc->data, sizeof(SLDatatype) * newcapacity);
if (tmp == NULL)
{
perror("SLCheckcapacity::realloc");
exit(-1);
}
//講開(kāi)辟的空間tmp給到數(shù)組
pc->data = tmp;
pc->capacity = newcapacity;
}
}2.2插入數(shù)據(jù)
插入數(shù)據(jù)時(shí)我們有三種情況，頭插尾插和中間任意位置插。
2.2.1尾插
先從最簡(jiǎn)單的尾插開(kāi)始，我們尾插時(shí)需要記錄下當(dāng)前的size，這樣插入的時(shí)候就可以直接找到尾部，我們需要注意的是，我們插入之前需要判斷一下當(dāng)前的容量滿了沒(méi)有，如果滿了就需要擴(kuò)容，沒(méi)滿就可以直接插入。
//尾插
void SLPushBack(SL* pc, SLDatatype x)
{
assert(pc != NULL);
//需要判斷是否需要增容
SLCheckcapacity(pc);
pc->data[pc->sz] = x;
pc->sz++;
}2.2.2頭插
頭插相對(duì)來(lái)說(shuō)要復(fù)雜一點(diǎn)，當(dāng)頭上沒(méi)有數(shù)據(jù)時(shí)，我們就可以看成尾插直接插入，當(dāng)頭上有數(shù)據(jù)時(shí)，我們?yōu)榱吮苊鈹?shù)據(jù)的覆蓋，需要將所有數(shù)據(jù)向后移動(dòng)，再放入在頭部，在我們向后移動(dòng)數(shù)據(jù)時(shí)我們也需要判斷是否滿容了。
//頭插
void SLPushFront(SL* pc, SLDatatype x)
{
assert(pc != NULL);
SLCheckcapacity(pc);
//挪動(dòng)數(shù)據(jù)
int end = pc->sz - 1;
while (end >= 0)
{
pc->data[end + 1] = pc->data[end];
--end;
}
//插入數(shù)據(jù)
pc->data[0] = x;
pc->sz++;
}2.2.3任意位置插入
我們?nèi)我馕恢貌迦霑r(shí)有三種情況，當(dāng)在第一個(gè)位置時(shí)就是頭插可以調(diào)用頭插的函數(shù)，在最后一個(gè)位置時(shí)就是尾插，就調(diào)用尾插的函數(shù)，當(dāng)我們?cè)谥虚g的時(shí)我們需要找到需要插入的位置，然后將數(shù)據(jù)從這個(gè)位置開(kāi)始向后挪動(dòng)，再插入進(jìn)去。
//任意位置插入
void SLInsert(SL* pc, int pos, SLDatatype x)
{
assert(pc);
//判斷pos是否在有效數(shù)據(jù)范圍內(nèi)
assert(pos >= 0 && pos <= pc->sz);
SLCheckcapacity(pc);
//挪動(dòng)數(shù)據(jù)
int end = pc->sz - 1;
while (end >= pos)
{
pc->data[end+1] = pc->data[end];
--end;
}
pc->data[pos] = x;
pc->sz++;
}2.3刪除數(shù)據(jù)
刪除數(shù)據(jù)和上面的插入數(shù)據(jù)差不多，我們也需要湊夠三個(gè)方面來(lái)撕開(kāi)，頭部刪除，尾部刪除，中間任意位置刪除，當(dāng)我們刪除數(shù)據(jù)時(shí)我們只需要將這個(gè)數(shù)據(jù)后的數(shù)據(jù)依次向前挪動(dòng)，覆蓋住這個(gè)數(shù)據(jù)即可。這里我們不能用free函數(shù)去釋放那塊地址的空間來(lái)刪除，因?yàn)轫樞虮淼奈锢淼刂肥沁B續(xù)的。鏈表可以，下一章會(huì)介紹。
2.3.1尾刪
尾部后面沒(méi)有數(shù)據(jù)那么就把最后一個(gè)數(shù)據(jù)制成0就好了
//尾刪
void SLPopBack(SL* pc)
{
assert(pc != NULL);
//不能刪多了
assert(pc->sz > 0);
pc->sz--;
}2.3.2頭刪
將從第二個(gè)位置開(kāi)始的數(shù)據(jù)往前挪動(dòng)，這里需要注意，刪除需要檢查，以免越界。
//刪除需要檢查，刪多了會(huì)越界
//頭刪
void SLPopFront(SL* pc)
{
assert(pc != NULL);
//檢查
assert(pc->sz > 0);
//從第二個(gè)元素開(kāi)始從后往前挪直接將其覆蓋
int begin = 0;
while (begin <= pc->sz)
{
pc->data[begin-1] = pc->data[begin];
++begin;
}
pc->sz--;
}2.3.3任意位置刪除
任意位置刪除我們只需要將我們需要?jiǎng)h除的位置后面的數(shù)往前挪動(dòng)就行了
//任意位置刪除
void SLErase(SL* pc, int pos)
{
assert(pc != NULL);
assert(pos >= 0 && pos < pc->sz);
int begin = pos;
while (begin < pc->sz-1)
{
pc->data[begin] = pc->data[begin + 1];
begin++;
}
pc->sz--;
}2.4查找
我們給一個(gè)數(shù)據(jù)x來(lái)表示我們想要查找的數(shù)據(jù)，從前往后把順序表遍歷一遍，當(dāng)給的X等于順序表中的X時(shí)就找到了，返回當(dāng)前位置的下標(biāo)。
//查找
int SLFind(SL* pc, SLDatatype x)
{
assert(pc != NULL);
for (int i = 0; i < pc->sz; ++i)
{
if (pc->data[i] == x)
{
return i;
}
}
printf("找不到\n");
return;
}2.5修改數(shù)據(jù)
當(dāng)我們想要修改某一個(gè)地方的數(shù)據(jù)時(shí)，直接將那個(gè)位置的數(shù)據(jù)輸入新的數(shù)據(jù)覆蓋掉就行了。
//改數(shù)據(jù)
void SlModify(SL* pc, int pos, SLDatatype x)
{
assert(pc != NULL);
if (pos >= 0 && pos <= pc->sz)
{
pc->data[pos] = x;
}
else
{
printf("超出范圍了\n");
}
}2.6銷毀空間
當(dāng)我們順序表使用完成過(guò)后，我們需要注意的是，我們malloc的空間并沒(méi)有得到釋放，可能會(huì)造成內(nèi)存泄漏等問(wèn)題（可參考前面的博客 '動(dòng)態(tài)內(nèi)存開(kāi)辟' ），釋放內(nèi)存就需要用到free函數(shù)
//銷毀空間
void SLDestory(SL* pc)
{
if (pc->data)
{
free(pc->data);
pc->data = NULL;
pc->capacity = pc->sz = 0;
}
}這里就簡(jiǎn)單的給大家介紹了動(dòng)態(tài)順序表的簡(jiǎn)單功能，在這里都是封裝成接口函數(shù)使用的，下一章給大家介紹鏈表的實(shí)現(xiàn)。
到此這篇關(guān)于C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)深入探索順序表的文章就介紹到這了,更多相關(guān)C語(yǔ)言順序表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
詳解C語(yǔ)言的結(jié)構(gòu)體中成員變量偏移問(wèn)題
這篇文章主要介紹了C語(yǔ)言的結(jié)構(gòu)體中成員變量偏移問(wèn)題,以講解如何編寫(xiě)宏來(lái)對(duì)成員變量進(jìn)行修改為主,需要的朋友可以參考下2016-04-04
這篇文章主要給大家介紹了關(guān)于利用C/C++篩選法算素?cái)?shù)的相關(guān)資料，文中給大家列舉了普通枚舉法和篩選法兩種方法實(shí)現(xiàn)的方法示例，文中通過(guò)示例代碼介紹的非常詳細(xì)，需要的朋友可以參考借鑒，下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧。2017-12-12
緩沖區(qū)是一塊連續(xù)的計(jì)算機(jī)內(nèi)存區(qū)域，可保存相同數(shù)據(jù)類型的多個(gè)實(shí)例。緩沖區(qū)可以是堆棧、堆和靜態(tài)數(shù)據(jù)區(qū)。在C/C++語(yǔ)言中，通常使用字符數(shù)組和malloc/new實(shí)現(xiàn)緩沖區(qū)。溢出指數(shù)據(jù)被添加到分配給該緩沖區(qū)的內(nèi)存塊之外。緩沖區(qū)溢出是最常見(jiàn)的程序缺陷2021-06-06
C++萬(wàn)能頭文件它是一個(gè)包含了每一個(gè)標(biāo)準(zhǔn)庫(kù)的頭文件，接下來(lái)通過(guò)本文給大家介紹C++中的萬(wàn)能頭文件及優(yōu)缺點(diǎn),需要的朋友可以參考下2023-02-02
這篇文章主要介紹了C++ 繼承詳解，這里整理了詳細(xì)的資料及實(shí)例代碼，有需要的小伙伴可以參考下2016-09-09
對(duì)C語(yǔ)言中指針的理解與其基礎(chǔ)使用實(shí)例
這篇文章主要介紹了對(duì)C語(yǔ)言中指針的理解與其基礎(chǔ)使用實(shí)例,文中援引了知乎熱門(mén)問(wèn)題"為什么說(shuō)指針是 C 語(yǔ)言的精髓？"中的精彩回答,需要的朋友可以參考下2016-03-03
使用CMake構(gòu)建一個(gè)簡(jiǎn)單的C++項(xiàng)目的實(shí)現(xiàn)
CMake是一個(gè)跨平臺(tái)的自動(dòng)化構(gòu)建工具,可以用于構(gòu)建各種類型的項(xiàng)目,本文主要介紹了使用CMake構(gòu)建一個(gè)簡(jiǎn)單的C++項(xiàng)目，具有一定的參考價(jià)值，感興趣的可以了解一下2023-10-10
這篇文章主要為大家詳細(xì)介紹了C++中關(guān)于特殊類設(shè)計(jì)的相關(guān)知識(shí)，文中的示例代碼講解詳細(xì)，對(duì)我們學(xué)習(xí)C++有一定的幫助，感興趣的可以了解一下2023-07-07
C語(yǔ)言結(jié)構(gòu)體內(nèi)存的對(duì)齊知識(shí)詳解
這篇文章主要介紹了C語(yǔ)言結(jié)構(gòu)體內(nèi)存的對(duì)齊的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03
這篇文章主要介紹了C++如何將運(yùn)行結(jié)果保存到txt中問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-08-08