快捷導(dǎo)航

C語(yǔ)言實(shí)現(xiàn)順序表的全操作詳解

更新時(shí)間：2022年04月23日 15:36:09 作者：風(fēng)＆646

順序表，全名順序存儲(chǔ)結(jié)構(gòu)，是線性表的一種，線性表用于存儲(chǔ)邏輯關(guān)系為“一對(duì)一”的數(shù)據(jù)，順序表自然也不例外，不僅如此，順序表對(duì)數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)也有要求，跟隨下文來(lái)具體了解吧

線性表

線性表(linear list)是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。線性表是一種在實(shí)際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見(jiàn)的線性表有：順序表、鏈表、棧、隊(duì)列、字符串等。

線性表在邏輯上是線性結(jié)構(gòu)，也就是連續(xù)的一條直線。但在物理結(jié)構(gòu)上并不一定是連續(xù)的，線性表在物理上存儲(chǔ)時(shí)，通常以數(shù)組和鏈?zhǔn)降男问酱鎯?chǔ)。

順序表

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

一般情況下，順序表可以分為一下兩種：

1.靜態(tài)順序表：使用定長(zhǎng)數(shù)組存儲(chǔ)元素。

2.動(dòng)態(tài)順序表：使用動(dòng)態(tài)開(kāi)辟的數(shù)組存儲(chǔ)。

順序表接口實(shí)現(xiàn)

靜態(tài)順序表只適用于確定知道需要存儲(chǔ)多少數(shù)據(jù)的場(chǎng)景。靜態(tài)順序表不夠靈活。所以我們基本都使用動(dòng)態(tài)順序表，根據(jù)需要空間的多少來(lái)分配大小，所有下面我們實(shí)現(xiàn)動(dòng)態(tài)順序表。

先定義一個(gè)結(jié)構(gòu)體：

typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* a;
	int size;     //存儲(chǔ)數(shù)據(jù)個(gè)數(shù)
	int capacity; //容量空間大小
}SeqList;

1.順序表初始化

void SeqListInit(SeqList* ps);
void SeqListInit(SeqList* ps)
{
	assert(ps); //檢查指針的有效性
	ps->a = NULL; //不知道開(kāi)多大的空間，就先賦值NULL
	ps->capacity = ps->size = 0;
}

我們?cè)诮ops->a開(kāi)辟空間的時(shí)候，還可以以如下方式開(kāi)辟，這樣甚至更簡(jiǎn)單一點(diǎn)(開(kāi)辟完空間后需要檢查空間的有效性)，但這兩種都可以。

STDataType*tmp=(STDataType*)malloc(sizeof(SeqList)*2);

2.順序表空間增容

//檢查空間，如果滿了，就進(jìn)行增容
void SeqListCheckCapacity(SeqList* ps);
void SeqListCheckCapacity(SeqList* ps)
{
	assert(ps);
	if (ps->capacity == ps->size)
	{
		size_t newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = realloc(ps->a, sizeof(SLDataType) * newcapacity);
		if (tmp == NULL)
		{
			printf("CheckCapacity::%s\n", strerror(errno));//若空間開(kāi)辟失敗，則打印開(kāi)辟失敗的原因
			exit(-1);//若空間開(kāi)辟失敗，則直接終止程序
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newcapacity;
		}
	}
}

1.此處realloc空間，如果容量不夠，我們就將容量擴(kuò)展為原來(lái)的兩倍，但是我們一開(kāi)始初始化的空間有可能是0，所以我們應(yīng)該把這種情況考慮進(jìn)去。

2.realloc空間可能因?yàn)橐恍┰蚨?，所以要?duì)開(kāi)辟的空間進(jìn)行檢查，即判斷申請(qǐng)的空間是否為空（NULL）。

3.順序表打印

//順序表打印
void SeqListPrint(SeqList* ps);
void SeqListPrint(SeqList* ps)
{
	assert(ps);
	for (int i = 0;i < ps->size;++i)//依次遍歷，打印出每一個(gè)信息
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

4.尾插數(shù)據(jù)

//順序表尾插
void SeqListPushBack(SeqList* ps, SLDataType x);
void SeqListPushBack(SeqList* ps, SLDataType x)
{
	assert(ps);
	SeqListCheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}

5.尾刪數(shù)據(jù)

//順序表尾刪
void SeqListPopBack(SeqList* ps);
void SeqListPopBack(SeqList* ps)
{
	assert(ps);
	if (ps->size > 0)//防止尾刪將數(shù)據(jù)刪完了，size出現(xiàn)負(fù)數(shù)
	{
		ps->size--;
	}
}

注意：size減的時(shí)候一定要加條件限制，防止下標(biāo)出現(xiàn)負(fù)數(shù)。

6.頭插數(shù)據(jù)

//順序表頭插
void SeqListPushFront(SeqList* ps, SLDataType x);
void SeqListPushFront(SeqList* ps, SLDataType x)
{
	assert(ps);
	SeqListCheckCapacity(ps);//檢查空間容量
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	ps->a[0] = x;
	ps->size++;
}

7.頭刪數(shù)據(jù)

//順序表頭刪
void SeqListPopFront(SeqList* ps);
void SeqListPopFront(SeqList* ps)
{
	assert(ps);
	//依次挪動(dòng)數(shù)據(jù)覆蓋刪除
	if (ps->size > 0)//確保有數(shù)據(jù)可刪除，防止下標(biāo)出現(xiàn)負(fù)數(shù)
	{
		int begin = 1;
		while (begin < ps->size)
		{
			ps->a[begin - 1] = ps->a[begin];
			++begin;
		}
		ps->size--;
	}
}

注意：頭刪一定要保證下標(biāo)大于0，不然刪掉一個(gè)下標(biāo)減一下，當(dāng)下標(biāo)減為負(fù)數(shù)的時(shí)候，程序就會(huì)出錯(cuò)。頭刪的時(shí)候數(shù)據(jù)從前向后數(shù)據(jù)依次向前覆蓋一位。

8.在pos下標(biāo)處插入數(shù)據(jù)

//順序表在pos位置插入數(shù)據(jù)
void SeqListInsert(SeqList* ps, size_t pos, SLDataType x);
void SeqListInsert(SeqList* ps, size_t pos, SLDataType x)
{
	assert(ps);
	if (pos > ps->size)
	{
		printf("pos越界\n");
		return;
	}
	SeqListCheckCapacity(ps);
	size_t end = ps->size;
	while (end > pos)
	{
		ps->a[end] = ps->a[end - 1];
		--end;
	}
	ps->a[pos] = x;
	ps->size++;
}

這里需要特別注意一下下標(biāo)的問(wèn)題，如下圖：

在這里循環(huán)有兩種寫(xiě)法，一種如上，還有一種就是下邊這種。

int end =ps->size-1;
while(end>=(int)pos)
{
    ps->a[end+1]=ps->a[end];
    --end;
}

注意:對(duì)比以上兩種寫(xiě)法，我們注意到了pos和end的類(lèi)型。因?yàn)樽鴺?biāo)不可能為負(fù)數(shù)，所以pos為size_t類(lèi)型。對(duì)于第二種情況：int end=ps->size-1時(shí)，循環(huán)執(zhí)行到最后end的值會(huì)變?yōu)?1，但pos的類(lèi)型為size_t，所以當(dāng)end與pos比較的時(shí)候，會(huì)發(fā)生整形提升，使無(wú)符號(hào)的end整形提升為有符號(hào)的數(shù)字和pos比較，所以while條件成立，會(huì)繼續(xù)循環(huán)，導(dǎo)致越界訪問(wèn)內(nèi)存。對(duì)于這種我們的解決方法是將pos強(qiáng)制轉(zhuǎn)換為int類(lèi)型，如上訴代碼。

對(duì)于第一種情況： int end=ps->size,循環(huán)執(zhí)行到最后end的值為0，為無(wú)符號(hào)數(shù)，因此剛好完美的進(jìn)行了移動(dòng)覆蓋，不會(huì)出現(xiàn)越界訪問(wèn)的情況。所以我們推薦使用第一種方法。

9.刪除pos下標(biāo)處數(shù)據(jù)

//順序表刪除pos位置的數(shù)據(jù)
void SeqListErase(SeqList* ps, size_t pos);
void SeqListErase(SeqList* ps, size_t pos)
{
	assert(ps);
	if (pos >= ps->size)
	{
		printf("pos越界\n");
		return;
	}
	size_t begin = pos + 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		++begin;
	}
	ps->size--;
}

10.數(shù)據(jù)查找

依次遍歷數(shù)據(jù)查找，若找到了對(duì)應(yīng)的數(shù)據(jù)，則返回它的下標(biāo)。若找不到，則返回-1.

//順序表查找
int SeqListFind(SeqList* ps, SLDataType x);
int SeqListFind(SeqList* ps, SLDataType x)
{
	assert(ps);
	for (int i = 0;i < ps->size;++i)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

11.順序表摧毀

當(dāng)我們使用動(dòng)態(tài)申請(qǐng)空間時(shí)，使用完后，一定要釋放動(dòng)態(tài)開(kāi)辟的內(nèi)存。否則可能會(huì)造成內(nèi)存泄漏。

//順序表銷(xiāo)毀
void SeqListDestroy(SeqList* ps);
void SeqListDestroy(SeqList* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->size = ps->capacity = 0;
}

到此這篇關(guān)于C語(yǔ)言實(shí)現(xiàn)順序表的全操作詳解的文章就介紹到這了,更多相關(guān)C語(yǔ)言順序表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: