C語言實現動態順序表詳解

Posted on by

什麼是順序表?

順序表是在計算機內存中以數組的形式保存的線性表，線性表的順序存儲是指用一組地址連續的存儲單元依次存儲線性表中的各個元素，使得線性表中在邏輯結構上相鄰的數據元素存儲在相鄰的物理存儲單元中，即通過數據元素物理存儲的相鄰關系來反映數據元素之間邏輯上的相鄰關系，采用順序存儲結構的線性表通常稱為順序表。順序表是將表中的結點依次存放在計算機內存中一組地址連續的存儲單元中。

簡言之，順序表是用一段物理地址連續的存儲單元依次存儲數據元素的線性結構，一般情況下采用數組存儲。在數組上完成數據的增刪查改。可以類比vector，簡單理解為可以動態增長的數組~~

順序表一般可以分為：

1.靜態順序表(直接定義數組)：存儲數據的空間是固定的；

導致的問題：開小瞭不夠用，開大瞭浪費空間，現實中不實用

2.動態順序表(用指針接收malloc動態開辟)：存儲數據的空間是可以動態增長的，可以更好的適應於現實中的使用

1. 定義順序表結構體：

首先，我們要創建一個順序表類型，該順序表類型包括瞭順序表的起始位置、記錄順序表內已有元素個數的計數器(size)，以及記錄當前順序表的容量的變量(capacity)。

typedef int SLDataType;//定義一個類型，以便更好的適應每一種數據的存儲，這裡以存放整型數據為例

typedef struct SeqList
{
	SLDataType* a;//聲明瞭一個指向順序表的指針
	int size;//記錄當前順序表內元素個數
	int capacity;//記錄當前順序表的最大容量
}SeqList;//C語言中直接使用Seqlist類型

2. 初始化順序表：

我們需要一個初始化函數，對順序表進行初始化。這裡多說兩句自己的一些理解：有些小夥伴會對結構體直接賦值為0來進行初始化，這種操作雖然編譯器不給error，但也會報warning，我們應該註意這一點，因為本身struct中的指針類型也不能簡單的以0來初始化，實在不想用接口的話，那我建議你用NULL來初始化指針~~當然我們要有意識地去寫工程化的代碼，每個獨立的功能習慣地去用函數封裝起來，我們調用接口實現功能。

//初始化順序表
void SeqListInit(SeqList* ps)
{
	assert(ps);//斷言
	ps->a = NULL;//剛開始時順序表為空，順序表指針為NULL
	ps->size = 0;//起始時元素個數為0
	ps->capacity = 0;//容量為0
	
	/* 或者一開始就開辟空間，給定capacity
	
		ps->a = (SLDateType*)malloc((sizeof(SLDateType)* 4));
	if (ps->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	ps->size = 0;
	ps->capacity = 4;
   */
}

3. 銷毀順序表：

因為順序表所用的內存空間是動態開辟在堆區的，所以我們在使用完後需要及時對其進行釋放，避免造成內存泄漏。 一般這個操作放在return之前調用。
當然，如果想在下次運行前記住當前的一些增刪查改，若需要對數據進行保存，可以使用文件操作函數將數據保存到一個文件中，下次使用順序表的時候先讀取文件數據即可。

//銷毀順序表
void SeqListDestory(SeqList* ps)
{
	assert(ps);//斷言
	free(ps->a);//釋放順序表指針指向的空間
	ps->a = NULL;//及時置空
	ps->size = 0;//元素個數置0
	ps->capacity = 0;//容量置0
}

4. 打印順序表：

打印函數沒啥好說的，直接遍歷一遍size個數組中的元素即可。

//打印順序表
void SeqListPrint(SeqList* ps)
{
	assert(ps);//斷言
	int i = 0;
	//循環打印順序表指針指向的數據
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

5. 判斷容量+擴容：

我們應該意識到，每次需要增加數據的時候，首先都應該先檢查順序表內元素個數是否已達順序表容量上限。若已達上限，那麼我們就需要先對順序表進行擴容，然後才能增加數據。擴容就要使用到realloc函數。

//檢查順序表容量是否已滿，若已滿，則增容
void SeqCheckCapacity(SeqList* ps)
{
	if (ps->size == ps->capacity)//判斷已滿，需要增容
	{
		//判斷順序表容量是否為0，若為0，則先開辟用於存放4個元素的空間大小，若不為0，則擴容為原來容量的兩倍
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* newArr = realloc(ps->a, newcapacity*sizeof(SLDataType));
		if (newArr == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		//最好用同一個指針維護較為穩妥，所以我們把newArr賦值給ps
		ps->a = newArr;//開辟成功，將順序表指針更新
		ps->capacity = newcapacity;//容量更新
	}
}

註意： 若傳入realloc的指針為空指針(NULL)，則realloc函數的作用相當於malloc函數。

6. 頭插數據：

要想在順序表的表頭插入數據，那麼就需要先將順序表原有的數據從後往前依次向後挪動一位，最後再將數據插入表頭。註意一定要依次從後面移動數據，否則會發生覆蓋。

//頭插
void SeqListPushFront(SeqList* ps, SLDataType x)
{
	assert(ps);
	SeqCheckCapacity(ps);//檢查容量
	int i = 0;
	for (i = ps->size; i > 0; i--)//將數據從後往前依次向後挪
	{
		ps->a[i] = ps->a[i - 1];
	}
	ps->a[0] = x;
	ps->size++;//順序表元素個數加一
}

註意： 挪動數據的時候應從後向前依次挪動，若從前向後挪動，會導致後一個數據被覆蓋。

7. 尾插數據：

尾插相對於頭插就比較簡單瞭，直接在表尾的size插入數據即可。記得size也要相應地++

//尾插
void SeqListPushBack(SeqList* ps, SLDataType x)
{
	assert(ps);
	SeqCheckCapacity(ps);//檢查容量
	ps->a[ps->size] = x;
	ps->size++;//順序表元素個數加一
}

8. 指定下標位置插入數據：

要做到在指定下標位置插入數據，首先我們需要得到一個下標位置，然後從該下標位置開始（包括該位置），其後的數據從後往前依次向後挪動一位，最後將數據插入到該下標位置。

//指定下標位置插入
void SeqListInsert(SeqList* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);//檢查輸入下標的合法性
	SeqCheckCapacity(ps);//檢查容量
	int i = 0;
	for (i = ps->size; i > pos; i--)//從pos下標位置開始，其後的數據從後往前依次向後挪
	{
		ps->a[i] = ps->a[i - 1];
	}
	ps->a[pos] = x;
	ps->size++;//順序表元素個數加一
}

我們可以發現，頭插和尾插實際上就是在下標為0的位置和下標為ps->size的位置插入數據，也就意味著我們可以統一使用該函數來實現頭插和尾插。
相當於實現瞭代碼復用，一定程度上也起到瞭便於管理的效果。

//頭插
void SeqListPushFront(SeqList* ps, SLDataType x)
{
	SeqListInsert(ps, 0, x);//在下標為0的位置插入數據
}
//尾插
void SeqListPushBack(SeqList* ps, SLDataType x)
{
	SeqListInsert(ps, ps->size, x);//在下標為ps->size的位置插入數據
}

9. 刪除數據：

刪除數據，其實可以理解為：從某個位置開始，數據依次向前覆蓋，相應的size做出改變。這樣一來，該位置的數據就相當於刪除瞭。

10. 尾刪數據：

尾刪就更簡單瞭，直接將順序表的元素個數減一即可。把size減一，讓其遍歷不到最後一個數據，也就是刪除瞭。ps：其實，深入瞭解的話，操作系統層面上的刪除也是如此，你不能訪問瞭，對於OS來說就是刪除瞭~~

//尾刪
void SeqListPopBack(SeqList* ps)
{
	assert(ps);
	assert(ps->size > 0);//保證順序表不為空
	ps->size--;//順序表元素個數減一
}

11. 指定下標位置刪除數據：

要刪除指定下標位置的數據，我們隻需要從下標位置開始，其後的數據從前向後依次覆蓋即可。

//指定下標位置刪除
void SeqListErase(SeqList* ps, int pos)
{
	assert(ps);
	assert(ps->size > 0);//保證順序表不為空
	assert(pos >= 0 && pos < ps->size);
	int i = 0;
	for (i = pos; i < ps->size - 1; i++)//從pos下標位置開始，其後的數據從前往後依次向前覆蓋
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;//順序表元素個數減一
}

同理，頭刪和尾刪實際上也就是刪除下標為0的位置和下標為ps->size – 1的位置的數據，也就意味著我們可以統一使用該函數來實現頭刪和尾刪。

//頭刪
void SeqListPopFront(SeqList* ps)
{
	SeqListErase(ps, 0);//刪除下標為0的位置的數據
}
//尾刪
void SeqListPopBack(SeqList* ps)
{
	SeqListErase(ps, ps->size - 1);//刪除下標為ps->size - 1的位置的數據
}

12. 查找數據：

查找數據也相對簡單，直接遍歷一次順序表即可，若找到瞭目標數據，則停止遍歷，並返回該數據的下標，否則返回-1。

//查找元素，若有，返回下標，否則返回-1
int SeqListFind(SeqList* ps, SLDataType x)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)//遍歷順序表進行查找
	{
		if (ps->a[i] == x)
			return i;//找到該數據，返回下標
	}
	return -1;//未找到，返回-1
}

13. 修改數據：

修改數據，就直接對該位置的數據進行再次賦值即可。

//修改指定下標位置元素
void SeqListModify(SeqList* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);//檢查輸入下標的合法性
	ps->a[pos] = x;//修改數據
}

14. 源代碼：

1. SeqList.h:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
typedef int SLDatatype;
typedef struct SeqList
{
    SLDatatype *a; //存儲數據空間的指針
    int size;      //有效數據的個數
    int capacity;  //容量空間大小
} SeqList;
//順序表初始化聲明
void SeqListInit(SeqList *ps);
//順序表銷毀聲明
void SeqListDestory(SeqList *ps);
//檢查空間，如果滿瞭，進行空間增容
void CheckCapacity(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);
//順序表查找
SLDatatype SeqListFind(SeqList *ps, SLDatatype x);
//順序表在pos位置插入
void SeqListInsert(SeqList *ps, int pos, SLDatatype x);
//順序表刪除pos位置的值
void SeqListErase(SeqList *ps, int pos);

2. SeqList.cpp:

#include "SeqList.h"
void CheckCapacity(SeqList *ps)
{
    //空間不夠，需要增容
    if (ps->size == ps->capacity)
    {
        SLDatatype *tmp = (SLDatatype *)realloc(ps->a, sizeof(SLDatatype) * ps->capacity * 2);
        //如果空間不足，可能增容失敗
        if (ps->a == NULL)
        {
            printf("順序表已滿,無法插入\n");
            exit(-1);
        }
        ps->a = tmp;
        ps->capacity *= 2;
    }
}
//順序表初始化；需要傳址
void SeqListInit(SeqList *ps)
{
    ps->a = (SLDatatype *)malloc(sizeof(SLDatatype) * 4);
    //malloc失敗
    if (ps->a == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    memset(ps->a, 0, sizeof(SLDatatype) * 4);
    ps->size = 0;
    ps->capacity = 4;
}
//順序表銷毀；需要傳址
void SeqListDestory(SeqList *ps)
{
    free(ps->a);
    ps->a = NULL;
    ps->size = 0;
    ps->capacity = 0;
}
//順序表打印
void SeqListPrint(SeqList *ps)
{
    for (int i = 0; i < ps->size; ++i)
    {
        printf("%d ", ps->a[i]);
    }
    printf("\n");
}
//順序表尾插
void SeqListPushBack(SeqList *ps, SLDatatype x)
{
    assert(ps);
    CheckCapacity(ps);
    //空間夠瞭，直接把插入的數據放到a[size]位置處
    ps->a[ps->size] = x;
    ps->size++;
}
//順序表頭插
void SeqListPushFront(SeqList *ps, SLDatatype x)
{
    assert(ps);
    CheckCapacity(ps);
    //從最後一個數的位置開始一個一個往後移
    int end = ps->size - 1;
    while (end >= 0)
    {
        ps->a[end + 1] = ps->a[end];
        --end;
    }
    //x賦值給頭位置
    ps->a[0] = x;
    ps->size++;
}
//順序表尾刪
void SeqListPopBack(SeqList *ps)
{
    assert(ps);
    //若無此步驟size為0時再size--為-1
    assert(ps->size > 0);
    ps->size--;
}
//順序表頭刪
void SeqListPopFront(SeqList *ps)
{
    assert(ps);
    assert(ps->size > 0);
    int begin = 1;
    //從第二個數的位置開始往前移
    while (begin < ps->size)
    {
        ps->a[begin - 1] = ps->a[begin];
        ++begin;
    }
    ps->size--;
}
//順序表查找,可以查找一個數在不在數組裡，並返回其下標，配合其他接口使用
SLDatatype SeqListFind(SeqList *ps, SLDatatype x)
{
    assert(ps);
    for (int i = 0; i < ps->size; ++i)
    {
        if (ps->a[i] == x)
        {
            return i;
        }
    }
    return -1;
}
//順序表在pos位置插入
void SeqListInsert(SeqList *ps, int pos, SLDatatype x)
{
    assert(ps);
    assert(pos >= 0 && pos < ps->size);
    CheckCapacity(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(SeqList *ps, int pos)
{
    assert(ps);
    assert(pos >= 0 && pos < ps->size);
    while (pos < ps->size - 1)
    {
        ps->a[pos] = ps->a[pos + 1];
        ++pos;
    }
    ps->size--;
}

3. test.cpp:

#include "SeqList.h"
int main()
{
    SeqList Sl;
    //測試順序表初始化
    SeqListInit(&Sl);
    //測試順序表尾插
    SeqListPushBack(&Sl, 1);
    SeqListPushBack(&Sl, 2);
    SeqListPushBack(&Sl, 3);
    SeqListPushBack(&Sl, 4);
    SeqListPushBack(&Sl, 5);
    SeqListPrint(&Sl);
    //測試順序表頭插
    SeqListPushFront(&Sl, 0);
    SeqListPrint(&Sl);
    //測試順序表尾刪
    SeqListPopBack(&Sl);
    SeqListPopBack(&Sl);
    SeqListPrint(&Sl);
    //測試順序表頭刪
    SeqListPopFront(&Sl);
    SeqListPrint(&Sl);
    SeqListFind(&Sl, 1);
    SeqListPrint(&Sl);
    //測試順序表在pos位置插入
    SeqListInsert(&Sl, 1, 20);
    SeqListPrint(&Sl);
    //測試順序表刪除pos位置的值
    SeqListErase(&Sl, 0);
    SeqListPrint(&Sl);
    //測試順序表查找
    int pos = SeqListFind(&Sl, 3);
    if (pos != -1)
    {
        printf("找到瞭\n");
    }
    //查找配合刪除刪掉指定的數
    int pos1 = SeqListFind(&Sl, 2);
    if (pos1 != -1)
    {
        SeqListErase(&Sl, pos1);
    }
    SeqListPrint(&Sl);
    //順序表銷毀
    SeqListDestory(&Sl);
    return 0;
}

15. 測試：

在這裡插入圖片描述

總結

本篇文章就到這裡瞭，希望能給你帶來幫助，也希望您能夠多多關註WalkonNet的更多內容！

推薦閱讀：