新手向超詳細(xì)的C語言實(shí)現(xiàn)動態(tài)順序表
一、各個函數(shù)接口的實(shí)現(xiàn)
1.1 不太好‘'李姐‘'的“容量檢測函數(shù)”
對順序表進(jìn)行插入數(shù)據(jù)時，需要判斷順序表的容量是否充足，增加數(shù)據(jù)的同時需要反復(fù)地檢測容量，所以推薦直接將以上步驟封裝成一個函數(shù)。
函數(shù)實(shí)現(xiàn)算法：若容量大小 == 有效數(shù)據(jù)大小，則為現(xiàn)有順序表增容一倍的空間。
但是需要注意的是：初始順序表后，容量為0，則需開辟4個有效數(shù)據(jù)的空間。
void SeqListCheckCapacity(SLT* psl)
{
assert(psl);
if (psl->size == psl->capacity)
{
size_t newcapacity = psl->capacity == 0 ? 4 : (psl->capacity) * 2;
psl->a = (SQDatatype*)realloc(psl->a, sizeof(SQDatatype) * newcapacity);
psl->capacity = newcapacity;
}
}
1.2 在任意位置插入的函數(shù)"坑！"
算法實(shí)現(xiàn)：首先檢測容量，再通過想要插入的下標(biāo)找到位置，將包括該下標(biāo)的元素以及其后的所有元素往后挪一步，最后在該下標(biāo)位置放入數(shù)據(jù)。
void SeqListInsert(SLT* psl, size_t pos, SQDatatype x)
{
assert(psl);
assert(pos >= 0 && pos <= psl->size);
SeqListCheckCapacity(&psl);
int end = psl->size - 1;
while (end >= pos)
{
psl->a[end + 1] = psl->a[end];
end--;
}
psl->a[pos] = x;
psl->size++;
}
考慮到下標(biāo)pos一定是個非負(fù)整數(shù)，故使用size_t類型。
如果利用該函數(shù)進(jìn)行頭插，即pos == 0;在while循環(huán)的最后一步，即end == pos時，end--后end變成-1，再回到while循環(huán)的判斷條件時，end會出現(xiàn)整形提升的情況，即-1變成無符號整形，約為21億。
end出現(xiàn)整形提升的原因在于pos是size_t類型。
解決方法就是保證while循環(huán)中和pos比較的式子為非負(fù)數(shù)即可。
void SeqListInsert(SLT* psl, size_t pos, SQDatatype x)
{
assert(psl);
assert(pos >= 0 && pos <= psl->size);
SeqListCheckCapacity(psl);
int end = psl->size;
while (end >= pos + 1)
{
psl->a[end] = psl->a[end - 1];
end--;
}
psl->a[pos] = x;
psl->size++;
}
1.3 在任意位置刪除數(shù)據(jù)的函數(shù)
算法思路：把指定元素之后的所有元素全部向前挪動一步。
void SeqListErase(SLT* psl, size_t pos)
{
assert(psl);
assert(pos >= 0 && pos < psl->size);
size_t begin = pos;
if (begin == psl->size - 1)
{
psl->size--;
return;
}
while (begin < psl->size - 1)
{
psl->a[begin] = psl->a[begin + 1];
begin++;
}
psl->size--;
}
上述代碼中if條件語句用于判斷是否為尾刪。
注意：避免負(fù)數(shù)與無符號數(shù)通過操作符連接，避免有符號數(shù)變成負(fù)數(shù)后被整型提升為無符號數(shù)或者強(qiáng)制轉(zhuǎn)換。
1.4 其余簡單的接口函數(shù)
初始化函數(shù)
void SeqListInit(SLT* psl)
{
assert(psl);
psl->a = NULL;
psl->capacity = psl->size = 0;
}
銷毀函數(shù)
void SeqListDestory(SLT* psl)
{
assert(psl);
if (psl->a)
{
free(psl->a);
psl->a = NULL;
}
psl->capacity = psl->size = 0;
}
打印函數(shù)
void SeqListPrint(SLT* psl)
{
assert(psl);
int i = 0;
for (i = 0; i < psl->size; i++)
{
printf("%d ", psl->a[i]);
}
printf("\n");
}
尾插
void SeqListPushBack(SLT* psl, SQDatatype x)
{
assert(psl);
SeqListCheckCapacity(psl);
psl->a[psl->size] = x;
psl->size++;
}
頭插
void SeqListPushFront(SLT* psl, SQDatatype x)
{
assert(psl);
SeqListCheckCapacity(psl);
int i = 0;
for (i = psl->size - 1; i >= 0; i--)
{
psl->a[i + 1] = psl->a[i];
}
psl->a[0] = x;
psl->size++;
}
尾刪
void SeqListPopBack(SLT* psl)
{
assert(psl);
psl->size--;
}
頭刪
{
assert(psl);
assert(psl->size > 0);
int begin = 0;
while (begin < psl->size - 1)
{
psl->a[begin] = psl->a[begin + 1];
begin++;
}
psl->size--;
}
通過數(shù)據(jù)查找下標(biāo)
int SeqListFind(SLT* psl, SQDatatype x)
{
assert(psl);
int begin = 0;
while (begin < psl->size)
{
if (x == psl->a[begin])
return begin;
begin++;
}
return -1;
}
二、順序表結(jié)構(gòu)體聲明與定義
typedef int SQDatatype;
重定義可方便以后更換元素類型時修改
typedef struct SeqList
{
SQDatatype* a;
int size;
int capacity;
}SLT;
重定義可以讓定義結(jié)構(gòu)體對象（變量）時，免去代碼的冗余。
如struct SeqList s1;可修改為SLT s1;
三、頭文件的調(diào)用
- #include<stdio.h>標(biāo)準(zhǔn)輸入輸出
- #include<assert.h>斷言錯誤，避免空指針對程序的影響
- #include<stdlib.h>動態(tài)函數(shù)
到此這篇關(guān)于新手向超詳細(xì)的C語言實(shí)現(xiàn)動態(tài)順序表的文章就介紹到這了,更多相關(guān)C語言動態(tài)順序表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要用代碼介紹了C語言線性表的順序線性表，對于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的朋友很有參考借鑒價值,需要的朋友可以參考下2021-09-09
C++11標(biāo)準(zhǔn)引入了nullptr來替代傳統(tǒng)的NULL,解決了NULL可能導(dǎo)致的類型混淆問題,nullptr是nullptr_t類型的實(shí)例,專用于初始化空類型指針,與整型不會發(fā)生隱式轉(zhuǎn)換,從而使代碼更健壯,它可以被隱式轉(zhuǎn)換為任意類型的指針,提高了代碼的安全性和可讀性2024-10-10
這篇文章主要介紹了C++?使用棧求解中綴、后綴表達(dá)式的值,本文講解了中綴、后綴表達(dá)式的求值過程以及如何將一個中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式，需要的朋友可以參考下2022-10-10
Linux下實(shí)現(xiàn)C++操作Mysql數(shù)據(jù)庫
由于工作需要抽出一周的時間來研究C/C++訪問各種數(shù)據(jù)庫的方法，并打算封裝一套數(shù)據(jù)庫操作類，現(xiàn)在奉上最簡單的一部分：在Linux下訪問MySQL數(shù)據(jù)庫。2017-05-05
這篇文章主要為大家詳細(xì)介紹了用C語言實(shí)現(xiàn)簡單的計(jì)算器功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-01-01
本文簡單介紹多態(tài)和多重繼承、虛擬繼承的基本概念。隨后重點(diǎn)分析了C++中對象模型之間的差異和運(yùn)行效率2014-08-08
維吉尼亞密碼（又譯維熱納爾密碼）是使用一系列凱撒密碼組成密碼字母表的加密算法，屬于多表密碼的一種簡單形式。本文將用C語言實(shí)現(xiàn)維吉尼亞密碼，需要的可以參考一下2022-11-11
C++中動態(tài)綁定和內(nèi)存管理的實(shí)現(xiàn)
本文主要介紹了C++中動態(tài)綁定和內(nèi)存管理的實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2024-12-12
黑樹在插入節(jié)點(diǎn)時，必須依照大小比對之后在一個合適的位置上執(zhí)行插入動作。所以作為關(guān)鍵字，起碼必須有“<”這個比較操作符2013-09-09
這篇文章主要為大家詳細(xì)介紹了利用C語言實(shí)現(xiàn)三子棋小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-08-08