C++?數(shù)據(jù)結(jié)構(gòu)超詳細(xì)講解順序表
(●’?’●)
前言
線(xiàn)性表是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ǔ)。
本章我們來(lái)深度初體驗(yàn)順序表
一、順序表是什么
概念及結(jié)構(gòu)
順序表是一段物理地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線(xiàn)性結(jié)構(gòu),一般情況下采用數(shù)組存儲(chǔ)。在數(shù)組上完成數(shù)據(jù)的增刪查改。
1.靜態(tài)順序表:使用定長(zhǎng)數(shù)組存儲(chǔ)元素
2.動(dòng)態(tài)順序表:使用動(dòng)態(tài)開(kāi)辟的數(shù)組存儲(chǔ)
二、順序表的實(shí)現(xiàn)
基本結(jié)構(gòu)
typedef int SLDataType; // 順序表的動(dòng)態(tài)存儲(chǔ) typedef struct SeqList { SLDataType* array; // 指向動(dòng)態(tài)開(kāi)辟的數(shù)組 size_t size ; // 有效數(shù)據(jù)個(gè)數(shù) size_t capicity ; // 容量空間的大小 }SeqList;
接口實(shí)現(xiàn)
靜態(tài)順序表只適用于確定知道需要多少數(shù)劇的場(chǎng)景。靜態(tài)順序表的定長(zhǎng)數(shù)組導(dǎo)致N定大了,空間開(kāi)多了浪費(fèi),開(kāi)少了不夠用。所以我們基本使用動(dòng)態(tài)順序表
typedef int SLDataType; // 順序表的動(dòng)態(tài)存儲(chǔ) typedef struct SeqList { SLDataType* array; // 指向動(dòng)態(tài)開(kāi)辟的數(shù)組 size_t size ; // 有效數(shù)據(jù)個(gè)數(shù) size_t capicity ; // 容量空間的大小 }SeqList; // 基本增刪查改接口 // 順序表初始化 void SeqListInit(SeqList* psl, size_t capacity); // 檢查空間,如果滿(mǎn)了,進(jìn)行增容 void CheckCapacity(SeqList* psl); // 順序表尾插 void SeqListPushBack(SeqList* psl, SLDataType x); // 順序表尾刪 void SeqListPopBack(SeqList* psl); // 順序表頭插 void SeqListPushFront(SeqList* psl, SLDataType x); // 順序表頭刪 void SeqListPopFront(SeqList* psl); // 順序表查找 int SeqListFind(SeqList* psl, SLDataType x); // 順序表在pos位置插入x void SeqListInsert(SeqList* psl, size_t pos, SLDataType x); // 順序表刪除pos位置的值 void SeqListErase(SeqList* psl, size_t pos); // 順序表銷(xiāo)毀 void SeqListDestory(SeqList* psl); // 順序表打印 void SeqListPrint(SeqList* psl);
順序表打印
普通的通過(guò)鏈表的數(shù)組打印
void SeqListPrint(SeqList* ps1) { assert(ps1); for (int i = 0; i < ps1->size; ++i) { printf("%d", ps1->a[i]); } printf("\n"); }
順序表初始化
置空
void SeqListInit(SeqList* ps1) { assert(ps1); ps1->a = NULL; ps1->size = 0; ps1->capacity = 0; }
順序表銷(xiāo)毀
順序表本質(zhì)是數(shù)組,是一片連續(xù)的存儲(chǔ)空間,頭部操作置空即可
void SeqListDestory(SeqList* ps1) { assert(ps1); free(ps1->a); ps1->a = NULL; ps1->capacity = ps1->size = 0; }
動(dòng)態(tài)擴(kuò)容
由于是動(dòng)態(tài)順序表,就是為了控制長(zhǎng)度來(lái)解決問(wèn)題,對(duì)順序表的操作大多離不開(kāi)擴(kuò)容
由于順序表是連續(xù)的如果使用malloc會(huì)出現(xiàn)異地?cái)U(kuò)容的現(xiàn)象,realloc雖然也存在異地?cái)U(kuò),但會(huì)返回一片連續(xù)空間的首地址.
void SeqListCheckCapacity(SeqList* ps1) { assert(ps1); if (ps1->size == ps1->capacity)//滿(mǎn)了 { size_t newCapacity = ps1->capacity == 0 ? 4 : ps1->capacity * 2;//兩倍擴(kuò)容 SLDateType* tmp = realloc(ps1->a, sizeof(SLDateType) * newCapacity); if (tmp == NULL)//擴(kuò)容失敗 { printf("realloc fail\n"); exit(-1); } else//擴(kuò)容成功 { ps1->a = tmp; ps1->capacity = newCapacity; } } }
在pos位置插入x
對(duì)頭插尾插幫助極大
要判斷是否可以插入以及有沒(méi)有必要插入
過(guò)程圖示
void SeqListInsert(SeqList* ps1, size_t pos, SLDateType x) { if (pos > ps1->size)//如圖 { printf("越界:pos %d\n", pos); return; } SeqListCheckCapacity(ps1);//插入即要擴(kuò)容 size_t end = ps1->size; while (end > pos) { ps1->a[end] = ps1->a[end - 1];//數(shù)據(jù)后挪,騰出空間 --end; } //end=pos ps1->a[pos] = x; ps1->size++;//添加數(shù)據(jù),需要增長(zhǎng) }
刪除pos位置
對(duì)頭刪尾刪幫助極大
//注意,順序表只注意size以前,size以后無(wú)硬性要求可以寬容對(duì)待
void SeqListErase(SeqList* ps1, size_t pos) { assert(ps1); assert(pos < ps1->size);//同插入,需要有東西可刪 size_t begin = pos + 1; while (begin < ps1->size)//由后向前覆蓋 { ps1->a[begin - 1] = ps1->a[begin]; ++begin; } ps1->size--; }
順序表尾插
相當(dāng)于上文在size處插入數(shù)據(jù),調(diào)用即可
void SeqListPushBack(SeqList* ps1, SLDateType x) { assert(ps1); SeqListInsert(ps1, ps1->size, x); }
順序表尾刪
注意辨別size的位置
void SeqListPopBack(SeqList* ps1) { assert(ps1); SeqListErase(ps1, ps1->size-1); }
順序表頭插
void SeqListPushFront(SeqList* ps1, SLDateType x) { assert(ps1); SeqListInsert(ps1, 0, x); }
順序表頭刪
//只需考慮size有效數(shù)據(jù)前
void SeqListPopFront(SeqList* ps1) { assert(ps1); SeqListErase(ps1, 0); }
查找數(shù)據(jù)x
int SeqListFind(SeqList* ps1, SLDateType x) { assert(ps1); for (int i = 0; i < ps1->size; ++i) { if (ps1->a[i] == x) { return i;//返回下標(biāo) } } return -1;//沒(méi)找到 }
順序表的缺點(diǎ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,我們?cè)倮^續(xù)插入了5個(gè)數(shù)據(jù),后面沒(méi)有數(shù)據(jù)插入了,那么就浪費(fèi)了95個(gè)數(shù)據(jù)空間
由此,前輩們總結(jié)出了鏈表
幾道練手題
原地移除數(shù)組中所有的元素val,要求時(shí)間復(fù)雜度為O(N),空間復(fù)雜度為O(1)。題目鏈接
刪除排序數(shù)組中的重復(fù)項(xiàng)。鏈接
合并兩個(gè)有序數(shù)組.題目鏈接
總結(jié)
學(xué)習(xí)編程,解決問(wèn)題,數(shù)據(jù)結(jié)構(gòu)與算法正是非常好的工具。模擬實(shí)現(xiàn)正是對(duì)自身代碼能力的鍛煉提升,也對(duì)其有了更深的理解.競(jìng)賽的話(huà),我認(rèn)為要先對(duì)知識(shí)進(jìn)行系統(tǒng)深度的學(xué)習(xí),才可隨機(jī)應(yīng)變。不可盲目刷題,有些深層原理可能與做題所理解出的出入極大。
到此這篇關(guān)于C++ 數(shù)據(jù)結(jié)構(gòu)超詳細(xì)講解順序表的文章就介紹到這了,更多相關(guān)C++ 順序表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C語(yǔ)言編寫(xiě)基于TCP和UDP協(xié)議的Socket通信程序示例
這篇文章主要介紹了C語(yǔ)言編寫(xiě)基于TCP和UDP協(xié)議的Socket通信程序示例,其中TCP的客戶(hù)端與服務(wù)器端采用多線(xiàn)程實(shí)現(xiàn),需要的朋友可以參考下2016-03-03利用C語(yǔ)言實(shí)現(xiàn)經(jīng)典多級(jí)時(shí)間輪定時(shí)器
C語(yǔ)言是一門(mén)通用計(jì)算機(jī)編程語(yǔ)言,廣泛應(yīng)用于底層開(kāi)發(fā),這篇文章主要給大家介紹了關(guān)于利用C語(yǔ)言實(shí)現(xiàn)經(jīng)典多級(jí)時(shí)間輪定時(shí)器的相關(guān)資料,需要的朋友可以參考下2021-07-07C語(yǔ)言實(shí)現(xiàn)經(jīng)典windows游戲掃雷的示例代碼
今天我們會(huì)用C語(yǔ)言實(shí)現(xiàn)一個(gè)經(jīng)典的windows小游戲:掃雷。掃雷是一款單機(jī)小游戲,每次通關(guān)最高難度的關(guān)卡都會(huì)開(kāi)心好一陣?,F(xiàn)在學(xué)會(huì)了C語(yǔ)言,總算可以自己實(shí)現(xiàn)掃雷了。話(huà)不多說(shuō),咱們開(kāi)始吧2022-10-10C++利用容器查找重復(fù)列功能實(shí)現(xiàn)
本文將詳細(xì)介紹c++容器簡(jiǎn)介,c++容器的比較 與操作實(shí)例,需要了解更多的朋友可以參考下2012-11-11