資料結構再學習--數組實作連結清單

連結清單一般情況下都是用指針實作的，但是某些語言根本沒有提供指針操作，我們可以用數組模拟出來。如下，定義了一個結構體。包含了一個nextIdx表示在數組中下一個元素的位置，data表示存儲的資料。在把這個結構體組成的數組定義為一種資料結構，數組中第0位不存資料，它的nextIdx表示下一個新的節點的索引。數組中最後一個元素也不存内容，它的nextIdx存儲的是連結清單的頭結點在數組中的索引，data表示的是目前數組中有多少個元素。下面是實作的增删改查。

github代碼位址：https://github.com/xiaobai1993/XBDataStructNote

#include "XBStaticLink.h"

//------------索引從1 開始


//擷取一個備用節點的下标
int XBGetNewIdx (XBStaticLinkList list)
{
    int i = list[0].nextIdx;//擷取新元素的下标
    if (list[0].nextIdx<MAX_SIZE-1) {
        list[0].nextIdx = list[i].nextIdx;//更新備用節點的位置，是以必須保證list[i].next是沒有用過的
    }
    return i;
}

void initXBStaticList(XBStaticLinkList sList)
{
    int i=0;
    for ( i =0; i<MAX_SIZE-1; i++) {//sList[0]不存資料。sList[0].data 表示的是新元素插入的索引位置
        
        sList[i].nextIdx=i+1;
    }
    sList[MAX_SIZE-1].nextIdx=0;//最後一個設定為0表示第一個插入的元素位置是0，也可以設定為其他的，startIdx.
    sList[MAX_SIZE-1].data=0;//儲存目前的數目
    /**
     sList[MAX_SIZE-1].cur=startIdx;
     則sList[startIdx].data 用來存儲下一個要插入資料的節點，但是把首尾單獨操作比較友善。是以這樣設定
     此時sList[i].nextIdx = 0 和 尾部指針相同，是以可以表示資料為空
     */
}

int isXBLinkStaticEmpty(XBStaticLinkList sList)
{
    return sList[MAX_SIZE-1].data==0;//表示數組裡面的沒有資料
}

int addItemToXBStaticLinkList(XBStaticLinkList  sList,DATATYPE obj)
{
   int newIdx = XBGetNewIdx(sList);//擷取一個新的節點
   if (newIdx<MAX_SIZE-1) {//表示沒有滿，
        sList[newIdx].data=obj;//進行插入
        //更新末尾指針的位置
        sList[0].nextIdx=sList[newIdx].nextIdx;
        sList[MAX_SIZE-1].nextIdx= 1;//
        sList[MAX_SIZE-1].data++; //更新數目
        return SUCCESS;
    }
    return FAIL;
}

void clearXBStaticLinkList(XBStaticLinkList  sList)
{
    while (!isXBLinkStaticEmpty(sList)) {
        
        deleteItemInXBStaticLinkList(sList, sList[MAX_SIZE-1].data);
    }
}

int getItemFromXBStaticLinkListByIndex(XBStaticLinkList sList,int idx,DATATYPE * obj)
{
    if (!isXBLinkStaticEmpty(sList)) {
        
        int startIdx = sList[MAX_SIZE-1].nextIdx;;
        int i =1;
        while (i<=sList[MAX_SIZE-1].data) {
            
            if (i==idx ) {
                *obj = sList[startIdx].data;
                break;
            }
            startIdx = sList[startIdx].nextIdx;
            i++;
        }
        
    }
    return FAIL;
}

int findItemInXBStaticLinkList(XBStaticLinkList sList,DATATYPE obj)
{
    if (!isXBLinkStaticEmpty(sList)) {
        
        int startIdx = sList[MAX_SIZE-1].nextIdx;
        int endIdx = sList[0].nextIdx;
        int i =1;
        while (startIdx!=endIdx) {
            
            if (sList[startIdx].data==obj) {
                return i;
            }
            startIdx = sList[startIdx].nextIdx;
            i++;
        }
        return FAIL;
    }
    return FAIL;
}

int insertItemInXBStaticLinkList(XBStaticLinkList sList,int idx,DATATYPE obj)
{
    
    if (idx<1||idx>getLengthForXBStaticLinkList(sList)) {
        return FAIL;
    }
    if (sList[MAX_SIZE-1].nextIdx == 0) {//
        
        return FAIL;
    }
    int i = XBGetNewIdx(sList);//現在最後邊找一個節點
    if (i<MAX_SIZE-1) {
       sList[i].data = obj;
        //尋找節點的位置
        int k= 1;
        int tempNext = MAX_SIZE-1;
        while (tempNext!=sList[0].nextIdx&&k<idx) {
            
            tempNext = sList[tempNext].nextIdx;
            k++;
        }
        sList[i].nextIdx = sList[tempNext].nextIdx;//把目前節點的下一個節點的位置指派給新節點
        sList[tempNext].nextIdx = i;//更新新的位置的索引
        sList[MAX_SIZE-1].data++;//
        return SUCCESS;
    }
    return FAIL;
}

//釋放一個節點
void Free_SSL (XBStaticLinkList slist,int k)
{
    slist[k].nextIdx = slist[0].nextIdx;//保留最新元素的位置
    slist[0].nextIdx = k;//把将要删除的位置留給slist[0]，表示這個位置是以後有元素來了要占據這個位置
}
int deleteItemInXBStaticLinkList(XBStaticLinkList sList,int idx)
{
    int j,k=1;
    if (idx < 1 || idx> getLengthForXBStaticLinkList(sList)) {
        return FAIL;
    }
    int tempNext = MAX_SIZE-1;
    while (tempNext!=sList[0].nextIdx&&k<idx) {
        
        tempNext = sList[tempNext].nextIdx;
        k++;
    }
    j = sList[tempNext].nextIdx;//删除保留下一個元素
    sList[tempNext].nextIdx = sList[j].nextIdx;
    
    sList[MAX_SIZE-1].data--;//數目總數要減一
    Free_SSL(sList,j);
    return SUCCESS;
}

// 傳回裡面資料元素的個數
int getLengthForXBStaticLinkList(XBStaticLinkList sList)
{
    return sList[MAX_SIZE-1].data;
}

void printXBStaticLinkList(XBStaticLinkList sList)
{
    int startIdx = sList[MAX_SIZE-1].nextIdx;
    printf("資料：\n");
    int i = 1;
    while (i<=sList[MAX_SIZE-1].data) {
        printf("%d ",sList[startIdx].data);
        startIdx = sList[startIdx].nextIdx;
        i++;
    }
    putchar('\n');
}

int replaceXBStaticLinkList(XBStaticLinkList sList,int idx,DATATYPE obj)
{
    int startIdx = sList[MAX_SIZE-1].nextIdx;
    if (idx>sList[MAX_SIZE-1].data&&idx<1) {
        return FAIL;
    }
    int i =1;
    while (i<=sList[MAX_SIZE-1].data) {
        if (idx==i) {
            sList[startIdx].data = obj;
            return SUCCESS;
        }
        startIdx = sList[startIdx].nextIdx;
        i++;
    }
    return FAIL;
}
           

void testXBStaticList()
{
    
    XBStaticLinkList list;
    initXBStaticList(list);
    //插入元素
    printf("開始添加元素:\n");
    for (int i = 0; i<5; i++) {
       
        addItemToXBStaticLinkList(list, (DATATYPE)(10+i));
    }
    printXBStaticLinkList(list);
    
    printf("查找元素12所在的位置 %d \n",findItemInXBStaticLinkList(list,12));

    printf("在索引為1的位置插入元素100:\n");
    insertItemInXBStaticLinkList(list, 1, 100);
    insertItemInXBStaticLinkList(list, 1, 100);

    printXBStaticLinkList(list);
//    printf("線性表目前的長度： %d \n",get(arrayList));
    
    printf("删除索引為3的位置的元素:\n");
    deleteItemInXBStaticLinkList(list, 3);//(list, 3);
    
    printXBStaticLinkList(list);
    int x ;
    printf("擷取2号位置的元素的值:\n");
    getItemFromXBStaticLinkListByIndex(list, 2, &x);
    //get(arrayList, 2, &x);
    printf("%d \n",x);
    
    printf("替換3号位置的元素為89:\n");
    replaceXBStaticLinkList(list, 3, 89);//
    printXBStaticLinkList(list);
    
    clearXBStaticLinkList(list);
    printf("清空後:\n");
    printXBStaticLinkList(list);

}