一.循环链表简介：

1.概念：

循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个节点的 指针域指向头节点，整个链表形成一个环。

2.分类：

（1）单循环链表——在单链表中，将尾节点的指针域NULL改为指向头节点即可。

（2）多重链的循环链表——将表中节点链在多个环上。

3.重点：

①循环链表中没有NULL指针。涉及遍历操作时，其终止条件就不再是像非循环链表那样判别p或p->next是否为空，而是判别它们是否等于某一指定指针，如头指针或尾指针或者顶一个等。

②在单链表中，从一已知点出发，只能访问到该节点及其后续结点，无法找到该节点之前的其它节点。而在单循环链表中，从任一节点出发都可访问到表中所有节点，这一优点使某些运算在单循环链表上易于实现。

二.单向循环链表的实现代码：

定义一个结构体，保存链表的next和data。 因为是循环链表，所以定义一个全局变量保存元素个数操作起来方便。新增一个节点num++。 创建节点函数便于我们创建一个新的节点。 创建链表，先创建一个头节点，然后根据头节点把一个个节点连接起来。 #include <stdio.h> struct node{ int data; struct node *next; }; typedef struct node Node; #define SIZE sizeof(Node) int num=1;//计算循环链表的节点个数 头节点已经创建好了 有一个节点了 //创建节点 Node* creteNode(int d) { Node* pn=malloc(SIZE); pn->data=d; pn->next=NULL; return pn; } //创建链表 void creatList(Node** h) { Node* pn=NULL; Node* p=NULL; int d; printf("请输入数据\n"); scanf("%d",&d); pn=creteNode(d); *h=pn; p=*h; while(1) { printf("请输入数据\n"); scanf("%d",&d); if(d==0) { p->next=*h; break; } pn=creteNode(d); ++num; p->next=pn; p=p->next; } } 因为是循环链表，不能依靠p->next==NULL；来判断，所以用num元素个数来判断是不是到了链表尾部。 //查找某个节点的位置 Node* findNode(Node* h,int n) { int i; if((h==NULL)||(n<0)) { printf("查找位置不合法||链表为空！\n"); return NULL; } if(n==1) { return h; } for(i=1;i<n;i++) { h=h->next; if(h==NULL) break; } return h; } 尾插法，在尾部插入一个元素，遍历可以用查找的那个函数，没必要自己遍历一遍，这里就不改了。 最后记得首位相连，num++。 //末尾增加一个新的节点 int addBack(int d,Node* h) { int i; int n=num; Node *pn=NULL; pn=creteNode(d); Node* p=h; for(i=0;i<n-1;i++) { p=p->next; } p->next=pn; pn->next=h; num++; } 头插法，在头部插入一个元素。 首先要断开首位相连，然后插入元素，最后首尾相连，num++。 //头插法 int addFont(int d,Node** h)//修改头节点 传入二级指针 { int n=num; Node* pf=findNode(h,n-1); pf->next=NULL; Node* pn=NULL; pn=creteNode(d); pn->next=*h; *h=pn; pf->next=*h; num++; } 插入元素，在链表任意位置插入元素。 先判断位置是否合法。 找到插入位置前一个元素，先断开连接，新节点的next等于前一个节点的next，前一个元素的next等于新节点，num++； //插入 int insertNode(int n,int d,Node** h)//在n位置插入d { if((n<1)||(*h==NULL)||(n>num)) { printf("插入位置不合法||链表为空!\n"); return 0; } //插入位置为1，即插入头节点的位置 if(n==1) { addFont(d,h); return 0; } Node* pn=creteNode(d);//创建新的节点 Node* pf=findNode(*h,n-1); pn->next=pf->next; pf->next=pn; num++; return 1; } 删除元素，删除链表中的某个元素。 判断位置。 然后找到前一个元素，断开连接，前一个元素的next指向删除元素next的元素，num--。 //删除第n个位置的元素 int deleteNode(int n,Node** h) { //判断头节点是否为空，位置是不是合法 if((*h==NULL)||(n<1)||(n>num)) { printf("删除的链表为空||删除的位置不合法！\n"); return 0; } Node* pd=NULL; //删除头节点 if(n==1) { int n1=num; Node* pf=findNode(*h,n1-1); pf->next=NULL; pd=*h; *h=pd->next; pf->next=*h; num--; return 1; } //删除 //判断节点是否存在 if(NULL==findNode(*h,n-1)) { printf("删除节点不存在\n"); return 0; } //找到要删除的节点的前一个节点 Node* pf=findNode(*h,n-1); printf("haha%d ",pf->data); pd=pf->next;//将要删除的节点的给pd pf->next=pd->next; pd->next=NULL; num--; return 1; } 打印和测试函数： //打印链表 void print(Node* h) { int n=num; printf("list:\n"); while(n--) { printf("%d ",h->data); h=h->next; } printf("\n"); } int main() { Node* head=NULL; creatList(&head); print(head); deleteNode(4,&head); print(head); /*deleteNode(2,&head); print(head);*/ return 0; }