初始化

在初步認(rèn)識(shí)順序表這一結(jié)構(gòu)后，我們就可以繼續(xù)深入探究
這是我之前在.h文件中創(chuàng)建的結(jié)構(gòu)體

typedef int type;
typedef struct list
{
	type* a;
	int size;
	int capacity;
}st;

在處理順序表結(jié)構(gòu)時(shí)我們會(huì)用到的一些接口，處理其中的關(guān)系，其實(shí)本質(zhì)上就是函數(shù)，這里我用復(fù)雜英文對(duì)應(yīng)出來(lái)方便形成記憶。

void init(st *s);  //插入
void pushback( st* p, type x);//尾插
void popback(st* p); //尾刪
void pushfront( st* p, type x); //頭插
void popfront(st* p);   //頭刪
void insert(st* p, int n, type x);  //中間位置插入
void erase(st* p, int n);  //中間位置刪處

我用 init 函數(shù)實(shí)現(xiàn)簡(jiǎn)單的初始化，首先會(huì)先把結(jié)構(gòu)體成員傳過(guò)來(lái)，注意再次強(qiáng)調(diào)區(qū)別形參和實(shí)參，傳值調(diào)用肯定會(huì)報(bào)錯(cuò)滴，乖乖的換成指針，其實(shí)不論是不是傳址調(diào)用，我們都可以搞成指針傳過(guò)去，為了保險(xiǎn)起見(jiàn)。
我們第一步肯定是開(kāi)辟空間，先用 malloc 函數(shù)參上，當(dāng)然，null 還玩?zhèn)€屁屁，為了先避免掉這種情況，我們就 if 意思一下，然后給初始有效位設(shè)為 0，初始容量設(shè)為 5。

void init(st *s)
{
	s->a = (type*)malloc(sizeof(type) * 4);
	if (s->a == NULL)
	{
		printf("申請(qǐng)內(nèi)存失?。n");
		exit(-1);
	}
	s->size = 0;
	s-> capacity = 1;
}

尾插

然后就開(kāi)始pushback 尾插操作：

void pushback(st* s, type x)
{
	assert(s);//空指針判斷
	s->a[s->size] = x;
	s->size++;
}

還是老規(guī)矩，assert 斷言是否為空指針，再放行。往下就簡(jiǎn)單的，把x的值放入數(shù)組的size 位置上，讓 size ++即可。

但是 malloc 這種的指針是指向獨(dú)立不連續(xù)的空間，我們監(jiān)視窗口觀察也只能看到一個(gè)個(gè)不連續(xù)的值，所以還是要老老實(shí)實(shí)搞一個(gè)打印函數(shù)，和數(shù)組一樣，直接遍歷一下我們++過(guò)的size即可:

void print(st* s)
{
	assert(s);
	int i = 0;
	for(i = 0; i < s->size; i++)
	{
		printf("%d ", s->a[i]);
	}
}

結(jié)果如下：

格局打開(kāi)

但是奇不奇怪，我 capacity 初始設(shè)定為 1，而我卻尾插了兩個(gè)數(shù)還沒(méi)有報(bào)錯(cuò)，為什么捏？其實(shí)報(bào)錯(cuò)了一定是你越界了，但沒(méi)有報(bào)錯(cuò)不代表你就沒(méi)有越界，往往有些越界是檢查不出來(lái)的，因?yàn)檫€沒(méi)走到檢查的點(diǎn)上；就好比咱卷了不一定成功但不卷就一定不會(huì)成功。
所以我們的邏輯就要進(jìn)行更替：

	if (s->size >= s->capacity)
		s->capacity++; 

在assert 后加上 if 判斷句，讓容量隨有效位及時(shí)更新，但是又有一個(gè)問(wèn)題，當(dāng)我數(shù)據(jù)量非常大時(shí)，我們使用一位開(kāi)辟一位的方法讓 capacity++ 非常頻繁，但一下子開(kāi)辟一大片空間有會(huì)浪費(fèi)資源，到后面已有數(shù)據(jù)越多開(kāi)辟越大浪費(fèi)的越多怎么辦呢？我們比較普遍的做法就是開(kāi)辟 2 倍：

	if (s->size == s->capacity)
	{
		s->capacity *= 2;
		s->a = (type*)realloc(s->a, sizeof(type) * s->capacity);
	}

這里敏感的朋友應(yīng)該張口就來(lái)realloc，realloc函數(shù)會(huì)對(duì)已有空間直接擴(kuò)容，但不一定是原地?cái)U(kuò)容，后面有足夠的空間就會(huì)原地?cái)U(kuò)容，但是不夠就會(huì)找一塊新的空間將數(shù)據(jù)拷貝過(guò)去再釋放掉原來(lái)空間。上面代碼將原來(lái)的空間給realloc，再增容到我要的空間，就能很好的滿足我們的要求。

尾刪

尾刪沒(méi)什么技術(shù)含量，和我們數(shù)組的思路一樣

void popback(st* s)
{
	assert(s);
	s->size--;
}

結(jié)果如下:

以此類(lèi)推，頭插頭刪是一個(gè)道理，不做贅述，更多關(guān)于C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)順序表增刪改的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論