頭插操作

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

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

那我們的邏輯就應該是從后往前挪，那我們就直接定一個下標，指向這段空間的最后一個位置即可，再利用香香 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 下標不是指向 size ，而是size后面一位也就是我們初始的capacity，end = 0時處理的是第一位之后的數(shù)據(jù)，那么我們while循環(huán)時就應該循環(huán)到 end<0為止。挪完了就可以sei數(shù)據(jù)，最后不要忘了讓size++。
結(jié)果如下：

我們?nèi)绻麑χ皩懳膊鍟r的細節(jié)記得的話，我們是需要有擴容操作的，這么寫過去寫過來很難受啊，我們就直接做成接口直接調(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("擴容失敗\n");
			exit(0);
		}
	}
}

頭刪操作

一樣的，在頭刪操作時不僅要像尾刪一樣置0，還得把數(shù)據(jù)挪回去，注意是從前往后挪，不然數(shù)據(jù)又會被覆蓋，最后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ù)據(jù)是連續(xù)的，但又擺脫了數(shù)組固定大小的限制，他適應性超強，隨插隨刪隨改。

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

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

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