C++?數(shù)據(jù)結(jié)構(gòu)超詳細(xì)講解順序表
(●’?’●)
前言
線性表是n個具有相同特性的數(shù)據(jù)元素的有限序列。線性表是一種在實際中廣泛使用的數(shù)據(jù)結(jié)構(gòu),常見的線性表:順序表、鏈表、棧、隊列、字符串。
線性表在邏輯上是線性結(jié)構(gòu),也就是說連續(xù)的一條直線,但是在物理結(jié)構(gòu)并不一定是連續(xù)的,線性表在物理上存儲時,通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲。
本章我們來深度初體驗順序表
一、順序表是什么
概念及結(jié)構(gòu)
順序表是一段物理地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu),一般情況下采用數(shù)組存儲。在數(shù)組上完成數(shù)據(jù)的增刪查改。
1.靜態(tài)順序表:使用定長數(shù)組存儲元素
2.動態(tài)順序表:使用動態(tài)開辟的數(shù)組存儲
二、順序表的實現(xiàn)
基本結(jié)構(gòu)
typedef int SLDataType; // 順序表的動態(tài)存儲 typedef struct SeqList { SLDataType* array; // 指向動態(tài)開辟的數(shù)組 size_t size ; // 有效數(shù)據(jù)個數(shù) size_t capicity ; // 容量空間的大小 }SeqList;
接口實現(xiàn)
靜態(tài)順序表只適用于確定知道需要多少數(shù)劇的場景。靜態(tài)順序表的定長數(shù)組導(dǎo)致N定大了,空間開多了浪費,開少了不夠用。所以我們基本使用動態(tài)順序表
typedef int SLDataType; // 順序表的動態(tài)存儲 typedef struct SeqList { SLDataType* array; // 指向動態(tài)開辟的數(shù)組 size_t size ; // 有效數(shù)據(jù)個數(shù) size_t capicity ; // 容量空間的大小 }SeqList; // 基本增刪查改接口 // 順序表初始化 void SeqListInit(SeqList* psl, size_t capacity); // 檢查空間,如果滿了,進(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); // 順序表銷毀 void SeqListDestory(SeqList* psl); // 順序表打印 void SeqListPrint(SeqList* psl);
順序表打印
普通的通過鏈表的數(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; }
順序表銷毀
順序表本質(zhì)是數(shù)組,是一片連續(xù)的存儲空間,頭部操作置空即可
void SeqListDestory(SeqList* ps1) { assert(ps1); free(ps1->a); ps1->a = NULL; ps1->capacity = ps1->size = 0; }
動態(tài)擴(kuò)容
由于是動態(tài)順序表,就是為了控制長度來解決問題,對順序表的操作大多離不開擴(kuò)容
由于順序表是連續(xù)的如果使用malloc會出現(xiàn)異地擴(kuò)容的現(xiàn)象,realloc雖然也存在異地擴(kuò),但會返回一片連續(xù)空間的首地址.
void SeqListCheckCapacity(SeqList* ps1) { assert(ps1); if (ps1->size == ps1->capacity)//滿了 { 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
對頭插尾插幫助極大
要判斷是否可以插入以及有沒有必要插入
過程圖示
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ù),需要增長 }
刪除pos位置
對頭刪尾刪幫助極大
//注意,順序表只注意size以前,size以后無硬性要求可以寬容對待
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;//沒找到 }
順序表的缺點
1. 中間/頭部的插入刪除,時間復(fù)雜度為O(N)
2. 增容需要申請新空間,拷貝數(shù)據(jù),釋放舊空間。會有不小的消耗。
3. 增容一般是呈2倍的增長,勢必會有一定的空間浪費。例如當(dāng)前容量為100,滿了以后增容到200,我們再繼續(xù)插入了5個數(shù)據(jù),后面沒有數(shù)據(jù)插入了,那么就浪費了95個數(shù)據(jù)空間
由此,前輩們總結(jié)出了鏈表
幾道練手題
原地移除數(shù)組中所有的元素val,要求時間復(fù)雜度為O(N),空間復(fù)雜度為O(1)。題目鏈接
刪除排序數(shù)組中的重復(fù)項。鏈接
合并兩個有序數(shù)組.題目鏈接
總結(jié)
學(xué)習(xí)編程,解決問題,數(shù)據(jù)結(jié)構(gòu)與算法正是非常好的工具。模擬實現(xiàn)正是對自身代碼能力的鍛煉提升,也對其有了更深的理解.競賽的話,我認(rèn)為要先對知識進(jìn)行系統(tǒng)深度的學(xué)習(xí),才可隨機(jī)應(yīng)變。不可盲目刷題,有些深層原理可能與做題所理解出的出入極大。
到此這篇關(guān)于C++ 數(shù)據(jù)結(jié)構(gòu)超詳細(xì)講解順序表的文章就介紹到這了,更多相關(guān)C++ 順序表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C語言編寫基于TCP和UDP協(xié)議的Socket通信程序示例
這篇文章主要介紹了C語言編寫基于TCP和UDP協(xié)議的Socket通信程序示例,其中TCP的客戶端與服務(wù)器端采用多線程實現(xiàn),需要的朋友可以參考下2016-03-03C語言實現(xiàn)經(jīng)典windows游戲掃雷的示例代碼
今天我們會用C語言實現(xiàn)一個經(jīng)典的windows小游戲:掃雷。掃雷是一款單機(jī)小游戲,每次通關(guān)最高難度的關(guān)卡都會開心好一陣?,F(xiàn)在學(xué)會了C語言,總算可以自己實現(xiàn)掃雷了。話不多說,咱們開始吧2022-10-10