當(dāng)我們寫完通訊錄后，順序表肯定難不倒你，跟著小張一起來(lái)學(xué)習(xí)順序表吧！
線性表
線性表（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ǔ)。
順序表
概念及結(jié)構(gòu)
順序表是用一段物理地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲(chǔ)。在數(shù)組上完成數(shù)據(jù)的增刪查改。
順序表一般可以分為：
- 靜態(tài)順序表：使用定長(zhǎng)數(shù)組存儲(chǔ)元素。
- 動(dòng)態(tài)順序表：使用動(dòng)態(tài)開辟的數(shù)組存儲(chǔ)。
接口實(shí)現(xiàn)
靜態(tài)順序表只適用于確定知道需要存多少數(shù)據(jù)的場(chǎng)景。靜態(tài)順序表的定長(zhǎng)數(shù)組導(dǎo)致N定大了，空間開多了浪費(fèi)，開少了不夠用。所以現(xiàn)實(shí)中基本都是使用動(dòng)態(tài)順序表，根據(jù)需要?jiǎng)討B(tài)的分配空間大小，所以下面我們實(shí)現(xiàn)動(dòng)態(tài)順序表。
typedef struct pro
{
int* p;// 指向動(dòng)態(tài)開辟的數(shù)組
int size;// 有效數(shù)據(jù)個(gè)數(shù)
int capcity;// 容量空間的大小
}pro;
void SeqListInit(pro* ps );//初始化順序表
void CheckCapacity(pro* ps);//判斷是否空間不夠，進(jìn)行擴(kuò)容
void SeqListPushBack(pro* ps,int x);//尾插
void SeqListPushFront(pro* ps, int x);//頭插
void SeqListPopBack(pro* ps);//尾刪
void SeqListPopFront(pro* ps);//頭刪
void SeqListPrint(pro* ps);//打印順序表
void SeqListInsert(pro* ps, int pos, int x);//隨意插
void SeqListErase(pro* ps, int pos);//隨意刪
void SeqListFind(pro* ps, int pos);//查找
void SeqListmodify(pro* ps, int x,int y);//修改
void SeqListDestory(pro* ps);//銷毀
結(jié)構(gòu)體定義和創(chuàng)建一個(gè)結(jié)構(gòu)體變量
typedef struct pro
{
int* p;// 指向動(dòng)態(tài)開辟的數(shù)組
int size;// 有效數(shù)據(jù)個(gè)數(shù)
int capcity;// 容量空間的大小
}pro;
int main()
{
pro info;//定義一個(gè)結(jié)構(gòu)體變量
}
初始化順序表
void SeqListInit(pro* ps )//初始化順序表
{
ps->p = NULL;
ps->size = 0;
ps->capcity = 0;
}
初始化順序表，有效數(shù)據(jù)個(gè)數(shù)為0，容量空間大小為0，還未給數(shù)據(jù)動(dòng)態(tài)開辟空間，指向動(dòng)態(tài)開辟空間的指針指向空地址
擴(kuò)容順序表
void CheckCapacity(pro* ps)//判斷是否空間不夠，進(jìn)行擴(kuò)容
{
if (ps->size == ps->capcity)
{
int newcapcity = ps->capcity == 0 ? 4 : (ps->capcity) * 2;
int* tmp = (int*)realloc(ps->p, sizeof(int) * newcapcity);
if (tmp == NULL)
{
perror("realloc fail!!");
}
ps->p = tmp;
ps->capcity = newcapcity;
}
}
什么時(shí)候需要擴(kuò)容順序表呢？？當(dāng)順序表剛被初始化，你要進(jìn)行插入數(shù)據(jù)時(shí)，發(fā)現(xiàn)容量空間已經(jīng)滿了，此時(shí)必須要擴(kuò)容空間，當(dāng)你要插入第一個(gè)數(shù)據(jù)時(shí)，在此之前，順序表沒有任何數(shù)據(jù)，容量空間為0，然后要插入數(shù)據(jù)的話，也必須擴(kuò)容。
條件判斷如果有效數(shù)據(jù)個(gè)數(shù)等于容量大小時(shí)，分兩種情況，第一種，剛開始的時(shí)候，有效數(shù)據(jù)個(gè)數(shù)和容量大小都為0的時(shí)候，第二種，當(dāng)要插入數(shù)據(jù)時(shí)，發(fā)現(xiàn)此時(shí)的有效數(shù)據(jù)個(gè)數(shù)和容量大小相等時(shí)，且不等于0.對(duì)空間進(jìn)行擴(kuò)容， newcapcity變量是新的容量大小，當(dāng)需要擴(kuò)容的時(shí)候，直接新容量為原來(lái)的2倍，剛開始，他的容量是0，采用三目運(yùn)算符，如果容量是0的話，就給四個(gè)空間大小，如果不是就開原來(lái)容量的2倍。將realloc來(lái)的空間的地址存放在tmp指針里面，如果realloc失敗就返回空指針，打印錯(cuò)誤信息，realloc成功的話就將tmp中存放擴(kuò)容的地址交給指針p,然后容量大小更新為newcapcity。
尾插
void SeqListPushBack(pro* ps,int x)//尾插
{
CheckCapacity(ps);
ps->p[ps->size] = x;
ps->size++;}
每次插入都要判斷是否需要擴(kuò)容
然后有效數(shù)據(jù)+1.
頭插
void SeqListPushFront(pro* ps, int x)//頭插
{
CheckCapacity(ps);
int end = ps->size - 1;
while (end>=0)
{
ps->p[end + 1] = ps->p[end];
end--;
}
ps->p[0] = x;
ps->size++;
}
頭插一個(gè)數(shù)據(jù)，必須將后面的數(shù)據(jù)向后面移動(dòng)，移動(dòng)的過(guò)程中可能超過(guò)容量大小，所以在插入時(shí)都需要進(jìn)行擴(kuò)容判斷
如果按這個(gè)順序移動(dòng)數(shù)據(jù)當(dāng)1挪到2的位置的時(shí)候，2這個(gè)數(shù)據(jù)就會(huì)被覆蓋，所以我們必須從后往前面挪當(dāng)數(shù)據(jù)挪到后面之后，然后在第一個(gè)位置填入x,第一個(gè)位置也就是下標(biāo)為0的位置。
在下標(biāo)為0的地方填入 插入的數(shù)據(jù)x,然后ps->size+1;
尾刪
void SeqListPopBack(pro* ps)//尾刪
{
assert(ps);
assert(ps->size > 0);
ps->size--;
}
尾巴要?jiǎng)h除一個(gè)數(shù)據(jù)的話，我們需要將刪除的數(shù)據(jù)改為0嗎？如果要?jiǎng)h除的數(shù)據(jù)本來(lái)就是0呢？所以我們只需要將ps->size–;因?yàn)榇蛴〉臅r(shí)候只打印到下標(biāo)為ps->size-1的位置，打印出來(lái)看起來(lái)就像 我們刪除了這個(gè)數(shù)據(jù)，注意這里用斷言是因?yàn)樵趧h除的時(shí)候ps->size–,當(dāng)ps->size<0的時(shí)候，在添加數(shù)據(jù)時(shí)
ps->p[-1]=x;這個(gè)是不合理的，在ps->size<0時(shí)，直接報(bào)錯(cuò)，第一個(gè)斷言是為了防止空指針。
頭刪
void SeqListPopFront(pro* ps)//頭刪
{
assert(ps->size > 0);
int begin = 1;
while (begin<ps->size)
{
ps->p[begin - 1] = ps->p[begin];
begin++;
}
ps->size--;
}
這里的斷言和上面是一個(gè)道理，然后相比尾刪向后挪動(dòng)數(shù)據(jù)，頭刪是往前挪數(shù)據(jù)，吸取尾刪的教訓(xùn)，我們可以直到移動(dòng)的順序是
定義一個(gè)變量begin=1,首先是要將數(shù)據(jù)2移動(dòng)到數(shù)據(jù)1的位置，對(duì)應(yīng)的操作是
ps->p[begin - 1] = ps->p[begin];然后begin++,依次將數(shù)據(jù)3挪到數(shù)據(jù)2的位置，數(shù)據(jù)4挪到數(shù)據(jù)3的位置。循環(huán)最后一次是將數(shù)據(jù)5挪到數(shù)據(jù)4的位置，也就是begin=4,ps->size=5.則循環(huán)判斷條件為beginsize,循環(huán)結(jié)束后將
ps->size–;
順序表的打印
void SeqListPrint(pro* ps)//打印順序表
{
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->p[i]);
}
}
循環(huán)遍歷順序表，將每個(gè)數(shù)據(jù)打印出來(lái)
隨意插
void SeqListInsert(pro* ps, int pos, int x)//隨意插
{
CheckCapacity(ps);
assert(pos>=0&&pos<=ps->size);
int end = ps->size - 1;
while (end>=pos)
{
ps->p[end + 1] = ps->p[end];
end--;
}
ps->p[pos] = x;
ps->size++;
}
斷言是為了檢查插入的位置是否合理
當(dāng)有5個(gè)數(shù)據(jù)時(shí)，pos的可能取值如圖所示，推廣到一般
就是pos>=0&&pos<=ps->size,如果我們想在pos=2的位置插入一個(gè)x,我們應(yīng)該怎么做呢？
1.插入一個(gè)x,我們需要將3，4，5向后移動(dòng)，必須先移動(dòng)5，定義一個(gè)變量end,
end變量的初值給ps->size-1，也就是4，要想將數(shù)據(jù)5向后挪動(dòng)，對(duì)應(yīng)的操作是ps->p[end + 1] = ps->p[end];然后end–;循環(huán)分別將4，3向后挪動(dòng)，循環(huán)結(jié)束后，將數(shù)據(jù)x插入到pos=2的位置，對(duì)應(yīng)操作為ps->p[pos] = x;然后有效數(shù)據(jù)大小ps->size++；
隨意刪
void SeqListErase(pro* ps, int pos)//隨意刪
{
int begin = pos;
assert(pos >= 0 && pos <= ps->size);
while (begin<ps->size-1)
{
ps->p[begin] = ps->p[begin+1];
begin++;
}
ps->size--;
}
斷言判斷刪除的數(shù)據(jù)的位置是否合理，和隨意插的那里一樣
如果我們要?jiǎng)h除數(shù)3，然后數(shù)據(jù)3后面的數(shù)據(jù)向前挪動(dòng)，第一步就是將數(shù)據(jù)4移動(dòng)到數(shù)據(jù)3的位置，定義一個(gè)變量begin=pos=2;對(duì)應(yīng)的操作為
ps->p[begin] = ps->p[begin+1];，然后begin++;將數(shù)據(jù)5移動(dòng)到最開始數(shù)據(jù)4的地方。最后一次循環(huán)是將數(shù)據(jù)5移動(dòng)到數(shù)據(jù)4的地方，也就是begin最后等于3，ps->size=5，則循環(huán)判斷條件是begin< ps->size-1,循環(huán)結(jié)束將ps->size–;
順序表的查找
void SeqListFind(pro* ps, int pos)//查找
{
assert(pos >= 0 && pos < ps->size);
printf("你查找的下標(biāo)是%d,對(duì)應(yīng)的數(shù)據(jù)是%d", pos, ps->p[pos]);
}
斷言保證查找位置的合理性，因?yàn)楹瘮?shù)傳參pos 剛好是要查找數(shù)據(jù)的下標(biāo)，直接打印出來(lái)
順序表的修改
void SeqListmodify(pro* ps, int x,int y)//修改
{
for (int i = 0; i < ps->size; i++)
{
if (x == ps->p[i])
{
ps->p[i] = y;
}
}
}
x為修改前的值，y是修改之后的值，循環(huán)遍歷順序表，將順序表中所有的x都修改成y文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-691770.html
順序表的銷毀
void SeqListDestory(pro* ps)//銷毀
{
ps->capcity = 0;
ps->size = 0;
free(ps->p);
ps->p = NULL;
}
銷毀一個(gè)順序表，將順序表的容量置為0，順序表的有效數(shù)據(jù)個(gè)數(shù)置為0，將p指針?biāo)赶虻膭?dòng)態(tài)開辟的內(nèi)存空間釋放了，由于釋放了動(dòng)態(tài)開辟的內(nèi)存空間，所有p指向的空間未初始化，p成為野指針，為了防止野指針，將p置為空指針。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-691770.html
整體代碼
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct pro
{
int* p;// 指向動(dòng)態(tài)開辟的數(shù)組
int size;// 有效數(shù)據(jù)個(gè)數(shù)
int capcity;// 容量空間的大小
}pro;
void SeqListInit(pro* ps )//初始化順序表
{
ps->p = NULL;
ps->size = 0;
ps->capcity = 0;
}
void CheckCapacity(pro* ps)//判斷是否空間不夠，進(jìn)行擴(kuò)容
{
if (ps->size == ps->capcity)
{
int newcapcity = ps->capcity == 0 ? 4 : (ps->capcity) * 2;
int* tmp = (int*)realloc(ps->p, sizeof(int) * newcapcity);
if (tmp == NULL)
{
perror("realloc fail!!");
}
ps->p = tmp;
ps->capcity = newcapcity;
}
}
void SeqListPushBack(pro* ps,int x)//尾插
{
CheckCapacity(ps);
ps->p[ps->size] = x;
ps->size++;
}
void SeqListPushFront(pro* ps, int x)//頭插
{
CheckCapacity(ps);
int end = ps->size - 1;
while (end>=0)
{
ps->p[end + 1] = ps->p[end];
end--;
}
ps->p[0] = x;
ps->size++;
}
void SeqListPopBack(pro* ps)//尾刪
{
assert(ps);
assert(ps->size > 0);
ps->size--;
}
void SeqListPopFront(pro* ps)//頭刪
{
assert(ps->size > 0);
int begin = 1;
while (begin<ps->size)
{
ps->p[begin - 1] = ps->p[begin];
begin++;
}
ps->size--;
}
void SeqListPrint(pro* ps)//打印順序表
{
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->p[i]);
}
}
void SeqListInsert(pro* ps, int pos, int x)//隨意插
{
CheckCapacity(ps);
assert(pos>=0&&pos<=ps->size);
int end = ps->size - 1;
while (end>=pos)
{
ps->p[end + 1] = ps->p[end];
end--;
}
ps->p[pos] = x;
ps->size++;
}
void SeqListErase(pro* ps, int pos)//隨意刪
{
int begin = pos;
assert(pos >= 0 && pos <= ps->size);
while (begin<ps->size-1)
{
ps->p[begin] = ps->p[begin+1];
begin++;
}
ps->size--;
}
void SeqListFind(pro* ps, int pos)//查找
{
assert(pos >= 0 && pos < ps->size);
printf("你查找的下標(biāo)是%d,對(duì)應(yīng)的數(shù)據(jù)是%d", pos, ps->p[pos]);
}
void SeqListmodify(pro* ps, int x,int y)//修改
{
for (int i = 0; i < ps->size; i++)
{
if (x == ps->p[i])
{
ps->p[i] = y;
}
}
}
void SeqListDestory(pro* ps)//銷毀
{
ps->capcity = 0;
ps->size = 0;
free(ps->p);
ps->p = NULL;
}
int main()
{
pro info;
SeqListInit(&info);
printf("尾插:");
SeqListPushBack(&info, 1);
SeqListPushBack(&info, 2);
SeqListPushBack(&info, 3);
SeqListPushBack(&info, 4);
SeqListPrint(&info);
printf("\n");
printf("頭插:");
SeqListPushFront(&info, 7);
SeqListPushFront(&info, 6);
SeqListPushFront(&info, 5);
SeqListPushFront(&info, 5);
SeqListPrint(&info);
printf("\n");
printf("尾刪:");
SeqListPopBack(&info);
SeqListPrint(&info);
printf("\n");
printf("頭刪:");
SeqListPopFront(&info);
SeqListPrint(&info);
printf("\n");
printf("隨意插:");
SeqListInsert(&info, 1, 1);
SeqListPrint(&info);
printf("\n");
printf("隨意刪:");
SeqListErase(&info,1,1);
SeqListPrint(&info);
printf("\n");
printf("查找:");
SeqListFind(&info, 3);
printf("\n");
printf("修改:");
SeqListmodify(&info, 1, 2);
SeqListPrint(&info);
printf("\n");
printf("銷毀:");
SeqListDestory(&info);
SeqListPrint(&info);
}
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】順序表詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
