C語言深入淺出講解順序表的實現(xiàn)
今天起開始編寫數(shù)據(jù)結(jié)構(gòu)中的各種數(shù)據(jù)結(jié)構(gòu)及算法的實現(xiàn)，說到順序表，我們首先得了解下線性表。
1.線性表
線性表（linear list）是n個具有相同特性的數(shù)據(jù)元素的有限序列。 線性表是一種在實際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見的線性表：順序表、鏈表、棧、隊列、字符串…
線性表在邏輯上是線性結(jié)構(gòu)，也就說是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，線性表在物理上存儲時，通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲。
2.順序表
2.1 概念及結(jié)構(gòu)
順序表是用一段物理地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲。在數(shù)組上完成數(shù)據(jù)的增刪查改。順序表一般可分為：
1.靜態(tài)順序表：使用定長數(shù)組存儲。
2.動態(tài)順序表：使用動態(tài)開辟的數(shù)組存儲。
//順序表的靜態(tài)存儲
#define N 100
struct SeqList
{
int a[N];//定長存儲
int size;//有效數(shù)據(jù)的個數(shù)
};
//順序表的動態(tài)存儲
typedef struct SeqList
{
SeqDataType* a;//指向動態(tài)開辟的數(shù)組
int size; //有效數(shù)據(jù)個數(shù)
int capacity; //容量
}SeqList;
順序表本質(zhì)上是數(shù)組，在數(shù)組上增加了兩個要求：
1.插入數(shù)據(jù)的過程中，可以動態(tài)增長
2.并且要求里面存儲的數(shù)據(jù)必須是從左往右，是連續(xù)的
順序表的缺陷
1.動態(tài)增容有性能消耗
2.頭部插入數(shù)據(jù)時，需要挪動數(shù)據(jù)
2.2 提供接口
靜態(tài)順序表只適用于確定知道需要存多少數(shù)據(jù)的場景。靜態(tài)順序表的定長數(shù)組導(dǎo)致N定大了，空間開多了浪費，開少了不夠用。所以現(xiàn)實中基本都是使用動態(tài)順序表，根據(jù)需要動態(tài)的分配空間大小，所以下面我們來實現(xiàn)動態(tài)順序表。
首先在頭文件<SeqList.h>中提供接口：
typedef int SeqDataType; //需要插入什么類型的數(shù)據(jù)，就改成對應(yīng)類型
typedef struct SeqList
{
SeqDataType* a;//指向動態(tài)開辟的數(shù)組
int size; //有效數(shù)據(jù)個數(shù)
int capacity; //容量
}SeqList;
//內(nèi)存中管理數(shù)據(jù)結(jié)構(gòu) 提供增刪查改的接口
//順序表初始化
void SeqListInit(SeqList* pq);
//順序表銷毀
void SeqListDestory(SeqList* pq);
//順序表打印
void SeqListPrint(SeqList* pq);//打印數(shù)組
//檢查空間，如果滿了，進行增容
void SeqCheckCapacity(SeqList* pq)
//順序表尾插
void SeqListPushBack(SeqList* pq, SeqDataType x);
//順序表頭插
void SeqListPushFront(SeqList* pq, SeqDataType x);
//順序表尾刪
void SeqListPopBack(SeqList* pq);
//順序表頭刪
void SeqListPopFront(SeqList* pq);
//順序表查找x
int SeqListFind(SeqList* pq, SeqDataType x);//查找 查到返回下標(biāo)，沒查到返回-1
//順序表在指定位置插入數(shù)據(jù)
void SeqListInsert(SeqList* pq, int pos, SeqDataType x);//在下標(biāo)pos位置處插入數(shù)據(jù)
//順序表在指定位置刪除數(shù)據(jù)
void SeqListErase(SeqList* pq, int pos);//把下標(biāo)為pos位置處的數(shù)據(jù)刪除
//順序表在指定位置替換數(shù)據(jù)
void SeqListModify(SeqList* pq, int pos, SeqDataType x);//把小標(biāo)為pos位置的值改為x
2.3 接口實現(xiàn)
在源文件SeqList.c中實現(xiàn)接口功能
（1）順序表初始化
void SeqListInit(SeqList* pq)
{
assert(pq != NULL);//或者 assert(pq); 斷言 防止傳入空指針
pq->a = NULL;
pq->size = 0;
pq->capacity = 0;
}
（2）順序表銷毀
void SeqListDestory(SeqList* pq)
{
assert(pq);
free(pq->a);
pq->a = NULL;
pq->size = 0;
pq->capacity = 0;
}
（3）順序表打印
void SeqListPrint(SeqList* pq)
{
assert(pq);
for (int i = 0; i < pq->size; ++i)
{
printf("%d ", pq->a[i]);
}
printf("\n");
}
（4）檢查空間，如果滿了，進行增容
//檢查是否需要擴容
void SeqCheckCapacity(SeqList* pq)
{
//滿了，需要增容
if (pq->size == pq->capacity)
{
int newcapacity = (pq->capacity == 0 ? 4 : pq->capacity * 2);
//realloc接收的地址如果為空，將像malloc一樣，開辟一塊新空間
SeqDataType* newA = realloc(pq->a, sizeof(SeqDataType) * newcapacity);//realloc返回 開辟的新空間的地址
if (newA == NULL)
{
printf("realloc fail\n");
exit(-1);//失敗了就退出
}
pq->a = newA;
pq->capacity = newcapacity;
}
}
（5）順序表尾插
void SeqListPushBack(SeqList* pq, SeqDataType x)//尾插
{
assert(pq);
SeqCheckCapacity(pq);
pq->a[pq->size] = x;
pq->size++;
}
（6）順序表頭插
void SeqListPushFront(SeqList* pq, SeqDataType x)
{
assert(pq);
SeqCheckCapacity(pq);
int end = pq->size - 1;
while (end >= 0)
{
pq->a[end + 1] = pq->a[end];
end--;
}
pq->a[0] = x;
pq->size++;
}
（7）順序表尾刪
void SeqListPopBack(SeqList* pq)
{
assert(pq);
assert(pq->size > 0);
pq->size--;
}
（8）順序表頭刪
void SeqListPopFront(SeqList* pq)
{
assert(pq);
assert(pq->size > 0);
int begin = 0;
while (begin < pq->size - 1)
{
pq->a[begin] = pq->a[begin + 1];
begin++;
}
pq->size--;
}
（9）順序表查找x
int SeqListFind(SeqList* pq, SeqDataType x)
{
assert(pq);
for (int i = 0; i < pq->size; ++i)
{
if (pq->a[i] == x)
{
return x;
}
}
return -1;//沒找到
}
（10）順序表在指定位置插入數(shù)據(jù)
void SeqListInsert(SeqList* pq, int pos, SeqDataType x){<!--{C}%3C!%2D%2D%20%2D%2D%3E-->assert(pq);assert(pos >= 0 && pos < pq->size);SeqCheckCapacity(pq);//檢查是否需要擴容int end = pq->size - 1;while (end >= pos){<!--{C}%3C!%2D%2D%20%2D%2D%3E-->pq->a[end + 1] = pq->a[end];end--;}pq->a[pos] = x;pq->size++;}void SeqListInsert(SeqList* pq, int pos, SeqDataType x)
{
assert(pq);
assert(pos >= 0 && pos < pq->size);
SeqCheckCapacity(pq);//檢查是否需要擴容
int end = pq->size - 1;
while (end >= pos)
{
pq->a[end + 1] = pq->a[end];
end--;
}
pq->a[pos] = x;
pq->size++;
}
（11）順序表在指定位置刪除數(shù)據(jù)
void SeqListErase(SeqList* pq, int pos)
{
assert(pq);
assert(pos >= 0 && pos < pq->size);
int begin = pos;
while (begin <= pq->size - 1)
{
pq->a[begin] = pq->a[begin + 1];
begin++;
}
pq->size--;
}
（12）順序表在指定位置替換數(shù)據(jù)
void SeqListModify(SeqList* pq, int pos, SeqDataType x)
{
assert(pq);
assert(pos >= 0 && pos < pq->size);
pq->a[pos] = x;
}
主函數(shù)的設(shè)計大家可以自由發(fā)揮，做個簡單的測試功能調(diào)用函數(shù)或是創(chuàng)建菜單欄實現(xiàn)交互都可以。我水平有限，請朋友們諒解！寫的不好的地方還請大佬們指出。
下期預(yù)告——單鏈表
到此這篇關(guān)于C語言深入淺出講解順序表的實現(xiàn)的文章就介紹到這了,更多相關(guān)C語言 順序表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要為大家詳細介紹了用C語言實現(xiàn)計算器功能，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-10-10
在網(wǎng)上找了份c++ MD5的代碼，就簡單保存一下,需要的朋友可以參考下2017-07-07
這篇文章主要給大家介紹了關(guān)于Qt如何快速讀取大文件最后一行內(nèi)容的解決方案,文中通過代碼介紹的非常詳細,對大家學(xué)習(xí)或者使用Qt具有一定的參考借鑒價值,需要的朋友可以參考下2024-01-01
這篇文章主要介紹了C語言常見的一些語義陷阱，梳理的比較全面，對我們做開發(fā)的過程中有一定幫助，感興趣的朋友快來看看吧2022-03-03
這篇文章主要介紹了數(shù)據(jù)結(jié)構(gòu)之堆詳解,本文講解了堆的基本常識堆的基本操作、堆的應(yīng)用等內(nèi)容,需要的朋友可以參考下2014-08-08
Qt圖形圖像開發(fā)之曲線圖表模塊QChart庫讀取/設(shè)置X軸的顯示區(qū)間
這篇文章主要介紹了Qt圖形圖像開發(fā)之曲線圖表模塊QChart庫讀取/設(shè)置X軸的顯示區(qū)間,需要的朋友可以參考下2020-03-03
這篇文章主要介紹了C++隊列用法,實例分析了C++實現(xiàn)隊列的入隊、出隊、讀取與判斷等相關(guān)技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-07-07
C語言之?dāng)?shù)組名與數(shù)組起始地址的關(guān)系解析
這篇文章主要介紹了C語言之?dāng)?shù)組名與數(shù)組起始地址的關(guān)系，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-07-07
這篇文章主要介紹了C++讀寫ini配置文件實現(xiàn)過程詳解,文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-07-07
C++實現(xiàn)二分法的一些細節(jié)(常用場景)
二分法算法思想首先確定有根區(qū)間，將區(qū)間二等分，通過判斷f（x）的符號，逐步將有根區(qū)間縮小，直至有根區(qū)間足夠小，便可求出滿足精度要求的近似值2021-07-07