C語言數(shù)據(jù)結(jié)構(gòu)深入探索順序表
1.順序表的概念及結(jié)構(gòu)
順序表是使用一段連續(xù)物理地址的單元來依次儲存數(shù)據(jù)的線性結(jié)構(gòu)，一般采用數(shù)組存儲。在數(shù)組上完成增刪查改。
順序表分為兩類：
靜態(tài)順序表：使用定長數(shù)組儲存元素
struct SeqList
{
int data;//存儲的數(shù)據(jù)
int size;//記錄數(shù)據(jù)個數(shù)
int 1000;//給定當(dāng)前順序表的總?cè)萘繛?000
};動態(tài)順序表：使用動態(tài)開辟的數(shù)組存儲
struct SeqList
{
int data;//存儲的數(shù)據(jù)
int size;//記錄數(shù)據(jù)個數(shù)
int capacity;//順序表的總?cè)萘?
};2.增刪查改的實現(xiàn)
當(dāng)我們需要儲存的數(shù)據(jù)數(shù)目不確定時我們使用動態(tài)順序表更佳，所以下面就用動態(tài)順序表來實現(xiàn)增刪查改。
2.1擴(kuò)容
首先我們動態(tài)順序表想要實現(xiàn)自動擴(kuò)容，當(dāng)當(dāng)前數(shù)據(jù)量size等于總?cè)萘縞apacity時我們就需要自動增容，具體就是使用malloc函數(shù)開辟一定數(shù)量的空間，假如我們設(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);
}
//講開辟的空間tmp給到數(shù)組
pc->data = tmp;
pc->capacity = newcapacity;
}
}2.2插入數(shù)據(jù)
插入數(shù)據(jù)時我們有三種情況，頭插尾插和中間任意位置插。
2.2.1尾插
先從最簡單的尾插開始，我們尾插時需要記錄下當(dāng)前的size，這樣插入的時候就可以直接找到尾部，我們需要注意的是，我們插入之前需要判斷一下當(dāng)前的容量滿了沒有，如果滿了就需要擴(kuò)容，沒滿就可以直接插入。
//尾插
void SLPushBack(SL* pc, SLDatatype x)
{
assert(pc != NULL);
//需要判斷是否需要增容
SLCheckcapacity(pc);
pc->data[pc->sz] = x;
pc->sz++;
}2.2.2頭插
頭插相對來說要復(fù)雜一點，當(dāng)頭上沒有數(shù)據(jù)時，我們就可以看成尾插直接插入，當(dāng)頭上有數(shù)據(jù)時，我們?yōu)榱吮苊鈹?shù)據(jù)的覆蓋，需要將所有數(shù)據(jù)向后移動，再放入在頭部，在我們向后移動數(shù)據(jù)時我們也需要判斷是否滿容了。
//頭插
void SLPushFront(SL* pc, SLDatatype x)
{
assert(pc != NULL);
SLCheckcapacity(pc);
//挪動數(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有三種情況，當(dāng)在第一個位置時就是頭插可以調(diào)用頭插的函數(shù)，在最后一個位置時就是尾插，就調(diào)用尾插的函數(shù)，當(dāng)我們在中間的時我們需要找到需要插入的位置，然后將數(shù)據(jù)從這個位置開始向后挪動，再插入進(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);
//挪動數(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ù)差不多，我們也需要湊夠三個方面來撕開，頭部刪除，尾部刪除，中間任意位置刪除，當(dāng)我們刪除數(shù)據(jù)時我們只需要將這個數(shù)據(jù)后的數(shù)據(jù)依次向前挪動，覆蓋住這個數(shù)據(jù)即可。這里我們不能用free函數(shù)去釋放那塊地址的空間來刪除，因為順序表的物理地址是連續(xù)的。鏈表可以，下一章會介紹。
2.3.1尾刪
尾部后面沒有數(shù)據(jù)那么就把最后一個數(shù)據(jù)制成0就好了
//尾刪
void SLPopBack(SL* pc)
{
assert(pc != NULL);
//不能刪多了
assert(pc->sz > 0);
pc->sz--;
}2.3.2頭刪
將從第二個位置開始的數(shù)據(jù)往前挪動，這里需要注意，刪除需要檢查，以免越界。
//刪除需要檢查，刪多了會越界
//頭刪
void SLPopFront(SL* pc)
{
assert(pc != NULL);
//檢查
assert(pc->sz > 0);
//從第二個元素開始從后往前挪直接將其覆蓋
int begin = 0;
while (begin <= pc->sz)
{
pc->data[begin-1] = pc->data[begin];
++begin;
}
pc->sz--;
}2.3.3任意位置刪除
任意位置刪除我們只需要將我們需要刪除的位置后面的數(shù)往前挪動就行了
//任意位置刪除
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查找
我們給一個數(shù)據(jù)x來表示我們想要查找的數(shù)據(jù)，從前往后把順序表遍歷一遍，當(dāng)給的X等于順序表中的X時就找到了，返回當(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)我們想要修改某一個地方的數(shù)據(jù)時，直接將那個位置的數(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)我們順序表使用完成過后，我們需要注意的是，我們malloc的空間并沒有得到釋放，可能會造成內(nèi)存泄漏等問題（可參考前面的博客 '動態(tài)內(nèi)存開辟' ），釋放內(nèi)存就需要用到free函數(shù)
//銷毀空間
void SLDestory(SL* pc)
{
if (pc->data)
{
free(pc->data);
pc->data = NULL;
pc->capacity = pc->sz = 0;
}
}這里就簡單的給大家介紹了動態(tài)順序表的簡單功能，在這里都是封裝成接口函數(shù)使用的，下一章給大家介紹鏈表的實現(xiàn)。
到此這篇關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)深入探索順序表的文章就介紹到這了,更多相關(guān)C語言順序表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了C++實現(xiàn)LeetCode(139.拆分詞句),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
解析linux 文件和目錄操作的相關(guān)函數(shù)
以下是對linux中文件和目錄操作的相關(guān)函數(shù)進(jìn)行了詳細(xì)的分析介紹，需要的朋友可以過來參考下2013-08-08
這篇文章主要介紹了C++命名空間實例解析,對C++程序員來說是非常重要的知識點,需要的朋友可以參考下2014-08-08
這篇文章主要為大家詳細(xì)介紹了C語言代碼實現(xiàn)掃雷游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-02-02
二分查找法（也叫折半查找）其本質(zhì)是分治算法的一種。這篇文章主要介紹了如何利用C語言實現(xiàn)折半查找，感興趣的小伙伴可以學(xué)習(xí)一下2022-05-05
這篇文章主要介紹了C++中構(gòu)造函數(shù)重載的相關(guān)資料，十分的詳細(xì)，需要的朋友可以參考下2015-06-06
C++中與輸入相關(guān)的istream類成員函數(shù)簡介
這篇文章主要介紹了C++中與輸入相關(guān)的istream類成員函數(shù)簡介,包括eof函數(shù)和peek函數(shù)以及putback函數(shù)還有ignore函數(shù),需要的朋友可以參考下2015-09-09
異常處理是C++的一項語言機(jī)制,用于在程序中處理異常事件,下面這篇文章主要給大家介紹了關(guān)于C++中異常的相關(guān)資料,文中通過實例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-02-02
這篇文章主要介紹了C語言線性表順序表示及實現(xiàn)，線性表是最常用且最簡單的一種數(shù)據(jù)結(jié)構(gòu)。簡而言之，一個線性表是n個數(shù)據(jù)元素的有限序列2022-07-07
這篇文章主要介紹了c++函數(shù)指針使用示例,需要的朋友可以參考下2014-03-03