1. 前言
在前一個(gè)章節(jié)中我們介紹到, 數(shù)據(jù)結(jié)構(gòu)(Data Structure)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式，指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。 那么具體有哪些結(jié)構(gòu)是我們常常用來(lái)存儲(chǔ)數(shù)據(jù)的呢?今天就給大家講解其中的一個(gè)結(jié)構(gòu):順序表, 本篇文章將收錄于數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)分享專(zhuān)欄,有興趣閱讀更多關(guān)于數(shù)據(jù)結(jié)構(gòu)知識(shí)的可以點(diǎn)點(diǎn)訂閱,持續(xù)更新中ing~~.
想看順序表所有代碼的同學(xué),我的碼云放在了最后
2. 線(xiàn)性表
在我們認(rèn)識(shí)順序表之前,我們先來(lái)了解一些線(xiàn)性表的概念:
- . 線(xiàn)性表（linear list）是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。 線(xiàn)性表是一種在實(shí)際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見(jiàn)的線(xiàn)性表：順序表、鏈表、棧、隊(duì)列、字符串…
- 線(xiàn)性表在邏輯上是線(xiàn)性結(jié)構(gòu)，也就說(shuō)是連續(xù)的一條直線(xiàn)。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，線(xiàn)性表在物
理上存儲(chǔ)時(shí)，通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲(chǔ)。
我們要講的順序表本質(zhì)上就是一個(gè)數(shù)組,通過(guò)數(shù)組形式來(lái)存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu),但是在數(shù)組的基礎(chǔ)上,它要求數(shù)據(jù)從頭開(kāi)始存,并且是連續(xù)存儲(chǔ),不能跳躍間隔
3. 順序表
3.1 概念以及結(jié)構(gòu)
順序表是用一段物理地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線(xiàn)性結(jié)構(gòu)，一般情況采用數(shù)組存儲(chǔ)。在數(shù)組上完成數(shù)據(jù)的增刪查改。 我們說(shuō)其實(shí)所有的數(shù)據(jù)結(jié)構(gòu)都離不開(kāi)增刪查改,因?yàn)樗淖饔檬怯脕?lái)存儲(chǔ)數(shù)據(jù),就得滿(mǎn)足這幾個(gè)需求
我們通常還講順序表分為兩種:
- 靜態(tài)順序表
- 動(dòng)態(tài)順序表
3.11 靜態(tài)順序表
靜態(tài)順序表就是使用定長(zhǎng)數(shù)組來(lái)存儲(chǔ)數(shù)據(jù),我們通常在寫(xiě)靜態(tài)順序表的時(shí)候?qū)?shù)組大小用define定義宏的形式定義在開(kāi)
但是靜態(tài)順序表有很大的缺陷,
- 那就是我不知道我要存儲(chǔ)的數(shù)據(jù)到底有多大,假如我的靜態(tài)空間為1000,但是我只存儲(chǔ)了100個(gè)數(shù)據(jù),這樣的空間浪費(fèi)是很可怕的
- . 又比如我們想存500個(gè)數(shù)據(jù),但是我們的靜態(tài)空間只有400個(gè),這也很苦惱.所以我們這一節(jié)只給大家實(shí)現(xiàn)動(dòng)態(tài)順序表,使用動(dòng)態(tài)順序表來(lái)彌補(bǔ)這種缺陷
3.12 動(dòng)態(tài)順序表
顧名思義就是通過(guò)動(dòng)態(tài)開(kāi)辟空間來(lái)存儲(chǔ)數(shù)據(jù)的順序表,這里我們可以使用malloc,realloc等函數(shù),實(shí)現(xiàn)它數(shù)據(jù)多了我們就擴(kuò)容這種功能
4. 順序表的實(shí)現(xiàn)
4.1 順序表內(nèi)容的命名
我們之前說(shuō)我們存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu)要實(shí)現(xiàn)增刪查改這些功能,這里我們給出了很幾個(gè)函數(shù)來(lái)實(shí)現(xiàn)這種功能,分別是: 尾插(在末尾插入數(shù)據(jù)),尾刪(刪除末尾的數(shù)據(jù)),頭插(從開(kāi)頭插入數(shù)據(jù)),頭刪(刪除開(kāi)頭的數(shù)據(jù)),還有一個(gè)銷(xiāo)毀順序表的函數(shù)和初始化函數(shù) ,我們將這些名字統(tǒng)一命名為:
- SeqListPushBack(尾插)
- SeqListPopBack(尾刪)
- SeqListPushFront(頭插)
- SeqListPopFront(頭刪)
- SeqListDestory(銷(xiāo)毀順序表)
- SeqListInit(初始化鏈表)
這里的前綴Seqlist就是順序表的意思,Push就是插入,Pop就是刪除.我們這樣命名這些函數(shù)的意義有兩個(gè),一是別人可以一眼看出我們寫(xiě)的函數(shù)是為了實(shí)現(xiàn)什么功能,增強(qiáng)了代碼的可讀性,二是這些函數(shù)名的出處來(lái)自于C++的STL庫(kù),在我們之后的C++學(xué)習(xí)中會(huì)遇見(jiàn)這些名字,所以我們跟著這個(gè)STL庫(kù)來(lái)取名字是沒(méi)有問(wèn)題的
_
如果你想取別的名字,比如a,b,c啥的也是沒(méi)問(wèn)題的,你自己能看懂就行,但是我不推薦這種做法,我們的代碼風(fēng)格也是很重要的.
4.2 初始化結(jié)構(gòu)
像這種比較正式的代碼我們都不會(huì)在一個(gè).c文件中完成.在我們編寫(xiě)代碼之前,我們需要?jiǎng)?chuàng)建三個(gè)文件,分別是:
- test.c文件—用來(lái)測(cè)試你寫(xiě)的順序表能不能用
- SeqList.c文件—函數(shù)的代碼實(shí)現(xiàn)
- SeqList.h文件—函數(shù)的聲明和庫(kù)函數(shù)的包含
我們先來(lái)定義一個(gè)結(jié)構(gòu)體:
struct SeqList
{
int* a;//創(chuàng)建的數(shù)組用來(lái)存儲(chǔ)數(shù)據(jù)
int size;//size代表數(shù)組中存儲(chǔ)了多少個(gè)有效數(shù)據(jù)
int capacity;//表示數(shù)組實(shí)際能存儲(chǔ)的空間有多大
};
我們會(huì)發(fā)現(xiàn),我們的結(jié)構(gòu)體中的數(shù)組定義用的是int類(lèi)型,那假如我們想存儲(chǔ)char類(lèi)型或者float類(lèi)型的數(shù)據(jù)我們就要把我們所有代碼中的int全都改了,所以我們這個(gè)地方借助typedef來(lái)重命名一下我們的類(lèi)型,并且我們還可以將我們的結(jié)構(gòu)體一塊重命名了,修改代碼后:
#pragma once//在.h文件中操作
#include<stdio.h>//包含常見(jiàn)的頭文件
#include<string.h>
#include<stdlib.h>
#include<assert.h>
#include<malloc.h>
typedef int SLDataType;//想存什么類(lèi)型就把int改成什么
//
typedef struct SeqList
{
SLDataType* a;
int size;//size代表數(shù)組中存儲(chǔ)了多少個(gè)有效數(shù)據(jù)
int capacity;//表示數(shù)組實(shí)際能存儲(chǔ)的空間有多大
}SL;//將struct SeqList重命名為SL,方便后面寫(xiě)代碼
4.3 初始化函數(shù)
我們定義了結(jié)構(gòu)體后沒(méi)有將結(jié)構(gòu)體初始化,所以我們寫(xiě)一個(gè)函數(shù)來(lái)將它初始化一下:(如果你不理解我們要傳地址,別慌,后面會(huì)講)
void SeqListInit(SL* ps)//初始化
{
ps->a = NULL;//這里代表數(shù)組里面最開(kāi)始什么都不放
ps->size = ps->capacity = 0;//容量和空間都為0
}
寫(xiě)完這個(gè)函數(shù)后,我們就可以在test,c文件中先調(diào)用一下它,看看有沒(méi)有問(wèn)題
#include"SeqList.h"//包含頭文件
void TestSeqList1()//這里我們?cè)趖est.c文件中創(chuàng)建了一個(gè)測(cè)試函數(shù),它的目的是為了測(cè)試我們寫(xiě)的SeqList.c文件中的代碼是否正確
{
SL s1;//定義一個(gè)結(jié)構(gòu)體(SL為重命名前的struct SeqList)
SeqListInit(&s1);
}
int main()
{
TestSeqList1();
//TestSeqList2();
return 0;
}
4.4 擴(kuò)容函數(shù)
我們?cè)诔跏蓟Y(jié)構(gòu)體時(shí),將數(shù)組的長(zhǎng)度設(shè)置為空,代表它是沒(méi)有空間的,所以我們?cè)谶M(jìn)行插入數(shù)據(jù)操作之前,應(yīng)該先判斷我們數(shù)組中有沒(méi)有空間?空間夠不夠?所以我們就引出了擴(kuò)容,我們把擴(kuò)容這個(gè)功能單獨(dú)寫(xiě)成一個(gè)函數(shù),當(dāng)然你也可以在尾插函數(shù)或者頭插函數(shù)中判斷是否需要擴(kuò)容,并且將擴(kuò)容函數(shù)一起寫(xiě)到尾插/頭插中,我們先上代碼再解釋:
(如果你不理解為什么要傳結(jié)構(gòu)體變量的地址,別慌,后面會(huì)講)
void SeqListCheckCapacity(SL* ps) //判斷是否需要擴(kuò)容
{
if (ps->size == ps->capacity)//兩種情況,一種為順序表沒(méi)有空間,一種為空間不夠(capacity已經(jīng)滿(mǎn)了)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//當(dāng)空間為0時(shí)給四個(gè)空間,不為0時(shí)將原先空間乘2;
SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));//當(dāng)我們的數(shù)組a的空間為0時(shí),realloc的功能相當(dāng)于malloc
if (tmp == NULL)//判斷動(dòng)態(tài)開(kāi)辟空間是否成功,如果不成功就退出程序
{
exit(-1);
}
ps->a = tmp;//將數(shù)組a指向我們開(kāi)辟成功的這份空間
ps->capacity = newcapacity;//將數(shù)組的容量賦值為新的容量
}
}
當(dāng)我們的size等于capacity時(shí),也就是數(shù)組存儲(chǔ)有效數(shù)據(jù)個(gè)數(shù)和空間容量大小相同時(shí),有兩種情況,一是size和capacity都為0,也就是沒(méi)有空間,還有一種就是空間被存儲(chǔ)滿(mǎn)了. 所以這個(gè)地方我們用了三目運(yùn)算符來(lái)判斷是哪一種情況,如果是沒(méi)有空間的情況,那我們先給它4個(gè)空間(當(dāng)然如果你愿意你也可以給他8個(gè),6個(gè),看你的意愿),如果是空間已經(jīng)滿(mǎn)了的情況,那我們就將它的空間給擴(kuò)容成原來(lái)的兩倍(當(dāng)然如果你愿意你也可以擴(kuò)容為原來(lái)的三倍,也是看你自己的意愿).最后將我們的數(shù)組指針a指向我們剛剛開(kāi)辟的這份空間.
4.5 尾插函數(shù)
在我們初始化之后,就可以開(kāi)始我們的尾插了,先上代碼再解釋:
( (如果你不理解為什么要傳結(jié)構(gòu)體變量的地址,別慌,后面會(huì)講) )
void SeqListPushBack(SL* ps, SLDataType x)//尾插
{
assert(ps!=NULL);//傳進(jìn)來(lái)的ps結(jié)構(gòu)體不能為空
SeqListCheckCapacity(ps);//這個(gè)地方我們只需要一級(jí)指針,傳ps而不是&ps,&ps是二級(jí)指針了
ps->a[ps->size] = x;//size位置剛好是數(shù)組最后一個(gè)元素的后一個(gè)位置
ps->size++;//尾插后講有效數(shù)據(jù)加1
}
在我們尾插之前,我們一定要判斷我們的數(shù)組存儲(chǔ)的數(shù)據(jù)是不是已經(jīng)滿(mǎn)了(甚至是不是沒(méi)有空間)
我們現(xiàn)在可以在test.c中測(cè)試一下我們寫(xiě)的尾插函數(shù)有沒(méi)有問(wèn)題:
#include"SeqList.h"
void TestSeqList1()
{
SL s1;//定義一個(gè)結(jié)構(gòu)體
SeqListInit(&s1);
SeqListPushBack(&s1,1);//尾插1 2 3 4
SeqListPushBack(&s1,2);
SeqListPushBack(&s1,3);
SeqListPushBack(&s1,4);
}
int main()
{
TestSeqList1();
return 0;
}
寫(xiě)完后如果你想看你是否插入成功了,我們可以取調(diào)試窗口查看,但是我覺(jué)得這樣每次都去看調(diào)試很麻煩,所以我寫(xiě)一個(gè)打印函數(shù),可以講數(shù)組的內(nèi)容打印出來(lái)
4.6 打印函數(shù)
void SeqListPrint(SL* ps)//打印
{
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
寫(xiě)完打印函數(shù)后我們?cè)偃ヲ?yàn)證一下上面寫(xiě)的尾插:
#include"SeqList.h"
void TestSeqList1()
{
SL s1;//定義一個(gè)結(jié)構(gòu)體
SeqListInit(&s1);
SeqListPushBack(&s1,1);//尾插1 2 3 4
SeqListPushBack(&s1,2);
SeqListPushBack(&s1,3);
SeqListPushBack(&s1,4);
SeqListPrint(&s1);
}
int main()
{
TestSeqList1();
return 0;
}
我們的1 2 3 4 就被打印出來(lái)了:
4.7 尾刪函數(shù)
先上代碼再解釋:
void SeqListPopBack(SL* ps)//尾刪
{
assert(ps);//ps不能為null
assert(ps->size > 0);//size必須大于0,不然是沒(méi)有數(shù)據(jù)可以刪除的,并且size--后,
//size會(huì)等于負(fù)數(shù),下次再使用ps->a[size]時(shí)會(huì)報(bào)錯(cuò)
ps->size--;//直接將size減1,我們的數(shù)組就訪(fǎng)問(wèn)不到最后一個(gè)數(shù)據(jù)了
}
這里大家可以自己去測(cè)試一下我們的尾刪代碼:
4.8 頭插函數(shù)
void SeqListPushFront(SL* ps, SLDataType x)//頭插
{
assert(ps);
SeqListCheckCapacity(ps);//判斷是否需要擴(kuò)容
int end = ps->size-1;//將end指向數(shù)組的最后一個(gè)元素
while (end >= 0)
{
ps->a[end + 1] = ps->a[end];//將前面的數(shù)據(jù)往后挪動(dòng),而且必須是從最后一個(gè)數(shù)據(jù)開(kāi)始挪
end--;
}
ps->a[0] = x;//將插入的數(shù)據(jù)放在第一個(gè)位置
ps->size++;//將有效數(shù)據(jù)加1
}
這里我還是說(shuō)明一下為什么我們挪動(dòng)數(shù)據(jù)的時(shí)候要從后面開(kāi)始挪動(dòng):
這里大家可以用test.c文件去測(cè)試一下:
4.9 頭刪函數(shù)
和尾刪一樣,頭刪之前也要判斷我們的順序表是否為空.
void SeqListPopFront(SL* ps)//頭刪
{
assert(ps);
assert(ps->size > 0);
for (int i = 1; i < ps->size; i++)
{
ps->a[i - 1] = ps->a[i];//將后面的數(shù)據(jù)往前挪動(dòng),并且要從最開(kāi)頭開(kāi)始挪動(dòng),原因和我們之前的頭插是一樣的
}
ps->size--;//挪動(dòng)完后將size減1
}
4.10 銷(xiāo)毀順序表
當(dāng)我們使用完順序表表后,需要將它銷(xiāo)毀掉,并且下次使用時(shí)再重新初始化:
void SeqListDestory(SL* ps)//銷(xiāo)毀順序表
{
free(ps->a);//把a(bǔ)指向的空間釋放掉
ps->a = NULL;//將指針a置空
ps->size = 0;//將size和capacity都置空
ps->capacity = 0;
}
5. 寫(xiě)代碼時(shí)應(yīng)該注意的點(diǎn)
- . 我們?cè)趯?xiě)尾插,尾刪,頭插,頭刪…時(shí),我們將結(jié)構(gòu)體的地址傳過(guò)去,并且用指向接受,這時(shí)因?yàn)槲覀冃枰淖兘Y(jié)構(gòu)體里面的內(nèi)容,和我們之前講過(guò)的傳值調(diào)用和傳址調(diào)用一樣,但是我們的打印函數(shù)其實(shí)是可以不傳地址過(guò)去的,因?yàn)樗桓淖冊(cè)瓉?lái)的內(nèi)容只是實(shí)現(xiàn)一個(gè)打印功能,但是為了這個(gè)地方函數(shù)聲明的統(tǒng)一美觀,所以我這里也傳了地址過(guò)去,當(dāng)然你們也可以不傳地址
- 我們?cè)趯?shí)現(xiàn)頭插和尾插的時(shí)候,首先要判斷順序表的空間足不足夠,或者有沒(méi)有空間,而在我們實(shí)現(xiàn)頭刪和尾刪的時(shí)候,首先要判斷順序表中還有沒(méi)有內(nèi)容給我們刪除,如果你不做判斷,多刪了內(nèi)容,可能這時(shí)是不會(huì)報(bào)錯(cuò)的,但是你在銷(xiāo)毀順序表時(shí)會(huì)遇見(jiàn)錯(cuò)誤
- 寫(xiě)代碼時(shí)應(yīng)該注意我們的命名風(fēng)格,因?yàn)槲覀兊拇a不僅僅是給自己看的,更重要的是別人能夠讀懂!如果命名風(fēng)格不好,甚至你自己過(guò)了段時(shí)間你都不知道自己寫(xiě)的是什么意思.
6. 順序表問(wèn)題思考以及題目推薦
問(wèn)題：
1. 順序表的中間/頭部的插入刪除，時(shí)間復(fù)雜度為O(N)
2. 增容需要申請(qǐng)新空間，拷貝數(shù)據(jù)，釋放舊空間。會(huì)有不小的消耗。
3. 增容一般是呈2倍的增長(zhǎng)，勢(shì)必會(huì)有一定的空間浪費(fèi)。例如當(dāng)前容量為100，滿(mǎn)了以后增容到200，我們
再繼續(xù)插入了5個(gè)數(shù)據(jù)，后面沒(méi)有數(shù)據(jù)插入了，那么就浪費(fèi)了95個(gè)數(shù)據(jù)空間。
思考：如何解決以上問(wèn)題呢？ 我們下一章將會(huì)為大家揭曉!
相關(guān)題目:
- 原地移除數(shù)組中所有的元素val，要求時(shí)間復(fù)雜度為O(N)，空間復(fù)雜度為O(1)。OJ題鏈接
- 刪除排序數(shù)組中的重復(fù)項(xiàng)。OJ題鏈接
- 合并兩個(gè)有序數(shù)組。OJ題鏈接
7. 總結(jié)
本章給大家講解完了數(shù)據(jù)結(jié)構(gòu)中最簡(jiǎn)單的結(jié)構(gòu)—順序表的增刪查改,其實(shí)我們的順序表還可以實(shí)現(xiàn)查找特定位置的數(shù)據(jù),
刪除特定位置的數(shù)據(jù)的功能,這里我只給出了我們最簡(jiǎn)單的功能的實(shí)現(xiàn),有興趣的同學(xué)可以去我的碼云看看所有的代碼.
下章預(yù)告:單鏈表文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-449409.html
我的碼云:gitee:杭電碼農(nóng)文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-449409.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)分享之順序表詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
