C語言數(shù)據(jù)結(jié)構深入探索順序表
1.順序表的概念及結(jié)構
順序表是使用一段連續(xù)物理地址的單元來依次儲存數(shù)據(jù)的線性結(jié)構，一般采用數(shù)組存儲。在數(shù)組上完成增刪查改。
順序表分為兩類：
靜態(tài)順序表：使用定長數(shù)組儲存元素
struct SeqList
{
int data;//存儲的數(shù)據(jù)
int size;//記錄數(shù)據(jù)個數(shù)
int 1000;//給定當前順序表的總?cè)萘繛?000
};動態(tài)順序表：使用動態(tài)開辟的數(shù)組存儲
struct SeqList
{
int data;//存儲的數(shù)據(jù)
int size;//記錄數(shù)據(jù)個數(shù)
int capacity;//順序表的總?cè)萘?
};2.增刪查改的實現(xiàn)
當我們需要儲存的數(shù)據(jù)數(shù)目不確定時我們使用動態(tài)順序表更佳，所以下面就用動態(tài)順序表來實現(xiàn)增刪查改。
2.1擴容
首先我們動態(tài)順序表想要實現(xiàn)自動擴容，當當前數(shù)據(jù)量size等于總?cè)萘縞apacity時我們就需要自動增容，具體就是使用malloc函數(shù)開辟一定數(shù)量的空間，假如我們設定每次擴充二倍，代碼如下：
//增容
void SLCheckcapacity(SL* pc)
{
assert(pc != NULL);
//檢查容量，滿了就擴容
if (pc->sz == pc->capacity)
{
//一次擴容二倍，如果初始為0就先擴容到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尾插
先從最簡單的尾插開始，我們尾插時需要記錄下當前的size，這樣插入的時候就可以直接找到尾部，我們需要注意的是，我們插入之前需要判斷一下當前的容量滿了沒有，如果滿了就需要擴容，沒滿就可以直接插入。
//尾插
void SLPushBack(SL* pc, SLDatatype x)
{
assert(pc != NULL);
//需要判斷是否需要增容
SLCheckcapacity(pc);
pc->data[pc->sz] = x;
pc->sz++;
}2.2.2頭插
頭插相對來說要復雜一點，當頭上沒有數(shù)據(jù)時，我們就可以看成尾插直接插入，當頭上有數(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有三種情況，當在第一個位置時就是頭插可以調(diào)用頭插的函數(shù)，在最后一個位置時就是尾插，就調(diào)用尾插的函數(shù)，當我們在中間的時我們需要找到需要插入的位置，然后將數(shù)據(jù)從這個位置開始向后挪動，再插入進去。
//任意位置插入
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ù)差不多，我們也需要湊夠三個方面來撕開，頭部刪除，尾部刪除，中間任意位置刪除，當我們刪除數(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ù)，從前往后把順序表遍歷一遍，當給的X等于順序表中的X時就找到了，返回當前位置的下標。
//查找
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ù)
當我們想要修改某一個地方的數(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銷毀空間
當我們順序表使用完成過后，我們需要注意的是，我們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)。
到此這篇關于C語言數(shù)據(jù)結(jié)構深入探索順序表的文章就介紹到這了,更多相關C語言順序表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了C語言的結(jié)構體中成員變量偏移問題,以講解如何編寫宏來對成員變量進行修改為主,需要的朋友可以參考下2016-04-04
這篇文章主要給大家介紹了關于利用C/C++篩選法算素數(shù)的相關資料，文中給大家列舉了普通枚舉法和篩選法兩種方法實現(xiàn)的方法示例，文中通過示例代碼介紹的非常詳細，需要的朋友可以參考借鑒，下面隨著小編來一起學習學習吧。2017-12-12
緩沖區(qū)是一塊連續(xù)的計算機內(nèi)存區(qū)域，可保存相同數(shù)據(jù)類型的多個實例。緩沖區(qū)可以是堆棧、堆和靜態(tài)數(shù)據(jù)區(qū)。在C/C++語言中，通常使用字符數(shù)組和malloc/new實現(xiàn)緩沖區(qū)。溢出指數(shù)據(jù)被添加到分配給該緩沖區(qū)的內(nèi)存塊之外。緩沖區(qū)溢出是最常見的程序缺陷2021-06-06
C++萬能頭文件它是一個包含了每一個標準庫的頭文件，接下來通過本文給大家介紹C++中的萬能頭文件及優(yōu)缺點,需要的朋友可以參考下2023-02-02
這篇文章主要介紹了C++ 繼承詳解，這里整理了詳細的資料及實例代碼，有需要的小伙伴可以參考下2016-09-09
這篇文章主要介紹了對C語言中指針的理解與其基礎使用實例,文中援引了知乎熱門問題"為什么說指針是 C 語言的精髓？"中的精彩回答,需要的朋友可以參考下2016-03-03
CMake是一個跨平臺的自動化構建工具,可以用于構建各種類型的項目,本文主要介紹了使用CMake構建一個簡單的C++項目，具有一定的參考價值，感興趣的可以了解一下2023-10-10
這篇文章主要為大家詳細介紹了C++中關于特殊類設計的相關知識，文中的示例代碼講解詳細，對我們學習C++有一定的幫助，感興趣的可以了解一下2023-07-07
這篇文章主要介紹了C語言結(jié)構體內(nèi)存的對齊的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-03-03
這篇文章主要介紹了C++如何將運行結(jié)果保存到txt中問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-08-08