【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#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; }
文章名称：【C语言数据结构】静态单链表
网页链接：http://scyanting.com/article/piiopi.html
