動態順序表的C語言實作：

正文開始@Assassin

動態順序表的C語言實作：
- ==什么是順序表?==
- 1. 定義順序表結構體：
- 2. 初始化順序表：
- 3. 銷毀順序表：
- 4. 列印順序表：
- 5. 判斷容量+擴容：
- 6. 頭插資料：
- 7. 尾插資料：
- 8. 指定下標位置插入資料：
- 9. 洗掉資料：
- 10. 尾刪資料：
- 11. 指定下標位置洗掉資料：
- 12. 查找資料：
- 13. 修改資料：
- 14. 源代碼：
- - 1. SeqList.h:
  - 2. SeqList.cpp:
  - 3. test.cpp:
- 15. 測驗：
- see you next blog~~

什么是順序表?

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

簡言之，順序表是用一段物理地址連續的存盤單元依次存盤資料元素的線性結構，一般情況下采用陣列存盤，在陣列上完成資料的增刪查改，可以類比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. 測驗：

在這里插入圖片描述

see you next blog~~

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

標籤：其他

上一篇：拿來吧你！?考研面試?每天練—— Z 字形變換（StringBuilder的用法總結）

下一篇：睡夢中面試騰訊 pcg 移動端開發，一+二+三+hr面（已oc）

資料結構C語言實作動態順序表