C语言中,链表是一种数据结构,相比较数组的连续存储,链表是一种将内存分散(当前也可以连续)的数据节点通过指针的方式连接在一起,此外,链表不仅可以存储简单的数据类型,还可以存储结构体,只要定义好自己的链表结构体即可。

链表,从名字上来看是一条数据链,一般的链表其末尾节点是没有指向的,但当把链表的末尾节点指定为指向头节点时,则构成了一个环形链表。

链表结构体

首先定义环形链表的节点的形式,即一个结构体,简单为例,该结构体内只有一个float数据,以及指向下一个节点的指针,如下:

1
2
3
4
5
6
//链表节点结构体 
typedef struct stData
{
float data;
struct stData *pNext;
}stData;

环形链表的使用需要定义3个指针:1个是环形链表的指针(分配后就是固定值),1个头指针和1个尾指针(在向链表写入新数据时这两个指针不不断的改变节点的指向)。

环形链表首先需要初始化,为其分配内存空间,初始化后,链表内的数据全部初始化为0,且头指针和尾指针都先与环形链表指向同一地址。

1
2
3
4
5
6
7
stData *pList = NULL; //环形链表指针 
stData *pHead = NULL; //环形链表中的数据头指针
stData *pTail = NULL; //环形链表中的数据尾指针

init_list(&pList, LIST_LEN); //初始化一个长度为 LIST_LEN的环形链表
pHead = pList;
pTail = pList;

环形链表初始化

环形链表的初始化过程如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//初始化链表  ---函数中分配内存,需要传入二级指针  
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个节点

1
2
3
4
5
6
//先为环形链表分配一个节点的内存 
*pList=(stData*)malloc(sizeof(stData));
(*pList)->data=0;
(*pList)->pNext=NULL;

pTmp1 = *pList; //临时指针1指向环形链表的头

第一个节点的内存先通过pList指针分配,然后临时指针pTmp1也先指向这个节点:

分配第2个节点

1
2
3
4
5
6
7
8
9
10
11
12
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
2
//整个链表长度都分配好内存后,临时指针1再指向链表头,这样就构成了一个环形链表  
pTmp1->pNext = *pList;

例子中环形链表的长度为5,因此分配第5个之后,会退出循环,然后:

  • 将pTmp1的pNext指向pList,这样就构成了一个环形链表
  • 链表初始化函数退出后,两个临时指针也会被自动释放

环形链表初始化完成

初始化完成后的效果如下,一个5个节点,构成了一个环形,且初始状态,头节点与尾节点均指向pList指向的节点:

查询环形链表中有效数据的长度

环形链表初始化后各节点的数据均为0,查询环形链表中有效数据的长度,用于指示在向链表写入数据时,头指针与尾指针是否需要移动,然后在合适的位置写入新的数据,以及用于在数据使用的是否,只有链表数据满了之后,才对整个环形链表中的数据进行使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//查询当前链表中数据的长度 -----初始时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个数据,环形链表的有效数据就满了

环形链表写入数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//添加数据到链表  ---函数中需要改变指针的指向,也要传入二级指针  
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个数据类似,并且之后数据的写入,都与次步骤类似。

环形链表的一种应用

计算一串数据的滑动平均值

比如传感器采集到连续的数据,需要作一个滑动的滤波处理,可以将数据不断的写入该循环链表,当链表满了之后,开始计算以链表长度为滑动窗口的平均值,并不断输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//计算平均值 
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()来释放内存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//释放链表 ---函数中需要改变指针的指向,也要传入二级指针 
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指向的节点的内存
  • 然后循环指向,逐个释放,直至遇到刚才设置的断开的节点处,整个链表释放完成

测试代码

主函数部分:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//测试数据 
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;
}

测试结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
--->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
请按任意键继续. . .

可以看到,测试程序有一个包含15个数的序列,并通过for循环依次将数据放入到环形链表中,在前4次循环(0~3)中,环形链表没有存满,不对链表中的数据处理,因此没有显示出打印信息,在第5次循环以及之后,环形链表始终是满的状态,因此可以一直对链表中数据进行处理,这里是求取平均值。