目錄

前言

順序表的介紹和簡單實作

關于順序表

順序表的分類

順序表的初步組成

功能函式的宣告

功能函式的實作

初始化

檢查容量判斷是否需要擴容

頭插

頭刪

尾插

尾刪

指定資料位置插入

指定資料洗掉

尋找資料并回傳下標

銷毀順序表

原始碼

SeqList.c函式定義

測驗代碼

順序表小結

前言

在介紹順序表之前我們先簡單了解一下線性表：

線性表是n個具有相同特性的資料元素的有限序列，在邏輯上是線性結構，也就說是連續的一條直線，但是在物理結構上并不一定是連續的，線性表在物理上存盤時，通常以陣列和鏈式結構的形式存盤，

常見的線性表：順序表、鏈表、堆疊、佇列、字串...

順序表的介紹和簡單實作

關于順序表

順序表就是采用陣列存盤，但在陣列的基礎上，要從頭部開始存盤且是連續存盤，中間不能跳躍

順序表的分類

順序表也分為動態線性表和靜態線性表，

靜態線性表：使用定長的陣列存盤，給定的空間是固定的，也可以理解為你申請了一個房間的空間，你只能在這個房間使用空間，由于不靈活這里就直接介紹動態的

動態線性表：采用動態開辟的陣列存盤，可以靈活的使用空間，空間不夠可以realloc擴容，可以理解為你開始申請了一個房間，而當你整個房間的空間用完后，你可以再申請一個房間的空間使用，

如果有不了解動態記憶體分配的可以小伙伴，可以看看我之前寫的動態記憶體分配

順序表的初步組成

由于是動態記憶體分配，我們需要定義一個結構體：

1.存放一個指標用來維護動態記憶體開辟的空間

2.存放變數size，記錄存放的個數

3.存放變數capacity，記錄當前空間的容量，空間滿了就擴容

typedef int DataType;
typedef struct SeqList
{
	DataType* p;
	int sz;
	int capacity;
}SL;

功能函式的宣告

SeqList.h

#pragma once

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

typedef int DataType;
typedef struct SeqList
{
	DataType* p;
	int sz;
	int capacity;
}SL;
//順序表初始化
void SeqListInit(SL* pc);
//檢查順序表的容量
void SeqListCheckCapacity(SL* pc);
//順序表尾插
void SeqListpushback(SL* pc, DataType x);
//順序表尾刪
void SeqListpopback(SL* pc);
//順序表頭插
void SeqListpushfront(SL* pc, DataType x);
//順序表頭刪
void SeqListpopfront(SL* pc);
//列印順序表
void SeqListPrint(SL* pc);
//洗掉順序表
void SeqListDestory(SL* pc);
//順序表指定pos位置插入
void SeqListInsert(SL* pc, DataType x, int pos);
// 洗掉pos位置的資料
void SeqListErase(SL* pc, int pos);
// 找到了回傳x位置下標，沒有找到回傳-1
int SeqListFind(SL* pc, DataType x);

功能函式的實作

初始化

我們先創建一個結構體變數 SL s，然后傳變數s的地址通過一系列的介面函式實作順序表的增刪查改，首先要先初始化s，將p置空，sz和capacity置0，

SL s;
SeqListInit(&s);

void SeqListInit(SL* pc)
{
	pc->sz = pc->capacity = 0;
	pc->p = NULL;
}

檢查容量判斷是否需要擴容

定義一個check函式判斷空間是否滿了，如果滿了就擴容，每次擴2倍，比如100空間的容量要變成200空間的容量，所以當插入資料時，首先需要呼叫check函式判斷容量是否滿了

void SeqListCheckCapacity(SL* pc)
{	
	//沒有空間則擴容
	if (pc->sz == pc->capacity)
	{
		int newcapacity = pc->capacity == 0 ? 4 : pc->capacity * 2;
		DataType* tmp = (DataType*)realloc(pc->p, newcapacity * sizeof(DataType));
		if (tmp == NULL)
		{
			printf("%s\n", strerror(errno));
			exit(-1);
		}
		pc->p = tmp;
		pc->capacity = newcapacity;
	}
}

然后就是順序表的頭插pushfront，頭刪popfront，尾插pushback，尾刪popback，指定pos位置插入pushpop，destory銷毀等，順序表的原始碼

尾插，尾刪直接插入洗掉，頭插，頭刪需要挪動資料后插入洗掉

頭插

假定當前的容量capacity是8，sz已經存放的個數是4，而我們要頭插資料5的話，就要把順序表整體后移，然后插入5，此時資料增加了一個，sz就要++，

對指標p，p[tmp]等價于 *(p+tmp)

void SeqListpushfront(SL* pc, DataType x)
{
	SeqListCheckCapacity(pc);
	int tmp = pc->sz;
	while (tmp > 0)
	{
		pc->p[tmp] = pc->p[tmp - 1];
		--tmp;
	}
	pc->p[0] = x;
	pc->sz++;
}

頭刪

頭刪與頭插類似，不過是向左挪動資料洗掉順序表中的第一個資料，但是當順序表沒有資料時就不能頭刪了，所以我們要assert斷言一下，斷言為真程式就繼續，為假就會報錯了，涉及指標大部分需要斷言

void SeqListpopfront(SL* pc)
{	
	assert(pc->sz > 0);
	int tmp = 1;
	while (tmp < pc->sz)
	{
		pc->p[tmp - 1] = pc->p[tmp];
		++tmp;
	}
	pc->sz--;
}

尾插

尾插只需要在當前順序表的最后一個資料后面插入，當然插入資料時首先要check容量

void SeqListpushback(SL* pc, DataType x)
{	
	SeqListCheckCapacity(pc);
	pc->p[pc->sz] = x;
	pc->sz++;
}

尾刪

先斷言順序表是否有資料支持洗掉

void SeqListpopback(SL* pc)
{
	assert(pc->sz > 0);
	pc->sz--;
}

指定資料位置插入

和頭插類似找到資料后挪動后面的資料再插入即可，這里的pos表示順序表中的第幾個數

void SeqListInsert(SL* pc, DataType x, int pos)
{
	SeqListCheckCapacity(pc);
	assert(pos <= (pc->sz+1) && pos > -1);    //pos表示第幾個數，不是下標索引
	int tmp = pc->sz;
	while (pos <= tmp + 1)
	{
		pc->p[tmp] = pc->p[tmp - 1];
		tmp--;
	}
		pc->p[pos - 1] = x;
	pc-> sz++;
}

指定資料洗掉

那我們只需找到這個數，然后通過左移洗掉即可

void SeqListErase(SL* pc, int pos)
{
	assert(pos <= pc->sz && pos > -1);
	while (pos <= pc->sz)
	{
		pc->p[pos - 1] = pc->p[pos];
		pos++;
	}
	pc->sz--;
}

尋找資料并回傳下標

遍歷順序表找到后回傳下標，找不到就回傳-1（那么前提是順序表中的數都是無符號型別）

int SeqListFind(SL* pc, DataType x)
{
	for (int i = 0; i < pc->sz; i++)
	{
		if (pc->p[i] == x)
			return i;
	}
	return -1;
}

銷毀順序表

因為我們是在堆區動態開辟的空間，不用了就要free釋放空間避免記憶體泄漏

void SeqListDestory(SL* pc)
{
	pc->sz = 0;
	pc->capacity = 0;
	free(pc->p);
	pc->p = NULL;
}

原始碼

SeqList.c函式定義

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"

void SeqListInit(SL* pc)
{
	pc->sz = pc->capacity = 0;
	pc->p = NULL;
}
void SeqListCheckCapacity(SL* pc)
{	
	//沒有空間則擴容
	if (pc->sz == pc->capacity)
	{
		int newcapacity = pc->capacity == 0 ? 4 : pc->capacity * 2;
		DataType* tmp = (DataType*)realloc(pc->p, newcapacity * sizeof(DataType));
		if (tmp == NULL)
		{
			printf("%s\n", strerror(errno));//errno是錯誤碼,strerror()根據錯誤碼判斷出錯原因
			exit(-1);//擴容失敗后就直接退出程式了
		}
		pc->p = tmp;
		pc->capacity = newcapacity;
	}
}
void SeqListPrint(SL* pc)
{
	for (int i = 0; i < pc->sz; i++)
	{
		printf("%d\t", pc->p[i]);
	}
	printf("\n");
}
void SeqListpushback(SL* pc, DataType x)
{	
	SeqListCheckCapacity(pc);
	pc->p[pc->sz] = x;
	pc->sz++;
}
void SeqListpopback(SL* pc)
{
	assert(pc->sz > 0);
	pc->sz--;
}
void SeqListpushfront(SL* pc, DataType x)
{
	SeqListCheckCapacity(pc);
	int tmp = pc->sz;
	while (tmp > 0)
	{
		pc->p[tmp] = pc->p[tmp - 1];
		--tmp;
	}
	pc->p[0] = x;
	pc->sz++;
}

void SeqListpopfront(SL* pc)
{	
	assert(pc->sz > 0);
	int tmp = 1;
	while (tmp < pc->sz)
	{
		pc->p[tmp - 1] = pc->p[tmp];
		++tmp;
	}
	pc->sz--;
}

void SeqListDestory(SL* pc)
{
	pc->sz = 0;
	pc->capacity = 0;
	free(pc->p);
	pc->p = NULL;
}
void SeqListInsert(SL* pc, DataType x, int pos)
{
	SeqListCheckCapacity(pc);
	assert(pos <= (pc->sz+1) && pos > -1);    //pos表示第幾個數，不是下標索引
	int tmp = pc->sz;
	while (pos <= tmp + 1)
	{
		pc->p[tmp] = pc->p[tmp - 1];
		tmp--;
	}
		pc->p[pos - 1] = x;
	pc-> sz++;
}

void SeqListErase(SL* pc, int pos)
{
	assert(pos <= pc->sz && pos > -1);
	while (pos <= pc->sz)
	{
		pc->p[pos - 1] = pc->p[pos];
		pos++;
	}
	pc->sz--;
}

int SeqListFind(SL* pc, DataType x)
{
	for (int i = 0; i < pc->sz; i++)
	{
		if (pc->p[i] == x)
			return i;
	}
	return -1;
}

測驗代碼

建議大家每寫完幾個函式就可以先通過介面測驗一下函式的功能是否滿足自己的要求

開頭的定義結構體變數s，和初始化都是必不可少的

#include "SeqList.h"

void Test2()
{
	SL s;
	SeqListInit(&s);
	SeqListpushback(&s, 1);
	SeqListpushback(&s, 2);
	SeqListpushback(&s, 3);
	SeqListpushback(&s, 4);
	SeqListpushback(&s, 5);
	SeqListPrint(&s);
	SeqListInsert(&s, 10, 6);
	SeqListPrint(&s);
	SeqListErase(&s, 1);
	SeqListPrint(&s);
	printf("%d\n", SeqListFind(&s, 10));
	printf("%d\n", SeqListFind(&s, 20));
	SeqListDestory(&s);
}
int main()
{	
	//Test1();
	Test2();
}

順序表小結

順序表也是有缺陷的：

1??空間不夠時需要擴容的，而擴容是需要付出代價的，我們一般是擴2倍，這也從一定程度上導致空間浪費，（比如我只需要120的空間，而100的空間滿了，擴容為200，導致80的空間浪費）且原空間不夠擴容的話，需要將資料全部遷移，大大降低了效率，

2??順序表是從頭開始且連續存盤資料的，而當我們要在頭部或是中間位置插入洗掉資料時，需要挪動資料，也大大降低了效率，

當然順序表也不是一無是處的，順序表空間是連續有序的，支持隨即訪問，有很多程式都要支持隨機訪問

針對順序表的這兩個缺陷又引入了鏈表，之后會給大家介紹鏈表以及鏈表的實作，

不是看到希望才去堅持，而是堅持了才看到希望，敬每一位努力奮斗的你和學習編程的你，希望我的文章能對你有所幫助，歡迎👍點贊 ，📝評論，🌟關注，??收藏