1.線性表
（1）.線性表是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。線性表是一種在實(shí)際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見的線性表：順序表，鏈表，棧，隊(duì)列，字符串...
（2）.線性表在邏輯上是線性結(jié)構(gòu)，也就是說連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不是一定是連續(xù)的，線性表在物理上存儲(chǔ)的，通常以數(shù)組和鏈表結(jié)構(gòu)的形式存儲(chǔ)。
?文章來源地址http://www.zghlxwxcb.cn/news/detail-645835.html
?文章來源：http://www.zghlxwxcb.cn/news/detail-645835.html
目錄
1.線性表
?2.順序表
順序表的初始化：
?順序表的擴(kuò)容：
?順序表的尾插：
順序表的頭插：?
順序表的尾刪：
順序表的頭刪：?
順序表的最后處理：
?順序表的指定位置插入：?
?順序表的指定位置刪除：?
?
?2.順序表
順序表是用一段物理連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用的數(shù)組存儲(chǔ)。在數(shù)組上完成數(shù)據(jù)的增刪查改。
在這里，我將給大家講動(dòng)態(tài)順序表是怎么實(shí)現(xiàn)的。
?
?
（1）.我先定義了一個(gè)結(jié)構(gòu)體，因?yàn)轫樞虮硎蔷哂邢嗤匦缘臄?shù)據(jù)元素的有限列表。所以我用SeqListDateType來typedef 了，這樣我們?nèi)绻莇ouble 或者float這樣的類型的話，我們就只用改變宏這里一處。
（2）.因?yàn)槭莿?dòng)態(tài)的，所以我就用指針，size就代表了順序表中有多少個(gè)元素，capacity代表了是有多少的空間。
#define SeqListDateType int
typedef struct SeqList
{
SeqListDateType* arr;
int size;
int capacity;
}SeqList;
?
順序表的初始化：
第一個(gè)函數(shù)就是度順序表的初始化，這里我是直接把ps->arr置位了NULL，size和capacity一開始是0。
void SeqListInit(SeqList* ps)
{
ps->arr = NULL;
ps->size = ps->capacity = 0;
}?順序表的擴(kuò)容：
因?yàn)槲覀兪菍?shí)現(xiàn)動(dòng)態(tài)的順序表，所以我們要處理一下，當(dāng)size和capacity相等的時(shí)候，有2種情況，一種情況：一開始為0的時(shí)候，第二種情況：當(dāng)空間不夠的時(shí)候
這里，我用三目來實(shí)現(xiàn)了，如果是一開始我就給了4個(gè)int大小的空間，如果是第二種情況的話我就用擴(kuò)二倍的思想來處理。
void SeqListCheckCapacity(SeqList* ps)
{
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SeqListDateType* tmp = (SeqListDateType*)realloc(ps->arr, newcapacity*sizeof(SeqListDateType)*2);
if (tmp == NULL)
{
perror("realloc fail\n");
exit(-1);
}
ps->capacity = newcapacity;
ps->arr = tmp;
}
}?順序表的尾插：
一開始，我們開辟了4個(gè)int大小的空間，所以size一開始是0，然后就插入，然后size++就可以實(shí)現(xiàn)了，不過在我們插入的時(shí)候我們要考慮擴(kuò)容的問題，如果空間滿了，是要擴(kuò)容的。
?
?
void SeqListPushBack(SeqList* ps, int x)
{
assert(ps);
SeqListCheckCapacity(ps);
ps->arr[ps->size] = x;
ps->size++;
//SeqListInsert(ps, ps->size,x);
}?
順序表的頭插：
思路：可以用迭代的思路走，但我們想一想，如果是從前面迭代的話，就會(huì)形成對(duì)數(shù)據(jù)的覆蓋，所以要從后面迭代走。
我定義了end指向了4的位置，然后4要到后面的位置去，然后end--，這樣當(dāng)我們迭代完，順序表0的位置就空了出來，直接把數(shù)據(jù)插入進(jìn)去就可以了。
void SeqListPushFront(SeqList* ps,int x)
{
assert(ps);
SeqListCheckCapacity(ps);
int end = ps->size - 1;
while (end >=0)
{
ps->arr[end + 1] = ps->arr[end];
end--;
}
ps->arr[0] = x;
ps->size++;
//SeqListInsert(ps,0,x);
}
順序表的尾刪：
順序表尾刪更簡(jiǎn)單，直接讓size--就可以實(shí)現(xiàn)了。因?yàn)?，我們打印的?shù)據(jù)就是size范圍內(nèi)的數(shù)據(jù)，size減了過后就沒有這個(gè)數(shù)據(jù)了。
void SeqListPopBack(SeqList* ps)
{
assert(ps);
ps->size--;
//SeqListErqse(ps, ps->size-1);
}
?
順序表的頭刪：
?
思路：先定義一個(gè)begin來指向第一個(gè)位置，我們迭代讓后面的數(shù)據(jù)覆蓋掉前面的數(shù)據(jù)就可以了。最后size--就實(shí)現(xiàn)了順序表的頭刪。
?
void SeqListPopFront(SeqList* ps)
{
assert(ps);
int begin = 0;
while (begin < ps->size - 1)
{
ps->arr[begin] = ps->arr[begin+1];
++begin;
}
ps->size--;
//SeqListErqse(ps, 0);
}
順序表的最后處理：
我們直接free掉動(dòng)態(tài)開辟的空間就可以了，然后把size和capacity置為0.
void SeqListDestory(SeqList* ps)
{
free(ps->arr);
ps->arr = NULL;
ps->size = ps->capacity = 0;
}?我們想一個(gè)問題，如果是在面試中，給了我們10分鐘來實(shí)現(xiàn)順序表，如果這樣處理時(shí)間是不是可能不夠呢？？所以，我給大家?guī)砹硗?個(gè)函數(shù)，這樣我們就可以復(fù)用這2個(gè)函數(shù)對(duì)順序表的頭插、尾插..就可以直接復(fù)用，大大節(jié)約了時(shí)間。話不多說，直接放碼！??！
?順序表的指定位置插入：
?
思路：假設(shè)pos=2，我定義了end來指向最后一個(gè)元素，只需要將最后一個(gè)元素往后移動(dòng)一位，然后end--，這樣就迭代了起來，最終就可以把pos的位置空出來，然后在pos位置插入想要的元素。
?
????????
void SeqListInsert(SeqList* ps, int pos, int x)
{
assert(pos <= ps->size && pos>=0);
SeqListCheckCapacity(ps);
int end = ps->size - 1;
while (end >= pos)
{
ps->arr[end+1] = ps->arr[end];
end--;
}
ps->arr[pos] = x;
ps->size++;
}?順序表的指定位置刪除：
思路：刪除的話，其實(shí)也是一個(gè)覆蓋的過程，將pos+1的位置覆蓋掉pos的位置，然后迭代，臨界位置就是size-1的時(shí)候，最后size--就實(shí)現(xiàn)了對(duì)指定位置的刪除。?
void SeqListErase(SeqList* ps, int pos)
{
assert(pos >=0 && pos <= ps->size-1);
int begin = pos+1;
while (begin <= ps->size-1)
{
ps->arr[begin-1] = ps->arr[begin];
begin++;
}
ps->size--;
}?
這樣，就可以用這兩個(gè)元素來復(fù)用了！
尾插：尾插其實(shí)就是對(duì)順序表最后的位置插入元素（注意，在最后一個(gè)位置插入的時(shí)候size已經(jīng)++了，所以是ps->size）SeqListInsert(ps, ps->size,x);頭插：頭插就是對(duì)0的位置插入元素
SeqListInsert(ps,0,x);尾刪：尾刪也是和尾插一樣的，對(duì)最后的位置刪除
SeqListErase(ps, ps->size-1);頭刪：頭刪是對(duì)0的位置開始刪除
SeqListErase(ps, 0);
?
?
?
?
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)——順序表（C語言）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
