C語言深入淺出講解順序表的實現

2022-04-14 19:01:56

1.線性表

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

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

2.順序表

2.1 概念及結構

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

1.靜態順序表：使用定長陣列儲存。

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

//順序表的靜態儲存 
#define N 100
struct SeqList
{
	int a[N];//定長儲存
	int size;//有效資料的個數
};

//順序表的動態儲存
typedef struct SeqList
{
	SeqDataType* a;//指向動態開闢的陣列
	int size;	  //有效資料個數
	int capacity; //容量
}SeqList;

順序表本質上是陣列，在陣列上增加了兩個要求：

1.插入資料的過程中，可以動態增長

2.並且要求裡面儲存的資料必須是從左往右，是連續的

順序表的缺陷

1.動態增容有效能消耗

2.頭部插入資料時，需要挪動資料

2.2 提供介面

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

首先在標頭檔案<SeqList.h>中提供介面：

typedef int SeqDataType; //需要插入什麼型別的資料，就改成對應型別

typedef struct SeqList
{
	SeqDataType* a;//指向動態開闢的陣列
	int size;	  //有效資料個數
	int capacity; //容量
}SeqList;

//記憶體中管理資料結構 提供增刪查改的介面
//順序表初始化
void SeqListInit(SeqList* pq);
//順序表銷燬
void SeqListDestory(SeqList* pq);
//順序表列印
void SeqListPrint(SeqList* pq);//列印陣列
//檢查空間，如果滿了，進行增容
void SeqCheckCapacity(SeqList* pq)
//順序表尾插
void SeqListPushBack(SeqList* pq, SeqDataType x);
//順序表頭插
void SeqListPushFront(SeqList* pq, SeqDataType x);
//順序表尾刪
void SeqListPopBack(SeqList* pq);
//順序表頭刪
void SeqListPopFront(SeqList* pq);
//順序表查詢x
int SeqListFind(SeqList* pq, SeqDataType x);//查詢 查到返回下標，沒查到返回-1
//順序表在指定位置插入資料
void SeqListInsert(SeqList* pq, int pos, SeqDataType x);//在下標pos位置處插入資料
//順序表在指定位置刪除資料
void SeqListErase(SeqList* pq, int pos);//把下標為pos位置處的資料刪除
//順序表在指定位置替換資料
void SeqListModify(SeqList* pq, int pos, SeqDataType x);//把小標為pos位置的值改為x

2.3 介面實現

在原始檔SeqList.c中實現介面功能

（1）順序表初始化

void SeqListInit(SeqList* pq)
{
	assert(pq != NULL);//或者 assert(pq); 斷言 防止傳入空指標
	pq->a = NULL;
	pq->size = 0;
	pq->capacity = 0;
}

（2）順序表銷燬

void SeqListDestory(SeqList* pq)
{
	assert(pq);
	free(pq->a);
	pq->a = NULL;
	pq->size = 0;
	pq->capacity = 0;
}

（3）順序表列印

void SeqListPrint(SeqList* pq)
{
	assert(pq);
	for (int i = 0; i < pq->size; ++i)
	{
		printf("%d ", pq->a[i]);
	}
	printf("n");
}

（4）檢查空間，如果滿了，進行增容

//檢查是否需要擴容
void SeqCheckCapacity(SeqList* pq)
{
	//滿了，需要增容
	if (pq->size == pq->capacity)
	{
		int newcapacity = (pq->capacity == 0 ? 4 : pq->capacity * 2);

		//realloc接收的地址如果為空，將像malloc一樣，開闢一塊新空間
		SeqDataType* newA = realloc(pq->a, sizeof(SeqDataType) * newcapacity);//realloc返回 開闢的新空間的地址
		if (newA == NULL)
		{
			printf("realloc failn");
			exit(-1);//失敗了就退出
		}
		pq->a = newA;
		pq->capacity = newcapacity;
	}
}

（5）順序表尾插

void SeqListPushBack(SeqList* pq, SeqDataType x)//尾插
{
	assert(pq);

	SeqCheckCapacity(pq);

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

（6）順序表頭插

void SeqListPushFront(SeqList* pq, SeqDataType x)
{
	assert(pq);

	SeqCheckCapacity(pq);

	int end = pq->size - 1;
	while (end >= 0)
	{
		pq->a[end + 1] = pq->a[end];
		end--;
	}
	pq->a[0] = x;
	pq->size++;
}

（7）順序表尾刪

void SeqListPopBack(SeqList* pq)
{
	assert(pq);
	assert(pq->size > 0);
	pq->size--;
}

（8）順序表頭刪

void SeqListPopFront(SeqList* pq)
{
	assert(pq);
	assert(pq->size > 0);

	int begin = 0;
	while (begin < pq->size - 1)
	{
		pq->a[begin] = pq->a[begin + 1];
		begin++;
	}
	pq->size--;
}

（9）順序表查詢x

int SeqListFind(SeqList* pq, SeqDataType x)
{
	assert(pq);
	for (int i = 0; i < pq->size; ++i)
	{
		if (pq->a[i] == x)
		{
			return x;
		}
	}
	return -1;//沒找到
}

（10）順序表在指定位置插入資料

void SeqListInsert(SeqList* pq, int pos, SeqDataType x){<!--{C}%3C!%2D%2D%20%2D%2D%3E-->assert(pq);assert(pos >= 0 && pos < pq->size);SeqCheckCapacity(pq);//檢查是否需要擴容int end = pq->size - 1;while (end >= pos){<!--{C}%3C!%2D%2D%20%2D%2D%3E-->pq->a[end + 1] = pq->a[end];end--;}pq->a[pos] = x;pq->size++;}void SeqListInsert(SeqList* pq, int pos, SeqDataType x)
{
	assert(pq);
	assert(pos >= 0 && pos < pq->size);

	SeqCheckCapacity(pq);//檢查是否需要擴容

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

（11）順序表在指定位置刪除資料

void SeqListErase(SeqList* pq, int pos)
{
	assert(pq);
	assert(pos >= 0 && pos < pq->size);
	int begin = pos;
	while (begin <= pq->size - 1)
	{
		pq->a[begin] = pq->a[begin + 1];
		begin++;
	}
	pq->size--;
}

（12）順序表在指定位置替換資料

void SeqListModify(SeqList* pq, int pos, SeqDataType x)
{
	assert(pq);
	assert(pos >= 0 && pos < pq->size);

	pq->a[pos] = x;
}

主函數的設計大家可以自由發揮，做個簡單的測試功能呼叫函數或是建立選單欄實現互動都可以。我水平有限，請朋友們諒解！寫的不好的地方還請大佬們指出。

下期預告——單連結串列

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