【數(shù)據(jù)結(jié)構(gòu)】順序表詳解（附leetcode練習題）

這篇具有很好參考價值的文章主要介紹了【數(shù)據(jù)結(jié)構(gòu)】順序表詳解（附leetcode練習題）。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

??個人主頁：fighting小澤
??作者簡介：目前正在學習C語言和數(shù)據(jù)結(jié)構(gòu)
??博客專欄：數(shù)據(jù)結(jié)構(gòu)
???歡迎關(guān)注：評論????點贊????留言????

1.線性表

線性表（linear list）是n個具有相同特性的數(shù)據(jù)元素的有限序列。線性表是一種在實際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見的線性表：順序表、鏈表、棧、隊列、字符串…
線性表在邏輯上是線性結(jié)構(gòu)，也就說是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，線性表在物理上存儲時，通常以數(shù)組和鏈式結(jié)構(gòu)的形式存儲。

為什么要這樣存儲呢？
因為有很多的列表需要依次展示我們的數(shù)據(jù)，比如微信聯(lián)系人，成員列表。
那展示了以后還存在什么問題呢？
增刪查改
但是存儲這些數(shù)據(jù)又有一些很不一樣的東西，它是什么呢？我們做個簡單的比方：線性表中最簡單的存儲方式是線性表，大家知不知道順序表的本質(zhì)是什么？順序表的本質(zhì)非常簡單是一個數(shù)組，把數(shù)據(jù)存放到數(shù)組里。
大家知道數(shù)組的缺陷是什么嗎？假設(shè)我們想要刪除數(shù)組的某個元素，我們能不能把這塊空間釋放了？我們只能挪動數(shù)據(jù)覆蓋。所以有一個非常好的結(jié)構(gòu)叫鏈表，鏈表是一塊一塊的小空間，它們之間地址上沒有關(guān)聯(lián)，所以想要找到下一個空間的地址就得用一個指針，上一個空間里存放一個指向下一個空間的指針，這樣就把它們鏈接起來了。當我們想刪除某個元素的時候該怎么辦?這個時候就簡單了，我們把這個空間釋放掉，上一個空間的指針指向下一個空間就可以了，不需要挪動數(shù)據(jù)。

所以不同的結(jié)構(gòu)有不同的特點，就像公交車可以拉很多人，小轎車坐著很方便一樣。
那既然順序表，數(shù)組如此的不方便，我們還為什么要學習呢？
數(shù)組有一個它絕對的優(yōu)勢，是下標的隨機訪問，非常方便。比如二分查找能不能在鏈表上玩？不可以。包括后面我們學習排序，也是需要大量使用下標訪問，因為它們的物理空間連續(xù)。

【數(shù)據(jù)結(jié)構(gòu)】順序表詳解（附leetcode練習題）

2.順序表

2.1 概念及結(jié)構(gòu)

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

順序表一般可以分為：

靜態(tài)順序表：使用定長數(shù)組存儲元素。
動態(tài)順序表：使用動態(tài)開辟的數(shù)組存儲。

2.2 靜態(tài)順序表

一般情況下我們想創(chuàng)建一個靜態(tài)順序表只需要一個數(shù)組還不行，還得告訴我們數(shù)組中有多少數(shù)據(jù)是有效數(shù)據(jù),所以我們需要創(chuàng)建一個結(jié)構(gòu)體，定義一個數(shù)組和它有效數(shù)據(jù)的個數(shù)

struct SeqList
{
	int arr[10];
	int size;
};

但是當前這種定義方式在實踐中是不太好的，第一是因為它只能存放有限個數(shù)據(jù)，第二是它只能存放整形變量，所以我們可以對它進行改進：

用一個#define定義的宏來表示它存放的個數(shù)，用typedef對它的類型重命名。如果我們想進行修改，只需要改變#define定義的數(shù)值，或者改變typedef的類型。
由于結(jié)構(gòu)體的名字太長了，我們也可以把它改成一個較短的名字。

#define N 10
typedef int SLDatatype;

typedef struct SeqList
{
	SLDatatype arr[N];
	int sz;
}SL;

這樣就定義了一個靜態(tài)的順序表了，大家想想它有沒有什么缺點？

做個簡單的比方：如果我們定義了數(shù)組的大小是10，我們想存11個數(shù)據(jù)就存不下了，它的空間是固定的。假如我們給了10000個空間，我們想存10001個數(shù)據(jù)還是不夠用。就算大多數(shù)情況夠用了，但是我就存5個或者100個呢，空間是不是就浪費了。所以靜態(tài)順序表有一個特點，給小了不夠用，給多了浪費。

所以一般情況下不推薦大家寫靜態(tài)的順序表，推薦大家寫動態(tài)的順序表。

2.3 動態(tài)順序表

靜態(tài)順序表只適用于確定知道需要存多少數(shù)據(jù)的場景，所以現(xiàn)實中基本都是使用動態(tài)順序表，動態(tài)順序表的實現(xiàn)其實跟我們的通訊錄的實現(xiàn)差不多，根據(jù)需要動態(tài)的分配空間大小，所以下面我們實現(xiàn)動態(tài)順序表。

動態(tài)的順序表就是我們?nèi)alloc它的空間，空間滿了后我們可以用realloc擴容，不夠了擴就可以了，所以我們還要創(chuàng)建一個變量定義它的容量大小

typedef int SLDataType;
// 順序表的動態(tài)存儲
typedef struct SeqList
{
  SLDataType* array;  // 指向動態(tài)開辟的數(shù)組
  size_t size ;       // 有效數(shù)據(jù)個數(shù)
  size_t capicity ;   // 容量空間的大小
}SeqList;

然后就是動態(tài)順序表的初始化和增刪查改了：

// 基本增刪查改接口
// 順序表初始化
void SeqListInit(SeqList* psl);
// 檢查空間，如果滿了，進行增容
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);

2.4 動態(tài)順序表的實現(xiàn)

我們同樣需要創(chuàng)建三個文件夾來實現(xiàn)動態(tài)順序表，SeqList.h頭文件定義函數(shù)，SeqList.c文件對函數(shù)進行實現(xiàn)，test.c文件實現(xiàn)動態(tài)順序表。

2.41順序表的初始化和銷毀

首先就是初始化我們的順序表的初始化：
注意：由于我們要改變順序表，所以我們要傳順序表的地址過去。
我們對它進行初始化只需要把每個變量置為空即可。

void SeqListInit(SL* psl)
{
	psl->a = NULL;
	psl->sz = 0;
	psl->capicity = 0;
}

上面只是一種方法，其實還有一種更好的方法，我們可以先開辟一點空間，不一定開特別大，開小一點就行，當空間不夠了我們再重新開辟空間

void SeqListInit(SL* psl)
{
	assert(psl);
	SLDatatype* tmp = (SLDatatype*)malloc(N * sizeof(SLDatatype));
	if (tmp == NULL)
	{
		perror("SL_malloc");
		return;
	}
	psl->a = tmp;
	psl->sz = 0;
	psl->capicity = N;
}

由于順序表是我們動態(tài)開辟的空間，所以結(jié)束時我們要把它釋放掉，否則會出現(xiàn)內(nèi)存泄漏。同時還有可能訪問到這塊空間，所以我們要把指向它的指針置空。

void SLDestroy(SL* psl)
{
	assert(psl);
	free(psl->a);
	psl->a = NULL;
	psl->sz = 0;
	psl->capicity = 0;
}

2.42檢查順序表的容量

當我們對順序表增加元素的時候要確保順序表的容量是足夠大的，如果不夠，我們可以把它的容量擴大兩倍。而判斷順序表容量滿的方式就是看它的有效變量size和容量capicity是否相等

void CheckCapicity(SL* psl)
{
	assert(psl);
	if (psl->capicity == psl->sz)
	{
		SLDatatype* tmp = (SLDatatype*)realloc(psl->a, 2 * psl->capicity * sizeof(SLDatatype));
		if (tmp == NULL)
		{
			perror("SL_realloc");
			return;
		}
		psl->a = tmp;
		psl->capicity *= 2;
	}
}

2.43順序表的尾插和頭插

我們想在尾部插入一個元素特別特別簡單，從下標的角度數(shù)據(jù)個數(shù)就是最后一個元素的下標加1，我們只需要在size的位置放數(shù)據(jù)，然后再size++ 即可，注意判斷順序表的容量

void SLPushBack(SL* psl,SLDatatype x)
{
	assert(psl);
	CheckCapicity(psl);
	psl->a[psl->sz] = x;
	psl->sz++;
}

而我們想進行頭部插入，只能從后向前每一個元素向后移動一位，在頭部存放我們想存放的數(shù)據(jù)，然后size++即可。

void SLPushFront(SL* psl, SLDatatype x)
{
	assert(psl);
	CheckCapicity(psl);
	for (int i = psl->sz; i > 0; i--)
	{
		psl->a[i] = psl->a[i - 1];
	}
	psl->a[0] = x;
	psl->sz++;
}

2.44打印順序表的元素

打印其實也非常簡單，因為順序表本質(zhì)上是一個數(shù)組，打印數(shù)組的每一個元素即可，我們也可以打印出它的size和capicity。

void SLPrint(SL* psl)
{
	assert(psl);
	for (int i = 0; i < psl->sz; i++)
	{
		printf("%d ", psl->a[i]);
	}
	printf("\nsz=%d\n", psl->sz);
	printf("capicity=%d\n", psl->capicity);
}

現(xiàn)在讓我們來測試剛剛的頭插和尾插
【數(shù)據(jù)結(jié)構(gòu)】順序表詳解（附leetcode練習題）

2.45順序表的尾刪和頭刪

我們想進行順序表的尾刪該怎樣做呢？把最后一位賦值為0，賦值為-1？要是它本身就是0或-1該怎么辦？其實有一種簡單的方法，我們直接把size 減1就可以了，之后又新元素再把它覆蓋就行了

void SLPopBack(SL* psl)
{
	assert(psl->sz > 0);
	psl->sz -= 1;
}

我們想進行頭刪時，也是把每一個元素向前移動一位，然后size減1即可

void SLPopFront(SL* psl)
{
	assert(psl->sz > 0);
	for (int i = 0; i < psl->sz - 1; i++)
	{
		psl->a[i] = psl->a[i + 1];
	}
	psl->sz--;
}

測試一下：

【數(shù)據(jù)結(jié)構(gòu)】順序表詳解（附leetcode練習題）

2.46順序表的隨機插入和刪除

我們想要在任意位置插入元素，只需要將此位置和之后的元素都向后移動一位，然后在這個位置插入元素，然后size加1即可。注意pos的值要在范圍之內(nèi)。

void SLInsert(SL* psl, int pos, SLDatatype x)
{
	assert(psl);
	assert(pos > 0 && pos <= psl->sz);
	CheckCapicity(psl);
	for (int i = psl->sz; i > pos-1; i--)
	{
		psl->a[i] = psl->a[i-1];
	}
	psl->a[pos-1] = x;
	psl->sz++;
}

刪除也是將這個位置后的元素都向前移動一位，然后size減1。注意pos的值要在范圍之內(nèi)。

void SLErase(SL* psl, int pos)
{
	assert(psl);
	assert(pos > 0 && pos < psl->sz);
	CheckCapicity(psl);
	for (int i = pos - 1; i < psl->sz-1; i++)
	{
		psl->a[i] = psl->a[i + 1];
	}
	psl->sz--;
}

我們前面的頭插頭刪，尾插尾刪也可以使用這兩個函數(shù)，只需要改成特定的位置就行。
【數(shù)據(jù)結(jié)構(gòu)】順序表詳解（附leetcode練習題）

2.47順序表的修改

修改也非常簡單，只需要將這個位置的元素修改即可，不夠要注意位置的范圍要合理

void SLModify(SL* psl, int pos, SLDatatype x)
{
	assert(psl);
	assert(pos > 0 && pos < psl->sz);
	psl->a[pos - 1] = x;
}

【數(shù)據(jù)結(jié)構(gòu)】順序表詳解（附leetcode練習題）

3.整體代碼

3.1SeqList.h代碼

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

#define N 4
typedef int SLDatatype;

//typedef struct SeqList
//{
//	SLDatatype arr[N];
//	int sz;
//}SL;

//struct SeqList
//{
//	int arr[10];
//	int sz;
//};
typedef struct SeqList
{
	SLDatatype* a;
	int sz;
	int capicity;
}SL;

void SeqListInit(SL* psl);

void CheckCapicity(SL* psl);

void SLPushBack(SL* psl,SLDatatype x);//尾插

void SLPopBack(SL* psl);//尾刪

void SLPrint(SL* psl);

void SLDestroy(SL* psl);

void SLPushFront(SL* psl, SLDatatype x);//頭插

void SLPopFront(SL* psl);//頭刪

int SLFind(SL* psl, SLDatatype x);

void SLInsert(SL* psl, int pos, SLDatatype x);

void SLErase(SL* psl, int pos);

void SLModify(SL* psl, int pos, SLDatatype x);

3.2SeqList.c代碼

#include"SeqList.h"

void SeqListInit(SL* psl)
{
	assert(psl);
	SLDatatype* tmp = (SLDatatype*)malloc(N * sizeof(SLDatatype));
	if (tmp == NULL)
	{
		perror("SL_malloc");
		return;
	}
	psl->a = tmp;
	psl->sz = 0;
	psl->capicity = N;
}

void CheckCapicity(SL* psl)
{
	assert(psl);
	if (psl->capicity == psl->sz)
	{
		SLDatatype* tmp = (SLDatatype*)realloc(psl->a, 2 * psl->capicity * sizeof(SLDatatype));
		if (tmp == NULL)
		{
			perror("SL_realloc");
			return;
		}
		psl->a = tmp;
		psl->capicity *= 2;
	}

}

void SLPushBack(SL* psl,SLDatatype x)
{
	assert(psl);
	CheckCapicity(psl);
	psl->a[psl->sz] = x;
	psl->sz++;
}

void SLPopBack(SL* psl)
{
	assert(psl->sz > 0);
	psl->sz -= 1;
}

void SLPrint(SL* psl)
{
	assert(psl);
	for (int i = 0; i < psl->sz; i++)
	{
		printf("%d ", psl->a[i]);
	}
	printf("\nsz=%d\n", psl->sz);
	printf("capicity=%d\n", psl->capicity);
}

void SLDestroy(SL* psl)
{
	assert(psl);
	free(psl->a);
	psl->a = NULL;
	psl->sz = 0;
	psl->capicity = 0;
}

void SLPushFront(SL* psl, SLDatatype x)
{
	assert(psl);
	CheckCapicity(psl);
	for (int i = psl->sz; i > 0; i--)
	{
		psl->a[i] = psl->a[i - 1];
	}
	psl->a[0] = x;
	psl->sz++;
}

void SLPopFront(SL* psl)
{
	assert(psl->sz > 0);
	for (int i = 0; i < psl->sz - 1; i++)
	{
		psl->a[i] = psl->a[i + 1];
	}
	psl->sz--;
}

int SLFind(SL* psl, SLDatatype x)
{
	assert(psl);
	for (int i = 0; i < psl->sz; i++)
	{
		if (psl->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

void SLInsert(SL* psl, int pos, SLDatatype x)
{
	assert(psl);
	assert(pos > 0 && pos <= psl->sz);
	CheckCapicity(psl);
	for (int i = psl->sz; i > pos-1; i--)
	{
		psl->a[i] = psl->a[i-1];
	}
	psl->a[pos-1] = x;
	psl->sz++;
}

void SLErase(SL* psl, int pos)
{
	assert(psl);
	assert(pos > 0 && pos < psl->sz);
	CheckCapicity(psl);
	for (int i = pos - 1; i < psl->sz-1; i++)
	{
		psl->a[i] = psl->a[i + 1];
	}
	psl->sz--;
}

void SLModify(SL* psl, int pos, SLDatatype x)
{
	assert(psl);
	assert(pos > 0 && pos < psl->sz);
	psl->a[pos - 1] = x;

}

4.leetcode練習題

力扣26，刪除有序數(shù)組中的重復項
給你一個升序排列的數(shù)組 nums ，請你原地刪除重復出現(xiàn)的元素，使每個元素只出現(xiàn)一次，返回刪除后數(shù)組的新長度。元素的相對順序應該保持一致。然后返回 nums 中唯一元素的個數(shù)。

我們可以通過利用雙指針的方法來解決這道題，我們定義兩個指針同時指向第二個元素，快指針向前遍歷，如果兩個指針指向的內(nèi)容相同，快指針加1，慢指針不變。如果兩個指針指向的內(nèi)容不同，就將快指針的值賦值給慢指針，兩個指針同時加1，最后返回慢指針的個數(shù)就可以了。

int removeDuplicates(int* nums, int numsSize) {
    if (numsSize == 0) {
        return 0;
    }
    int fast = 1, slow = 1;
    while (fast < numsSize) {
        if (nums[fast] != nums[fast - 1]) {
            nums[slow] = nums[fast];
            ++slow;
        }
        ++fast;
    }
    return slow;
}

5.結(jié)尾

這些就是我給大家分享的關(guān)于順序表的知識啦，希望我們都能有所收獲!
先贊后看,養(yǎng)成習慣??！^ _ ^
碼字不易，大家的支持就是我堅持下去的動力，點贊后不要忘了關(guān)注我哦！

如有錯誤，還請您批評改正(?ì _ í?)文章來源地址http://www.zghlxwxcb.cn/news/detail-426745.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】順序表詳解（附leetcode練習題）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！