靜態(tài)鏈表詳解

 
            《 靜態(tài)鏈表的創(chuàng)建、插入、刪除、銷毀代碼實(shí)現(xiàn)》
 
序言：表的學(xué)習(xí)也沒學(xué)習(xí)多久，對(duì)于我而言大部分都是研究別人的代碼，取其精華取其糟粕。鏈表在學(xué)習(xí)計(jì)算機(jī)課程的時(shí)候，數(shù)據(jù)結(jié)構(gòu)是一門基礎(chǔ)課程，基礎(chǔ)不代表不重要，相反是特別重要，就好比你想學(xué)習(xí)騎自行車，但是你連走路都不會(huì)，怎么會(huì)騎自行車呢？哈哈，學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的基本思路是:
順序表，鏈表，靜態(tài)鏈表、雙鏈表，循環(huán)量表等 .
要求：c語言要懂一點(diǎn)。
接下來我們就一起分析下面一段代碼吧！
#include<stdlib.h>
#include  <stdio.h> //頭函數(shù)就好比一個(gè)倉庫,存儲(chǔ)我們需要的基礎(chǔ)函數(shù),如printf 等
#include<malloc.h>
#define AVAILABLE -1

typedef void StaticList;
typedef void StaticListNode;
 
/**************頭函數(shù)定義其實(shí)也可以不需要只是為了實(shí)現(xiàn)結(jié)構(gòu)化***************/
//下面通過英語提示大家都應(yīng)該知道函數(shù)的實(shí)現(xiàn)功能了吧
StaticList* StaticList_Create(int capacity);                        //創(chuàng)建
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);                //插入數(shù)據(jù) 
StaticListNode* StaticList_Get(StaticList* list, int pos);                                    //獲取元素 
StaticListNode* StaticList_Delete(StaticList* list, int pos);                                //刪除元素
 
//對(duì)于這個(gè)結(jié)構(gòu)體的定義相信大家都應(yīng)該很熟悉了吧，關(guān)鍵在這里typedef的應(yīng)用

typedef struct _tag_StaticListNode
{
    unsigned int data;                    //存放和數(shù)據(jù)的地方
    int next;                                    //指向下一個(gè)數(shù)組坐標(biāo)的值
} TStaticListNode;    //結(jié)構(gòu)體變量相當(dāng)于別名
 
 
 
typedef struct _tag_StaticList              //定義一個(gè)數(shù)據(jù)域結(jié)構(gòu)體
{
    int capacity;
    TStaticListNode header;            //數(shù)組頭
    TStaticListNode node[];            //相當(dāng)于指針地址
} TStaticList;
 
 
/************************創(chuàng)建鏈表*****************************/
StaticList* StaticList_Create(int capacity) // O(n)
{
    TStaticList* ret = NULL;
    int i = 0;
    
    if( capacity >= 0 )
   {                                                                /*申請內(nèi)存大小capacity加一是因?yàn)轭^數(shù)據(jù)要算一個(gè)*/     
   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++)                    /*用來找出數(shù)組空閑的數(shù)據(jù)位置*/
        {
            ret->node[i].next = AVAILABLE;
        }
    }
    
    return ret;
}
 
 
/*銷毀鏈表內(nèi)存申請相當(dāng)于調(diào)用了一個(gè)free函數(shù)*/
void StaticList_Destroy(StaticList* list) // O(1)
{
    free(list);
}
 
/*清除鏈表元素*/
void StaticList_Clear(StaticList* list) // O(n)
{
    TStaticList* sList = (TStaticList*)list;//ba void turn point 
    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;
        }
    }
}
 
/*獲取數(shù)組元素個(gè)數(shù)*/
int StaticList_Length(StaticList* list) // O(1)
{
    TStaticList* sList = (TStaticList*)list;
    int ret = -1;
    
    if( sList != NULL )
    {
        ret = sList->header.data;
    }
    
    return ret;
}
 /****獲取內(nèi)存容量***/
int StaticList_Capacity(StaticList* list) // O(1)
{
    TStaticList* sList = (TStaticList*)list;
    int ret = -1;
    
    if( sList != NULL )
    {
        ret = sList->capacity;
    }
    
    return ret;
}
 /****插入數(shù)據(jù)元素***/
int StaticList_Insert(StaticList* list, StaticListNode* node, int pos)  // O(n)
{                                                     /***參數(shù)1 鏈表頭指針 參數(shù)2 具體數(shù)據(jù)地址 參數(shù)3 位置****/
    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; (inode[current].next != 0); i++)
        {
            current = sList->node[current].next;
        }
         /****下面兩行代碼是說明具體插入位置的算法實(shí)現(xiàn)***/
        sList->node[index].next = sList->node[current].next;
        sList->node[current].next = index;
        
        sList->node[0].data++;                     /****之后要data加以***/        
        sList->header = sList->node[0];      /***節(jié)點(diǎn)游標(biāo)要回到初始位置****/
    }
    
    return ret;
}
 /****獲取元素值***/
 
StaticListNode* StaticList_Get(StaticList* list, int pos)  // O(n)
{
    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); /***賦值結(jié)構(gòu)體求出該位置的數(shù)據(jù)****/
    }
    
    return ret;
}
 /****刪除元素具體實(shí)現(xiàn)和插入相仿***/
StaticListNode* StaticList_Delete(StaticList* list, int pos) // O(n)
{
    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;
         /****主要區(qū)別還是上面兩行代碼進(jìn)行插入實(shí)現(xiàn)***/
 
        sList->node[0].data--;
        
        sList->header = sList->node[0];
        
        sList->node[object].next = AVAILABLE;
        
        ret = (StaticListNode*)(sList->node[object].data);
    }
    
    return ret;
}
 
 
 /***主函數(shù)具體實(shí)現(xiàn)創(chuàng)建鏈表，插入、刪除、銷毀、獲取元素、等操作****/
 
 
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, 1);
    StaticList_Insert(list, &j, 3);
    StaticList_Insert(list, &k, 2);
    StaticList_Insert(list, &x, 5);
    StaticList_Insert(list, &y, 4);    /****剛開始對(duì)于這個(gè)賦值沒有理解后來明白了***/
    StaticList_Insert(list, &z, 6);   /****&i 也就是插入的元素的地址，這個(gè)地址是指向下一個(gè)元素的地址***/      
    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); /**刪除數(shù)據(jù)
     **/        
        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); /**銷毀鏈表，不用的時(shí)候必須要進(jìn)行操作不然會(huì)有內(nèi)
















                    
泄露*****/    
 return 0;
}
 
好啦結(jié)束了，希望對(duì)于你會(huì)有一點(diǎn)幫助，我也是自己理解的難免會(huì)有都錯(cuò)誤，請諒解 ！