程序中經(jīng)常需要將一組數(shù)據(jù)元素作為整體管理和使用，需要?jiǎng)?chuàng)建這種元素組，用變量記錄它們，傳進(jìn)傳出函數(shù)等。一組數(shù)據(jù)中包含的元素個(gè)數(shù)可能發(fā)生變化，順序表則是將元素順序地存放在一塊連續(xù)的存儲(chǔ)區(qū)里，元素間的順序關(guān)系由它們的存儲(chǔ)順序自然表示

本次我們解剖順序表將從以下三個(gè)結(jié)構(gòu)：

1、靜態(tài)順序表和動(dòng)態(tài)順序表

2、順序表實(shí)現(xiàn)增刪查改等常見接口

3、順序表相關(guān)OJ題練習(xí)

什么是順序表

順序表是用一段物理地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲(chǔ)。在數(shù)組上完成數(shù)據(jù)的增刪查改。

兄弟們兄弟們，記得摳字眼啊，順序表一定是連續(xù)的存儲(chǔ)單元，并且是依次存儲(chǔ)數(shù)據(jù)的?。。?！

順序表一般可以分為：

? 靜態(tài)順序表 ?? 動(dòng)態(tài)順序表

靜態(tài)順序表：使用定長(zhǎng)數(shù)組存儲(chǔ)，簡(jiǎn)單來說大小是固定的，數(shù)據(jù)個(gè)數(shù)也是固定的！

動(dòng)態(tài)順序表：使用動(dòng)態(tài)開辟的數(shù)組存儲(chǔ)，簡(jiǎn)單來說，裝滿了會(huì)自動(dòng)擴(kuò)大容量！

靜態(tài)順序表的實(shí)現(xiàn)我們就不講了，冬天到了春天還會(huì)遠(yuǎn)嗎？會(huì)了動(dòng)態(tài)你還不會(huì)靜態(tài)嗎？所以我們今天主要講動(dòng)態(tài)順序表！靜態(tài)順序表搭建代碼如下：

// 順序表的靜態(tài)存儲(chǔ)
#define N 100
typedef int SLDataType;
typedef struct SeqList
{
    SLDataType array[N]; // 定長(zhǎng)數(shù)組
    size_t size;     // 有效數(shù)據(jù)的個(gè)數(shù) 
}SeqList;

動(dòng)態(tài)順序表

?? 來到今天的重點(diǎn)！動(dòng)態(tài)順序表！

首先先來搭建順序表的結(jié)構(gòu)。

?? 上面就是我給大家畫的基本一個(gè)結(jié)構(gòu)圖了，下面我們來實(shí)現(xiàn)順序表的基本接口：

?? 首先我們順序表需要初始化：

?? 既然我們沒有在初始化給定大小，我們現(xiàn)在要判斷需不需要給動(dòng)態(tài)表順序表增容：

?? 我們來實(shí)現(xiàn)動(dòng)態(tài)順序表頭部插入數(shù)據(jù)：

?? 接著來實(shí)現(xiàn)尾部插入數(shù)據(jù)：

?? 我們要開始實(shí)現(xiàn)頭部刪除數(shù)據(jù)了：

?? 下面實(shí)現(xiàn)尾部刪除數(shù)據(jù)：

?? 接著我們來實(shí)現(xiàn)在pos下標(biāo)位置插入數(shù)據(jù)：

?? 我們?cè)賮韺?shí)現(xiàn)刪除pos下標(biāo)位置的數(shù)據(jù)：

? 查找順序表中的元素x：

?? 修改指定pos下標(biāo)的數(shù)據(jù)

在實(shí)際中在我上面寫的函數(shù)有些都可以復(fù)用哦！這個(gè)就等著你們?nèi)グl(fā)現(xiàn)吧，我們接著往下走：

其實(shí)還有一些順序表的打印，清空，求元素個(gè)數(shù)，這些相信你們看完上面的內(nèi)容對(duì)于你們來說非常容易！我就不一一舉例了，下面進(jìn)入我們的習(xí)題時(shí)間！(●'?'●)

題目1：給你一個(gè)數(shù)組 nums 和一個(gè)值 val，你需要原地移除所有數(shù)值等于 val 的元素，并返回移除后數(shù)組的新長(zhǎng)度。不要使用額外的數(shù)組空間，你必須僅使用 O(1) 額外空間并原地修改輸入數(shù)組。元素的順序可以改變。你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。

示例 1：

輸入：nums = [0,1,2,2,3,0,4,2], val = 2

輸出：5, nums = [0,1,4,0,3]

解釋：函數(shù)應(yīng)該返回新的長(zhǎng)度 5, 并且 nums 中的前五個(gè)元素為 0, 1, 3, 0, 4。注意這五個(gè)元素可為任意順序。你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。

題目來源：27. 移除元素 - 力扣（LeetCode） (leetcode-cn.com)

思路1：遍歷數(shù)組，發(fā)現(xiàn)元素為val就把后面的往前挪覆蓋掉val，但是這樣的時(shí)間復(fù)雜度為O(N²)，這樣當(dāng)數(shù)組全是val，效率就會(huì)特別低！

思路2：以空間換時(shí)間，開辟一個(gè)新數(shù)組，把不是val的數(shù)放到新數(shù)組，再把新數(shù)組的值拷貝回來！但是這樣的話空間復(fù)雜度O(N)不符合題意！

思路3：使用雙指針，空間復(fù)雜度O(1),時(shí)間復(fù)雜度O(n),代碼如下：

int removeElement(int* nums, int numsSize, int val)
{
	int src = 0;
	int dst = 0;
	while (src < numsSize)
	{
		if (nums[src] != val)
		{
			nums[dst++] = nums[src++];
		}
		else
		{
			++src;
		}
	}
	return dst;
}

題目2：給你兩個(gè)按非遞減順序排列的整數(shù)數(shù)組 nums1 和 nums2，另有兩個(gè)整數(shù) m 和 n ，分別表示 nums1 和 nums2 中的元素?cái)?shù)目。請(qǐng)你合并 nums2 到 nums1 中，使合并后的數(shù)組同樣按非遞減順序排列。

示例 1：

輸入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3

輸出：[1,2,2,3,5,6]

解釋：需要合并 [1,2,3] 和 [2,5,6] 。

合并結(jié)果是 [1,2,2,3,5,6] ，其中斜體加粗標(biāo)注的為 nums1 中的元素。

題目來源：88. 合并兩個(gè)有序數(shù)組 - 力扣（LeetCode） (leetcode-cn.com)

那這道題的思路就留給小伙伴們自己去思考了，我就直接給你們上代碼！

void merge(int* nums1, int m, int* nums2, int n)
{
	int end1 = m - 1;
	int end2 = n - 1;
	int end = m + n - 1;
	while (end1 >= 0 && end2 >= 0)
	{
		if (nums1[end1] > nums2[end2])
		{
			nums1[end] = nums1[end1];
			--end;
			--end1;
		}
		else
		{
			nums1[end] = nums2[end2];
			--end;
			--end2;
		}
	}
	//如果是end2結(jié)束，不需要處理因?yàn)榫褪窃趎ums1里面
	while (end2 >= 0)
	{
		nums1[end] = nums2[end2];
		--end;
		--end2;
	}
}

好了，通過這篇文章的學(xué)習(xí)，相信你會(huì)把順序表理解的更透徹，還是那句話，我們一起快樂編程不頭禿！加油奧里給！??????

????????????完結(jié)撒花！????????????

gitee(碼云)：Mercury. (zzwlwp) - Gitee.com

到此這篇關(guān)于C++超詳細(xì)分析順序表的文章就介紹到這了,更多相關(guān)C++ 順序表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: