一、循环链表
1、循环链表
将链表的尾节点指向链表的头节点，使得该链表可循环访问。
二、单/双向循环链表
1、单/双向链表
在单链表中，查找ai 的后继Next(l,ai),耗时仅为0(1),因为取ai之后继指针即可。但是查找ai的前驱Prior(L,ai),则需从链表的头指针开始，找到接到ai前一节点即是。故运算Prior(L,ai)依赖表长n，耗时为O(n).另外，若链表中有一指针值被破坏，则整个指针脱节，这是单恋表的不足，为此，引入双向链表。先定义双向链表的节点。
其中，data和next同单链表，增加一指针域prior,其指向本结点的直接前驱。
结点描述：
typedef int data_t;
typedef struct dnode_t
{
data_t data;
struct dnode_t * prior,*next;
}dlinknode_t,*dlinklist_t;
2、单/双向循环链表
设p为链表中某结点的指针，有对称性：
（p->prior）->next = p = (p->next)->prior
双向链表的查找运算基本上同单链表。
下面讨论双向循环链表的插入和删除运算。
三、双向循环链表的应用
1、cirlist.c
#include "cirlist.h"
cirlist * cirlist_create(void) //双向链表的建立
{
cirlist * r;
cirlist * H;
cirlist * p;
int n;
H = (cirlist*)malloc(sizeof(cirlist));
if(H == NULL)
{
printf("cirlist malloc faile !!");
return NULL;
}
H->next = H;
H->pront = H;
r = H;
while(1)
{
printf("请输入节点：");
scanf("%d",&n);
if(n == -1)
{
break;
}
if((p=(cirlist*)malloc(sizeof(cirlist)))==NULL)
{
printf("cirlist insert faile !!");
return NULL;
}
p->data = n;
p->next = r->next;//新加入的节点的后继指向前一个节点指向的后继
p->pront = r;
r->next = p;
H->pront = p;//头结点的前驱永远指向最后一个结点
r = p;
}
return H;
}
void cirlist_show(cirlist * L) //双向链表的遍历
{
cirlist * q;
if(L == NULL)
{
printf("cirlist is NULL !!");
return;
}
q = L;
while(q ->next != L)
{
printf("%d ",q->next->data);
q = q->next;
}
}
void cirlist_free(cirlist * L) //释放双向链表
{
cirlist * q;
if(L == NULL)
{
printf("cirlist is NULL !!");
return;
}
q = L;
while(q->next != L)
{
free(q);
q = q->next;
}
free(q);
q = NULL;
}
int cirlist_length(cirlist * L) //获取双向链表的长度
{
int cir_length = 0;
cirlist * q;
if(L == NULL)
{
printf("cirlist is NULL !!");
return -1;
}
q = L;
while(q->next != L)
{
cir_length++;
q = q->next;
}
return cir_length;
}
int cirlist_insert(cirlist * L,data_t x,data_t pos) //向双向链表中插入数据
{
int i = 0;
cirlist * p;
cirlist * q;
if(L == NULL)
{
printf("cirlist is NULL !!");
return -1;
}
q = (cirlist*)malloc(sizeof(cirlist));
if(q == NULL)return -1;
p = L;
while(i<pos)
{
i++;
p=p->next;
if(p == L)
{
printf("pos is invalid !!");
return -1;
}
}
q->data = x;
q->pront = p;
q->next = p->next;
p->next->pront = q;
p->next = q;
return 0;
}
int cirlist_delete(cirlist * L,data_t pos)//数据的删除
{
cirlist * q;
int i = -1;
if(L == NULL)
{
printf("cirlist is NULL !!");
return -1;
}
q = L;
while(i<pos)
{
i++;
q = q->next;
if(q == L)
{
printf("pos is invalid !!");
return -1;
}
}
q->pront->next = q->next;
q->next->pront = q->pront;
free(q);
q = NULL;
return 0;
}
2、cirlist.h
#ifndef __CIRLIST_H__
#define __CIRLIST_H__
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
typedef int data_t;
typedef struct node_t {
data_t data;
struct node_t * next;
struct node_t * pront;
}cirlist;
cirlist * cirlist_create(void);
void cirlist_show(cirlist * L);
int cirlist_insert(cirlist * L,data_t x,data_t pos);
void cirlist_free(cirlist * L);
int cirlist_delete(cirlist * L,data_t pos);
int cirlist_is_emty(cirlist * L);
int cirlist_length(cirlist * L);
#endif
3、test.c
#include "cirlist.h"
//主函数
int main(int argc, const char *argv[])
{
cirlist * p;
p = cirlist_create();
if(p == NULL)
{
printf("cirlist malloc faile !!!");
return -1;
}
cirlist_show(p);
puts(" ");
cirlist_insert(p,10,1);
cirlist_insert(p,20,1);
cirlist_insert(p,30,1);
cirlist_show(p);
puts("");
cirlist_delete(p,0);
cirlist_delete(p,1);
cirlist_delete(p,2);
cirlist_show(p);
cirlist_free(p);
return 0;
}
