一：線性表

線性表（linear list）是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。 線性表是一種在實(shí)際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見的線性表：順序表、鏈表、棧、隊(duì)列、字符串…

線性表在邏輯上是線性結(jié)構(gòu)，也就說(shuō)是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，線性表在物理上存儲(chǔ)時(shí)，通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲(chǔ)

二：順序表

1：概念與結(jié)構(gòu)

順序表是用一段物理地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲(chǔ)。在數(shù)組上完成數(shù)據(jù)的增刪查改。

1：靜態(tài)順序表

靜態(tài)順序表：使用定長(zhǎng)數(shù)組存儲(chǔ)元素

#pragma once //為了避免同一個(gè)頭文件被包含(include)多次//靜態(tài)順序表:使用定長(zhǎng)數(shù)組存儲(chǔ)元素.(不太實(shí)用)
// Max太小了不夠用 太大了怕浪費(fèi)
#define Max 10
//定長(zhǎng)數(shù)組不只是int類型的,
//因此用結(jié)構(gòu)體來(lái)方便修改其他數(shù)據(jù)類型
typedef int SLDataType;//順序表SL的DataType
typedef struct SeqList
{//int a[Max];//定長(zhǎng)數(shù)組SLDataType a[Max];size_t size;//記錄數(shù)組中的有效數(shù)據(jù)
}SL;

靜態(tài)順序表一般不太實(shí)用 我們經(jīng)常用的是動(dòng)態(tài)順序表

2：動(dòng)態(tài)順序表

動(dòng)態(tài)順序表：使用動(dòng)態(tài)開辟的數(shù)組存儲(chǔ)

2：動(dòng)態(tài)順序表的代碼實(shí)現(xiàn)

1：結(jié)構(gòu)

//結(jié)構(gòu)
typedef int SLDataType;//順序表SL的DataType
typedef struct SeqList
{SLDataType* a;//定義一個(gè)指針指向動(dòng)態(tài)開辟的數(shù)組size_t size;//記錄數(shù)組中的有效數(shù)據(jù)(指向最后數(shù)據(jù)的下一個(gè)位置)size_t capcity;//空間容量的大小
}SL;

2：接口實(shí)現(xiàn)

1：初始化

將有效數(shù)據(jù)個(gè)數(shù)和容量都初始化為0,并將指針指空

void SLInit(SL* ps)
{assert(ps);ps->a = NULL;ps->size = ps->capcity = 0;
}

2：釋放內(nèi)存

釋放順序表的空間,并將指針指空,容量和數(shù)據(jù)個(gè)數(shù)置0 (只有在數(shù)組不為空的情況下才會(huì)銷毀)

void SLDestroy(SL* ps)
{//if (ps->a != NULL)if (ps->a)//非0為真{free(ps->a);ps->a = NULL;ps->size = ps->capcity = 0;}		
}

3：檢查容量

在增加數(shù)據(jù)的時(shí)候，首先需要判斷順序表的容量是否夠用，如果不夠用就需要增容。

每次擴(kuò)容擴(kuò)成原來(lái)容量二倍的原因：

• 如果一次擴(kuò)多了，會(huì)造成空間的浪費(fèi)
• 擴(kuò)的少了在增加數(shù)據(jù)的時(shí)候就需要頻繁擴(kuò)容，降低了程序的效率。realloc函數(shù)擴(kuò)容存在原地?cái)U(kuò)容和異地?cái)U(kuò)容倆種情況，如果是異地的話無(wú)疑會(huì)更加增加擴(kuò)容的成本，需要花費(fèi)更多時(shí)間。
• 綜合考慮倆種因素，擴(kuò)成原來(lái)的二倍是比較合理的

我們知道，開辟動(dòng)態(tài)空間使用的是malloc或者calloc函數(shù)，而realloc是用來(lái)擴(kuò)容的，而我們這里僅使用realloc既實(shí)現(xiàn)開辟，又實(shí)現(xiàn)擴(kuò)容。-

僅用realloc不用malloc的原因：

• malloc僅在初始化后容量為0的時(shí)候開辟動(dòng)態(tài)空間使用，之后的擴(kuò)容都是使用到realloc，如果分情況寫就會(huì)比較冗余
• realloc同樣可以實(shí)現(xiàn)malloc的功能，當(dāng)傳給realloc的指針是空指針NULL的時(shí)候，realloc的功能和malloc是一樣的，所以我們?cè)诔跏蓟瘯r(shí)也是將管理數(shù)據(jù)的指針設(shè)為空指針的

void SLCheckCapacity(SL* ps)
{assert(ps);//擴(kuò)容if (ps->size == ps->capcity)//如果越界了或者為NULL{//一般2倍擴(kuò)容//如果是0,則空間為4個(gè)(隨機(jī))int newCapcity = ps->capcity * 2 == 0 ? 4 : ps->capcity * 2;//空間容量應(yīng)當(dāng)將個(gè)數(shù)*字節(jié)//realloc:返回新開的數(shù)組空間的地址,可能第一次為NULL,也有可能接收失敗//因此用tmp變量接收SLDataType* tmp = realloc(ps->a, newCapcity * sizeof(SLDataType));if (tmp == NULL){perror("realloc is fail");exit(-1);//異常終止返回-1,正常結(jié)束返回0}ps->a = tmp;ps->capcity = newCapcity;}
}

4：尾插

在數(shù)組尾部插入數(shù)據(jù),首先要考慮擴(kuò)容問(wèn)題,再插入數(shù)據(jù),同時(shí)元素個(gè)數(shù)增加

void SLPushBack(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);//防止數(shù)組越界ps->a[ps->size] = x;ps->size++;
}

5：尾刪

刪除數(shù)組尾部的數(shù)據(jù),同時(shí)元素個(gè)數(shù)減小,要考慮數(shù)組為空不能刪的情況

void SLPopBack(SL* ps)
{//溫柔的檢查//if (ps->size == 0) //{//	return;//}//暴力檢查assert(ps->size > 0);//為真就通過(guò)運(yùn)行,為假就結(jié)束運(yùn)行了ps->size--;
}

6：頭插

在數(shù)組尾部插入數(shù)據(jù),首先要考慮擴(kuò)容問(wèn)題,再將數(shù)組的每個(gè)元素依次向后移動(dòng)一位，再在第一個(gè)位置插入數(shù)據(jù)即可,同時(shí)元素個(gè)數(shù)增加

void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);//從最后一個(gè)數(shù)據(jù)開始依次向后挪動(dòng)一位數(shù)據(jù)進(jìn)行覆蓋int end = ps->size - 1;while (end >= 0){ps->a[end + 1] = ps->a[end];end--;}ps->a[0] = x;//頭部插入數(shù)據(jù)ps->size++;
}

7：頭刪

void SLPopFront(SL* ps)
{assert(ps);assert(ps->size > 0);//從第一個(gè)元素開始刪int begin = 0;while (begin < ps->size - 1){ps->a[begin] = ps->a[begin + 1];begin++;}//或者從第二個(gè)元素開始刪/*int begin = 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}*/ps->size--;
}

8：順序表在任意位置(pos)插入x

//任意位置插入數(shù)據(jù)
void SLInsert(SL* ps, int pos, SLDataType x)
{//防止越界assert(ps);assert(pos >= 0 && pos <= ps->size);//檢查容量SLCheckCapacity(ps);//從最后一個(gè)數(shù)據(jù)到目標(biāo)位置結(jié)束開始依次向后挪動(dòng)一位數(shù)據(jù)覆蓋int end = ps->size - 1;while (end >= pos){ps->a[end + 1] = ps->a[end];end--;}ps->a[pos] = x;//在pos處插入數(shù)據(jù)ps->size++;
}

9：順序表在任意位置(pos)刪除x

void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);int begin = pos;while (begin < ps->size - 1){ps->a[begin] = ps->a[begin + 1];begin++;}ps->size--;//或者/*int begin = pos + 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;*/
}

10：在順序表中查找指定值

//查找指定值
int SLFind(SL* ps, SLDataType x, int begin)
{assert(ps);for (int i = begin; i < ps->size; ++i){if (ps->a[i] == x){return i;//找到直接返回下標(biāo)}}//查找不到，返回-1return -1;
}

3：接口優(yōu)化

1：尾插尾刪優(yōu)化

尾插

void SLPushBack(SL* ps, SLDataType x)
{//在下標(biāo)為size的位置插入數(shù)據(jù)(末尾元素的下一個(gè))SLInsert(ps, ps->size, x);
}

尾刪

void SLPopBack(SL* ps)
{//刪除下標(biāo)為size-1的數(shù)據(jù)(末尾元素)SLErase(ps, ps->size - 1);
}

2：頭插頭刪優(yōu)化

頭插

void SLPushFront(SL* ps, SLDataType x)
{	//在下標(biāo)為0的位置插入數(shù)據(jù)(首元素)SLInsert(ps, 0, x);
}

頭刪

void SLPopFront(SL* ps)
{//刪除下標(biāo)為0的數(shù)據(jù)(首元素)SLErase(ps, 0);
}

具體代碼可見：https://gitee.com/calcium-oxide-2411/test_c