c語言實作順序表(初階資料結構)

前言

這是小編第一篇資料結構的文章，從今天開始更新資料結構相關的博客，希望大家多多關注，一起學習，

今天小編主要說的是順序表的相關內容，

順序表的介紹

說到順序表，就需要介紹一下線性表了，線性表是什么呢？

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

現在知道了順序表是線性表的一種,線性表還包括鏈表，堆疊、佇列和字串，

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

這里的陣列也就是順序表的基本結構，鏈式結構也就是鏈表的基本結構，這里我們先談順序表，以后再談鏈表，

還需要補充一下邏輯結構和物理結構,這個沒理解好，后面是不太好學的

邏輯結構:簡單地理解，就是指的資料之間的邏輯關系，
物理結構:資料在物理存盤空間上選擇集中存放還是分散存放

單看這個可能不太好理解，舉個簡單的例子

人物的關系就是邏輯結構，我是爸爸的兒子，爸爸是爺爺的兒子，正是這種關系才把我們串聯在一起，我們可以不在一起，但是我們在邏輯上相當于有一條線將我們串在一起，

排隊時就是物理結構，我們必須站在一列，是什么把我們串聯在一起，是排隊這種物理結構，相當于有一條實質性的線，而且這條一旦斷了，物理結構也就沒了，

順序表在物理和邏輯上都是連續的，而鏈表在邏輯是連續的，物理上是不連續的

接下來正式談順序表

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

順序表的分類

靜態順序表:使用定長陣列存盤，
動態順序表:使用動態開辟的陣列存盤，

這里我們主要講解動態版本，靜態在c語言中也學過，就是一個普通陣列，實際意義不大，

動態開辟是什么意思？也就是陣列的容量不是確定的，是可以動態增長的，這樣其實更有利于存盤資料，支持增刪等操作的，

接下來我們就開始實作

專案分配

小編是使用的是vs2019作為開發工具,搭建順序表工程

• SeqList.h作為頭檔案，順序表的創建、儲存函式宣告和參考函式所需的頭檔案
• SeqList.c作為函式介面檔案，即需求函式的定義
• test 7_29_.c作為測驗檔案，看函式實作是否正確

順序表的定義

typedef int SQDataType;
//動態順序表的定義
typedef struct SeqList
{
	SQDataType* a;//陣列的名稱
	int size; //有效資料的個數
	int capacity;//空間總容量大小
}SLT;

看這段代碼，其實還是有一些小技巧，解決了一些重要的問題

在一個專案中我們需要在很多地方用到資料的型別名，如int、char，如果我們想把原本儲存資料型別為int改為char，就需要改很多的地方，那么有沒有什么一勞永逸的方法呢？

答案是有的,我們可以用到typedef,直接將int定義為SQDataType，后面全用SQDataType，以后要改的話，就只需將int改為char或者其他型別，結構體也是如此，定義為了SLT，

這個小問題就解決了，
定義完成后將這段程式放在SeqList.h中，

順序表的初始化

//初始化
void SeqListInit(SLT* psl)
{
	assert(psl);//斷言psl一定不能為空，要引頭檔案assert.h
	psl->a = NULL;
	psl->size = psl->capacity = 0;
}

初始化需要將陣列置為空，有效資料個數和大小均置為0，如果不進行初始化，將全部為隨機值，可能會影響后續操作，
這里非常重要一點是傳址,不是傳值，記住一般需要修改數值時都是傳址，

其實直接將main函式中創建的順序表s直接s = {0};來初始化也是可以的，只是上面這樣寫是為了讓大家了解具體是如何實作的，

我們可以通過除錯來查看是否成功，

成功！！！

順序表的列印

已經建立了一個順序表，如何才能清楚的看到呢？這就需要我們將他列印在螢屏上了

//列印函式
void SeqListPrint(SLT* psl)
{
	assert(psl);
	for (int i = 0; i < psl->size; i++)
	{
		printf("%d ", psl->a[i]);
	}
	printf("\n");
}

列印就是簡單的回圈來完成就可以，需要注意的是傳址，

等下講尾插的時候可以檢測是否正確，

順序表的銷毀

順序表在使用完畢后，由于是動態開辟的記憶體空間，是需要free掉的，不然會造成記憶體泄漏，所以我們需要銷毀這塊已經使用過的空間，

//銷毀函式
void SeqListDestory(SLT* psl)
{
	assert(psl);
	if (psl->a)//判斷動態開辟的陣列是否為空
	{
		free(psl->a);//不為空就釋放掉
	}
	psl->size = psl->capacity = 0;
}

接下來都是些重要的函式介面了

順序表的尾插

尾插其實就是從尾部插入資料，組成一個新的順序表，

增容函式的實作

但是需要注意的是我們需要判斷原有順序表是否為慷訓者已滿，如果為慷訓者已滿我們就需要開辟新空間來儲存插入的資料,所以需要寫一個判斷代碼，再開辟新空間，由于還有其他的插入介面，所以我們可以直接內部封裝一個增容函式SeqListCheclCapacity，

//封裝一個增容函式
void SeqListCheclCapacity(SLT* psl)
{
	if (psl->size == psl->capacity)//判斷是否滿了
	{
		//如果為空，大小就置為4，否則就以2倍遞增
		size_t newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		//動態開辟空間
		psl->a = realloc(psl->a, newcapacity * sizeof(SQDataType));
		psl->capacity = newcapacity;
	}
}

這個增容代碼需要注意的是呼叫realloc函式時，第二個引數是新的存盤大小，單位為位元組，所以傳的應該是sizeof(存盤的資料型別) * newcapacity(新大小)，不能直接傳新大小，

再就是解釋為什么以二倍遞增？二倍其實是一種折中的考慮，避免造成空間的浪費，要是以3倍、4倍也行，

尾插

//尾插
void SeqListPushBack(SLT* psl, SQDataType x)
{
	assert(psl);
	SeqListCheclCapacity(psl);
	psl->a[psl->size] = x;
	psl->size++;
}

先判斷是否滿了，滿了就增容，然后就直接插入到size的位置，然后size++，有效個數加一，尾插就是這么簡單，

我們來通過測驗檔案來看一下效果

完美創建，增容成功，列印也沒有問題！！！

順序表的頭插

講完尾插后，就是頭插了，頭插也就是從頭部插入，

頭部插入要比尾部插入麻煩一丟丟啦， 只需要將資料整體向后移動一位就可以，再在下標為0的位置插入就可以了,因為是插入，所以也需要考慮增容問題，

//頭插
void SeqListPushFront(SLT* psl, SQDataType x)
{
	assert(psl);
	SeqListCheclCapacity(psl);//判斷是否已滿
	int end = psl->size - 1;//找到尾部
	while (end >= 0)
	{
		psl->a[end + 1] = psl->a[end];//整體向后移動一位
		end--;
	}
	psl->a[0] = x;
	psl->size++;
}

看一下效果

成功！！！

順序表的任意位置插入資料

知道尾插和頭插后一定就更想知道如何在任意位置插入了，其實任意位置插入也就和頭插類似，也就是在將指定位置的后面所有數值均向后移動一位，而頭插是固定的移動所有數值，這個移動要看要求，也就是傳過來的pos值，pos值也就是下標值，

函式宣告為

//在指定位置插入數值
void SeqListInsert(SLT* psl, size_t pos, SQDataType x);//pos為指定的下標位置，x為傳過來的數值

//指定位置插入數值(可以代替頭插和尾插)
void SeqListInsert(SLT* psl, size_t pos, SQDataType x)
{
	assert(psl);
	assert(pos <= psl->size);//插入的位置必須小于等于含有的資料數
	SeqListCheclCapacity(psl);//判斷是否需要增容

	size_t end = psl->size;
	//指定位置后的資料全部向后移動一位
	while (end > pos)
	{
		psl->a[end] = psl->a[end - 1];
		end--;
	}
	psl->a[pos] = x;
	psl->size++;
}

這個代碼是可以代替頭插和尾插的
看一下效果

成功！！！

順序表的尾刪

講完插入就要講洗掉了，一些不要的資料是需要洗掉的，踢出我們的順序表，洗掉也和插入一樣，我們先來看尾刪，其實尾刪是非常簡單的，我們只需要把有效數字的個數減一就行了，這樣就訪問不到這個資料了，

這里就有同學會問了，你這樣不是資料還在嗎？沒有洗掉掉啊，

這里我想說的是，我們完全沒有必要去把這個資料free掉，回想一下我們插入是怎么插入的，我們除了尾插其他都是通過后移資料來操作的，其實這個有點像的就是覆寫，所以如果要重新插入資料，也就是覆寫，所以這個洗掉資料在不在也就不影響，只是覆寫換值，我們所要做的也就是讓順序表訪問不到就行了，

//尾刪
void SeqListPopBack(SLT* psl)
{
	assert(psl);
	//assert(psl->size > 0); 不太溫和的方式
	//溫和一點
	if (psl->size > 0)
	{
		psl->size--;//有效資料個數減一
	}
}

這里溫和和不太溫和的方式意思其實是一樣的，就是防止順序表為空時還要進行洗掉，不溫合就直接報錯，溫和就是判斷一下，

看一下效果

成功！！！

順序表的頭刪

講完尾刪就是頭刪了，頭刪的主要操作也就是覆寫，除了下標為0的所有資料全部向前移動一位，將第一個資料覆寫掉，有效資料個數減一即可，

將2、3、4、5依次向前覆寫，再將size減一，所得到的的就是頭刪后的順序表，

//頭刪
void SeqListPopFront(SLT* psl)
{
	assert(psl);
	int head = 1;
	while (head < psl->size)//從下標為1的位置開始前移
	{
		psl->a[head - 1] = psl->a[head];
		head++;
	}
	//assert(psl->size > 0); //不太溫和的方式
	//溫和一點
	if (psl->size > 0)
	{
		psl->size--;
	}
}

看一下效果

成功！！！

順序表的任意位置洗掉

講完尾刪和頭刪，接下來就是任意位置的洗掉，這個的主要思想也是覆寫，插入是往后覆寫，洗掉則是往前覆寫，在給定位置后的所有資料依次向前覆寫，再size減一，

//指定位置洗掉資料(可以代替頭刪和尾刪)
void SeqListErase(SLT* 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--;
}

看一下效果

成功！！！

順序表的查找

查找就是看順序表是否存在指定的數值，直接遍歷判斷即可，存在就回傳下標，不存在就回傳-1,所以函式的回傳值為int型別，

//查找
int SeqListFind(SLT* psl, SQDataType x)
{
	assert(psl);
	for (int i = 0; i < psl->size; i++)
	{
		if (psl->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

這個代碼有個缺陷就是如果存在兩個相同的數值，就只會回傳下標小的那個，不會全部回傳，這里只需要要求我們判斷存不存在就夠了，
看一下效果

成功！！！

順序表的元素個數

直接將size列印即可，由于個數一定是大于等于0的，所以函式的回傳值型別可以為size_t，

/求出順序表中的元素數目
size_t SeqListSize(SLT* psl)
{
	assert(psl);
	return psl->size;
}
看一下效果

成功！！！

修改指定位置的數值

直接賦值替換就行，

//修改指定位置的值
void SeqListAt(SLT* psl, size_t pos, SQDataType x)
{
	assert(psl);
	assert(pos < psl->size);//位置要小于現有的數值個數
	psl->a[pos] = x;
}

看一下效果

成功！！！

結語

這就是順序表所要掌握的所有函式介面，相信你肯定對順序表有了一定了解，整體來看，順序表的缺點還是很明顯的，就是空間的浪費，實際使用的空間是常常小于所開辟的空間的，并且增容拷貝資料也是消耗很大的，所以鏈表就出現了，小編將在不久出一篇關于鏈表的博客，

不過當下為了鞏固大家順序表的理解，小編大概在兩天后更新一篇關于順序表的幾題力扣oj題，歡迎大家關注，共同學習，如果在閱讀時發現錯誤，可以私信我修改，如果不理解，也可以來討論，私信必回哦，感謝大家參考學習，

SeqList.h檔案內容

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>


typedef int SQDataType;

//動態順序表的定義
typedef struct SeqList
{
	SQDataType* a;
	int size; //有效資料的個數
	int capacity;//空間總容量大小
}SLT;

//增刪查改

//初始化
void SeqListInit(SLT* psl);

//銷毀函式
void SeqListDestory(SLT* psl);

//列印函式
void SeqListPrint(SLT* psl);

//封裝一個增容函式
void SeqListCheclCapacity(SLT* psl);

//尾插
void SeqListPushBack(SLT* psl, SQDataType x);

//頭插
void SeqListPushFront(SLT* psl, SQDataType x);

//尾刪
void SeqListPopBack(SLT* psl);

//頭刪
void SeqListPopFront(SLT* psl);

//查找
int SeqListFind(SLT* psl, SQDataType x);

//在指定位置插入數值
void SeqListInsert(SLT* psl, size_t pos, SQDataType x);

//洗掉指定位置的數值
void SeqListErase(SLT* psl, size_t pos);

//求出順序表中的元素數目
size_t SeqListSize(SLT* psl);

//修改指定位置的值
void SeqListAt(SLT* psl, size_t pos, SQDataType x);

test 7_29_.c檔案內容

#pragma once
#include"SeqList.h"

//初始化
void SeqListInit(SLT* psl)
{
	assert(psl);//psl一定不能為空
	psl->a = NULL;
	psl->size = psl->capacity = 0;
}

//銷毀函式
void SeqListDestory(SLT* psl)
{
	assert(psl);
	if (psl->a)
	{
		free(psl->a);
	}
	psl->size = psl->capacity = 0;
}

//列印函式
void SeqListPrint(SLT* psl)
{
	assert(psl);
	for (int i = 0; i < psl->size; i++)
	{
		printf("%d ", psl->a[i]);
	}
	printf("\n");
}

//封裝一個增容函式
void SeqListCheclCapacity(SLT* psl)
{
	
	if (psl->size == psl->capacity)
	{
		size_t newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		psl->a = realloc(psl->a, newcapacity * sizeof(SQDataType));
		psl->capacity = newcapacity;
	}
}

//尾插
void SeqListPushBack(SLT* psl, SQDataType x)
{
	assert(psl);
	SeqListCheclCapacity(psl);
	psl->a[psl->size] = x;
	psl->size++;
}

//頭插
void SeqListPushFront(SLT* psl, SQDataType x)
{
	assert(psl);
	SeqListCheclCapacity(psl);
	int end = psl->size - 1;
	while (end >= 0)
	{
		psl->a[end + 1] = psl->a[end];
		end--;
	}
	psl->a[0] = x;
	psl->size++;
}

//尾刪
void SeqListPopBack(SLT* psl)
{
	assert(psl);
	//assert(psl->size > 0); 不太溫和的方式
	//溫和一點
	if (psl->size > 0)
	{
		psl->size--;
	}
}

//頭刪
void SeqListPopFront(SLT* psl)
{
	assert(psl);
	int head = 1;
	while (head < psl->size)
	{
		psl->a[head - 1] = psl->a[head];
		head++;
	}
	//assert(psl->size > 0); 不太溫和的方式
	//溫和一點
	if (psl->size > 0)
	{
		psl->size--;
	}
}

//查找
int SeqListFind(SLT* psl, SQDataType x)
{
	assert(psl);
	for (int i = 0; i < psl->size; i++)
	{
		if (psl->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

//指定位置插入數值(可以代替頭插和尾插)
void SeqListInsert(SLT* psl, size_t pos, SQDataType x)
{
	assert(psl);
	assert(pos <= psl->size);//插入的位置必須小于等于含有的資料數
	SeqListCheclCapacity(psl);

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

//指定位置洗掉資料(可以代替頭刪和尾刪)
void SeqListErase(SLT* 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--;
}

//求出順序表中的元素數目
size_t SeqListSize(SLT* psl)
{
	assert(psl);
	return psl->size;
}

//修改指定位置的值
void SeqListAt(SLT* psl, size_t pos, SQDataType x)
{
	assert(psl);
	assert(pos < psl->size);
	psl->a[pos] = x;
}