【C语言数据结构】静态单链表

StaticLinkLinst.h

#ifndef STATIC_LINKLIST_H#define STATIC_LINKLIST_Htypedef 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  -1typedef 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 #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;}