hello，大家好，今天的內(nèi)容是關(guān)于順序表的，其實(shí)之前也發(fā)過文章，但是那個(gè)時(shí)候水平還是差了一點(diǎn)，有些地方不是很詳細(xì)，這次會(huì)把每個(gè)點(diǎn)都講清楚，也當(dāng)給自己在復(fù)習(xí)一遍。

順序表在本質(zhì)上就是數(shù)組，順序表是連續(xù)的，我們的數(shù)組在內(nèi)存上也是連續(xù)存儲的，所以我們可以認(rèn)為他們在物理結(jié)構(gòu)上是一樣的。

1.線性表

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

簡單來講其實(shí)線性表就是零個(gè)或者多個(gè)元素的有限序列。

線性表有鏈表和順序表，我們今天來講的就是最簡單的順序表。

2.順序表

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

順序表也可以分為動(dòng)態(tài)順序表和靜態(tài)的順序表，靜態(tài)的意義不是很大，使用場景受到權(quán)限，所以我們這里一般用動(dòng)態(tài)順序表。我們今天講的是動(dòng)態(tài)的，但是也會(huì)提到靜態(tài)是怎么個(gè)樣子，會(huì)寫動(dòng)態(tài)的，靜態(tài)的肯定也會(huì)。

如果我們要定義一個(gè)靜態(tài)的話。

這個(gè)就是我們靜態(tài)的順序表的結(jié)構(gòu)體，但是靜態(tài)的是存在缺陷的，比如我們?nèi)绻?個(gè)數(shù)據(jù)，這樣就存不下來，如果我們這個(gè)N給的太大，我們假設(shè)這里有十萬個(gè)數(shù)據(jù)，那我們這來存一萬個(gè)數(shù)據(jù)的話，這就是鐵鐵的浪費(fèi)，所以我們用動(dòng)態(tài)開辟的方法來實(shí)現(xiàn)才是最好的。

動(dòng)態(tài)寫的方式

size就是我們有多少個(gè)數(shù)據(jù)，capacity就是有多是空間，我們這里在進(jìn)行一些優(yōu)化，比如我們要存儲的是double的類型，我們這里需要改很多東西，結(jié)構(gòu)體的名字太長了，我們也簡化一下。

typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* a;//指向動(dòng)態(tài)開辟的空間
	int size;//數(shù)據(jù)個(gè)數(shù)
	int capacity;//容量
}SL;

這里引出一個(gè)問題，我們數(shù)據(jù)結(jié)構(gòu)順序表中每次開空間都是二倍的開嗎？

答案：不是，二倍是一個(gè)比較合理的開辟內(nèi)存大小的倍數(shù)，當(dāng)然我們也可以1.5倍的開辟，數(shù)據(jù)結(jié)構(gòu)中沒有規(guī)定一次性開多少空間，只有合理和不合理之說。這里我們開空間就是以二倍的方式進(jìn)行開辟。

完成了這個(gè)之后，我們得先寫一個(gè)初始化，這個(gè)是必須的，我們后面也一定要寫初始化，當(dāng)然在C++中就可以不用，我們有我們的構(gòu)造函數(shù)。

void SLInit(SL psl);

我們這樣寫初始化是對的嗎，我們都知道，在C語言中，形參是實(shí)參的一份臨時(shí)拷貝，改變形參是不會(huì)對實(shí)參進(jìn)行改變的，我們要對外面的內(nèi)容進(jìn)行修改，就得用指針，所以我們需要傳他們的地址。

那正確的寫法就是void SLInit(SL* psl);

我們實(shí)現(xiàn)一下。

void SLInit(SL* psl)
{
	psl->a = NULL;
	psl->capacity = psl->size = 0;
}

我們初始化其實(shí)有兩種方法，在初始化的時(shí)候就給空間，當(dāng)然也可以在我們擴(kuò)容的時(shí)候給空間，我們今天這里就不在初始化的時(shí)候給空間。
我們會(huì)開空間，也就代表我們還需要寫一個(gè)函數(shù)來釋放我們動(dòng)態(tài)開辟的空間。

void SLDestory(SL* psl)
{
	if (psl->a != NULL)
	{
		free(psl->a);
		psl->a = NULL;
		psl->capacity = psl->size = 0;

	}
}

那像我們的通訊錄是一樣的我們對數(shù)據(jù)進(jìn)行處理的話，需要增刪查改，那這里順序表也是一樣，我們這里就先對順序表進(jìn)行尾插。

首先我們要思考，尾插是不是就是在數(shù)據(jù)的末尾插入一個(gè)空間，那我們需要考慮的問題最主要的就是我們的內(nèi)存空間夠嗎，比如我們的capacity是4個(gè)空間容量大小，我們這個(gè)數(shù)據(jù)個(gè)數(shù)剛剛好就是4個(gè)，那我們還要在插入一個(gè)數(shù)據(jù)的話，是不是滿了，這個(gè)時(shí)候動(dòng)態(tài)順序表的作用就出來了，我們在開辟二倍的空間進(jìn)行插入，這個(gè)時(shí)候我們的空間容量就是8個(gè)，在插入的時(shí)候就是沒有問題。

那我們在尾插的時(shí)候是不是就要寫一個(gè)檢查空間的函數(shù)。

void SLCheakCapacity(SL* psl)
{
	if (psl->capacity == psl->size)
	{
		int NewCapacity = psl->capacity == 0 ? 4 :psl->capacity * 2;
		SLDateType* tmp = (SLDateType*)realloc(psl->a, sizeof(SLDateType) * NewCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail\n");
			exit(-1);
		}
		psl->a = tmp;
		psl->capacity = NewCapacity;
	}
}

這里我們其實(shí)要注意的有兩點(diǎn)，一個(gè)就是我們在初始化函數(shù)的時(shí)候我們是沒有進(jìn)行空間開辟的，所以我們用一個(gè)三目操作符來進(jìn)行判斷，還有一個(gè)就是realloc的理解問題，大家這里可能多少有點(diǎn)疑問，首先我認(rèn)為在這里使用realloc的原因一就是當(dāng)我們的地址第一個(gè)參數(shù)為空的時(shí)候就是malloc，然后因?yàn)槲覀冺樞虮硎沁B續(xù)開辟空間的，所以用realloc更好，realloc的特點(diǎn)是如果后面的空間是足夠的，我們之間原地?cái)U(kuò)容，但是如果后面的空間是不夠的，那這個(gè)時(shí)候我們就會(huì)采取另一種方式，異地?cái)U(kuò)容，找一個(gè)空間大的，然后擴(kuò)容，并返回該地址，還會(huì)釋放之前的空間，所以realloc更好。

那我們實(shí)現(xiàn)檢查空間后，我們尾插是怎樣的呢，我們都知道順序表的本質(zhì)就是數(shù)組，所以順序表的尾插就可以相當(dāng)于在數(shù)組末尾插入一個(gè)數(shù)據(jù)。

void SLPushBack(SL* psl, SLDateType x)
{
	SLCheakCapacity(psl);
	psl->a[psl->size] = x;
	psl->size++;
}

那我們可以在寫一個(gè)printf的函數(shù)來看我們的結(jié)果，當(dāng)然也可以通過其他調(diào)試窗口來看我們的結(jié)果，這里我們就簡單一點(diǎn)，通過我們打印來看。

打印函數(shù)

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

測試代碼

int main()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPushBack(&s, 5);
	SLPrint(&s);
	return 0;
}

測試結(jié)果

尾插寫完之后，我們就馬上來寫我們的頭插，頭插就是在我們的數(shù)組下標(biāo)為0的位置進(jìn)行插入，那我們要保持后面的數(shù)據(jù)整體往后移動(dòng)，整體移動(dòng)的時(shí)間復(fù)雜度就是O（N），所以這里的問題就是頭插的效率慢。那插入數(shù)據(jù)就要看空間是不是滿足，所以擴(kuò)容之前我們一定要檢查空間是不是夠的。

void SLPushFront(SL* psl, SLDateType x)
{
	SLCheakCapacity(psl);
	int end = psl->size - 1;
	while (end >= 0)
	{
		psl->a[end + 1] = psl->a[end];
		end--;
	}
	psl->a[0] = x;
	psl->size++;
}

我們再來測試一下看看結(jié)果和測試代碼

測試代碼

#include"Seqlist.h"
void test1()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPushBack(&s, 5);
	SLPrint(&s);
	SLPushFront(&s, 10);
	SLPushFront(&s, 20);
	SLPushFront(&s, 30);
	SLPushFront(&s, 40);

	SLPrint(&s);

}
int main()
{
	test1();

	return 0;
}

我們后面馬上來實(shí)現(xiàn)尾插是怎樣的，尾插這里我們主要考慮兩個(gè)問題，一個(gè)是刪完了怎么辦，還有一個(gè)就是刪的這個(gè)位置怎么處理。

void SLPopBack(SL* psl)
{
	assert(psl->size > 0);
	psl->size--;
}

其實(shí)仔細(xì)想想就這一點(diǎn)代碼，如果我們的元素只有0個(gè)的時(shí)候，我們就不能在對順序表進(jìn)行刪除，所以我們這里要的就是斷言一下，還有就是我們因?yàn)楹竺娌僮髌鋵?shí)會(huì)覆蓋，那我們就不需要考慮這么多，直接刪除就完事了。
我們來測試看看。

測試代碼

void test2()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPrint(&s);
	SLPopBack(&s);
	SLPopBack(&s);
	SLPopBack(&s);
	SLPrint(&s);

}
int main()
{
	//test1();
	test2();

	return 0;
}

那如果我們再刪兩個(gè)看看。

就被提醒了，所以這里斷言我們就暴力一點(diǎn)，當(dāng)然也可以溫柔一點(diǎn)的給個(gè)if，

在這里小編推薦暴力一點(diǎn)的寫法。

就直接用assert

這里我們可以看到其實(shí)我們尾刪和尾插都是特別高效的，但是頭插入和頭刪除，因?yàn)槲覀円苿?dòng)數(shù)據(jù)，所以變得不是特別高效

下一個(gè)就是怎么實(shí)現(xiàn)我們得頭刪，首先啥都不管，我們先要考慮得就是我們不能為空得順序表，一個(gè)數(shù)據(jù)都沒有我們也就不要再繼續(xù)刪了，其次我們刪除頭部得數(shù)據(jù)，但是還有保持其他數(shù)據(jù)是按順序的，所以這里我們就要考慮覆蓋的問題。

void SLPopFront(SL* psl)
{
	assert(psl->size > 0);
	int begin = 1;
	while (begin < psl->size)
	{
		psl->a[begin - 1] = psl->a[begin];
		begin++;
	}
	psl->size--;
}

測試代碼和結(jié)果

void test2()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	
	SLPrint(&s);
	SLPushFront(&s, 10);
	SLPushFront(&s, 20);
	SLPushFront(&s, 30);
	SLPushFront(&s, 40);
	SLPrint(&s);
	SLPopFront(&s);
	SLPopFront(&s);
	SLPrint(&s);
}
int main()
{
	//test1();
	test2();

	return 0;
}

下面我們還有一個(gè)隨機(jī)插入和隨機(jī)刪除，這兩個(gè)的插入刪除我們就需要注意一點(diǎn)東西了，比如我們插入和刪除是不是還是要保持順序表是線性結(jié)構(gòu)，是線性結(jié)構(gòu)我們就需要他們保持連續(xù)，所以一些位置的刪除和插入需要我們注意，還有就是我們還需要主要隨機(jī)插入和刪除覆蓋數(shù)據(jù)的順序，是從前覆蓋還是從后覆蓋，這都需要我們注意，那我們寫寫一個(gè)隨機(jī)插入吧。

void SLInsert(SL* psl, int pos, SLDateType x)
{
	assert(pos >= 0 && pos <= psl->size);
	SLCheakCapacity(psl);
	int end = psl->size - 1;
	while (end >= pos)
	{
		psl->a[end + 1] = psl->a[end];
		end--;
	}
	psl->a[pos] = x;
	psl->size++;

}

自信的男人不需要測試(這里大家還是需要不斷進(jìn)行調(diào)試的，因?yàn)槿绻覀兒竺娉鲥e(cuò)的話很麻煩，如果你水平很高的話，當(dāng)我沒說，小編是弱雞)

那我們這里也來測試和調(diào)試一下吧

測試代碼

void test2()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	
	SLPrint(&s);
	SLPushFront(&s, 10);
	SLPushFront(&s, 20);
	SLPushFront(&s, 30);
	SLPushFront(&s, 40);
	SLPrint(&s);
	SLPopFront(&s);
	SLPopFront(&s);
	SLPrint(&s);
	SLInsert(&s, 1, 100);
	SLInsert(&s, 1, 100);
	SLInsert(&s, 0, 100);
	SLPrint(&s);
}

還有一個(gè)就是隨機(jī)刪除。

void SLErase(SL* psl, int pos)
{
	assert(pos >= 0 && pos < psl->size);
	assert(psl->size > 0);
	int begin = pos;
	while (begin < psl->size - 1)
	{
		psl->a[begin] = psl->a[begin + 1];
		begin++;
	}
	psl->size--;
}

隨機(jī)刪除就要看數(shù)據(jù)有沒有，是不是順序表為空，還要判斷我們刪除的位置是不是正確，我們不能在psl->size位置進(jìn)行刪除，這個(gè)大家可以通過畫圖來思考，下面我們在寫一個(gè)查找，查找其實(shí)就是遍歷數(shù)組.

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

找到了我們就返回當(dāng)前的位置，沒找到就返回-1。

那今天我們的學(xué)習(xí)就到這里了，我們后面接著干，我要補(bǔ)作業(yè)了家人們。

文章來源地址http://www.zghlxwxcb.cn/news/detail-736419.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)之順序表詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！