【資料結構初階】順序表_增刪查改、查詢、列印、銷毀 (附原始碼+realloc深解)

原始碼下載地址

線性表

• 線性表（linear list）是n個具有相同特性的資料元素的有限序列， 線性表是一種在實際中廣泛使用的資料結構，常見的線性表：順序表、鏈表、堆疊、佇列、字串…
• 線性表在邏輯上是線性結構，也就說是連續的一條直線，但是在物理結構上并不一定是連續的，線性表在物理上存盤時，通常以陣列和鏈式結構的形式存盤，

順序表

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

順序表一般可以分為：

• 靜態順序表：使用定長陣列存盤元素

# define N 7
typedef int SLDataType;

typedef struct SeqList
{
	SLDataType arr[N];  // 定長陣列
	size_t size;  // 有效資料的個數
}SeqList;

• 動態順序表：使用動態開辟的陣列存盤，

typedef int SLDataType;

// 動態順序表
typedef struct SeqList
{
	SLDataType* a;  // 指向動態開辟的陣列
	int size;  // 有效資料個數
	int capacity; // 容量空間的大小
}SeqList;

介面實作

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

// 對資料的管理 增刪查改
void SeqListInit(SeqList* ps);
void SeqListDestroy(SeqList* ps);

void SeqListPrint(SeqList* ps);
void SeqListPushBack(SeqList* ps, SLDataType x);
void SeqListPushFront(SeqList* ps, SLDataType x);
void SeqListPopBack(SeqList* ps);
void SeqListPopFront(SeqList* ps);

// 順序表查找 沒有回傳-1
int SeqListFind(SeqList* ps, SLDataType x);
// 順序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDataType x);
// 順序表洗掉pos位置的值
void SeqListErase(SeqList* ps, int pos);

順序表初始化

1. 判斷指標是否為空
2. 動態順序表空間置0

void SeqListInit(SeqList* ps) {
	assert(ps);

	ps->a = NULL;
	ps->size = ps->capacity = 0;
}

順序表銷毀

1. 釋放堆空間
2. 指向陣列的指標指向空
3. 當前有效數字個數和空間容量置為0

void SeqListDestroy(SeqList* ps) {
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->size = ps->capacity = 0;
}

順序表列印

遍歷思想

void SeqListPrint(SeqList* ps) {
	assert(ps);

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

擴容

在和插入元素有關的函式功能中，要求檢查順序表容量是否足夠，如果順序表空間不夠，則需擴容，

void SeqListCheckCapacity(SeqList* ps) {
	if (ps->size == ps->capacity)
	{
		// 空間不夠，擴容
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
		if (tmp == NULL) 
		{
			printf("realloc fail!\n");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
}

補充：realloc的用法

尾插

1. 檢查空間是否足夠，不夠擴容
2. 增加資料
3. 當前有效資料數加一

void SeqListPushBack(SeqList* ps, SLDataType x) {
	// 檢查空間是否足夠，不夠擴容
	SeqListCheckCapacity(ps);

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

頭插

1. 檢查空間是否足夠，不夠擴容
2. 挪動資料
3. 添加資料

void SeqListPushFront(SeqList* ps, SLDataType x) {
	SeqListCheckCapacity(ps);

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

尾插

1. 判斷是否為空陣列
2. 有效資料數減一

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

頭刪

1. 空順序表判斷
2. 挪動資料
3. 有效資料數減一

void SeqListPopFront(SeqList* ps) {
	// 空順序表判斷
	assert(ps->size > 0);

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

	ps->size--;
}

順序表查找

沒有找到回傳-1， 找到x位置回傳下標，

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

在指定pos下標插入x

1. pos下標位置合法性判斷
2. 檢查空間容量
3. 挪動資料

void SeqListInsert(SeqList* ps, int pos, SLDataType x) {
	assert(pos >= 0 && pos <= ps->size);

	SeqListCheckCapacity(ps);

	// 挪動資料
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}

洗掉pos下標位置的值

1. pos下標位置合法性判斷
2. 挪動資料

void SeqListErase(SeqList* ps, int pos) {
	assert(pos >= 0 && pos < ps->size);

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

	ps->size--;
}

順序表缺陷

1. 空間不夠了需要增容，增容是需要代價的，
   realloc分為原地擴容和異地擴容（高代價），

原地擴容：

異地擴容：

2. 避免頻繁擴容，擴容模糊2倍，會有空間浪費
3. 順序表要求資料從開始位置連續存盤，那么在頭部或者中間增刪資料，效率不高，

相關OJ

27. 移除元素
26. 洗掉有序陣列中的重復項
88. 合并兩個有序陣列