靜态連結清單 StaticList

單連結清單的實作嚴重依賴指針，資料元素中必須包含一個額外的指針域，沒有指針的程式設計語言無法實作。

靜态連結清單的定義

順序表數組中的元素由兩個資料域組成：data和next。

data域用于存儲資料

next域用于存儲下一個元素在數組中的下标

如下圖所示：

靜态連結清單是在順序表的基礎上利用數組實作的單連結清單

代碼編寫

//靜态連結清單頭檔案 StaticList.h
#ifndef _STATICLIST_H_
#define _STATICLIST_H_

typedef void StaticList;
typedef void StaticListNode;
//此處定義void，目的是資料封裝。

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
           

#include <stdio.h>
#include <malloc.h>
#include "StaticList.h"

#define AVAILABLE -1 
//-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) // O(n)  建立靜态連結清單
{
    TStaticList* ret = NULL;
    int i = ;    
    if( capacity >=  )
    {
        ret = (TStaticList*)malloc(sizeof(TStaticList) + sizeof(TStaticListNode) * (capacity + ));
    } 
    if( ret != NULL )
    {
        ret->capacity = capacity;
        ret->header.data = ;
        ret->header.next = ;        
        for(i=; i<=capacity; i++)
        {
            ret->node[i].next = AVAILABLE;  //表明該位置可以使用
        }
    }    
    return ret;
}

void StaticList_Destroy(StaticList* list) // O(1) 銷毀靜态連結清單
{
    free(list);
}

void StaticList_Clear(StaticList* list) // O(n) 清空資料元素
{
    TStaticList* sList = (TStaticList*)list;//類型轉換
    int i = ;    
    if( sList != NULL )
    {
        sList->header.data = ;
        sList->header.next = ;        
        for(i=; i<=sList->capacity; i++)
        {
            sList->node[i].next = AVAILABLE;
        }
    }
}

int StaticList_Length(StaticList* list) // O(1) 擷取目前連結清單的長度
{
    TStaticList* sList = (TStaticList*)list;
    int ret = -;    
    if( sList != NULL )
    {
        ret = sList->header.data;
    }    
    return ret;
}

int StaticList_Capacity(StaticList* list) // O(1) 擷取連結清單的最大長度
{
    TStaticList* sList = (TStaticList*)list;
    int ret = -;   
    if( sList != NULL )
    {
        ret = sList->capacity;
    }   
    return ret;
}

int StaticList_Insert(StaticList* list, StaticListNode* node, int pos)  // O(n)
// 在連結清單的指定位置插入一個資料元素
{
    TStaticList* sList = (TStaticList*)list;
    int ret = (sList != NULL);
    int current = ;
    int index = ;
    int i = ;    
    ret = ret && (sList->header.data +  <= sList->capacity);//判斷位置是否合法
    ret = ret && (pos >=) && (node != NULL);   
    if( ret )
    {
        for(i=; i<=sList->capacity; i++)
        {
            if( sList->node[i].next == AVAILABLE )//找一個位置存放新插入的資料
            {
                index = i;
                break;
            }
        }        
        sList->node[index].data = (unsigned int)node;        
        sList->node[] = sList->header;//把表頭資料放入數組的0位置處        
        for(i=; (i<pos) && (sList->node[current].next != ); i++)
        {
            current = sList->node[current].next;
        }

        sList->node[index].next = sList->node[current].next;  //核心代碼
        sList->node[current].next = index;       
        sList->node[].data++;      
        sList->header = sList->node[];
    }    
    return ret;
}

StaticListNode* StaticList_Get(StaticList* list, int pos)  // O(n) 擷取某位置上的資料元素
{
    TStaticList* sList = (TStaticList*)list;
    StaticListNode* ret = NULL;
    int current = ;
    int object = ;
    int i = ;    
    if( (sList != NULL) && ( <= pos) && (pos < sList->header.data) )
    {
        sList->node[] = sList->header;       
        for(i=; 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) // O(n) 删除某個資料元素
{
    TStaticList* sList = (TStaticList*)list;
    StaticListNode* ret = NULL;
    int current = ;
    int object = ;
    int i = ;    
    if( (sList != NULL) && ( <= pos) && (pos < sList->header.data) )
    {
        sList->node[] = sList->header;        
        for(i=; i<pos; i++)
        {
            current = sList->node[current].next;
        }      
        object = sList->node[current].next;        
        sList->node[current].next = sList->node[object].next;//核心代碼        
        sList->node[].data--;       
        sList->header = sList->node[];        
        sList->node[object].next = AVAILABLE;        
        ret = (StaticListNode*)(sList->node[object].data);
    }    
    return ret;
}
           

為什麼靜态連結清單結構體中要在定義個header成員，而不直接使用node[0]?

在靜态連結清單中 我們把所有的空閑結點都用-1來标記當插入一個元素的時候 我們需要周遊查找空閑結點 你想想這樣是不是有點低效了。

是以一個想法就是把所有的空閑結點也連接配接成一個連結清單 那麼也就是說在同一段空間中 部分結點是靜态連結清單存儲了實際的資料元素 部分沒有用的空閑結點連接配接成空閑連結清單。

那麼你想想是不是我們需要兩個表頭來辨別兩個連結清單呢 是以我們把0元素空出來 當把0元素指派為靜态連結清單頭的時候 從0開始通路的就是靜态連結清單元素 當把0元素指派為空閑連結清單頭的時候 從0開始通路的就是空閑連結清單元素。

這樣子如果我們插一個新元素時 直接從空閑連結清單中拿一個空間出來 存儲新元素即可 這個方法從空間連結清單取空間的時間複雜度為O(1)。

小結

靜态連結清單其實是單連結清單的另一種實作方式

靜态連結清單的實作“媒介”不是指針而是數組

靜态連結清單主要用于不支援指針的程式設計語言中

靜态連結清單的實作是一種記憶體管理的簡易方法