C語(yǔ)言實(shí)現(xiàn)動(dòng)態(tài)順序表詳解
什么是順序表?
順序表是在計(jì)算機(jī)內(nèi)存中以數(shù)組的形式保存的線性表，線性表的順序存儲(chǔ)是指用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的各個(gè)元素，使得線性表中在邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素存儲(chǔ)在相鄰的物理存儲(chǔ)單元中，即通過數(shù)據(jù)元素物理存儲(chǔ)的相鄰關(guān)系來(lái)反映數(shù)據(jù)元素之間邏輯上的相鄰關(guān)系，采用順序存儲(chǔ)結(jié)構(gòu)的線性表通常稱為順序表。順序表是將表中的結(jié)點(diǎn)依次存放在計(jì)算機(jī)內(nèi)存中一組地址連續(xù)的存儲(chǔ)單元中。
簡(jiǎn)言之，順序表是用一段物理地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲(chǔ)。在數(shù)組上完成數(shù)據(jù)的增刪查改。可以類比vector，簡(jiǎn)單理解為可以動(dòng)態(tài)增長(zhǎng)的數(shù)組~~
順序表一般可以分為：
1.靜態(tài)順序表(直接定義數(shù)組)：存儲(chǔ)數(shù)據(jù)的空間是固定的；
導(dǎo)致的問題：開小了不夠用，開大了浪費(fèi)空間，現(xiàn)實(shí)中不實(shí)用
2.動(dòng)態(tài)順序表(用指針接收malloc動(dòng)態(tài)開辟)：存儲(chǔ)數(shù)據(jù)的空間是可以動(dòng)態(tài)增長(zhǎng)的，可以更好的適應(yīng)于現(xiàn)實(shí)中的使用
1. 定義順序表結(jié)構(gòu)體：
首先，我們要?jiǎng)?chuàng)建一個(gè)順序表類型，該順序表類型包括了順序表的起始位置、記錄順序表內(nèi)已有元素個(gè)數(shù)的計(jì)數(shù)器(size)，以及記錄當(dāng)前順序表的容量的變量(capacity)。
typedef int SLDataType;//定義一個(gè)類型，以便更好的適應(yīng)每一種數(shù)據(jù)的存儲(chǔ)，這里以存放整型數(shù)據(jù)為例
typedef struct SeqList
{
SLDataType* a;//聲明了一個(gè)指向順序表的指針
int size;//記錄當(dāng)前順序表內(nèi)元素個(gè)數(shù)
int capacity;//記錄當(dāng)前順序表的最大容量
}SeqList;//C語(yǔ)言中直接使用Seqlist類型
2. 初始化順序表：
我們需要一個(gè)初始化函數(shù)，對(duì)順序表進(jìn)行初始化。這里多說兩句自己的一些理解：有些小伙伴會(huì)對(duì)結(jié)構(gòu)體直接賦值為0來(lái)進(jìn)行初始化，這種操作雖然編譯器不給error，但也會(huì)報(bào)warning，我們應(yīng)該注意這一點(diǎn)，因?yàn)楸旧韘truct中的指針類型也不能簡(jiǎn)單的以0來(lái)初始化，實(shí)在不想用接口的話，那我建議你用NULL來(lái)初始化指針~~當(dāng)然我們要有意識(shí)地去寫工程化的代碼，每個(gè)獨(dú)立的功能習(xí)慣地去用函數(shù)封裝起來(lái)，我們調(diào)用接口實(shí)現(xiàn)功能。
//初始化順序表
void SeqListInit(SeqList* ps)
{
assert(ps);//斷言
ps->a = NULL;//剛開始時(shí)順序表為空，順序表指針為NULL
ps->size = 0;//起始時(shí)元素個(gè)數(shù)為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. 銷毀順序表：
因?yàn)轫樞虮硭玫膬?nèi)存空間是動(dòng)態(tài)開辟在堆區(qū)的，所以我們?cè)?mark>使用完后需要及時(shí)對(duì)其進(jìn)行釋放，避免造成內(nèi)存泄漏。 一般這個(gè)操作放在return之前調(diào)用。
當(dāng)然，如果想在下次運(yùn)行前記住當(dāng)前的一些增刪查改，若需要對(duì)數(shù)據(jù)進(jìn)行保存，可以使用文件操作函數(shù)將數(shù)據(jù)保存到一個(gè)文件中，下次使用順序表的時(shí)候先讀取文件數(shù)據(jù)即可。
//銷毀順序表
void SeqListDestory(SeqList* ps)
{
assert(ps);//斷言
free(ps->a);//釋放順序表指針指向的空間
ps->a = NULL;//及時(shí)置空
ps->size = 0;//元素個(gè)數(shù)置0
ps->capacity = 0;//容量置0
}
4. 打印順序表：
打印函數(shù)沒啥好說的，直接遍歷一遍size個(gè)數(shù)組中的元素即可。
//打印順序表
void SeqListPrint(SeqList* ps)
{
assert(ps);//斷言
int i = 0;
//循環(huán)打印順序表指針指向的數(shù)據(jù)
for (i = 0; i < ps->size; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
5. 判斷容量+擴(kuò)容：
我們應(yīng)該意識(shí)到，每次需要增加數(shù)據(jù)的時(shí)候，首先都應(yīng)該先檢查順序表內(nèi)元素個(gè)數(shù)是否已達(dá)順序表容量上限。若已達(dá)上限，那么我們就需要先對(duì)順序表進(jìn)行擴(kuò)容，然后才能增加數(shù)據(jù)。擴(kuò)容就要使用到realloc函數(shù)。
//檢查順序表容量是否已滿，若已滿，則增容
void SeqCheckCapacity(SeqList* ps)
{
if (ps->size == ps->capacity)//判斷已滿，需要增容
{
//判斷順序表容量是否為0，若為0，則先開辟用于存放4個(gè)元素的空間大小，若不為0，則擴(kuò)容為原來(lái)容量的兩倍
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);
}
//最好用同一個(gè)指針維護(hù)較為穩(wěn)妥，所以我們把newArr賦值給ps
ps->a = newArr;//開辟成功，將順序表指針更新
ps->capacity = newcapacity;//容量更新
}
}
注意： 若傳入realloc的指針為空指針(NULL)，則realloc函數(shù)的作用相當(dāng)于malloc函數(shù)。
6. 頭插數(shù)據(jù)：
要想在順序表的表頭插入數(shù)據(jù)，那么就需要先將順序表原有的數(shù)據(jù)從后往前依次向后挪動(dòng)一位，最后再將數(shù)據(jù)插入表頭。注意一定要依次從后面移動(dòng)數(shù)據(jù)，否則會(huì)發(fā)生覆蓋。
//頭插
void SeqListPushFront(SeqList* ps, SLDataType x)
{
assert(ps);
SeqCheckCapacity(ps);//檢查容量
int i = 0;
for (i = ps->size; i > 0; i--)//將數(shù)據(jù)從后往前依次向后挪
{
ps->a[i] = ps->a[i - 1];
}
ps->a[0] = x;
ps->size++;//順序表元素個(gè)數(shù)加一
}
注意： 挪動(dòng)數(shù)據(jù)的時(shí)候應(yīng)從后向前依次挪動(dòng)，若從前向后挪動(dòng)，會(huì)導(dǎo)致后一個(gè)數(shù)據(jù)被覆蓋。
7. 尾插數(shù)據(jù)：
尾插相對(duì)于頭插就比較簡(jiǎn)單了，直接在表尾的size插入數(shù)據(jù)即可。記得size也要相應(yīng)地++
//尾插
void SeqListPushBack(SeqList* ps, SLDataType x)
{
assert(ps);
SeqCheckCapacity(ps);//檢查容量
ps->a[ps->size] = x;
ps->size++;//順序表元素個(gè)數(shù)加一
}
8. 指定下標(biāo)位置插入數(shù)據(jù)：
要做到在指定下標(biāo)位置插入數(shù)據(jù)，首先我們需要得到一個(gè)下標(biāo)位置，然后從該下標(biāo)位置開始（包括該位置），其后的數(shù)據(jù)從后往前依次向后挪動(dòng)一位，最后將數(shù)據(jù)插入到該下標(biāo)位置。
//指定下標(biāo)位置插入
void SeqListInsert(SeqList* ps, int pos, SLDataType x)
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);//檢查輸入下標(biāo)的合法性
SeqCheckCapacity(ps);//檢查容量
int i = 0;
for (i = ps->size; i > pos; i--)//從pos下標(biāo)位置開始，其后的數(shù)據(jù)從后往前依次向后挪
{
ps->a[i] = ps->a[i - 1];
}
ps->a[pos] = x;
ps->size++;//順序表元素個(gè)數(shù)加一
}
我們可以發(fā)現(xiàn)，頭插和尾插實(shí)際上就是在下標(biāo)為0的位置和下標(biāo)為ps->size的位置插入數(shù)據(jù)，也就意味著我們可以統(tǒng)一使用該函數(shù)來(lái)實(shí)現(xiàn)頭插和尾插。
相當(dāng)于實(shí)現(xiàn)了代碼復(fù)用，一定程度上也起到了便于管理的效果。
//頭插
void SeqListPushFront(SeqList* ps, SLDataType x)
{
SeqListInsert(ps, 0, x);//在下標(biāo)為0的位置插入數(shù)據(jù)
}
//尾插
void SeqListPushBack(SeqList* ps, SLDataType x)
{
SeqListInsert(ps, ps->size, x);//在下標(biāo)為ps->size的位置插入數(shù)據(jù)
}
9. 刪除數(shù)據(jù)：
刪除數(shù)據(jù)，其實(shí)可以理解為：從某個(gè)位置開始，數(shù)據(jù)依次向前覆蓋，相應(yīng)的size做出改變。這樣一來(lái)，該位置的數(shù)據(jù)就相當(dāng)于刪除了。
10. 尾刪數(shù)據(jù)：
尾刪就更簡(jiǎn)單了，直接將順序表的元素個(gè)數(shù)減一即可。把size減一，讓其遍歷不到最后一個(gè)數(shù)據(jù)，也就是刪除了。ps：其實(shí)，深入了解的話，操作系統(tǒng)層面上的刪除也是如此，你不能訪問了，對(duì)于OS來(lái)說就是刪除了~~
//尾刪
void SeqListPopBack(SeqList* ps)
{
assert(ps);
assert(ps->size > 0);//保證順序表不為空
ps->size--;//順序表元素個(gè)數(shù)減一
}
11. 指定下標(biāo)位置刪除數(shù)據(jù)：
要?jiǎng)h除指定下標(biāo)位置的數(shù)據(jù)，我們只需要從下標(biāo)位置開始，其后的數(shù)據(jù)從前向后依次覆蓋即可。
//指定下標(biāo)位置刪除
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下標(biāo)位置開始，其后的數(shù)據(jù)從前往后依次向前覆蓋
{
ps->a[i] = ps->a[i + 1];
}
ps->size--;//順序表元素個(gè)數(shù)減一
}
同理，頭刪和尾刪實(shí)際上也就是刪除下標(biāo)為0的位置和下標(biāo)為ps->size - 1的位置的數(shù)據(jù)，也就意味著我們可以統(tǒng)一使用該函數(shù)來(lái)實(shí)現(xiàn)頭刪和尾刪。
//頭刪
void SeqListPopFront(SeqList* ps)
{
SeqListErase(ps, 0);//刪除下標(biāo)為0的位置的數(shù)據(jù)
}
//尾刪
void SeqListPopBack(SeqList* ps)
{
SeqListErase(ps, ps->size - 1);//刪除下標(biāo)為ps->size - 1的位置的數(shù)據(jù)
}
12. 查找數(shù)據(jù)：
查找數(shù)據(jù)也相對(duì)簡(jiǎn)單，直接遍歷一次順序表即可，若找到了目標(biāo)數(shù)據(jù)，則停止遍歷，并返回該數(shù)據(jù)的下標(biāo)，否則返回-1。
//查找元素，若有，返回下標(biāo)，否則返回-1
int SeqListFind(SeqList* ps, SLDataType x)
{
assert(ps);
int i = 0;
for (i = 0; i < ps->size; i++)//遍歷順序表進(jìn)行查找
{
if (ps->a[i] == x)
return i;//找到該數(shù)據(jù)，返回下標(biāo)
}
return -1;//未找到，返回-1
}
13. 修改數(shù)據(jù)：
修改數(shù)據(jù)，就直接對(duì)該位置的數(shù)據(jù)進(jìn)行再次賦值即可。
//修改指定下標(biāo)位置元素
void SeqListModify(SeqList* ps, int pos, SLDataType x)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);//檢查輸入下標(biāo)的合法性
ps->a[pos] = x;//修改數(shù)據(jù)
}
14. 源代碼：
1. SeqList.h:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
typedef int SLDatatype;
typedef struct SeqList
{
SLDatatype *a; //存儲(chǔ)數(shù)據(jù)空間的指針
int size; //有效數(shù)據(jù)的個(gè)數(shù)
int capacity; //容量空間大小
} SeqList;
//順序表初始化聲明
void SeqListInit(SeqList *ps);
//順序表銷毀聲明
void SeqListDestory(SeqList *ps);
//檢查空間，如果滿了，進(jìn)行空間增容
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("順序表已滿,無(wú)法插入\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);
//空間夠了，直接把插入的數(shù)據(jù)放到a[size]位置處
ps->a[ps->size] = x;
ps->size++;
}
//順序表頭插
void SeqListPushFront(SeqList *ps, SLDatatype x)
{
assert(ps);
CheckCapacity(ps);
//從最后一個(gè)數(shù)的位置開始一個(gè)一個(gè)往后移
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);
//若無(wú)此步驟size為0時(shí)再size--為-1
assert(ps->size > 0);
ps->size--;
}
//順序表頭刪
void SeqListPopFront(SeqList *ps)
{
assert(ps);
assert(ps->size > 0);
int begin = 1;
//從第二個(gè)數(shù)的位置開始往前移
while (begin < ps->size)
{
ps->a[begin - 1] = ps->a[begin];
++begin;
}
ps->size--;
}
//順序表查找,可以查找一個(gè)數(shù)在不在數(shù)組里，并返回其下標(biāo)，配合其他接口使用
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;
//測(cè)試順序表初始化
SeqListInit(&Sl);
//測(cè)試順序表尾插
SeqListPushBack(&Sl, 1);
SeqListPushBack(&Sl, 2);
SeqListPushBack(&Sl, 3);
SeqListPushBack(&Sl, 4);
SeqListPushBack(&Sl, 5);
SeqListPrint(&Sl);
//測(cè)試順序表頭插
SeqListPushFront(&Sl, 0);
SeqListPrint(&Sl);
//測(cè)試順序表尾刪
SeqListPopBack(&Sl);
SeqListPopBack(&Sl);
SeqListPrint(&Sl);
//測(cè)試順序表頭刪
SeqListPopFront(&Sl);
SeqListPrint(&Sl);
SeqListFind(&Sl, 1);
SeqListPrint(&Sl);
//測(cè)試順序表在pos位置插入
SeqListInsert(&Sl, 1, 20);
SeqListPrint(&Sl);
//測(cè)試順序表刪除pos位置的值
SeqListErase(&Sl, 0);
SeqListPrint(&Sl);
//測(cè)試順序表查找
int pos = SeqListFind(&Sl, 3);
if (pos != -1)
{
printf("找到了\n");
}
//查找配合刪除刪掉指定的數(shù)
int pos1 = SeqListFind(&Sl, 2);
if (pos1 != -1)
{
SeqListErase(&Sl, pos1);
}
SeqListPrint(&Sl);
//順序表銷毀
SeqListDestory(&Sl);
return 0;
}
15. 測(cè)試：
總結(jié)
本篇文章就到這里了，希望能給你帶來(lái)幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容！
- C語(yǔ)言 數(shù)據(jù)結(jié)構(gòu)之?dāng)?shù)組模擬實(shí)現(xiàn)順序表流程詳解
- C語(yǔ)言實(shí)現(xiàn)順序表的基本操作指南(注釋很詳細(xì))
- 新手向超詳細(xì)的C語(yǔ)言實(shí)現(xiàn)動(dòng)態(tài)順序表
- C語(yǔ)言實(shí)現(xiàn)的順序表功能完整實(shí)例
- C語(yǔ)言使用順序表實(shí)現(xiàn)電話本功能
- C語(yǔ)言順序表的實(shí)現(xiàn)代碼
- C語(yǔ)言實(shí)現(xiàn)動(dòng)態(tài)順序表的實(shí)現(xiàn)代碼
- C語(yǔ)言?超詳細(xì)順序表的模擬實(shí)現(xiàn)實(shí)例建議收藏
相關(guān)文章
這篇文章主要介紹了MFC LoadImage用法案例詳解,本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08
求32位機(jī)器上unsigned int的最大值及int的最大值的解決方法
本篇文章是對(duì)求32位機(jī)器上unsigned int的最大值及int的最大值的解決方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
C++中的vector使用詳解及重要部分底層實(shí)現(xiàn)
本篇文章會(huì)對(duì)vector的語(yǔ)法使用進(jìn)行詳解，同時(shí)，還會(huì)對(duì)重要難點(diǎn)部分的底層實(shí)現(xiàn)進(jìn)行講解，其中有vector的迭代器失效和深拷貝問題，希望本篇文章的內(nèi)容會(huì)對(duì)你有所幫助2023-07-07
這篇文章主要介紹了C++中static修飾符的詳解及其作用介紹，本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-09-09
這篇文章主要介紹了C++中指定的異常和未經(jīng)處理的異常,介紹了有關(guān)noexcept和terminate的作用,并結(jié)合了C++11標(biāo)準(zhǔn)的新特性,需要的朋友可以參考下2016-01-01
詳解C++中的vector容器及用迭代器訪問vector的方法
使用迭代器iterator可以更方便地解引用和訪問成員,當(dāng)然也包括vector中的元素,本文就來(lái)詳解C++中的vector容器及用迭代器訪問vector的方法,需要的朋友可以參考下2016-05-05
C++實(shí)現(xiàn)當(dāng)前時(shí)間動(dòng)態(tài)顯示的方法
這篇文章主要介紹了C++實(shí)現(xiàn)當(dāng)前時(shí)間動(dòng)態(tài)顯示的方法,涉及C++時(shí)間操作及Sleep方法的使用,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-07-07
C++基于reactor的服務(wù)器百萬(wàn)并發(fā)實(shí)現(xiàn)與講解
這篇文章主要介紹了C++基于reactor的服務(wù)器百萬(wàn)并發(fā)實(shí)現(xiàn)與講解，本文通過實(shí)例圖文相結(jié)合給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-07-07
vs2019+win10配置boost庫(kù)的詳細(xì)教程
這篇文章主要介紹了vs2019+win10配置boost庫(kù),本文通過圖文實(shí)例相結(jié)合給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-06-06
C++雙向鏈表實(shí)現(xiàn)簡(jiǎn)單通訊錄
這篇文章主要為大家詳細(xì)介紹了C++雙向鏈表實(shí)現(xiàn)簡(jiǎn)單通訊錄，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-05-05