图解环形链表——创建、循环赋值与删除
链表结构体
首先定义环形链表的节点的形式，即一个结构体，简单为例，该结构体内只有一个float数据，以及指向下一个节点的指针，如下：
//链表节点结构体
typedef struct stData
{
float data;
struct stData *pNext;
}stData;环形链表的使用需要定义3个指针：1个是环形链表的指针（分配后就是固定值），1个头指针和1个尾指针（在向链表写入新数据时这两个指针不不断的改变节点的指向）。
环形链表首先需要初始化，为其分配内存空间，初始化后，链表内的数据全部初始化为0，且头指针和尾指针都先与环形链表指向同一地址。
stData *pList = NULL; //环形链表指针
stData *pHead = NULL; //环形链表中的数据头指针
stData *pTail = NULL; //环形链表中的数据尾指针
init_list(&pList, LIST_LEN); //初始化一个长度为 LIST_LEN的环形链表
pHead = pList;
pTail = pList;环形链表初始化
环形链表的初始化过程如下：
//初始化链表 ---函数中分配内存，需要传入二级指针
void init_list(stData **pList, int len)
{
int i=0;
stData *pTmp1 = NULL; //临时指针1
stData *pTmp2 = NULL; //临时指针2
//先为环形链表分配一个节点的内存
*pList=(stData*)malloc(sizeof(stData));
(*pList)->data=0;
(*pList)->pNext=NULL;
//再为剩余的链表元素分配内存
pTmp1 = *pList; //临时指针1指向环形链表的头
for(i=0;i<len-1;i++)
{
//临时指针2用于逐个申请内存
pTmp2=(stData*)malloc(sizeof(stData));
pTmp2->data=0;
pTmp2->pNext=NULL;
//临时指针1的next指向刚分配内存的临时指针2
pTmp1->pNext=pTmp2;
//然后临时指针1再指向临时指针2
pTmp1=pTmp2;
//printf("init_list i---%d\r\n",i);
}
//整个链表长度都分配好内存后，临时指针1再指向链表头，这样就构成了一个环形链表
pTmp1->pNext = *pList;
}基本思路是：
-
首先分配第一个节点，这也是整个环形链表的地址，即pList的指向
-
然后使用两个临时指针，pTmp1用于连接各个节点（指定各节点的pNext指针指向下一个）,pTmp2用于不断分配下一个节点的内存
分配第1个节点
//先为环形链表分配一个节点的内存
*pList=(stData*)malloc(sizeof(stData));
(*pList)->data=0;
(*pList)->pNext=NULL;
pTmp1 = *pList; //临时指针1指向环形链表的头 第一个节点的内存先通过pList指针分配，然后临时指针pTmp1也先指向这个节点：
分配第2个节点
for(i=0;i<len-1;i++)
{
//临时指针2用于逐个申请内存
pTmp2=(stData*)malloc(sizeof(stData));
pTmp2->data=0;
pTmp2->pNext=NULL;
//临时指针1的next指向刚分配内存的临时指针2
pTmp1->pNext=pTmp2;
//然后临时指针1再指向临时指针2
pTmp1=pTmp2;
}-
pTmp2先分配一个节点内存
-
pTmp1使第1节点的pNext指向第2个节点
-
pTmp1再指向第2个节点，为下一次作准备
分配第3个节点
与分配第2个节点类似，后面的节点分配都是同样的循环操作：
分配最后1个节点
//整个链表长度都分配好内存后，临时指针1再指向链表头，这样就构成了一个环形链表
pTmp1->pNext = *pList;例子中环形链表的长度为5，因此分配第5个之后，会退出循环，然后：
-
将pTmp1的pNext指向pList，这样就构成了一个环形链表
-
链表初始化函数退出后，两个临时指针也会被自动释放
环形链表初始化完成
初始化完成后的效果如下，一个5个节点，构成了一个环形，且初始状态，头节点与尾节点均指向pList指向的节点：
查询环形链表中有效数据的长度
环形链表初始化后各节点的数据均为0，查询环形链表中有效数据的长度，用于指示在向链表写入数据时，头指针与尾指针是否需要移动，然后在合适的位置写入新的数据，以及用于在数据使用的是否，只有链表数据满了之后，才对整个环形链表中的数据进行使用。
//查询当前链表中数据的长度 -----初始时pHead = pTail = pList
static int check_list_isfull(stData *pHead,stData *pTail)
{
int cnt = 0;
stData *pTmp = NULL; //临时指针
if(pHead==NULL||pTail==NULL) return -1;
pTmp = pHead;//临时指针指向头指针
while(pTmp!=pTail && pTmp!=NULL)//计算的是pHead到pTail间的距离
{
cnt++;//开始存入第1个数据之后，pHead与pTail不会再次指向同一节点，所以cnt最大是(LIST_LEN-1)
pTmp=pTmp->pNext;
}
return cnt;
}基本思路是：首先使用一个临时指针指向头节点指向的节点，然后判断该节点是否是尾节点指向的节点。
链表刚初始时
环形链表刚初始化时，有效数据为0个：
写入1个数据后
写入1个数据后，尾指针向后移动一个节点，此时查询有效数据为1：
写入4个数据后
写入4个数据后，此时查询有效数据为4，之后若再写入1个数据，环形链表的有效数据就满了
环形链表写入数据
//添加数据到链表 ---函数中需要改变指针的指向，也要传入二级指针
int add_data2list(stData **pHead,stData **pTail, float val)
{
int ret = -1;
int cnt = 0;
stData *pTmp = NULL; //临时指针
if(pHead==NULL||pTail==NULL) return -1;
cnt = check_list_isfull(*pHead, *pTail);
//printf("......cnt:%d\r\n",cnt);
if((LIST_LEN-1) == cnt)//只剩一个可以存了 (或是pTail已经绕了一圈与pHead相邻了)
{
//则 pHead向后移动一个
*pHead = (*pHead)->pNext;
ret = 0;//表示环形链表存满了（虽然现在还剩一个位置，但本函数退出前会将这个位置填入数据）
}
else
{
ret = -1;//表示环形链表中的数据还未添满
}
//临时指针指向尾指针，并填入数据，即在环形链表的尾部更新了一个数据
pTmp=(*pTail);
pTmp->data=val;
*pTail=(*pTail)->pNext;//pTail向后移动一个
return ret;
}基本思路是：
-
通过check_list_isfull()函数检查当前链表中有效数据的个数
-
若有效数据的个数是(LIST_LEN-1)，则将头指针向后移动一个几点，且该函数最终返回0，表示此次添加数据后，链表数据为满的状态
-
若有效数据的个数少于(LIST_LEN-1)，即刚开始向链表中写入数据的阶段，则该函数最终返回-1，表示此次写入数据后链表未满
-
将临时指针pTmp指向尾节点pTail指向的节点，并将数据写入该节点
-
尾节点pTail指向下一个节点
-
下次写入数据时按照上面过程循环执行
写入第1个数据
写入第1个数据分3步：
-
pTmp指向尾节点pTail指向的节点
-
为该节点写入数据
-
pTail指向下一个节点
写入第2个数据
步骤与写入第1个数据类似：
写入第4个数据
步骤也与写入第1个数据类似：
写入第5个数据
第5个数据，也是环形链表种的最后1个数据。
注意此时环形链表数据已满，头指针pHead开始它的第1次向后移动：
-
check_list_isfull()判断为满，pHead指向下一个节点
-
临时指针pTmp指向pTail指向的节点
-
为该节点写入数据
-
pTail指向下一个节点
-
写入第6个数据
第6个数据，则需要覆盖写入到环形链表中的第1个数据。
其步骤实际与写入第5个数据类似，并且之后数据的写入，都与次步骤类似。
环形链表的一种应用
计算一串数据的滑动平均值
比如传感器采集到连续的数据，需要作一个滑动的滤波处理，可以将数据不断的写入该循环链表，当链表满了之后，开始计算以链表长度为滑动窗口的平均值，并不断输出。
//计算平均值
void calc_list_ave(stData *pHead, float *res)
{
stData *pTmp=NULL;//临时指针
pTmp=pHead;//临时指针指向链表头
int cnt = 0;
float sum = 0;
do{
sum += pTmp->data;
cnt++;
pTmp=pTmp->pNext;
}while(cnt<LIST_LEN);
//平均值结果通过指针传出
*res = sum/LIST_LEN;
}计算链表中所有数据的平均值，首先要获取各个节点的数据，基本思路是：
使用一个临时指针指向头节点pHead（当然选用pList或pTail也可以），然后获取该节点的数据，并移动到下一个节点，循环获取数据即可，停止条件为移动了链表的长度次。
环形链表的销毁
环形链表在初始化时是使用malloc()为各个节点动态分配内存的，因此在使用完链表后，需要使用free()来释放内存。
//释放链表 ---函数中需要改变指针的指向，也要传入二级指针
void release_list(stData **pList)
{
stData *pTmp=NULL;//临时指针
stData *pDel=NULL;
pTmp=(*pList)->pNext;
(*pList)->pNext=0;//断开第一个节点
do{
pDel=pTmp;
pTmp=pTmp->pNext;
free(pDel);
}while(pTmp->pNext != 0);
}基本思路是：首先断开环形链表的第1个和第2个节点的指向关系，然后逐个释放各个节点即可。
-
使用一个临时指针pTmp指向尾节点pTail
-
将pList的pNext置为0，断开环形链表的第1个和第2个节点的指向关系，作为循环销毁结束的判断条件：
-
再使用一个临时指针pDel指向刚才的临时指针pTmp指向的节点
-
将pTmp向后移动一个节点
-
释放pDel指向的节点的内存
-
然后循环指向，逐个释放，直至遇到刚才设置的断开的节点处，整个链表释放完成
测试代码
主函数部分：
//测试数据
float data[15]=
{
20.0, 20.3, 20.0, 19.8, 20.0,
19.0, 20.0, 20.4, 20.0, 20.0,
19.6, 20.0, 20.6, 20.0, 20.0
};
int main()
{
stData *pList = NULL; //环形链表指针
stData *pHead = NULL; //环形链表中的数据头指针
stData *pTail = NULL; //环形链表中的数据尾指针
init_list(&pList, LIST_LEN); //初始化一个长度为 LIST_LEN的环形链表 (LIST_LEN=5)
pHead = pTail = pList;
int i = 0;
int ret = -1;
for(i=0;i<15;i++)
{
//printf("mian--->i: %d \r\n", i);
ret = add_data2list(&pHead, &pTail, data[i]);
if(0 == ret)
{
float res;
calc_list_ave(pHead, &res);
printf("--->i: %d (%.2f)\r\n", i, res);
}
}
release_list(&pList);
return 0;
}测试结果：
--->i: 4 (20.02)
--->i: 5 (19.82)
--->i: 6 (19.76)
--->i: 7 (19.84)
--->i: 8 (19.88)
--->i: 9 (19.88)
--->i: 10 (20.00)
--->i: 11 (20.00)
--->i: 12 (20.04)
--->i: 13 (20.04)
--->i: 14 (20.04)
--------------------------------
Process exited after 0.01616 seconds with return value 0
请按任意键继续. . .
- 点赞
- 收藏
- 关注作者
评论（0）