1、線性表
線性表（linear list）是n個具有相同特性的數(shù)據(jù)元素的有限序列。 線性表是一種在實際中廣泛使用的數(shù)據(jù)結(jié)構，常見的線性表：順序表、鏈表、棧、隊列、字符串…
線性表在邏輯上是線性結(jié)構，也就說是連續(xù)的一條直線。但是在物理結(jié)構上并不一定是連續(xù)的，線性表在物理上存儲時，通常以數(shù)組和鏈式結(jié)構的形式存儲。
下面借助圖形直觀感受一下順序表和鏈表的結(jié)構:
2、順序表
2.1 概念和結(jié)構
順序表是用一段物理地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構，一般情況下采用數(shù)組存儲。在數(shù)組上完成數(shù)據(jù)的增刪查改。
順序表有靜態(tài)和動態(tài)兩種。
1.靜態(tài)順序表:使用定長數(shù)組存儲元素。
2.動態(tài)順序表:使用動態(tài)開辟的數(shù)組存儲元素。
其中在存儲過程中都會存在空間不夠的情況，通常情況下我們用realloc(C語言的一個重點，后面復習會單獨寫博客來詳細介紹)來擴容。
其中呢，realloc有兩種擴容方式:
a.原地擴容:其效率非常高。
b.異地擴容:相較于原地擴容來講，效率會低一些。
要用到異地擴容的原因是因為后面的空間已經(jīng)分配給別人了，所以此方法是將原有空間拷貝到異地，再將原空間釋放，最終會返回新的地址。
因此要判斷擴容類型也很簡單:
只需要驗證返回地址即可。
下面我們一起通過兩個例子看看如何通過地址判斷是原地擴容還是異地擴容。
原地擴容:
異地擴容:
注意一點: realloc在異地擴容的時候，會自動釋放空間，不需要我們?nèi)ヅ袛嗫臻g是否相等來決定是否需要釋放。
2.2 接口實現(xiàn)
靜態(tài)順序表只適用于確定知道需要存多少數(shù)據(jù)的場景。靜態(tài)順序表的定長數(shù)組導致N定大了，空
間開多了浪費，開少了不夠用。所以現(xiàn)實中基本都是使用動態(tài)順序表，根據(jù)需要動態(tài)的分配空間
大小，所以下面我們實現(xiàn)動態(tài)順序表。
typedef int SLDataType;
// 順序表的動態(tài)存儲
typedef struct SeqList
{
SLDataType* array; // 指向動態(tài)開辟的數(shù)組
size_t size ; // 有效數(shù)據(jù)個數(shù)
size_t capicity ; // 容量空間的大小
}SL;
// 基本增刪查改接口
// 順序表初始化
void SLInit(SeqList* psl);
// 檢查空間，如果滿了，進行增容
void SLCheckCapacity(SeqList* psl);
// 順序表尾插
void SLPushBack(SeqList* psl, SLDataType x);
// 順序表尾刪
void SLPopBack(SeqList* psl);
// 順序表頭插
void SLPushFront(SeqList* psl, SLDataType x);
// 順序表頭刪
void SLPopFront(SeqList* psl);
// 順序表查找
int SLFind(SeqList* psl, SLDataType x);
// 順序表在pos位置插入x
void SLInsert(SeqList* psl, size_t pos, SLDataType x);
// 順序表刪除pos位置的值
void SLErase(SeqList* psl, size_t pos);
// 順序表銷毀
void SLDestory(SeqList* psl);
// 順序表打印
void SLPrint(SeqList* psl);
有了整體框架之后,我們就能更清晰地去實現(xiàn)順序表了。
下面讓我們一起各接口的具體實現(xiàn)方法吧!
2.2.1 順序表初始化、銷毀與打印
void SLInit(SL* psl)//初始化
{
assert(psl);
psl->a = NULL;
psl->size = 0;
psl->capacity = 0;
}
void SLDestroy(SL* psl)
{
assert(psl);
if (psl->a != NULL)
{
free(psl->a);
psl->a = NULL;
psl->size = 0;
psl->capacity = 0;
}
}
void SLPrint(SL* psl)
{
assert(psl);
for (int i = 0; i < psl->size; i++)
{
printf("%d ", psl->a[i]);
}
printf("\n");
}
2.2.2 檢查空間容量(是否增容)
在這個地方我們加入一個 SLCheckCapacity 函數(shù)實現(xiàn)該接口功能。
void SLCheckCapacity(SL* psl)
{
assert(psl);
if (psl->size == psl->capacity)
{
int newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
SLDataType* tmp = (SLDataType*)realloc(psl->a, sizeof(SLDataType) * newCapacity);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
psl->a = tmp;
psl->capacity = newCapacity;
}
}
2.3 順序表頭插尾插
首先我們來看尾插,尾插就直接在后空間插入,空間不夠的話有SLCheckCapacity函數(shù)接口檢查,自動擴容插入就OK了。咱們直接上代碼:
void SLPushBack(SL* psl, SLDataType x)
{
assert(psl);
SLCheckCapacity(psl);
psl->a[psl->size] = x;
psl->size++;
}
但是頭插就不太一樣了,因為我們沒有向前擴容的說法，更不允許這么做。所以我們想完成頭插，就要挪動數(shù)據(jù)(將前面的數(shù)據(jù)往后挪)。
特別注意:size是指向最后一個數(shù)據(jù)的下一個位置。
void SLPushFront(SL* psl, SLDataType x)
{
assert(psl);
SLCheckCapacity(psl);
// 挪動數(shù)據(jù)
int end = psl->size - 1;
while (end >= 0)
{
psl->a[end + 1] = psl->a[end];
--end;
}
psl->a[0] = x;
psl->size++;
}
2.4 順序表的頭刪尾刪
就如下圖所示,想要把最后一個數(shù)據(jù)刪除,我們只要把size從之前的5改為4就可以了,這其實就代表了改動之后只有前4個數(shù)據(jù)是有效的。
有一點需要注意:在這個地方,被刪掉的數(shù)據(jù)的內(nèi)存不需要free,也不能free。
原因是:申請的空間如果要釋放,那么就要全部釋放,不能只釋放一個內(nèi)存單元。(這樣就不連續(xù)了)
同時呢,如果我們還要進行頭尾查,被刪除的數(shù)據(jù)所留下的那處空間也會被重新覆蓋,不必麻煩。
OK，根據(jù)上述思路上代碼:
void SLPopBack(SL* psl)
{
assert(psl);
// 空
// 溫柔的檢查
/*if (psl->size == 0)
{
return;
}*/
// 暴力檢查:如果size小于0直接報錯
assert(psl->size > 0);
psl->size--;
}
頭刪其實原理差不多了
void SLPopFront(SL* psl)
{
assert(psl);
// 暴力檢查
assert(psl->size > 0);
int begin = 1;
while (begin < psl->size)
{
psl->a[begin - 1] = psl->a[begin];
++begin;
}
psl->size--;
}
2.5 順序表插入(在pos插入x)
原理同樣有挪動的思想在里面
void SLInsert(SL* psl, int pos, SLDataType x)
{
assert(psl);
assert(pos >= 0 && pos <= psl->size);
SLCheckCapacity(psl);
// 挪動數(shù)據(jù)
int end = psl->size - 1;
while (end >= pos)
{
psl->a[end + 1] = psl->a[end];
--end;
}
psl->a[pos] = x;
psl->size++;
}//pos是下標,size是數(shù)據(jù)個數(shù)，如果看做下標的話，它是最后一個數(shù)據(jù)的下一個位置
2.6 順序表在pos處消除x
思想:后一個數(shù)據(jù)往前面一個數(shù)據(jù)覆蓋(挪動覆蓋)
文章來源：http://www.zghlxwxcb.cn/news/detail-836716.html
void SLErase(SL* psl, int pos)
{
assert(psl);
assert(pos >= 0 && pos < psl->size);
// 挪動覆蓋
int begin = pos + 1;
while (begin < psl->size)
{
psl->a[begin - 1] = psl->a[begin];
++begin;
}
psl->size--;
}
好的,咱們這篇博客就先到這里了,有不足或錯誤的地方歡迎朋友們指正,感謝支持,謝謝!
咱們下篇博客見~~文章來源地址http://www.zghlxwxcb.cn/news/detail-836716.html
到了這里，關于順序表和鏈表從零詳細梳理(順序表篇)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
