C語言順序表的基本結構與實現思路詳解

2023-02-14 06:02:33

一、順序表的概念與結構

1、線性表的解釋

首先我們在這裡引入線性表的概念。線性表是n個具有相同特性的資料元素的有限序列。線性表是一種在實際中廣泛使用的資料結構。

常見的線性表：順序表、連結串列、棧、佇列、字串……

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

順序表就是線性表的一種，我們在這裡詳細解釋一下順序表的實現，後續我們會更新連結串列等內容。

2、順序表概念解釋

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

而順序表一般可分為：

靜態順序表：使用定長陣列儲存。
動態順序表：使用動態開闢的陣列儲存。

二、順序表的思路及程式碼實現詳解

1.靜態順序表的實現

我們先想出來一個靜態表整體的模板思路：

定義一個結構體，該結構體包含一個可以存放資料的陣列和記錄陣列中有效數位的變數。
初始化結構體。
列印結構體。
頭插。
尾插。
頭刪。
尾刪。
任意位置插入。
任意位置刪除。

這裡需要有一點注意的是，我們在定義結構體中的陣列時，我們可以用typedef進行變數名簡化，這也方便我們後期更改儲存型別的時候直接更改typedef處就行。同時我們會想到陣列的大小需要define定義一個宏，這樣大大提高了程式碼後期的可維護性。

但是我們仔細想一下，假如我們儲存的資料滿了，我們想要繼續儲存的話還要找到原始碼進行更改大小。每次儲存滿了，都要更改。那是不是太麻煩了，且效率很低。這時候我們就聯想到了動態的順序表，可以自動開闢空間，從而大大提高效率。

這裡我就給出大家靜態順序表定義及介面的程式碼，不再詳細解釋介面的實現了。我們這裡詳細解釋一下動態順序表的解釋。靜態順序表介面的實現與動態順序表介面實現大同小異，可參考動態順序表介面的詳解。

程式碼如下：

#define MAX_SIZE 10
typedef int SQDataType;
typedef struct SeqList
{
	SQDataType a[MAX_SIZE];
	int size;
}SL;
//typedef struct SeqList SL;
typedef struct SeqList SL;
//初始化結構體
void SeqListInit(SL* ps);
//列印
void SeqListPrint(SL s);
//尾插
void SeqListPushBack(SL* ps, SQDataType x);
//尾刪
void SeqListPopBack(SL* ps);
//頭插
void SeqListPushFrint(SL* ps, SQDataType x);
//頭刪
void SeqListPopFrint(SL* ps);
//查詢位置
int SeqListFind(SL s, SQDataType x);
//任意插入
void SeqListInsert(SL* ps, int pos, SQDataType x);
//任意刪
void SeqListErase(SL* ps, int pos);

2.動態順序表思路及程式碼實現

2.1 動態順序表的整體思路

動態順序表的思路與靜態大致相同，但也有所不同，我來給大家詳細解釋一下。我們先看動態順序表的整體思路模板：

定義一個結構體，該結構體包含一個可以存放資料的動態陣列和記錄陣列中有效資料的變數，兩外還需要一個變數記錄當前陣列的大小。
初始化結構體。
列印結構體。
檢查陣列容量
頭插。
尾插。
頭刪。
尾刪。
任意位置插入。
任意位置刪除。
釋放動態陣列空間

我們上面提到了動態的陣列，需要用malloc或realloc動態開闢空間。由於是動態開闢的，我們這裡多了一項釋放動態開闢的空間。注意，記錄陣列的有效資料和陣列大小並不相同。有效資料是已經儲存的資料個數，而陣列大小是指最能夠儲存陣列的個數。我們為什麼要記錄陣列的大小呢？這裡是用來判斷是否儲存滿了，滿了話要開闢空間。

我們來詳細看一下每個介面的實現。

2.2 定義結構體的實現

在定義結構體時，我們可以用typedef進行陣列型別簡化，同時方便我們後期更改儲存型別的時候直接更改typedef處即可。同時我們也用typedef進行結構體型別簡化，方便我們以後編輯程式碼。我們來看一下程式碼的實現：

typedef int SQDataType;
struct SeqList
{
	SQDataType* a;
	int size;
	int capacity;
};
typedef struct SeqList SL;

通過上面的程式碼我們可以發現，當我們不想儲存int型資料時，我們只需把‘typedef int SQDataType’改為‘typedef doubleSQDataType’即可。極大的提高了程式碼的維護性。

2.3 初始化結構體

我們初始化結構體時，可以先將陣列置空，我們後期插入資料時可再開闢空間。同時當然有效資料和陣列大小都要初始化成零。我們看程式碼的實現。

void SeqListInit(SL* ps)
{
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

我們這裡是改變了結構體的內容，所以需要傳地址，用指標變數來接收。

2.4 結構體列印

結構體列印方便我們觀察對動態陣列的操作。列印的時陣列的有效資料的內容。我們來看程式碼的實現。

void SeqListPrint(SL s)
{
	int i = 0;
	for (i = 0; i < s.size; i++)
	{
		printf("%d ", s.a[i]);
	}
	printf("n");
}

2.5 檢查陣列容量

我們仔細想一想，是不是在插入每個資料之前都要檢查陣列是否已經滿了。如果滿了，則需要增容。如果沒有滿，就插入資料即可。在這裡我們需要實現頭插、尾插、任意插入三個介面，所以我們就把檢查陣列容量單獨分裝一個函數，這樣提高程式碼的簡潔性。我們看一下程式碼的實現。

void SQLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SQDataType* tmp =(SQDataType*)realloc(ps->a, sizeof(SQDataType) * newcapacity);
		if (tmp == NULL)
		{
			printf("realloc failedn");
			exit(-1);
		}
		ps->capacity = newcapacity;
		ps->a = tmp;
	}
}

當我們檢查增容時，我們還要判斷一下之前的陣列大小是否為零，如果是零的話，我們要給其賦一個值。因為我們剛開始初始化陣列的時候把陣列指標置空了。在動態順序表中我們增容一般會擴大到原來的2倍。

2.6 頭插

在插入之前要判斷陣列是否已經滿了。頭插的思想就是把陣列的內容整體後移一位，我們把要插入的資料放在第一位。我們結合著程式碼一起理解。

void SeqListPushFrint(SL* ps, SQDataType x)
{
	SQLCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end+1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}

2.7 尾插

同樣，在插入之前要判斷陣列是否已經滿了。尾插的思想很簡單。就是直接在陣列尾部插入一個資料即可。我們看一下程式碼的實現。

void SeqListPushBack(SL* ps, SQDataType x)
{
	SQLCheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}

2.8 頭刪

刪除時我們也有要注意的一點，就是檢查陣列中是否有元素給我們刪除。頭刪的思想就是除去陣列的第一個元素，我們將後面的元素整體向前移動一位，將第一位給覆蓋了。我們來看程式碼。

void SeqListPopFrint(SL* ps)
{
	assert(ps->size > 0);
	int i = 0;
	for (i = 0; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

2.9 尾刪

同樣，在尾刪之前，我們要檢查陣列中是否有元素給我們刪除。尾刪的思想十分簡單，就是把陣列的有效資料減一即可。我們看一下程式碼的實現。

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

2.10 任意刪除

在任意刪除時，我們首先要判斷刪除的位置是否合理，不能違背順序表的規則。同樣，在尾刪之前，我們要檢查陣列中是否有元素給我們刪除。任意刪除就是我們指出刪除位置的下標進行刪除。當然，我們想要刪除陣列中指定元素時，我們可以先查出元素下標在進行刪除。這個相對來說較複雜一點，我們結合著程式碼理解一下。

//查詢位置
int SeqListFind(SL s, SQDataType x)
{
	int i = 0;
	for (i = 0; i < s.size; i++)
	{
		if (s.a[i] == x)
		{
			return i;
		}
	}
	return -1;
}
void SeqListErase(SL* ps, int pos)
{
	assert(pos >= 0 && pos < ps->size);
	int begin = pos + 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}
	ps->size--;
}

2.11 任意插入

在任意插入時時，我們也要判斷插入的位置是否合理，不能違背順序表的規則。插入時，我們不能忘記檢查陣列是否滿了。任意插入的思想與任意刪除的思想基本相同。任意插入的思想就是在我們指出刪除位置的下標進行插入。我們看一下程式碼實現。

void SeqListInsert(SL* ps, int pos, SQDataType x)
{
	assert(pos >= 0 && pos <= ps->size);
	SQLCheckCapacity(ps);
	int end = ps->size-1;
	while (end >= pos)
	{
		ps->a[end+1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}

2.12 空間釋放

由於我們的陣列是動態開闢的，所以當我們不用時，我們要及時釋放掉動態開闢的空間，避免記憶體漏失。同時我們要把陣列指標再次置空，避免產生野指標。我們看程式碼實現。

void SeqListDestory(SL* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

三、順序表程式碼整合

由於程式碼量相對來說有一點多，所以我們就將函數的宣告的定義分開，這樣有利於提高程式碼的可讀性，同時會保持一個良好的思路，且方便編寫程式碼。

我們將函數的宣告放在單獨的一個SeqList.h的標頭檔案，函數的實現放在一個單獨的SeqList.c原始檔，函數的主方法及呼叫放在另一個單獨的test.c原始檔。

SeqList.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SQDataType;
struct SeqList
{
	SQDataType* a;
	int size;
	int capacity;
};
typedef struct SeqList SL;
//初始化結構體
void SeqListInit(SL* ps);
//列印
void SeqListPrint(SL s);
//尾插
void SeqListPushBack(SL* ps, SQDataType x);
//尾刪
void SeqListPopBack(SL* ps);
//頭插
void SeqListPushFrint(SL* ps, SQDataType x);
//頭刪
void SeqListPopFrint(SL* ps);
//查詢位置
int SeqListFind(SL s, SQDataType x);
//任意插入
void SeqListInsert(SL* ps, int pos, SQDataType x);
//任意刪
void SeqListErase(SL* ps, int pos);
//銷燬空間
void SeqListDestory(SL* ps);

SeqList.c

#include"SeqList.h"
//初始化結構體
void SeqListInit(SL* ps)
{
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
//列印
void SeqListPrint(SL s)
{
	int i = 0;
	for (i = 0; i < s.size; i++)
	{
		printf("%d ", s.a[i]);
	}
	printf("n");
}
//查容增容
void SQLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SQDataType* tmp =(SQDataType*)realloc(ps->a, sizeof(SQDataType) * newcapacity);
		if (tmp == NULL)
		{
			printf("realloc failedn");
			exit(-1);
		}
		ps->capacity = newcapacity;
		ps->a = tmp;
	}
}
//尾插
void SeqListPushBack(SL* ps, SQDataType x)
{
	SQLCheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}
//尾刪
void SeqListPopBack(SL* ps)
{
	assert(ps->size > 0);
	ps->size--;
}
//頭插
void SeqListPushFrint(SL* ps, SQDataType x)
{
	SQLCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end+1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}
//頭刪
void SeqListPopFrint(SL* ps)
{
	assert(ps->size > 0);
	int i = 0;
	for (i = 0; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}
//查詢位置
int SeqListFind(SL s, SQDataType x)
{
	int i = 0;
	for (i = 0; i < s.size; i++)
	{
		if (s.a[i] == x)
		{
			return i;
		}
	}
	return -1;
}
//任意插——在下標為pos的位置插入資料
void SeqListInsert(SL* ps, int pos, SQDataType x)
{
	assert(pos >= 0 && pos <= ps->size);
	SQLCheckCapacity(ps);
	int end = ps->size-1;
	while (end >= pos)
	{
		ps->a[end+1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}
//任意刪——刪除下標為pos的資料
void SeqListErase(SL* ps, int pos)
{
	assert(pos >= 0 && pos < ps->size);
	int begin = pos + 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}
	ps->size--;
}
//銷燬空間
void SeqListDestory(SL* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

test.c

#include"SeqList.h"
void test()
{
	SL s1;
	SeqListInit(&s1);
	SeqListPushBack(&s1, 1);
	SeqListPushFrint(&s1, 1);
	SeqListPushFrint(&s1, 2);
	SeqListPushFrint(&s1, 3);
	SeqListPushFrint(&s1, 4);
	SeqListPushBack(&s1, 5);
	SeqListPrint(s1);
	SeqListPopFrint(&s1);
	SeqListPrint(s1);
	int pos = SeqListFind(s1, 1);
	SeqListInsert(&s1, pos, 10);
	SeqListInsert(&s1, 0, 20);
	SeqListPrint(s1);
	SeqListErase(&s1, 0);
	SeqListPrint(s1);
	SeqListDestory(&s1);
}
int main()
{
	test();
	return 0;
}

到此這篇關於C語言順序表的基本結構與實現思路詳解的文章就介紹到這了,更多相關C語言順序表內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！