文章目錄

（1）線性表
（2）順序表
- 1）什么是順序表
- 2）順序表的定義
- 2）順序表的介面實作
- - 1、初始化順序表
  - 2、銷毀（釋放）順序表
  - 3、檢查順序表容量是否滿了，好進行增容
  - 3、順序表尾插
  - 4、順序表尾刪
  - 5、順序表頭插
  - 6、順序表頭刪
  - 7、列印順序表
  - 8、在順序表中查找指定值
  - 9、在順序表指定下標位置插入資料
  - 10、在順序表中洗掉指定下標位置的資料
  - 11、查看順序表中有效資料個數
  - 12、修改指定下標位置的資料

（1）線性表

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

（2）順序表

1）什么是順序表

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

2）順序表的定義

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

缺陷：給小了不夠用，給大了可能浪費，非常不實用

#define N 10
typedef int SLDataType;

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

2、動態順序表：使用動態開辟的陣列存盤元素

動態順序表可根據我們的需要分配空間大小
size 表示當前順序表中已存放的資料個數
capacity 表示順序表總共能夠存放的資料個數

typedef int SLDataType; //型別重命名，后續要存盤其它型別時方便更改

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

2）順序表的介面實作

首先新建一個工程（博主使用的是 VS2019 ）此次用的是動態順序表

SeqList.h（順序表的型別定義、介面函式宣告、參考的頭檔案）
SeqList.c（順序表介面函式的實作）
Test.c（主函式、測驗順序表各個介面功能）

如圖：

SeqList.h 頭檔案代碼如下：

#pragma once  //防止頭檔案被二次參考

#include<stdio.h>   /*perror, printf*/
#include<assert.h>  /*assert*/
#include<stdlib.h>  /*realloc*/

typedef int SLDataType;  //后續要存盤其它型別時方便更改
//順序表的動態存盤
typedef struct SeqList
{
	SLDataType* a;    //指向動態開辟的陣列
	size_t size;      //有效資料個數
	size_t capacity;  //容量大小
}SeqList;

//初始化順序表
void SeqListInit(SeqList* psl);
//銷毀順序表
void SeqListDestory(SeqList* psl);
//檢查順序表容量是否滿了，好進行增容
void CheckCapacity(SeqList* psl);
//順序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x);//O(1)
//順序表尾刪
void SeqListPopBack(SeqList* psl);//O(1)
//順序表頭插
void SeqListPushFront(SeqList* psl, SLDataType x);//O(n)
//順序表頭刪
void SeqListPopFront(SeqList* psl);//O(n)
//列印順序表
void SeqListPrint(const SeqList* psl);
//在順序表中查找指定值
int SeqListFind(const SeqList* psl, SLDataType x);
//在順序表指定下標位置插入資料
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
//在順序表中洗掉指定下標位置的資料
void SeqListErase(SeqList* psl, size_t pos);
//查看順序表中資料個數
size_t SeqListSize(const SeqList* psl);
//修改指定下標位置的資料
void SeqListAt(SeqList* psl, size_t pos, SLDataType x);

這里重點講解 SeqList.c 中各個介面函式的實作，

1、初始化順序表

記得一定要加上斷言，防止傳進來的指標為空

void SeqListInit(SeqList* psl)
{
	assert(psl != NULL);  //斷言

	psl->a = NULL;  //初始順序表為空
	psl->size = 0;  //初始資料個數為0
	psl->capacity = 0;  //初始空間容量為0
}

2、銷毀（釋放）順序表

記得一定要加上斷言，防止傳進來的指標為空

void SeqListDestory(SeqList* psl)
{
	assert(psl != NULL);  //斷言

	free(psl->a);   //釋放動態開辟的空間
	psl->a = NULL;  //置空
	psl->size = 0;  //資料個數置0
	psl->capacity = 0;  //空間容量大小置0
}

3、檢查順序表容量是否滿了，好進行增容

為什么不采取插一個資料，增容一個空間的方式呢，因為這樣也太麻煩了，代價也太大了，一般情況下，為了避免頻繁的增容，當空間滿了后，我們不會一個一個的去增，而是一次增容 2 倍，當然也不會一次增容太大，比如 3 倍 4 倍，空間可能會浪費，2 倍是一個折中的選擇，

void CheckCapacity(SeqList* psl)
{
	assert(psl != NULL);  //斷言

	if (psl->size == psl->capacity)  //檢查容量，滿了則增容
	{
		size_t newcapacity;  //新容量
		if (psl->capacity == 0)
			newcapacity = psl->capacity = 4;  //原來容量為0，擴容為4
		else
			newcapacity = 2 * psl->capacity;  //原來容量不為0，擴容為原來的2倍
		
		SLDataType* p = (SLDataType*)realloc(psl->a, newcapacity*sizeof(SLDataType));  //擴容
		if (p == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		psl->a = p;  // p 不為空，開辟成功
		psl->capacity = newcapacity;  //更新容量
	}
}

3、順序表尾插

void SeqListPushBack(SeqList* psl, SLDataType x)
{
	assert(psl != NULL);  //斷言

	CheckCapacity(psl);  //檢查順序表容量是否已滿

	psl->a[psl->size] = x;  //尾插資料
	psl->size++;  //有效資料個數+1
}

測驗其功能

4、順序表尾刪

不知道 SLDataType 是什么型別的資料，不能冒然的將順序表最后一個資料賦值為 0，我們只需將有效資料個數 size 減 1 即可達到尾刪的目的，

void SeqListPopBack(SeqList* psl)
{
	assert(psl != NULL);  //斷言
	assert(psl->size > 0);  //順序表不能為空

	//不知道SLDataType是什么型別的資料，不能冒然的賦值為0
	//psl->a[psl->size - 1] = 0;
	psl->size--;  //有效資料個數-1
}

測驗其功能

5、順序表頭插

因為順序表是連續存盤的，所以頭插時要依次挪動資料

void SeqListPushFront(SeqList* psl, SLDataType x)
{
	assert(psl);  //斷言
	CheckCapacity(psl);  //檢查順序表容量是否已滿
    
	int i = 0;
	for (i = psl->size - 1; i >= 0; i--)  //順序表中[0,size-1]的元素依次向后挪動一位
	{
		psl->a[i + 1] = psl->a[i];
	}
	psl->a[0] = x;  //頭插資料
	psl->size++;  //有效資料個數+1
}

測驗其功能

6、順序表頭刪

因為順序表是連續存盤的，所以頭刪時要依次挪動資料

void SeqListPopFront(SeqList* psl)
{
	assert(psl);  //斷言
	assert(psl->size > 0);  //順序表不能為空

	int i = 0;
	for (i = 1; i < psl->size; i++)  //順序表中[1,size-1]的元素依次向前挪動一位
	{
		psl->a[i - 1] = psl->a[i];
	}
	psl->size--;  //有效資料個數-1
}

測驗其功能

7、列印順序表

void SeqListPrint(const SeqList* psl)
{
	assert(psl != NULL);  //斷言

	if (psl->size == 0)  //判斷順序表是否為空
	{
		printf("順序表為空\n");
		return;
	}

	int i = 0;
	for (i = 0; i < psl->size; i++)  //列印順序表
	{
		printf("%d ", psl->a[i]);
	}
	printf("\n");
}

8、在順序表中查找指定值

int SeqListFind(const SeqList* psl, SLDataType x)
{
	assert(psl);  //斷言

	int i = 0;
	for (i = 0; i < psl->size; i++)
	{
		if (psl->a[i] == x)
		{
			return i;  //查找到，回傳該值在陣列中的下標
		}
	}
	return -1;  //沒有查找到
}

測驗其功能

9、在順序表指定下標位置插入資料

將指定位置后的所有資料依次向后挪動一位，為改進代碼如下：

int i = 0;
for (i = psl->size - 1; i >= pos; i--)
	psl->a[i + 1] = psl->a[i];

原先這種寫法，當順序表為空 size = 0 時，會導致 i = -1，
執行 i >= pos 時，i 被算術轉換成無符號數，而無符號數的 -1 是一個值很大的正數，
遠大于 pos，滿足條件進入回圈，會造成越界訪問
注：轉換并不會改變 i 本身的值，而是執行 i >= pos 時，生成一個臨時的值與 pos 比較
如果在順序表頭部插入資料 pos = 0，i 最終也會減減變成 -1，被算術轉換后變成一個很大的數
總結：避免負數給到無符號數，或者避免有符號數變成負數后，被算術轉換或整型提升后，變成一個很大的數

下面這樣寫就避免 i 變成 -1 負數了

void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl);  //斷言
	assert(pos >= 0 && pos <= psl->size);  //檢查pos下標的合法性

	CheckCapacity(psl);  //檢查順序表容量是否已滿

	size_t i = 0;
	for (i = psl->size; i > pos; i--)  //將pos位置后面的資料依次向后挪動一位
	{
		psl->a[i] = psl->a[i - 1];
	}
	psl->a[pos] = x;  //插入資料
	psl->size++;  //有效資料個數+1
}

測驗其功能

實作了此介面，順序表頭插相當于在下標為 0 位置處插入資料，可以改進下順序表頭插的代碼：

void SeqListPushFront(SeqList* psl, SLDataType x)
{
	SeqListInsert(psl, 0, x);  //改造頭插介面
}

10、在順序表中洗掉指定下標位置的資料

void SeqListErase(SeqList* psl, size_t pos)
{
	assert(psl);  //斷言
	assert(psl->size > 0);  //順序表不能為空
	assert(pos >= 0 && pos < psl->size);  //檢查pos下標的合法性

	size_t i = 0;
	for (i = pos + 1; i < psl->size; i++)  //將pos位置后面的資料依次向前挪動一位
	{
		psl->a[i - 1] = psl->a[i];
	}
	psl->size--;  //有效資料個數-1
}

測驗其功能

實作了此介面，順序表頭刪相當于洗掉下標為 0 位置處的資料，可以改進下順序表頭刪的代碼：

//順序表頭刪
void SeqListPopFront(SeqList* psl)
{
	SeqListErase(psl, 0);  //改造頭刪介面
}

11、查看順序表中有效資料個數

可能大家會有一個疑問，我在主函式里面直接通過定義的結構體變數直接訪問就好了呀，為啥還要弄一個函式嘞
在資料結構中有一個約定，如果要訪問或修改資料結構中的資料，不要直接去訪問，要去呼叫它的函式來訪問和修改，這樣更加規范安全，也更方便檢查是否出現了越界等一些錯誤情況

size_t SeqListSize(const SeqList* psl)
{
	assert(psl);  //斷言

	return psl->size;
}

補充：

越界不一定報錯，系統對越界的檢查是一種抽查

越界讀一般是檢查不出來的

越界寫如果是修改到標志位才會檢查出來

（系統在陣列末尾后設的有標志位，越界寫時，恰好修改到標志位了，就會被檢查出來）

12、修改指定下標位置的資料

void SeqListAt(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl);  //斷言
	assert(psl->size > 0);  //順序表不能為空
	assert(pos >= 0 && pos < psl->size);  //檢查pos下標的合法性

	psl->a[pos] = x;  //修改pos下標處對應的資料
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/294941.html

標籤：其他

上一篇：Python攻防-Socket通信建立TCP反向連接

下一篇：奇葩面試題，O(logn)的底數是多少？

【資料結構入門】順序表（SeqList）詳解（初始化、增、刪、查、改）