C語言怎么實現順序表的操作

這篇文章主要介紹了C語言怎么實現順序表的操作的相關知識，內容詳細易懂，操作簡單快捷，具有一定借鑒價值，相信大家閱讀完這篇C語言怎么實現順序表的操作文章都會有所收獲，下面我們一起來看看吧。

線性表

線性表(linear list)是n個具有相同特性的數據元素的有限序列。線性表是一種在實際中廣泛使用的數據結構，常見的線性表有：順序表、鏈表、棧、隊列、字符串等。

線性表在邏輯上是線性結構，也就是連續的一條直線。但在物理結構上并不一定是連續的，線性表在物理上存儲時，通常以數組和鏈式的形式存儲。

順序表

順序表是用一段物理連續地址的存儲單元依次存儲數據元素的線性結構，一般情況采用數組存儲。在數組上面完成數據的增刪查改。

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

1.靜態順序表：使用定長數組存儲元素。

2.動態順序表：使用動態開辟的數組存儲。

順序表接口實現

靜態順序表只適用于確定知道需要存儲多少數據的場景。靜態順序表不夠靈活。所以我們基本都使用動態順序表，根據需要空間的多少來分配大小，所有下面我們實現動態順序表。

先定義一個結構體：

typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* a;
	int size;     //存儲數據個數
	int capacity; //容量空間大小
}SeqList;

1.順序表初始化

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

我們在給ps->a開辟空間的時候，還可以以如下方式開辟，這樣甚至更簡單一點(開辟完空間后需要檢查空間的有效性)，但這兩種都可以。

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

2.順序表空間增容

//檢查空間，如果滿了，就進行增容
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));//若空間開辟失敗，則打印開辟失敗的原因
			exit(-1);//若空間開辟失敗，則直接終止程序
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newcapacity;
		}
	}
}

1.此處realloc空間，如果容量不夠，我們就將容量擴展為原來的兩倍，但是我們一開始初始化的空間有可能是0，所以我們應該把這種情況考慮進去。

2.realloc空間可能因為一些原因而失敗，所以要對開辟的空間進行檢查，即判斷申請的空間是否為空（NULL）。

3.順序表打印

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

4.尾插數據

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

5.尾刪數據

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

注意：size減的時候一定要加條件限制，防止下標出現負數。

6.頭插數據

//順序表頭插
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.頭刪數據

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

注意：頭刪一定要保證下標大于0，不然刪掉一個下標減一下，當下標減為負數的時候，程序就會出錯。頭刪的時候數據從前向后數據依次向前覆蓋一位。

8.在pos下標處插入數據

//順序表在pos位置插入數據
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++;
}

這里需要特別注意一下下標的問題，如下圖：

在這里循環有兩種寫法，一種如上，還有一種就是下邊這種。

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

注意:對比以上兩種寫法，我們注意到了pos和end的類型。因為坐標不可能為負數，所以pos為size_t類型。對于第二種情況：int end=ps->size-1時，循環執行到最后end的值會變為-1，但pos的類型為size_t，所以當end與pos比較的時候，會發生整形提升，使無符號的end整形提升為有符號的數字和pos比較，所以while條件成立，會繼續循環，導致越界訪問內存。對于這種我們的解決方法是將pos強制轉換為int類型，如上訴代碼。

對于第一種情況： int end=ps->size,循環執行到最后end的值為0，為無符號數，因此剛好完美的進行了移動覆蓋，不會出現越界訪問的情況。所以我們推薦使用第一種方法。

9.刪除pos下標處數據

//順序表刪除pos位置的數據
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.數據查找

依次遍歷數據查找，若找到了對應的數據，則返回它的下標。若找不到，則返回-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.順序表摧毀

當我們使用動態申請空間時，使用完后，一定要釋放動態開辟的內存。否則可能會造成內存泄漏。

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

關于“C語言怎么實現順序表的操作”這篇文章的內容就介紹到這里，感謝各位的閱讀！相信大家對“C語言怎么實現順序表的操作”知識都有一定的了解，大家如果還想學習更多知識，歡迎關注億速云行業資訊頻道。