鏈表的替代品--Vector組件

概述

• 在之前的一篇文章中，作者寫(xiě)了一個(gè)事件組件-- 超精簡(jiǎn)的訂閱發(fā)布事件組件--SPEvent，這個(gè)組件是采用鏈表建立所有事件節(jié)點(diǎn)的關(guān)系的。
• 鏈表的優(yōu)缺點(diǎn)：

1. 優(yōu)點(diǎn)：①鏈表上的元素在空間存儲(chǔ)上內(nèi)存地址不連續(xù)；②在插入和刪除操作時(shí)，只需要修改被刪節(jié)點(diǎn)上一節(jié)點(diǎn)的鏈接地址，不需要移動(dòng)元素；
2. 缺點(diǎn)：①?zèng)]有解決連續(xù)存儲(chǔ)分配帶來(lái)的表長(zhǎng)難以確定的問(wèn)題；②失去了順序存儲(chǔ)結(jié)構(gòu)隨機(jī)存取的特性；③不能通過(guò)數(shù)學(xué)表達(dá)式計(jì)算被查找元素的內(nèi)存地址，每一次查找都是從頭節(jié)點(diǎn)開(kāi)始遍歷，直到找到為止。

• SPEvent實(shí)際不會(huì)存在刪改的動(dòng)作，顯然鏈表的優(yōu)點(diǎn)在這個(gè)組件中無(wú)法體現(xiàn)優(yōu)勢(shì)。而實(shí)際順利存儲(chǔ)更能滿足SPEvent的業(yè)務(wù)及能力，那么有什么方式能做到這個(gè)操作了？答案肯定是有的，有一個(gè)好組件(Vector)正好可以解決掉這個(gè)問(wèn)題。
• Vector組件--向量；這個(gè)名稱一點(diǎn)也不陌生，比如我們單片機(jī)開(kāi)發(fā)中常常聽(tīng)到中斷向量表，它是通過(guò)地址查找對(duì)應(yīng)中斷服務(wù)函數(shù)；而Vector組件也有點(diǎn)類似這個(gè)概念，它可以通過(guò)名稱、類型查找對(duì)象。
• Vector組件的優(yōu)勢(shì)可以應(yīng)用像SPEvent這類組件中，如：SPEvent就可以通過(guò)Event類型去查找事件節(jié)點(diǎn)。那么Vector是怎么實(shí)現(xiàn)的？？

Vector組件

Vector組件--它是類似于鏈表?yè)碛械哪芰?，是一種動(dòng)態(tài)數(shù)組存儲(chǔ)組件，Vector組件擁有的能力如下：

1. 提供了順序存儲(chǔ)的能力，并且能夠動(dòng)態(tài)增大順序存儲(chǔ)空間；
2. 提供了增加對(duì)象能力，查找對(duì)象能力。
3. 提供獲取順序存儲(chǔ)空間能力，獲取對(duì)象個(gè)數(shù)能力。
4. 采用KEY-VALUE的特性開(kāi)查找對(duì)象。

Vector接口說(shuō)明：

Vector實(shí)現(xiàn)：

• 數(shù)據(jù)結(jié)構(gòu)：每一個(gè)存儲(chǔ)列表都需要構(gòu)造一個(gè)Vector結(jié)構(gòu)體對(duì)象，用于存儲(chǔ)元素對(duì)象。

复制//vector.h
#defineGROW_STEP4

#defineINVALID_INDEX(-1)
typedefvoid*(*VECTOR_Key)(constvoid*);//應(yīng)用層提供KEY-VALUE獲取方法，泛類型
typedefint(*VECTOR_Compare)(constvoid*,constvoid*);//應(yīng)用層提供比較函數(shù)，泛類型

typedefstructSimpleVector{
int16_tmax;//vector所能存儲(chǔ)的最大數(shù)據(jù)記錄數(shù)目
int16_ttop;//vector當(dāng)前已經(jīng)存儲(chǔ)的數(shù)據(jù)的峰值數(shù)目
int16_tfree;//vector已經(jīng)被釋放的數(shù)據(jù)記錄數(shù)目
void**data;//vector存儲(chǔ)數(shù)據(jù)指針
VECTOR_Keykey;//將數(shù)據(jù)元素轉(zhuǎn)換為用于比較的鍵。方法由用戶提供
VECTOR_Comparecompare;//將用于比較鍵值。方法由用戶提供
}Vector;

• Vector列表對(duì)象構(gòu)造方法：其中max，top，free初始狀態(tài)都為0。

复制VectorVECTOR_Make(VECTOR_Keykey,VECTOR_Comparecompare)
{
Vectorvector={0,0,0,NULL,key,compare};
returnvector;
}

• Vector列表對(duì)象清除方法：將Vector列表對(duì)象的數(shù)據(jù)元素空間釋放，并將max，top，free清0。

复制voidVECTOR_Clear(Vector*vector)
{
if(vector==NULL){
return;
}
if(vector->data==NULL){
return;
}
free(vector->data);
vector->max=0;
vector->top=0;
vector->free=0;
vector->data=NULL;
}

• Vector列表對(duì)象增加元素方法：
  • 存儲(chǔ)方式：采用順序存儲(chǔ)方式
  • 存儲(chǔ)空間擴(kuò)展策略：通過(guò)GROW_STEP的來(lái)決定沒(méi)存儲(chǔ)多少個(gè)元素來(lái)動(dòng)態(tài)擴(kuò)展空間；描述：如GROW_STEP的值為4，每次申請(qǐng)4個(gè)空間進(jìn)行存儲(chǔ)，如果存儲(chǔ)元素個(gè)數(shù)小于4個(gè)，不會(huì)重新申請(qǐng)空間；如果元素個(gè)數(shù)個(gè)數(shù)超過(guò)4個(gè)，那么將重新申請(qǐng)4個(gè)空間。以此類推。優(yōu)點(diǎn)：減少每次增加元素都要重新申請(qǐng)空間，提高了效率。

复制int16_tVECTOR_Add(Vector*vector,void*element)
{
if(vector==NULL||element==NULL){
returnINVALID_INDEX;
}

if(vector->top>=vector->max){
int16_ti;
for(i=vector->top-(int16_t)1;i>=0;--i){
if(vector->data[i]==NULL){
vector->data[i]=element;
vector->free--;
returni;
}
}

if(vector->max+GROW_STEP0){
returnINVALID_INDEX;
}

void**data=(void**)malloc(sizeof(void*)*(vector->max+GROW_STEP));
if(data==NULL){
returnINVALID_INDEX;
}

if(vector->data!=NULL){
(void)memcpy(data,vector->data,sizeof(void*)*vector->max);
free(vector->data);
}
vector->data=data;
vector->max+=GROW_STEP;
}

vector->data[vector->top]=element;
returnvector->top++;
}

• Vector列表對(duì)象根據(jù)下標(biāo)過(guò)去對(duì)象方法：Vector可以直接通過(guò)順序表的策略，直接通過(guò)下標(biāo)獲取元素；相對(duì)于鏈表來(lái)說(shuō)，效率更加有優(yōu)勢(shì)。

复制void*VECTOR_At(Vector*vector,int16_tindex)
{
if(vector==NULL||vector->top<=?index?||?index?0){
returnNULL;
}

returnvector->data[index];
}

• Vector列表對(duì)象根據(jù)下標(biāo)替換對(duì)象方法：Vector可以直接通過(guò)順序表的策略，直接通過(guò)下標(biāo)修改元素；相對(duì)于鏈表來(lái)說(shuō)，效率更加有優(yōu)勢(shì)。

复制void*VECTOR_Swap(Vector*vector,int16_tindex,void*element)
{
if(vector==NULL||vector->top<=?index?||?index?0){
returnNULL;
}
if(element==NULL){
vector->free++;
}
void*oldElement=vector->data[index];
vector->data[index]=element;
returnoldElement;
}

• Vector列表對(duì)象根據(jù)元素查找對(duì)應(yīng)下標(biāo)方法：最終也是調(diào)用VECTOR_FindByKey方法。

复制int16_tVECTOR_Find(Vector*vector,constvoid*element)
{
if(vector==NULL||element==NULL){
returnINVALID_INDEX;
}
returnVECTOR_FindByKey(vector,(vector->key==NULL)?element:vector->key(element));
}

• Vector列表對(duì)象根據(jù)鍵查找對(duì)應(yīng)下標(biāo)方法：遍歷整個(gè)Vector列表，查詢對(duì)應(yīng)的key值，并返回對(duì)應(yīng)下邊。

复制int16_tVECTOR_FindByKey(Vector*vector,constvoid*key)
{
if(vector==NULL||key==NULL){
returnINVALID_INDEX;
}

int16_ti;
for(i=0;ivector->top;++i){
if(vector->data[i]==NULL){
continue;
}

void*first=(vector->key!=NULL)?vector->key(vector->data[i]):vector->data[i];
if(first==key){
returni;
}

if(vector->compare==NULL||first==NULL){
continue;
}

if(vector->compare(first,key)==0){
returni;
}
}
returnINVALID_INDEX;
}

• Vector列表對(duì)象中元素個(gè)數(shù)獲取方法：

复制int16_tVECTOR_Size(Vector*vector)
{
if(vector==NULL){
returnINVALID_INDEX;
}
returnvector->top;
}

• Vector列表對(duì)象中元素記錄數(shù)目獲取方法：

复制int16_tVECTOR_Num(Vector*vector)
{
if(vector==NULL){
returnINVALID_INDEX;
}
returnvector->top-vector->free;
}

Vector使用：

1. 定義一個(gè)元素結(jié)構(gòu)體（vector_test），包含兩個(gè)字段：name和data，其中name可以作為元素對(duì)象的唯一標(biāo)識(shí)。

2. 定義兩個(gè)vector_test變量，test1和test2。

3. 我們這個(gè)demo是采用name作為唯一標(biāo)識(shí)，需要頂一個(gè)函數(shù)用于獲取vector_test變量的name字段成員的值，作為VECTOR_Key指向函數(shù)。

4. 通過(guò)VECTOR_Make構(gòu)造一個(gè)vector對(duì)象。其中VECTOR_Key指向vector_name_get函數(shù)作為key獲取，VECTOR_Compare指向strcmp函數(shù)用于key（name字符串）的比較。

5. 通過(guò)VECTOR_Add向vector對(duì)象增加元素test1和test2。

6. 通過(guò)VECTOR_FindByKey從vector對(duì)象查找元素對(duì)象下標(biāo)。如：key為"rice"的元素對(duì)象下標(biāo)。

7. 通過(guò)VECTOR_FindByKey獲取的pos，調(diào)用VECTOR_At獲取元素對(duì)象。

8. 驗(yàn)證：根據(jù)獲取元素對(duì)象調(diào)用其成員，確定是否成功。

复制#include"vector.h"

Vectorvector;

typedefstruct{
char*name;
intdata;
}vector_test;

vector_testtest1={"rice",100};
vector_testtest2={"chen",100};

constchar*vector_name_get(vector_test*test)
{
returntest->name;
}

intmain(void)
{
vector=VECTOR_Make(vector_name_get,strcmp);

VECTOR_Add(&vector,&test1);
VECTOR_Add(&vector,&test2);

int16_tpos=VECTOR_FindByKey(&vector,"rice");

printf("pos:%drn",pos);

vector_test*temp=VECTOR_At(&vector,pos);

printf("name:%srn",temp->name);

returnRT_EOK;
}

• 結(jié)果：

歡迎關(guān)注微信公眾號(hào)『Rice嵌入式開(kāi)發(fā)技術(shù)分享』