【C語言數據結構】靜態單鏈表

StaticLinkLinst.h

#ifndef STATIC_LINKLIST_H
#define STATIC_LINKLIST_H

typedef void StaticLinkListNode;    //靜態單鏈表節點
typedef void StaticLinkList;        //靜態單鏈表

/*
 * 創建靜態單鏈表
 * @param capacity 靜態單鏈表的最大容量
 * @return 返回靜態單鏈表的指針
 */
StaticLinkList* StaticLinkList_Create(int capacity);

/*
 * 銷毀靜態單鏈表
 * @param list 靜態單鏈表的指針
 */
void StaticLinkList_Destroy(StaticLinkList *list);

/*
 * 清空靜態單鏈表
 * @param list 靜態單鏈表的指針
 */
void StaticLinkList_Clear(StaticLinkList *list);

/*
 * 向靜態單鏈表pos位置處插入元素
 * @param list 靜態單鏈表指針
 * @param node 元素指針
 * @param pos 插入的索引
 */
int StaticLinkList_Insert(StaticLinkList *list,StaticLinkListNode *node,int pos);

/*
 * 獲取靜態單鏈表中索引位置處的元素
 * @param list   靜態單鏈表指針
 * @param pos   靜態單鏈表索引值
 * @param return 元素指針
 */
StaticLinkListNode* StaticLinkList_Get(StaticLinkList *list,int pos);

/*
 * 刪除靜態單鏈表中索引位置處的值
 * @param list 靜態單鏈表的指針
 * @param pos   靜態單鏈表索引
 * @param return 非0表示刪除成功
 */
int StaticLinkList_Remove(StaticLinkList *list,int pos);

/*
 * 獲取靜態單鏈表當前已存儲元素的個數
 * @param list 靜態單鏈表的指針
 * @return 靜態單鏈表中已存儲元素的個數
 */
int StaticLinkList_Length(StaticLinkList *list);

/*
 * 獲取靜態單鏈表最大可存儲元素的個數
 * @param list 靜態單鏈表的指針
 * @return 靜態單鏈表最大可存儲元素的個數
 */
int StaticLinkList_Capacity(StaticLinkList *list);

#endif // STATICLINKLIST_H

StaticLinkList.c

#include "StaticLinkList.h"
#include "malloc.h"

#define NO_NODE  -1

typedef struct _StaticLinkListNode
{
    unsigned int data;  //數據域指針
    int next;           //下一個節點的數組下標
}TStaticLinkListNode;

typedef struct _StaticLinkList
{
    int length;
    int capacity;
    TStaticLinkListNode node[]; //用于存儲靜態鏈表的柔性數組
}TStaticLinkList;

/*
 * 創建靜態單鏈表
 * @param capacity 靜態單鏈表的最大容量
 * @return 返回靜態單鏈表的指針
 */
StaticLinkList* StaticLinkList_Create(int capacity)
{
    //由于柔性數組的0位置會被作為頭節點，所以實際上容量是capapcity + 1
    size_t size = sizeof(TStaticLinkList) + sizeof(TStaticLinkListNode) * (capacity + 1);
    TStaticLinkList *list = (TStaticLinkList *)malloc(size);

    if(list != 0)
    {
        int i;
        list->capacity = capacity;
        list->length = 0;
        list->node[0].next = 0;

        for(i = 1;i <= capacity;i++)
        {
            list->node[i].next = NO_NODE;
        }
    }

    return list;
}

/*
 * 銷毀靜態單鏈表
 * @param list 靜態單鏈表的指針
 */
void StaticLinkList_Destroy(StaticLinkList *list)
{
    free(list);
}

/*
 * 清空靜態單鏈表
 * @param list 靜態單鏈表的指針
 */
void StaticLinkList_Clear(StaticLinkList *list)
{
    if(list != 0)
    {
        TStaticLinkList *s_list = (TStaticLinkList *)list;
        s_list->length = 0;
    }
}

/*
 * 向靜態單鏈表pos位置處插入元素
 * @param list 靜態單鏈表指針
 * @param node 元素指針
 * @param pos 插入的索引
 * @param return 非0表示插入成功
 */
int StaticLinkList_Insert(StaticLinkList *list,StaticLinkListNode *node,int pos)
{
    TStaticLinkList *s_list = (TStaticLinkList *)list;
    //判斷鏈表和節點指針不為空，位置合法，增加后容量不會大于最大容量
    int ret = ( (s_list != 0) && (node != 0) && (pos >= 0) && \
                (pos <= s_list->length) && (s_list->length + 1 <= s_list->capacity + 1) );

    if(ret)
    {
        int index = -1;                    //待放入元素的數組下標
        int current = 0;                   //當前節點的數組下標
        int i = 0;
        //遍歷查找數組中的空余項
        for(i =1; i <= s_list->capacity;i++)
        {
            if(s_list->node[i].next == NO_NODE)
            {
                index = i;
                break;
            }
        }

        //移動到需要插入位置的前驅
        for(i = 0; i < pos ; i++)
        {
            current = s_list->node[current].next;
        }

        s_list->node[index].next = s_list->node[current].next;
        s_list->node[index].data = (unsigned int)node;
        s_list->node[current].next = index;
        s_list->length++;

    }

    return ret;
}

/*
 * 獲取靜態單鏈表中索引位置處的元素
 * @param list   靜態單鏈表指針
 * @param pos   靜態單鏈表索引值
 * @param return 元素指針
 */
StaticLinkListNode* StaticLinkList_Get(StaticLinkList *list,int pos)
{
    TStaticLinkListNode *s_node = 0;
    TStaticLinkList *s_list = (TStaticLinkList *)list;

    if( (list != 0) && (pos >=0) && (pos < s_list->length))
    {
        int current = 0;
        int index = -1;
        int i;
        //移動到需要查詢的位置
        for(i = 0; i < pos ; i++)
        {
            current = s_list->node[current].next;
        }

        //獲取元素的數組下標
        index = s_list->node[current].next;
        //將data中的類型強制轉換成StaticLinkListNode *，因為插入時保存的就是節點的指針
        s_node = (StaticLinkListNode *)s_list->node[index].data;
    }

    return s_node;
}

/*
 * 刪除靜態單鏈表中索引位置處的值
 * @param list 靜態單鏈表的指針
 * @param pos   靜態單鏈表索引
 * @param return 非0表示刪除成功
 */
int StaticLinkList_Remove(StaticLinkList *list,int pos)
{
    TStaticLinkList *s_list = (TStaticLinkList *)list;
    int ret = ( (s_list != 0) && (pos >= 0) && (pos < s_list->length));

    if(ret)
    {
        int index = -1;
        int current = 0;
        int i = 0;

        for(i = 0; i < pos;i++)
        {
            current = s_list->node[current].next;
        }

        //被刪除元素的數組下標
        index = s_list->node[current].next;
        //將被刪元素的后繼下標賦值給除被刪除元素前驅的后繼下標
        s_list->node[current].next = s_list->node[index].next;
        //設置被刪除元素的后繼下標為NO_NODE
        s_list->node[index].next = NO_NODE;
        s_list->length--;

    }


    return ret;
}

/*
 * 獲取靜態單鏈表當前已存儲元素的個數
 * @param list 靜態單鏈表的指針
 * @return 靜態單鏈表中已存儲元素的個數
 */
int StaticLinkList_Length(StaticLinkList *list)
{
    int ret = -1;
    if(list != 0)
    {
        TStaticLinkList *s_list = (TStaticLinkList *)list;
        ret = s_list->length;
    }

    return ret;
}

/*
 * 獲取靜態單鏈表最大可存儲元素的個數
 * @param list 靜態單鏈表的指針
 * @return 靜態單鏈表最大可存儲元素的個數
 */
int StaticLinkList_Capacity(StaticLinkList *list)
{
    int ret = -1;

    if(list != 0)
    {
        TStaticLinkList *s_list = (TStaticLinkList *)list;
        ret = s_list->capacity;
    }

    return ret;
}

測試代碼

#include <stdio.h>
#include "StaticLinkList.h"

int main(void)
{
    int i,*j;
    int a[5];
    StaticLinkList *list = StaticLinkList_Create(5);

   for(i = 0;i < 5;i++)
   {
       a[i] = i;
   }



   for(i = 0; i < 5;i++)
   {
        StaticLinkList_Insert(list,&(a[i]),0);
   }

   StaticLinkList_Remove(list,0);



   for(i = 0; i < StaticLinkList_Length(list);i++)
   {
      j = StaticLinkList_Get(list,i);
      printf("%d\n",*j);
   }



   return 0;
}