程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 數據結構:靜態鏈表

數據結構:靜態鏈表

編輯:C++入門知識

首先我們讓數組的元素都是由兩個數據域組成,data和cur。也就是說,數組的每一個下標都對應一個data和一個cur。

數據域data用來存放數據元素,也就是通常我們要處理的數據;而游標cur相當於單鏈表中的next指針,

存放該元素的後繼在數組中的下標。我們把這種用數組描述的鏈表叫做靜態鏈表。

數組的第一個元素,即下標為0的元素的cur就存放備用鏈表的第一個結點的下標;而數組的最後一個元素的cur

則存放第一個有數值的元素的下標,相當於單鏈表的頭節點作用,當整個鏈表為空時,則為0,表示無指向。

 

\
示例代碼:(改編自《大話數據結構》)


 
  #include<iostream>
using namespace std;

#define MAXSIZE 100

typedef int ElemType;
/* 線性表的靜態鏈表存儲結構 */
typedef struct Node
{
    ElemType data;
    int cur; //為0時表示無指向
} StaticLinkList[MAXSIZE];

/* 將一維數組array中各分量鏈成一個備用鏈表,array[0].cur為頭指針,"0"表示空指針 */
bool InitList(StaticLinkList array)
{
    cout << "InitList..." << endl;
    for (int i = 0; i < MAXSIZE - 1; i++)
    {
        array[i].cur = i + 1;
    }

    array[MAXSIZE - 1].cur = 0;/* 目前靜態鏈表為空,最後一個元素的cur為0 */

    return true;
}
/* 若備用空間鏈表非空,則返回分配的結點下標,否則返回0 */
int Malloc_SLL(StaticLinkList array)
{
    int k = array[0].cur;
    if (k)
        array[0].cur = array[k].cur;/* 下一個分量用來做備用 */

    return k;
}
/*  將下標為pos的空閒結點回收到備用鏈表 */
void Free_SLL(StaticLinkList array, int pos)
{
    array[pos].cur = array[0].cur; /* 把第一個元素的cur值賦給要刪除的分量cur */
    array[0].cur = pos; /* 把要刪除的分量下標賦值給第一個元素的cur */
}

int ListLength(StaticLinkList array)
{
    int i = array[MAXSIZE - 1].cur;
    int j = 0;
    while(i)
    {
        i = array[i].cur;
        ++j;
    }
    return j;
}
/*  在array中第pos個元素之前插入新的數據元素Elem  */
bool ListInsert(StaticLinkList array, int pos, ElemType Elem)
{
    cout << "Insert List from pos: " << pos << " Item " << Elem << endl;
    if (pos < 1 || pos > ListLength(array) + 1)
        return false;

    int k = MAXSIZE - 1;
    int i = Malloc_SLL(array); /* 獲得空閒分量的下標 */

    if (i)
    {
        array[i].data = Elem;

        for (int l = 1; l <= pos - 1; l++)
            k = array[k].cur;

        array[i].cur = array[k].cur;/* 把第pos個元素之前的cur賦值給新元素的cur */
        array[k].cur = i;/* 把新元素的下標賦值給第pos個元素之前元素的cur */
        return true;
    }

    return false;
}
/*  刪除在array中第pos個數據元素   */
bool ListDelete(StaticLinkList array, int pos)
{
    cout << "Delete List from pos: " << pos << endl;
    if (pos < 1 || pos > ListLength(array))
        return false;

    int k = MAXSIZE - 1;

    for (int l = 1; l <= pos - 1; l++)
        k = array[k].cur;

    int j = array[k].cur;
    array[k].cur = array[pos].cur;

    Free_SLL(array, j);

    return true;
}

bool ListTraverse(StaticLinkList array)
{
    cout << "List Traverse : " << endl;
    int k = MAXSIZE - 1;
    while (array[k].cur != 0)
    {
        k = array[k].cur;
        cout << array[k].data << ' ';
    }

    cout << endl;
    return true;
}


int main(void)
{
    StaticLinkList SSL;
    InitList(SSL);
    for (int i = 1; i < 5; i++)
        ListInsert(SSL, i, i);
    ListTraverse(SSL);

    ListDelete(SSL, 3);
    ListTraverse(SSL);
    cout << "List Length : " << ListLength(SSL) << endl;

    return 0;
}

輸出為:

 

 \

 

靜態鏈表在插入和刪除操作時不需要移動元素,只需要修改游標,從而改進了在順序存儲結構中插入和刪除操作需要移動

大量元素的缺點;但並沒有解決連續分配存儲帶來的表長難以確定的問題;並且失去了順序存儲結構隨機存取的特性。

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved