歡迎來到博主的新專欄——C語言數(shù)據(jù)結(jié)構(gòu)
博主ID：代碼小豪
再開始這篇文章之前，我們假設(shè)要對10個數(shù)據(jù)進行操作。這十個數(shù)據(jù)全都被聲明成10個變量
int n1, n2, n3, n4, n5, n6, n7, n8, n9, n10;
如果我們準(zhǔn)備為這些數(shù)據(jù)增加功能，將他們進行賦值，打印，交換等。就會發(fā)現(xiàn)一個特別棘手的問題，這些程序?qū)懫饋硖彪s了，我們需要將這些數(shù)據(jù)一個個賦值，寫十個printf函數(shù)才能將他們打印。更麻煩的是，連操作他們的函數(shù)都要十個形式參數(shù)。這不是太麻煩了嘛？
學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)就是解決這個問題的好工具，當(dāng)我們實現(xiàn)某一種功能時，如果選擇了合適的數(shù)據(jù)結(jié)構(gòu)和算法時，那么將這個功能的實現(xiàn)就會簡單很多，效率也會變高。
順序表
線性表是什么
在了解順序表之前，我們得先明白線性表是什么，線性表的定義是這樣的：
一個線性表是N個具有相同特性的數(shù)據(jù)元素組成的有限序列
我們將注意力放在關(guān)鍵詞上
（1）有限:線性表中的元素是有限個的
（2）相同特性:在C語言中，可以理解為這些數(shù)據(jù)類型是一致的
（3）序列：這些數(shù)據(jù)元素被排列了，而且還是有順序的排列了。
這么說都還有些抽象，以現(xiàn)實舉例。小明夫婦打算在春節(jié)假期帶一家四口去旅游，分別是小明兩口子，和小明的兒子、女兒。但是有一個問題困擾住了夫婦兩，因為孩子小啊。景區(qū)又大，人又多，小孩子要是一不小心走丟了就不好找了。
最后小明想到了一個辦法。在景區(qū)里游玩的時候，他們一家四口手牽著手，小明牽著女兒，女兒又牽著小明的兒子，而兒子牽著媽媽。如果其中有一個人走丟，那么牽著手的人就能很快的感覺到。
小明夫婦的這個方法就是構(gòu)成了線性表中的一個最重要的特征，那就是線性邏輯結(jié)構(gòu)。在小明夫婦的方法當(dāng)中，家里四個人（四個數(shù)據(jù)）以某種方式聯(lián)系了起來，而且這個聯(lián)系是具有順序的。
從這里可以發(fā)現(xiàn)“線性”的關(guān)系，可以發(fā)現(xiàn)，小明一家之間都是一對一的關(guān)系（爸爸——女兒——兒子——妻子）。這個邏輯結(jié)構(gòu)中并沒有出現(xiàn)分支。
在線性表中，數(shù)據(jù)元素之間的關(guān)系都是一對一的，即除了首元素和末尾元素外，所有的元素都有一個前置的元素（前驅(qū)元素）和一個后置的元素（后繼元素）。這些元素以某種方式聯(lián)系在一起。
根據(jù)不同的線性聯(lián)系方式，線性表是有多種類型的，而順序表就是線性表中的其中一種。
順序表的線性邏輯結(jié)構(gòu)
在內(nèi)存當(dāng)中，十個聲明的數(shù)據(jù)的存儲形式是這樣的，這十個變量的存儲方式是隨機存儲。
現(xiàn)在，我們要想個方法使得這十個數(shù)據(jù)具有線性的邏輯結(jié)構(gòu)，使得這些數(shù)據(jù)構(gòu)成線性表
令n1為表頭，n10為表尾，其余數(shù)據(jù)按照下標(biāo)的順序排列，即（n1,n2……ni……n10）。但是這樣仍不是線性表，因為這些數(shù)據(jù)之間并沒有“聯(lián)系”，什么是數(shù)據(jù)之間的聯(lián)系呢？就好比小明一家人之間牽著的“手”一樣，沒有這只手，他們之間就不能算是線性的結(jié)構(gòu)。
參考小明夫婦的方法，讓這些數(shù)據(jù)不在零零散散了，讓他們按照順序，存儲在內(nèi)存當(dāng)中。
這樣，這些數(shù)據(jù)不就聯(lián)系起來了嗎？我們只需要知道表中任意元素的地址，比如取n4的地址，那么n4前面是n3，n4后面是n5，而n5后面是n6，以此類推。
通過指針的加減運算就能訪問到10個元素，再也不需要像開頭那種存儲方式一樣，需要將十個元素分別進行操作。
這種具有順序存儲結(jié)構(gòu)的線性表，被稱為順序表
靜態(tài)順序表
我們仔細回想以下順序表的定義：將元素順序存儲在內(nèi)存當(dāng)中。
這不是數(shù)組嗎！
所以C語言（或其他語言）可以通過數(shù)組來實現(xiàn)順序表的
#define N 100
typedef int SLdatetype;
typedef struct SeqList
{
SLdatetype a[N];//順序表的最大表長
int lenth;//順序表的當(dāng)前表長
};
用數(shù)組實現(xiàn)的順序表有以下特點
（1）lenth是順序表的當(dāng)前長度
（2）由于順序表有可能進行增加數(shù)據(jù)的操作，所以數(shù)組的元素個數(shù)>=順序表中的元素個數(shù)
由于數(shù)組的元素個數(shù)在創(chuàng)建之后是固定的，所以將這種順序表稱為靜態(tài)順序表，由于靜態(tài)順序表在程序運行的過程中不能進行調(diào)整，所以順序表的預(yù)留空間要足夠大。
總體而言，靜態(tài)順序表雖然操作簡單，但是不夠靈活，而且造成的內(nèi)存空間的浪費也較大。動態(tài)順序表具有更多的優(yōu)勢。
動態(tài)順序表
動態(tài)順序表是使用動態(tài)內(nèi)存來管理順序表的空間。使用了動態(tài)內(nèi)存之后，可以對順序表中的空間進行擴容、修改等操作。
動態(tài)順序表的定義如下：
typedef struct SeqList
{
SLdatetype* seqlist;
int capacity;
int size;
}SeqList;
seqlist是一個指針，主要作用是通過這個指針對順序表進行操作。
capacity是順序表的最大容量，如果數(shù)據(jù)進行操作時發(fā)現(xiàn)容量不夠，可以對順序表進行擴容
size是順序表的當(dāng)前數(shù)據(jù)的長度
動態(tài)順序表通過動態(tài)內(nèi)存分配的形式，對順序表的空間管理更加的靈活，而且造成的空間浪費也會更容易管控。這是動態(tài)順序表相對于靜態(tài)順序表的優(yōu)勢
順序表的操作
和變量的聲明與初始化類似，一個順序表在創(chuàng)建時也是需要對順序表進行聲明與初始化的。這里將順序表的初始化封裝成一個函數(shù)
SeqList s1;
InitList(&s1);
這個新建的順序表還沒有任何數(shù)據(jù)，也沒有為其分配動態(tài)內(nèi)存的空間，因此將順序表初始化成一個空表
void InitList(SeqList* psl)
{
psl->seqlist = NULL;
psl->capacity = 0;
psl->size = 0;
}
由于操作系統(tǒng)尚未為順序表分配空間，因此將指針置為NULL，容量為0，大小也為0。
對順序表初始化完成后，就可以對順序表進行操作了。順序表的操作無非是“增刪查改”這幾種。下面將對順序表的操作進行講解
為順序表增加數(shù)據(jù)
尾插法
我們假設(shè)大街上有一群人在排隊，現(xiàn)在，小明來到了排隊的地方，那么他有幾種方法排隊呢？
第一種，就是排在隊伍的后頭，這樣子大家也就和和氣氣的，什么事都沒有發(fā)生。
在順序表中，將數(shù)據(jù)添加在表尾的方法被稱為尾插法，這種方法是時間復(fù)雜度最低的插入算法。假設(shè)現(xiàn)在順序表的最大容量（capacity）為4，當(dāng)前表長（size）為2。
當(dāng)前的順序表并沒有達到最大容量的限制，因此只需要將數(shù)據(jù)排列到順序表的末尾即可，我們可以計算一下新數(shù)據(jù)的位置。
新數(shù)據(jù)n3是順序表的第三位，但是C語言中數(shù)組的下標(biāo)是從[0]開始計算的，所以n3的位置是在下標(biāo)為[2]的位置?？梢园l(fā)現(xiàn)，新數(shù)據(jù)的下標(biāo)計數(shù)，與順序表的當(dāng)前表長（size）是一致的，因此可以讓當(dāng)前表長（size）作為尾插法使用時的數(shù)據(jù)下標(biāo)。
ps1->seqlist[ps1->size] = n;
別忘了添加新數(shù)據(jù)后，當(dāng)前表長要加1.
size++;
順序表的擴容
如果新數(shù)據(jù)添加后超出了最大容量的限制（capacity==size）。那么此時數(shù)據(jù)是無法插入順序表的
解決方法是使用realloc函數(shù)為順序表進行擴容（關(guān)于動態(tài)內(nèi)存分配函數(shù)的性質(zhì)可以查看博主的上一個專欄，這里不在贅述），再進行數(shù)據(jù)插入。
擴容的方式有以下幾種，這里簡單說說優(yōu)缺點
（1）單個元素擴容：每次擴容只增加一個元素的空間，這樣子會導(dǎo)致realloc函數(shù)調(diào)用過多導(dǎo)致的運行時間增加，但是內(nèi)存使用率會相當(dāng)高
（2）固定多個元素擴容：使用空間換取時間效率的方法
（3）倍數(shù)擴容：每次擴容時，都將空間擴容1.5倍或者2倍。能讓realloc函數(shù)的調(diào)用次數(shù)變得非常少，現(xiàn)在的計算機一般空間都比較大，建議使用第三種
bool SLCheckCapacity(SeqList* psl)
{
if (psl->size == psl->capacity)
{
int newcapacity = psl->capacity == 0 ? 4 : 2 * psl->capacity;
SLdatetype* ptmp = realloc(psl->seqlist, sizeof(SLdatetype) * newcapacity);
if (!ptmp)
{
perror("realloc capacity fail");
return false;
}
psl->seqlist = ptmp;
psl->capacity = newcapacity;
return true;
}
}
將這些擴容的程序封裝成一個函數(shù)SLCheckCapacity
那么尾插法的算法用C語言編寫出來是這樣的
void datapushback(SeqList* psl, SLdatetype n)
{
SLCheckCapacity(psl);
psl->seqlist[psl->size] = n;
psl->size++;
}
頭插法
小明看到排隊的人這么多，不行啊，我不等了。一下子插入進隊伍的開頭（錯誤示例，小朋友不要模仿）。此時隊伍里的人為了給前面的人留出位置，每個人都要往后退一位，于是罵聲四起。
將數(shù)據(jù)插入至表頭的方法稱為頭插法，首先我們還是先判斷順序表是否要擴容，之后將數(shù)據(jù)插入至開頭。
但是要注意，數(shù)據(jù)插入開頭的方式并不是直接讓開頭的數(shù)據(jù)變?yōu)椴迦氲臄?shù)據(jù)。這樣子會導(dǎo)致數(shù)據(jù)丟失。正確的方式是從表尾開始，數(shù)據(jù)依次往后挪動一位，直到表頭的數(shù)據(jù)位置變成了空余的數(shù)據(jù)位置再插入新數(shù)據(jù)。
用c語言實現(xiàn)頭插法的代碼如下
void datepushfront(SeqList* psl, SLdatetype n)
{
SLCheckCapacity(psl);
for (int i = psl->size; i > 0; i--)
{
psl->seqlist[i] = psl->seqlist[i - 1];
}
psl->seqlist[0] = n;
psl->size++;
}
任意位置的插入
小明的朋友在隊伍里排隊，看到在隊外的小明便招呼小明過來一起排，那么這時候排隊的人群就要分成兩部分了，小明的朋友的后置的人就要依次往后退一步騰出空間，而前置的人則保持不動的位置
那么理解順序表中任意位置的數(shù)據(jù)插入也是這個原理，首先要確定數(shù)據(jù)插入的位置，然后讓這個位置后的數(shù)據(jù)往后一個空間，前置的數(shù)據(jù)則保持原位。
首先還是要先判斷順序表的空間是否足夠，然后使用循環(huán)將后置數(shù)據(jù)往后一個空間，最后將數(shù)據(jù)插入指定位置。
現(xiàn)在來想想函數(shù)原型的參數(shù)應(yīng)該是什么，首先是我們想要插入的順序表，然后是數(shù)據(jù)插入的位置，最后是插入的數(shù)據(jù)的值。
那么函數(shù)原型如下：
void datainsert(SeqList* psl, int pos, SLdatetype n)
具體的代碼實現(xiàn)如下
void datainsert(SeqList* psl, int pos, SLdatetype n)
{
assert(psl);
assert(psl->size);
if (pos<0 || pos>psl->size)
//pos可以是表頭，也可以是表尾，超出則不行
{
perror("pos illegal");
exit(EXIT_FAILURE);
}
SLCheckCapacity(psl);
for (int i = psl->size - 1; i >= pos; i--)
//注意這里的pos指的是元素插入的順序表的下標(biāo)，具體實現(xiàn)可以根據(jù)要求進行修改
{
psl->seqlist[i+1] = psl->seqlist[i];
}
psl->seqlist[pos] = n;
}
這里再講講pos這個參數(shù)，由于我的設(shè)想中pos的位置是參考下標(biāo)的，所以for循環(huán)的取值如下，如果你需要的是其他實現(xiàn)（比如想要按照物理位置來選取pos，那么需要修改這些數(shù)據(jù)）。
如果你掌握了這個方法，那么我要恭喜你，你的頭插法和尾插法白學(xué)了，因為這個方法可以在任意位置插入數(shù)據(jù)，包括表頭和表尾（^_^Hiahiahia）
我們來計算一下順序表的插入的時間復(fù)雜度 是多少，根據(jù)插入的位置可以分為以下三種情況
（1）插入表尾（O（1））。
（2）插入表頭（O（N））。
（3）插入其他位置（F（pos）=n-pos）
平均的輸入與指令執(zhí)行次數(shù)的關(guān)系函數(shù)為N/2.
根據(jù)大O階的推導(dǎo)公式，時間復(fù)雜度為O（N）
刪除順序表中的數(shù)據(jù)
現(xiàn)在小明插隊的行為引來了眾怒，他被排隊的人群趕出了隊列，于是后面被插隊的人都往前了一步，隊伍的總長度少了一個人。
如何刪除一個數(shù)據(jù)呢，我們選擇一個位置，將這個位置的數(shù)據(jù)清空（實際操作時只需要將該位置的數(shù)據(jù)用后繼元素覆蓋即可，不需要將這個位置的數(shù)據(jù)清空），并將后面的數(shù)據(jù)往前移動，最后將順序表的表長減1.
思考一下函數(shù)原型是什么
首先要將順序表傳入函數(shù)，然后將指定的位置作為參數(shù)傳入函數(shù)。函數(shù)原型如下：
void DataDelete(SeqList* psl, int pos);
代碼實現(xiàn)如下：
void DataDelete(SeqList* psl, int pos)//刪除順序表中指定位置的數(shù)據(jù)
{
assert(psl);
assert(psl->size);
if (pos<0 || pos>=psl->size)
{
perror("illegal pos");
exit(EXIT_FAILURE);
}
for (int i = pos; i <psl->size - 1; i++)
{
psl->seqlist[i] = psl->seqlist[i + 1];
}
psl->size--;
}
順序表中數(shù)據(jù)的查找與修改
如果你掌握了前面有關(guān)順序表的特性，那么查找和修改順序表是一個易如反掌的事。
為什么這么說呢？因為仔細觀看前面畫的有關(guān)順序表的圖，有沒有覺得那些順序存儲的元素特別眼熟？沒錯，他們和數(shù)組的原理是非常相似的，如果你會訪問和修改數(shù)組，你就會訪問和修改順序表。
話不多說，直接上函數(shù)原型和代碼
首先思考訪問順序表的函數(shù)需要什么參數(shù)，假如你要上門拜訪一個人，那么是不是需要知道這個人所在的地點？
查找數(shù)據(jù)也是同理，需要輸入查找的位置。
void FindListData(const SeqList* psl, int pos);
函數(shù)實現(xiàn)如下
void FindListData(SeqList* psl, int pos)
{
assert(psl);
assert(psl->size);
if (pos < 0 || pos >= psl->size)
{
perror("illegal pos");
exit(EXIT_FAILURE);
}
printf("%d\n", psl->seqlist[pos]);
}
修改也是同理，我這里使用標(biāo)準(zhǔn)的輸入輸出函數(shù)對數(shù)據(jù)進行修改，修改方法不唯一。
void ModifyListData(SeqList* psl, int pos)
{
assert(psl);
assert(psl->size);
if (pos < 0 || pos >= psl->size)
{
perror("illegal pos");
exit(EXIT_FAILURE);
}
printf("請輸入修改后的數(shù)字");
scanf("%d", &(psl->seqlist[pos]));
}
如果大家在閱讀完這篇文章后發(fā)現(xiàn)問題歡迎指正，如果家人們有疑問，歡迎私信博主求解。博主將在觀看私信后回答問題。
最后附上順序表的所有源碼！
C語言實現(xiàn)順序表的所有源碼
博主將實現(xiàn)順序表的代碼分為一個頭文件和一個源文件，其中，頭文件用于聲明，源文件用于定義函數(shù)。不要忘記在源文件中包含此頭文件
頭文件“seqlist.h”文章來源：http://www.zghlxwxcb.cn/news/detail-804111.html
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#define N 100
typedef int SLdatetype;
typedef struct SeqList
{
SLdatetype* seqlist;
int capacity;
int size;
}SeqList;
//順序表的初始化與銷毀
void InitList(SeqList* psl);
void ListDestory(SeqList* psl);
//頭插法和尾插法
void datapushback(SeqList* psl, SLdatetype n);
void datapushfront(SeqList* psl, SLdatetype n);
//一些輔助函數(shù)
bool SLCheckCapacity(SeqList* psl);
void printlist(const SeqList* psl);
void dataPopback(SeqList* psl);//表尾刪除操作
void dataPopfornt(SeqList* psl);//表頭刪除操作
void datainsert(SeqList* psl, int pos, SLdatetype n);//任意位置插入
void DataDelete(SeqList* psl, int pos);//任意位置刪除
源文件“seqlist.c”：文章來源地址http://www.zghlxwxcb.cn/news/detail-804111.html
#include"seqlist.h"
bool SLCheckCapacity(SeqList* psl)
{
if (psl->size == psl->capacity)
{
int newcapacity = psl->capacity == 0 ? 4 : 2 * psl->capacity;
SLdatetype* ptmp = realloc(psl->seqlist, sizeof(SeqList) * newcapacity);
if (!ptmp)
{
perror("realloc capacity fail");
return false;
}
psl->seqlist = ptmp;
psl->capacity = newcapacity;
return true;
}
return true;
}
void InitList(SeqList* psl)
{
psl->seqlist = NULL;
psl->capacity = 0;
psl->size = 0;
}
void datapushback(SeqList* psl, SLdatetype n)
{
SLCheckCapacity(psl);
psl->seqlist[psl->size] = n;
psl->size++;
}
void datapushfront(SeqList* psl, SLdatetype n)
{
SLCheckCapacity(psl);
for (int i = psl->size; i > 0; i--)
{
psl->seqlist[i] = psl->seqlist[i - 1];
}
psl->seqlist[0] = n;
psl->size++;
}
void printlist(const SeqList* psl)
{
for (int i = 0; i < psl->size; i++)
{
printf("%d ", psl->seqlist[i]);
}
printf("\n");
}
void dataPopback(SeqList* psl)//尾刪法
{
assert(psl);
assert(psl->size);
psl->size--;
}
void dataPopfornt(SeqList* psl)//頭刪法
{
assert(psl);
assert(psl->size);
for (int i = 0; i < psl->size; i++)
{
psl->seqlist[i-1] = psl->seqlist[i];
}
psl->size--;
}
void datainsert(SeqList* psl, int pos, SLdatetype n)
{
assert(psl);
assert(psl->size);
if (pos<0 || pos>psl->size)
//pos可以是表頭，也可以是表尾，超出則不行
{
perror("pos illegal");
exit(EXIT_FAILURE);
}
SLCheckCapacity(psl);
for (int i = psl->size - 1; i >= pos; i--)
//注意這里的pos指的是元素插入的順序表的下標(biāo)，具體實現(xiàn)可以根據(jù)要求進行修改
{
psl->seqlist[i+1] = psl->seqlist[i];
}
psl->seqlist[pos] = n;
psl->size++;
}
void DataDelete(SeqList* psl, int pos)//刪除順序表中指定位置的數(shù)據(jù)
{
assert(psl);
assert(psl->size);
if (pos<0 || pos>=psl->size)
{
perror("illegal pos");
exit(EXIT_FAILURE);
}
for (int i = pos; i <psl->size - 1; i++)
{
psl->seqlist[i] = psl->seqlist[i + 1];
}
psl->size--;
}
void ListDestory(SeqList* psl)
{
free(psl->seqlist);
psl->capacity = 0;
psl->size = 0;
}
到了這里，關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)（2）——線性表其一（順序表）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
