《 静态链表的创建、插入、删除、销毁代码实现》
序言：表的学习也没学习多久，对于我而言大部分都是研究别人的代码，取其精华取其糟粕。链表在学习计算机课程的时候，数据结构是一门基础课程，基础不代表不重要，相反是特别重要，就好比你想学习骑自行车，但是你连走路都不会，怎么会骑自行车呢？哈哈，学习数据结构的基本思路是:
顺序表，链表，静态链表、双链表，循环量表等 .
要求：c语言要懂一点。
接下来我们就一起分析下面一段代码吧！
#include<stdlib.h>
#include <stdio.h> //头函数就好比一个仓库,存储我们需要的基础函数,如printf 等
#include<malloc.h>
#define AVAILABLE -1
typedef void StaticList;
typedef void StaticListNode;
/**************头函数定义其实也可以不需要只是为了实现结构化***************/
//下面通过英语提示大家都应该知道函数的实现功能了吧
StaticList* StaticList_Create(int capacity); //创建
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); //插入数据
StaticListNode* StaticList_Get(StaticList* list, int pos); //获取元素
StaticListNode* StaticList_Delete(StaticList* list, int pos); //删除元素
//对于这个结构体的定义相信大家都应该很熟悉了吧，关键在这里typedef的应用
typedef struct _tag_StaticListNode
{
unsigned int data; //存放和数据的地方
int next; //指向下一个数组坐标的值
} TStaticListNode; //结构体变量相当于别名
typedef struct _tag_StaticList //定义一个数据域结构体
{
int capacity;
TStaticListNode header; //数组头
TStaticListNode node[]; //相当于指针地址
} TStaticList;
/************************创建链表*****************************/
StaticList* StaticList_Create(int capacity) // O(n)
{
TStaticList* ret = NULL;
int i = 0;
if( capacity >= 0 )
{ /*申请内存大小capacity加一是因为头数据要算一个*/
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++) /*用来找出数组空闲的数据位置*/
{
ret->node[i].next = AVAILABLE;
}
}
return ret;
}
/*销毁链表内存申请相当于调用了一个free函数*/
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;
}
}
}
/*获取数组元素个数*/
int StaticList_Length(StaticList* list) // O(1)
{
TStaticList* sList = (TStaticList*)list;
int ret = -1;
if( sList != NULL )
{
ret = sList->header.data;
}
return ret;
}
/****获取内存容量***/
int StaticList_Capacity(StaticList* list) // O(1)
{
TStaticList* sList = (TStaticList*)list;
int ret = -1;
if( sList != NULL )
{
ret = sList->capacity;
}
return ret;
}
/****插入数据元素***/
int StaticList_Insert(StaticList* list, StaticListNode* node, int pos) // O(n)
{ /***参数1 链表头指针 参数2 具体数据地址 参数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;
}
/****下面两行代码是说明具体插入位置的算法实现***/
sList->node[index].next = sList->node[current].next;
sList->node[current].next = index;
sList->node[0].data++; /****之后要data加以***/
sList->header = sList->node[0]; /***节点游标要回到初始位置****/
}
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); /***赋值结构体求出该位置的数据****/
}
return ret;
}
/****删除元素具体实现和插入相仿***/
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;
/****主要区别还是上面两行代码进行插入实现***/
sList->node[0].data--;
sList->header = sList->node[0];
sList->node[object].next = AVAILABLE;
ret = (StaticListNode*)(sList->node[object].data);
}
return ret;
}
/***主函数具体实现创建链表，插入、删除、销毁、获取元素、等操作****/
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); /****刚开始对于这个赋值没有理解后来明白了***/
StaticList_Insert(list, &z, 6); /****&i 也就是插入的元素的地址，这个地址是指向下一个元素的地址***/
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); /**删除数据
**/
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); /**销毁链表，不用的时候必须要进行操作不然会有内
泄露*****/
return 0;
}
好啦结束了，希望对于你会有一点帮助，我也是自己理解的难免会有都错误，请谅解 ！
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
