0.引言

在本章之后，就要求大家對于指針、結(jié)構(gòu)體、動態(tài)開辟等相關(guān)的知識要熟練的掌握，如果有小伙伴對上面相關(guān)的知識還不是很清晰，要先弄明白再過來接著學(xué)習(xí)哦！

那進入正題，在講解順序表之前，我們先來介紹線性表這個數(shù)據(jù)結(jié)構(gòu)。

0.1 線性表

線性表是 n個具有相同特性的數(shù)據(jù)元素組成的有限的序列。

相同特性：同一種數(shù)據(jù)類型
有限：數(shù)據(jù)元素的個數(shù)是有限的

常見的線性表：順序表、鏈表、棧、隊列、字符串等。

0.2 線性表的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)

0.2.1 邏輯結(jié)構(gòu)

線性表的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)，線性結(jié)構(gòu)?是一條連續(xù)的直線，也就是說 線性表在邏輯上是連續(xù)的，比如我們在C語言學(xué)過的的數(shù)組（順序表），指針（可以構(gòu)成鏈表）。

上圖分別為順序表跟鏈表，他們在邏輯結(jié)構(gòu)上都是一個接著一個，連續(xù)的。然而在物理結(jié)構(gòu)他們還依舊連續(xù)嗎？

0.2.2 線性表的物理結(jié)構(gòu)

線性表在物理結(jié)構(gòu)上不一定連續(xù)，我們可以構(gòu)成線性表的結(jié)構(gòu)有數(shù)組和指針，指針又被稱作鏈?zhǔn)浇Y(jié)構(gòu)。

當(dāng)線性表是由數(shù)組構(gòu)成時：
????????它在邏輯結(jié)構(gòu)是連續(xù)的，物理結(jié)構(gòu)也一定連續(xù)，因為數(shù)組是一個一個挨著的空間，在地址上是緊挨著的，所以是連續(xù)的。

如圖：

當(dāng)線性表為鏈?zhǔn)浇Y(jié)構(gòu)時：

? ? ? ? 鏈?zhǔn)浇Y(jié)構(gòu)在邏輯上一定是連續(xù)的，因為我們可以通過指針就找到該指針對應(yīng)的地址
????????但指針的地址不一定是連續(xù)的，我們可以這存一個，那存一個，通過指針給他們鏈接起來。

如圖：

當(dāng)了解了線性表之后，就讓我們一起學(xué)習(xí)第一種數(shù)據(jù)結(jié)構(gòu)——順序表吧！

1. 順序表

1.1概念

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

1.2 順序表的分類

1.2.1 靜態(tài)順序表

靜態(tài)順序表指的是利用定長數(shù)組來存儲元素

//順序表的靜態(tài)存儲
#define N 7 //順序表一次開辟的空間個數(shù)
typedef int SLDataType; //將數(shù)據(jù)類型重命名，以便我們未來換用其他的數(shù)據(jù)類型
typedef struct SeqList
{SLDataType arr[N]; //定長數(shù)組size_t size; //有效的數(shù)據(jù)個數(shù)，size_t指的是無符號整型
}Seqlist;

我們在使用靜態(tài)順序表的時候，只能每次開辟N個大小的空間，這也就要求我們在使用之前就要想好你要存放多少個數(shù)據(jù)，非常不靈活，所以我們大多時候不使用靜態(tài)順序表，而是改用動態(tài)順序表作為我們?nèi)粘?yīng)用。

1.2.2 動態(tài)順序表

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

1. 動態(tài)順序表的定義

typedef int SLDataType; //數(shù)據(jù)類型的重命名，方便更改數(shù)據(jù)類型
typedef struct SeqList
{SLDataType *a; //指向動態(tài)開辟的數(shù)組int size;     //有效的數(shù)據(jù)個數(shù)int capacity; //動態(tài)開辟的數(shù)組的容量
}SL;

2.初始化

void SLInit(SL*ps) //初始化
{ps->a = (SLDataType*)malloc(sizeof(SLDataType)*4);if(ps->a == NULL){perror("malloc");exit(EXIT_FAILURE);}ps ->size = 0;ps ->capacity = 4;
}

3.退出程序時的銷毀

void SLDestroy(SL*ps) //退出時銷毀
{free(ps->a);ps->a = NULL;ps->size = 0;ps->capacity = 0;
}

4.尾插尾刪

尾插
void SLPushBack(SL*ps,int i) 
{SLCheckCapacity(ps);ps->a[ps->size] = i;ps->size++;
}尾刪
void SLPopBack(SL*ps) 
{assert(ps->size > 0);ps->size--;
}

5.頭插頭刪

頭插
void SLPushFront(SL*ps,int i)
{SLCheckCapacity(ps);int end = ps->size;for(;end - 1 >= 0 ; end--){ps->a[end] = ps->a[end - 1];}ps->a[0] = i;ps->size++;
}///頭刪
void SLPopFront(SL*ps)
{assert(ps->size > 0);int i = 0;for(i = 0 ; i + 1 < ps->size ; i++){ps->a[i] = ps->a[i+1];}ps->size--;
}

6.擴容

void SLCheckCapacity(SL*ps)  //擴容函數(shù)
{if(ps->size == ps->capacity){SLDataType *tmp = (SLDataType*)realloc(ps->a,((sizeof(SLDataType)) * ((ps->capacity) * 2)));if(tmp == NULL){perror("realloc");exit(EXIT_FAILURE);}ps -> a = tmp;ps->capacity *= 2;}
}

7.打印

void SLPrint(SL*ps) //打印
{int i = 0;for(i = 0 ; i < ps->size ;i++){printf("%d ",ps->a[i]);}printf("\n");
}

以上就是順序表的相關(guān)接口實現(xiàn)。