鏈表的替代品Vector組件介紹

概述

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

鏈表的優(yōu)缺點(diǎn)：

優(yōu)點(diǎn)：①鏈表上的元素在空間存儲(chǔ)上內(nèi)存地址不連續(xù)；②在插入和刪除操作時(shí)，只需要修改被刪節(jié)點(diǎn)上一節(jié)點(diǎn)的鏈接地址，不需要移動(dòng)元素；

缺點(diǎn)：①?zèng)]有解決連續(xù)存儲(chǔ)分配帶來的表長(zhǎng)難以確定的問題；②失去了順序存儲(chǔ)結(jié)構(gòu)隨機(jī)存取的特性；③不能通過數(shù)學(xué)表達(dá)式計(jì)算被查找元素的內(nèi)存地址，每一次查找都是從頭節(jié)點(diǎn)開始遍歷，直到找到為止。

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è)問題。

Vector組件--向量；這個(gè)名稱一點(diǎn)也不陌生，比如我們單片機(jī)開發(fā)中常常聽到中斷向量表，它是通過地址查找對(duì)應(yīng)中斷服務(wù)函數(shù)；而Vector組件也有點(diǎn)類似這個(gè)概念，它可以通過名稱、類型查找對(duì)象。

Vector組件的優(yōu)勢(shì)可以應(yīng)用像SPEvent這類組件中，如：SPEvent就可以通過Event類型去查找事件節(jié)點(diǎn)。那么Vector是怎么實(shí)現(xiàn)的？？

Vector組件

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

提供了順序存儲(chǔ)的能力，并且能夠動(dòng)態(tài)增大順序存儲(chǔ)空間；

提供了增加對(duì)象能力，查找對(duì)象能力。

提供獲取順序存儲(chǔ)空間能力，獲取對(duì)象個(gè)數(shù)能力。

采用KEY-VALUE的特性開查找對(duì)象。

Vector接口說明：

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ò)展策略：通過GROW_STEP的來決定沒存儲(chǔ)多少個(gè)元素來動(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ù)超過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_STEPmax+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)過去對(duì)象方法：Vector可以直接通過順序表的策略，直接通過下標(biāo)獲取元素；相對(duì)于鏈表來說，效率更加有優(yōu)勢(shì)。

void*VECTOR_At(Vector*vector,int16_tindex)
{
if(vector==NULL||vector->top<=?index?||?index?data[index];
}

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

void*VECTOR_Swap(Vector*vector,int16_tindex,void*element)
{
if(vector==NULL||vector->top<=?index?||?index?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;itop;++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使用：

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

定義兩個(gè)vector_test變量，youyeetoo1和youyeetoo2。

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

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

通過VECTOR_Add向vector對(duì)象增加元素youyeetoo1和youyeetoo2。

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

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

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

#include"vector.h"

Vectoryouyeetoo_vector;

typedefstruct{
char*name;
intdata;
}vector_test;

vector_testyouyeetoo1={"rice",100};
vector_testyouyeetoo2={"youyeetoo",100};

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

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

VECTOR_Add(&youyeetoo_vector,&youyeetoo1);
VECTOR_Add(&youyeetoo_vector,&youyeetoo2);

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

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

vector_test*youyeetoo_temp=VECTOR_At(&youyeetoo_vector,pos);

printf("name:%s
",youyeetoo_temp->name);

returnRT_EOK;
}

結(jié)果：

審核編輯：劉清