C語言資料結構深入探索順序表

2022-03-25 16:01:19

2.2.1初始化
2.2.2 檢查容量
2.2.3 順序表列印
2.2.4 順序表尾插
2.2.5 順序表尾刪
2.2.6 順序表頭插
2.2.7 順序表頭刪
2.2.8 順序表在pos位置插入x
2.2.9 順序表刪除pos位置的值
2.2.10 尾插、尾刪、頭插、頭刪的改進
2.2.11 順序表查詢
2.2.12 順序表銷燬

2.3 陣列相關面試題

2.4 順序表的問題及思考

1.線性表

線性表（linear list）是n個具有相同特性的資料元素的有限序列。線性表是一種在實際中廣泛使用的資料結構，常見的線性表：順序表、連結串列、棧、佇列、字串…

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

2.順序表

2.1概念及結構

順序表是用一段實體地址連續的儲存單元依次儲存資料元素的線性結構，一般情況下采用陣列儲存。在陣列上完成資料的增刪查改。

順序表一般可以分為：

靜態順序表：使用定長陣列儲存元素。

動態順序表：使用動態開闢的陣列儲存

2.2 介面實現

靜態順序表只適用於確定知道需要存多少資料的場景。靜態順序表的定長陣列導致N定大了，空間開多了浪費，開少了不夠用。所以現實中基本都是使用動態順序表，根據需要動態的分配空間大小，所以下面我們實現動態順序表。

#pragma once
#include<stdio.h>
#include<assert.h>
typedef int SLDataType;
typedef struct SeqList
{
	int* a;
	int size;	 //儲存資料個數
	int capacity;//儲存空間大小
}SeqList;

void SeqListInit(SeqList* psl);//初始化
void SeqListDestroy(SeqList* psl);//銷燬

void SeqListPrint(SeqList* psl);//列印

void SeqListCheckCapacity(SeqList* psl);//檢查容量

int SeqListFind(SeqList* psl, SLDataType x);//查詢

//時間複雜度是O（1）
void SeqListPushBack(SeqList* psl, SLDataType x);//尾插
void SeqListPopBack(SeqList* psl);//尾刪

//時間複雜度是O（N）
void SeqListPushFront(SeqList* psl, SLDataType x);//頭插
void SeqListPopFront(SeqList* psl);//頭刪

//時間複雜度是O（N）
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);//在pos位置插入
void SeqListErase(SeqList* psl, size_t pos);//在pos位置刪除

2.2.1初始化

就是將元素分別初始化。

//初始化
void SeqListInit(SeqList* psl)
{
	assert(psl);
	psl->a = NULL;
	psl->size = 0;
	psl->capacity = 0;
}

2.2.2 檢查容量

初始化時容量為0，想要放資料得增加容量，每次插入資料也得保證容量充足，為了方便，我們先寫一個用於檢查容量並增容的函數。

//檢查容量
void SeqListCheckCapacity(SeqList* psl)
{
	assert(psl);

	//如果滿了，就要擴容
	if (psl->size == psl->capacity)
	{
		size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;//防止一開始capacity=0無法*2增容
		SLDataType* tmp = realloc(psl->a, sizeof(SLDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc failn");
			exit(-1);
		}
		else
		{
			psl->a = tmp;
			psl->capacity = newCapacity;
		}
	}
}

2.2.3 順序表列印

就是遍歷一次把所有元素列印出來，這樣可以檢查函數寫的是否正確，及時訂正。

//列印
void SeqListPrint(SeqList* psl)
{
	assert(psl);

	for (int i = 0; i < psl->size; i++)
	{
		printf("%d ", psl->a[i]);
	}
	printf("n");

}

2.2.4 順序表尾插

//尾插
void SeqListPushBack(SeqList* psl, SLDataType x)
{
	assert(psl);

	//如果滿了，就要擴容
	SeqListCheckCapacity(psl);

	psl->a[psl->size] = x;
	psl->size++;
}

2.2.5 順序表尾刪

只需要把size-1這樣的話下一個資料就會把尾部資料覆蓋掉，達到刪除的效果。

//尾刪
void SeqListPopBack(SeqList* psl)
{
	assert(psl);

	if (psl->size > 0)
	{
		psl->size--;
	}
}

2.2.6 順序表頭插

//頭插
void SeqListPushFront(SeqList* psl, SLDataType x)
{
	assert(psl);

	//如果滿了，就要擴容
	SeqListCheckCapacity(psl);

	//挪動資料,騰出頭部位置
	int end = psl->size - 1;
	while (end >= 0)
	{
		psl->a[end + 1] = psl->a[end];
		end--;
	}
	psl->a[0] = x;
	psl->size++;

}

2.2.7 順序表頭刪

將第一個位置覆蓋掉，然後用尾刪的思路將最後一個資料刪除。

//頭刪
void SeqListPopFront(SeqList* psl)
{
	assert(psl);

	//挪動資料覆蓋第一個
	if(psl->size>0)
	{
		int begin = 1;
		while (begin < psl->size)
		{
			psl->a[begin - 1] = psl->a[begin];
			begin++;
		}
	}
	psl->size--;
}

2.2.8 順序表在pos位置插入x

思路跟頭插很像,但內含陷阱！

//在pos位置插入
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl);

	//如果滿了，就要擴容
	SeqListCheckCapacity(psl);

	溫和檢測
	//if (pos > psl->size)
	//{
	//	printf("pos越界：%dn", pos);
	//	return;
	//}
	//暴力檢測
	assert(pos <= psl->size);

	//pos=0的時候由於無符號整型判斷時的整型提升，會出問題
	//size_t end = psl->size - 1;
	//while (end >= pos)
	//{
	//	psl->a[end + 1] = psl->a[end];
	//	end--;
	//}
	//psl->a[pos] = x;
	//psl->size++;

	//這樣寫才不會有問題
	size_t end = psl->size;
	while (end > pos)
	{
		psl->a[end] = psl->a[end - 1];
		--end;
	}

	psl->a[pos] = x;
	psl->size++;
}

2.2.9 順序表刪除pos位置的值

思路跟頭刪很像

//在pos位置刪除
void SeqListErase(SeqList* psl, size_t pos)
{
	assert(psl);
	assert(pos < psl->size);

	size_t begin = pos + 1;
	while (begin < psl->size)
	{
		psl->a[begin - 1] = psl->a[begin];
		++begin;
	}

	psl->size--;
}

2.2.10 尾插、尾刪、頭插、頭刪的改進

有了上面兩個通常情況下的增刪函數，我們就能改進尾插、尾刪、頭插、頭刪。這樣能夠快速寫完順序表

//尾插
void SeqListPushBack(SeqList* psl, SLDataType x)
{
	assert(psl);
	SeqListCheckCapacity(psl);
	SeqListInsert(psl, psl->size, x);//在size位置插入資料
}

//尾刪
void SeqListPopBack(SeqList* psl)
{
	assert(psl);
	SeqListErase(psl, psl->size-1);//在size-1位置刪除資料
}

//頭插
void SeqListPushFront(SeqList* psl, SLDataType x)
{
	assert(psl);
	SeqListCheckCapacity(psl);
	SeqListInsert(psl, 0, x);//在0位置插入資料
}

//頭刪
void SeqListPopFront(SeqList* psl)
{
	assert(psl);
	SeqListErase(psl, 0);//在0位置刪除資料
}

2.2.11 順序表查詢

遍歷一遍，一個個找

int SeqListFind(SeqList* psl, SLDataType x)
{
	assert(psl);

	for (int i = 0; i < psl->size; ++i)
	{
		if (psl->a[i] == x)
		{
			return i;
		}
	}

	return -1;
}

2.2.12 順序表銷燬

最後的最後，一定要養成好習慣，不要忘記銷燬之前申請的空間，防止記憶體漏失。

//銷燬
void SeqListDestroy(SeqList* psl)
{
	free(psl->a);
	psl->a = NULL;
	psl->capacity = 0;
	psl->size = 0;
}

2.3 陣列相關面試題

刪除排序陣列中的重複項。26. 刪除有序陣列中的重複項.

原地移除陣列中所有的元素val，要求時間複雜度為O(N)，空間複雜度為O(1)。27. 移除元素.

合併兩個有序陣列。88. 合併兩個有序陣列.

2.4 順序表的問題及思考

問題：

中間/頭部的插入刪除，時間複雜度為O(N)
增容需要申請新空間，拷貝資料，釋放舊空間。會有不小的消耗。
增容一般是呈2倍的增長，勢必會有一定的空間浪費。例如當前容量為100，滿了以後增容到200，我們再繼續插入了5個資料，後面沒有資料插入了，那麼就浪費了95個資料空間。

思考：如何解決以上問題呢？下期會給出了連結串列的結構，現在大家可以想想連結串列會如何解決這些問題。

到此這篇關於C語言資料結構深入探索順序表的文章就介紹到這了,更多相關C語言順序表內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！