單鏈表的相對(duì)劣勢(shì)
- 單鏈表的實(shí)現(xiàn)嚴(yán)重依賴指針
- 數(shù)據(jù)元素中必須包含一個(gè)額外的指針域
- 沒(méi)有指針的程序設(shè)計(jì)語(yǔ)言無(wú)法實(shí)現(xiàn)
靜態(tài)鏈表的定義
- 順序表數(shù)組中的元素由兩個(gè)數(shù)據(jù)域組成：data和next
- data域用于存儲(chǔ)數(shù)據(jù)
- next域用于存儲(chǔ)下一個(gè)元素在數(shù)組中的下標(biāo)
靜態(tài)鏈表是在順序表的基礎(chǔ)上利用數(shù)組實(shí)現(xiàn)的單鏈表
創(chuàng)建靜態(tài)鏈表
獲取第pos個(gè)元素操作
- 判斷線性表是否合法
- 判斷位置是否合法
- 由表頭開始通過(guò)next域移動(dòng)pos次后，當(dāng)前元素的next域即要獲取的元素在數(shù)組中的下標(biāo)
插入元素到位置pos操作
- 判斷線性表是否合法
- 判斷插入位置是否合法
- 在數(shù)組中查找空閑位置index
- 由表頭開始通過(guò)next域移動(dòng)pos次后盔沫，當(dāng)前元素的next域?yàn)橐迦氲奈恢?/li>
- 將新元素插入
- 線性表長(zhǎng)度加一
刪除第pos個(gè)元素操作
- 判斷線性表是否合法
- 判斷插入位置是否合法
- 獲取第pos個(gè)元素
- 將第pos個(gè)元素從鏈表中刪除
- 線性表長(zhǎng)度減一
小結(jié)
- 靜態(tài)鏈表其實(shí)是單鏈表的另外一種實(shí)現(xiàn)方式
- 靜態(tài)鏈表的實(shí)現(xiàn)“媒介”不是指針而是數(shù)組
- 靜態(tài)鏈表主要用于不支持指針的程序設(shè)計(jì)語(yǔ)言中
- 靜態(tài)鏈表的實(shí)現(xiàn)是一種內(nèi)存管理的簡(jiǎn)易方法
代碼
StaticList.h
#ifndef _STATICLIST_H_
#define _STATICLIST_H_
typedef void StaticList;
typedef void StaticListNode;
StaticList* StaticList_Create(int capacity);
void StaticList_Destroy(StaticList* list);
void StaticList_Clear(StaticList* list);
int StaticList_Length(StaticList* list);
int StaticList_Capacity(StaticList* list);
int StaticList_Insert(StaticList* list, StaticListNode* node, int pos);
StaticListNode* StaticList_Get(StaticList* list, int pos);
StaticListNode* StaticList_Delete(StaticList* list, int pos);
#endif
StaticList.c
#include <stdio.h>
#include <malloc.h>
#include "StaticList.h"
#define AVAILABLE -1
typedef struct _tag_StaticListNode
{
unsigned int data;
int next;
} TStaticListNode;
typedef struct _tag_StaticList
{
int capacity;
TStaticListNode header;
TStaticListNode node[];
} TStaticList;
StaticList* StaticList_Create(int capacity)
{
TStaticList* ret = NULL;
int i = 0;
if( capacity >= 0 )
{
ret = (TStaticList*)malloc(sizeof(TStaticList) + sizeof(TStaticListNode) * (capacity + 1));
}
if( ret != NULL )
{
ret->capacity = capacity;
ret->header.data = 0;
ret->header.next = 0;
for(i=1; i<=capacity; i++)
{
ret->node[i].next = AVAILABLE;
}
}
return ret;
}
void StaticList_Destroy(StaticList* list)
{
free(list);
}
void StaticList_Clear(StaticList* list)
{
TStaticList* sList = (TStaticList*)list;
int i = 0;
if( sList != NULL )
{
sList->header.data = 0;
sList->header.next = 0;
for(i=1; i<=sList->capacity; i++)
{
sList->node[i].next = AVAILABLE;
}
}
}
int StaticList_Length(StaticList* list)
{
TStaticList* sList = (TStaticList*)list;
int ret = -1;
if( sList != NULL )
{
ret = sList->header.data;
}
return ret;
}
int StaticList_Capacity(StaticList* list)
{
TStaticList* sList = (TStaticList*)list;
int ret = -1;
if( sList != NULL )
{
ret = sList->capacity;
}
return ret;
}
int StaticList_Insert(StaticList* list, StaticListNode* node, int pos)
{
TStaticList* sList = (TStaticList*)list;
int ret = (sList != NULL);
int current = 0;
int index = 0;
int i = 0;
ret = ret && (sList->header.data + 1 <= sList->capacity);
ret = ret && (pos >=0) && (node != NULL);
if( ret )
{
for(i=1; i<=sList->capacity; i++)
{
if( sList->node[i].next == AVAILABLE )
{
index = i;
break;
}
}
sList->node[index].data = (unsigned int)node;
sList->node[0] = sList->header;
for(i=0; (i<pos) && (sList->node[current].next != 0); i++)
{
current = sList->node[current].next;
}
sList->node[index].next = sList->node[current].next;
sList->node[current].next = index;
sList->node[0].data++;
sList->header = sList->node[0];
}
return ret;
}
StaticListNode* StaticList_Get(StaticList* list, int pos)
{
TStaticList* sList = (TStaticList*)list;
StaticListNode* ret = NULL;
int current = 0;
int object = 0;
int i = 0;
if( (sList != NULL) && (0 <= pos) && (pos < sList->header.data) )
{
sList->node[0] = sList->header;
for(i=0; i<pos; i++)
{
current = sList->node[current].next;
}
object = sList->node[current].next;
ret = (StaticListNode*)(sList->node[object].data);
}
return ret;
}
StaticListNode* StaticList_Delete(StaticList* list, int pos)
{
TStaticList* sList = (TStaticList*)list;
StaticListNode* ret = NULL;
int current = 0;
int object = 0;
int i = 0;
if( (sList != NULL) && (0 <= pos) && (pos < sList->header.data) )
{
sList->node[0] = sList->header;
for(i=0; i<pos; i++)
{
current = sList->node[current].next;
}
object = sList->node[current].next;
sList->node[current].next = sList->node[object].next;
sList->node[0].data--;
sList->header = sList->node[0];
sList->node[object].next = AVAILABLE;
ret = (StaticListNode*)(sList->node[object].data);
}
return ret;
}
main.c
#include <stdio.h>
#include <stdlib.h>
#include "StaticList.h"
int main(int argc, char *argv[])
{
StaticList* list = StaticList_Create(10);
int index = 0;
int i = 0;
int j = 1;
int k = 2;
int x = 3;
int y = 4;
int z = 5;
StaticList_Insert(list, &i, 0);
StaticList_Insert(list, &j, 0);
StaticList_Insert(list, &k, 0);
for(index=0; index<StaticList_Length(list); index++)
{
int* p = (int*)StaticList_Get(list, index);
printf("%d\n", *p);
}
printf("\n");
while( StaticList_Length(list) > 0 )
{
int* p = (int*)StaticList_Delete(list, 0);
printf("%d\n", *p);
}
printf("\n");
StaticList_Insert(list, &x, 0);
StaticList_Insert(list, &y, 0);
StaticList_Insert(list, &z, 0);
printf("Capacity: %d Length: %d\n", StaticList_Capacity(list), StaticList_Length(list));
for(index=0; index<StaticList_Length(list); index++)
{
int* p = (int*)StaticList_Get(list, index);
printf("%d\n", *p);
}
StaticList_Destroy(list);
return 0;
}
