C语言实现个循环静态链表
C语言实现个循环静态链表
平时用循环缓冲区接收数据习惯了，突然有个需求不让用了。因为在数据缓冲的时间段内可能会删除数据，而且还要实现按照接收的顺序存储，相信小伙伴们也都遇到过同样的需求，下面来个简单的循环链表模型，希望能帮上有需要的。废话不多说，直接上代码。
/*
功能：建立一个静态循环链表
限制：数组长度不大于(0xffffU-1)且第0个位置不能存储有效数据,用于存放有效数据个数
*/
/*头文件*/
#include<stdio.h>
#include<stdint.h>
/*宏定义*/
#define N_SIZE 7U
#defineUSED_SEAT 1U
#defineLAST_DATA 0xffffU
/*结点结构体*/
typedef structnode
{
int flag;
int next;
int data;
}node_t;
/*声明内部函数*/
static intFindNodeSeat(node_t *arry, int seat);
static intFindNodeData(node_t *arry, int key);
static intMallocNode(node_t *arry);
/*找到下标为src的结点,返回找到的前向下标值，如果没有找到，返回0*/
static intFindNodeSeat(node_t *arry, int seat)
{
int i = 0;
int ret = 0;/*查找结果*/
int temp = 0;/*记录前向结点的下标*/
i = arry[0].next;/*从第1个有效结点开始找*/
if(arry[0].flag == USED_SEAT)/*已经被使用的结点*/
{
while(i != 0)/*有后继结点*/
{
if(i == seat)
{
/*找到了要查找的结点位置*/
ret = 1;
break;
}
else
{
temp = i;/*记录前向结点的下标*/
i = arry[i].next;
if(i == LAST_DATA)
{
/*到链表的最后一个结点了*/
ret = 2;
break;
}
else
{
ret = 0;
}
}
}
}
else
{
printf("空链表,查找结点失败\n");
}
if(ret == 1)
{
/*找到要查找的结点*/
i = temp;
}
else
{
i = 0;
printf("没有找到要查找的结点\n");
}
return i;
}
/*找到数据内容为key的结点,返回找到的前向下标值，如果没有找到，返回0*/
static intFindNodeData(node_t *arry, int key)
{
int i = 0;
int ret = 0;/*查找的结果*/
int temp = 0;/*记录前向结点的下标*/
i = arry[0].next;/*从第1个有效结点开始找*/
if(arry[0].flag == USED_SEAT)/*已经被使用的结点*/
{
while(i != 0)/*有后继结点*/
{
if(arry[i].data == key)
{
/*找到了要查找的结点位置*/
ret = 1;
break;
}
else
{
temp = i;/*记录前向结点的下标*/
i = arry[i].next;
if(i == LAST_DATA)
{
/*到链表的最后一个结点了*/
printf("到链表的最后一个结点了\n", i);
temp = i;
ret = 2;
break;
}
else
{
ret = 0;
}
}
}
}
else
{
printf("空链表,查找结点失败\n");
}
if(ret == 1)
{
/*找到要查找的结点*/
i = temp;
}
else
{
i = 0;
printf("没有找到要查找的结点\n");
}
return i;
}
/*初始化缓冲区*/
voidInitList(node_t *arry)
{
int i=0;
for(i=0; i<N_SIZE; i++)
{
arry[i].flag = 0;/*0：空，1：占用*/
arry[i].next = 0;/*0：没有后继结点,0xffff:表示最后一个有效结点*/
arry[i].data = 0;/*数据内容*/
}
}
/*分配一个空结点,如果找到空结点返回结点值，如果没有找到空结点，返回缓冲区的大小*/
static intMallocNode(node_t *arry)
{
int i = 0;
for(i=0; i<N_SIZE; i++)
{
if(arry[i].flag == 0)
{
/*找到一个可用结点*/
if(i == 0)
{
/*i=0表示尾空表*/
arry[0].flag = USED_SEAT;/*0：空，1：占用*/
arry[0].next = 1U;/*0：没有后继结点*/
arry[0].data +=1U;/*arry[0].data用于存放有效数据个数，有效数据个数加1*/
i = 1;/*第0个位置保留*/
}
else
{
/*不动作*/
}
break;/*找到一个可用结点就退出*/
}
else
{
/*不动作*/
}
}
return i;
}
/*在尾部插入一个结点*/
intInsertTail(node_t *arry, int key)
{
int i = 0;
int j = 0;
i = MallocNode(arry);
if(i == 1)
{
arry[i].flag = USED_SEAT;/*0：空，1：占用*/
arry[i].next = LAST_DATA;/*LAST_DATA：最后一个有效结点*/
arry[i].data = key;/*数据内容*/
}
else if(i == N_SIZE)
{
/*缓冲区已满，需要调头*/
i = arry[0].next;
printf("已满 head = %d\n", i);
/*找到上一个被占用且游标为LAST_DATA的结点，将找到的结点的next指向i*/
for(j=1; j<N_SIZE; j++)
{
if(arry[j].next == LAST_DATA)
{
/*找到了最后一个结点*/
arry[j].next = i;
arry[i].flag =USED_SEAT;/*0：空，1：占用*/
arry[i].data = key;/*数据内容*/
arry[0].next =arry[i].next;/*修改第一个元素的位置*/
arry[i].next =LAST_DATA;/*LAST_DATA：最后一个有效结点*/
break;
}
else
{
/*不动作*/
}
}
}
else if(i < N_SIZE)
{
/*找到上一个被占用且游标为LAST_DATA的结点，将找到的结点的next指向i*/
for(j=1; j<N_SIZE; j++)
{
if(arry[j].next == LAST_DATA)
{
break;
}
}
if(j < N_SIZE)
{
/*找到了上一个结点*/
arry[j].next = i;
arry[i].flag = USED_SEAT;/*0：空，1：占用*/
arry[i].next = LAST_DATA;/*LAST_DATA：最后一个有效结点*/
arry[i].data = key;/*数据内容*/
arry[0].data += 1U;/*有效数据个数加1*/
}
else
{
/*error：没找到上一个结点*/
}
}
else
{
/*error：没找到上一个结点*/
}
return i;
}
/*删除下标为seat的结点*/
intDeletSeatNode(node_t *arry, int seat)
{
int i = 0;
int temp = 0;/*记录前向结点的下标*/
temp = FindNodeSeat(arry, seat);
i = arry[temp].next;
if(i != 0)
{
/*找到要删除的元素*/
/*将其前向结点的next改为该结点的next值,删除该结点，总数减1*/
arry[temp].next = arry[i].next;
arry[i].flag = 0;
arry[i].next = 0;
arry[i].data = 0;
/*如果只剩下1个有效值了，初始化缓冲区*/
if(arry[0].data == 1)
{
arry[0].flag = 0;
arry[0].next = 0;
arry[0].data = 0;
}
else if(arry[0].data > 0)
{
arry[0].data -= 1;
}
else
{
/*不动作*/
}
}
else
{
printf("没有找到要删除的结点\n");
}
return i;
}
/*删除数据内容为key的结点*/
intDeletDataNode(node_t *arry, int key)
{
int i = 0;
int temp = 0;/*记录前向结点的下标*/
temp = FindNodeData(arry, key);
i = arry[temp].next;
if(i != 0)
{
/*找到要删除的元素*/
/*将其前向结点的next改为该结点的next值,删除该结点，总数减1*/
arry[temp].next = arry[i].next;
arry[i].flag = 0;
arry[i].next = 0;
arry[i].data = 0;
/*如果只剩下1个有效值了，初始化缓冲区*/
if(arry[0].data == 1)
{
arry[0].flag = 0;
arry[0].next = 0;
arry[0].data = 0;
}
else if(arry[0].data > 0)
{
arry[0].data -= 1;
}
else
{
/*不动作*/
}
}
else
{
printf("没有找到要删除的结点\n");
}
return i;
}
/*找到数据内容为src的结点,并将数据内容放到des中,返回找到的下标值，如果没有找到，返回0*/
intFindDataNode(node_t *arry, int src, int *des)
{
int i = 0;
int temp = 0;/*记录前向结点的下标*/
temp = FindNodeData(arry, src);
i = arry[temp].next;
if(i != 0)
{
/*找到要查找的元素*/
printf("找到要查找的元素 i = %d\n", i);
*des = arry[i].data;
}
else
{
i = 0;/*没有找到返回0*/
printf("没有找到要查找的结点\n");
}
return i;
}
/*找到数据内容为src的结点,并用des数据内容替换该元素的值,返回找到的下标值，如果没有找到，返回0*/
intPlaceNode(node_t *arry, int src, int des)
{
int i = 0;
int temp = 0;/*记录前向结点的下标*/
temp = FindNodeData(arry, src);
i = arry[temp].next;
if(i != 0)
{
/*找到要查找的元素*/
printf("找到要替换的元素 i = %d\n", i);
arry[i].data = des;
}
else
{
i = 0;/*没有找到返回0*/
printf("没有找到要替换的结点\n");
}
return i;
}
/*遍历链表*/
voidListScan(node_t *arry)
{
int i = 0;
if(arry[0].flag == USED_SEAT)
{
while(arry[i].next != 0)/*有后继结点*/
{
if(arry[i].next == LAST_DATA)
{
/*到链表的最后一个结点了*/
printf("(%d, %d, %d,%d)", i, arry[i].flag, arry[i].data, arry[i].next);
break;
}
else
{
printf("(%d, %d, %d,%d)", i, arry[i].flag, arry[i].data, arry[i].next);
i = arry[i].next;
}
}
}
else
{
printf("空链表\n");
}
printf("\n");
}
/*主函数*/
void main(void)
{
int i = 0;
int n_data = 5;
int test = 0;
int find = 0;
node_t ListBuf[N_SIZE];/*数据缓冲区*/
/*初始化缓冲区*/
printf("初始化缓冲区\n");
InitList(ListBuf);
ListScan(ListBuf);
/*插入数据*/
printf("插入数据\n");
for(i=0; i<(N_SIZE-1); i++)
{
InsertTail(ListBuf, i);
ListScan(ListBuf);
}
/*按照数据内容删除数据*/
printf("按照数据内容删除数据\n");
for(i=1; i<N_SIZE; i++)
{
DeletDataNode(ListBuf, (i-1));
ListScan(ListBuf);
}
/*插入数据*/
printf("插入数据\n");
for(i=0; i<(N_SIZE-1); i++)
{
InsertTail(ListBuf, i);
ListScan(ListBuf);
}
/*按照下标内容删除数据*/
printf("按照下标删除数据\n");
for(i=1; i<N_SIZE; i++)
{
DeletSeatNode(ListBuf,i);
ListScan(ListBuf);
}
/*删除一个不存在的结点*/
printf("删除一个不存在的结点\n");
DeletSeatNode(ListBuf,0);
ListScan(ListBuf);
/*插入数据*/
printf("插入数据\n");
for(i=0; i<(N_SIZE-1); i++)
{
InsertTail(ListBuf, i);
ListScan(ListBuf);
}
/*循环覆盖老数据*/
printf("循环覆盖老数据\n");
for(i=0; i<(N_SIZE-1); i++)
{
InsertTail(ListBuf, (i+N_SIZE));
ListScan(ListBuf);
}
/*查找数据*/
find = 9;
printf("查找数据%d\n", find);
FindDataNode(ListBuf, find, &test);
printf("test = %d\n", test);
/*替换数据*/
find = 10;
printf("替换数据%d\n", find);
test = 123;
PlaceNode(ListBuf, find, test);
ListScan(ListBuf);
/*删除指定位置数据*/
find = 3;
printf("删除指定位置数据 %d\n", find);
DeletSeatNode(ListBuf, find);
ListScan(ListBuf);
/*删除指定内容数据*/
find = 11;
printf("删除指定内容数据 %d\n", find);
DeletDataNode(ListBuf, find);
ListScan(ListBuf);
}
花了大半天的时间基本功能和框架有了，纯属娱乐，大神勿喷。