頭插操作

繼上一章內(nèi)容（C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)順序表中的增刪改教程示例詳解），繼續(xù)講講順序表的基礎(chǔ)操作。

和尾插不一樣，尾插出手闊綽直接的開(kāi)空間，咱頭插能開(kāi)嗎？好像沒(méi)聽(tīng)說(shuō)過(guò)哪個(gè)接口可以在數(shù)據(jù)前面開(kāi)一片空間吧，那我們思路就只有一個(gè)了——挪數(shù)據(jù)。那應(yīng)該從第一位開(kāi)始挪嗎？注意，這和 memcpy 函數(shù)機(jī)制是一樣的，并不意味著后面數(shù)據(jù)一起挪動(dòng)，也不會(huì)彼此獨(dú)立，而是相互影響，挪動(dòng)的數(shù)據(jù)會(huì)對(duì)后面數(shù)據(jù)進(jìn)行覆蓋。

那我們的邏輯就應(yīng)該是從后往前挪，那我們就直接定一個(gè)下標(biāo)，指向這段空間的最后一個(gè)位置即可，再利用香香 while 循環(huán)一手：

void pushfront(st* s, type x)
{
	assert(s);
	int end = s->size - 1;
	while (end >= 0)
	{
		s->a[end + 1] = s->a[end];//將從后往前的數(shù)據(jù)都向后挪一位
		end--;
	}
	s->a[0] = x;
	s->size++;
}

我們的 end 下標(biāo)不是指向 size ，而是size后面一位也就是我們初始的capacity，end = 0時(shí)處理的是第一位之后的數(shù)據(jù)，那么我們while循環(huán)時(shí)就應(yīng)該循環(huán)到 end<0為止。挪完了就可以sei數(shù)據(jù)，最后不要忘了讓size++。
結(jié)果如下：

我們?nèi)绻麑?duì)之前寫(xiě)尾插時(shí)的細(xì)節(jié)記得的話，我們是需要有擴(kuò)容操作的，這么寫(xiě)過(guò)去寫(xiě)過(guò)來(lái)很難受啊，我們就直接做成接口直接調(diào)用豈不美哉？

void enough(st* s)
{
	if (s->size == s->capacity)
	{
		s->capacity *= 2;
		s->a = (type*)realloc(s->a, sizeof(type) * s->capacity);
		if (s->a == NULL)
		{
			printf("擴(kuò)容失敗\n");
			exit(0);
		}
	}
}

頭刪操作

一樣的，在頭刪操作時(shí)不僅要像尾刪一樣置0，還得把數(shù)據(jù)挪回去，注意是從前往后挪，不然數(shù)據(jù)又會(huì)被覆蓋，最后size–一下就搞定：

void popfront(st* s)
{
	assert(s);
	enough(s);
	int head = 0;
	while (head < s->size - 1)
	{
		s->a[head] = s->a[head + 1]; //從前往后的數(shù)據(jù)依次向前挪一位
		head++;
	}
	s->size--;
}

結(jié)果如下：

小結(jié)

綜上所述，順序表其實(shí)就是在數(shù)組的基礎(chǔ)上保留了一個(gè)特性——數(shù)據(jù)是連續(xù)的，但又?jǐn)[脫了數(shù)組固定大小的限制，他適應(yīng)性超強(qiáng)，隨插隨刪隨改。

但是順序表不是十全十美，我們數(shù)據(jù)量足夠龐大，比如已有一萬(wàn)條數(shù)據(jù)的空間，我要插入一萬(wàn)零一條，增容就會(huì)增到兩萬(wàn)，空間浪費(fèi)率極高。另外，尾插尾刪操作是很快的，直接放入拿走數(shù)據(jù)，這是順序表最常見(jiàn)的操作，這是他的特長(zhǎng)。

但是話說(shuō)回來(lái)，頭插頭刪也很快嗎？顯然不是，頭插頭刪的時(shí)間復(fù)雜度是O(n), 代價(jià)全在數(shù)據(jù)挪動(dòng)上，所以如果要想不挪動(dòng)的話，就要涉及到鏈表的引入。但鏈表在二分查找，排序等方面都有致命缺陷，他不能隨機(jī)訪問(wèn)，所以鏈表和順序表是相輔相成的。

今天就先到這里吧，摸了家人們，更多關(guān)于C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)順序表增刪改的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論