一：線性表

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

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

二：順序表

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

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

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

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

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

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

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

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

2：動態(tài)順序表的代碼實現(xiàn)

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

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

2：接口實現(xiàn)

1：初始化

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

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

2：釋放內(nèi)存

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

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ù)據(jù)的時候就需要頻繁擴容，降低了程序的效率。realloc函數(shù)擴容存在原地擴容和異地擴容倆種情況，如果是異地的話無疑會更加增加擴容的成本，需要花費更多時間。
• 綜合考慮倆種因素，擴成原來的二倍是比較合理的

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

僅用realloc不用malloc的原因：

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

void SLCheckCapacity(SL* ps)
{assert(ps);//擴容if (ps->size == ps->capcity)//如果越界了或者為NULL{//一般2倍擴容//如果是0,則空間為4個(隨機)int newCapcity = ps->capcity * 2 == 0 ? 4 : ps->capcity * 2;//空間容量應當將個數(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ù),首先要考慮擴容問題,再插入數(shù)據(jù),同時元素個數(shù)增加

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

5：尾刪

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

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

6：頭插

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

void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);//從最后一個數(shù)據(jù)開始依次向后挪動一位數(shù)據(jù)進行覆蓋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);//從第一個元素開始刪int begin = 0;while (begin < ps->size - 1){ps->a[begin] = ps->a[begin + 1];begin++;}//或者從第二個元素開始刪/*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);//從最后一個數(shù)據(jù)到目標位置結(jié)束開始依次向后挪動一位數(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;//找到直接返回下標}}//查找不到，返回-1return -1;
}

3：接口優(yōu)化

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

尾插

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

尾刪

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

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

頭插

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

頭刪

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

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