循环链表是一种链式存储结构,它的最后一个结点指向头结点,形成一个环。因此,从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表的操作和单链表的操作基本一致,差别仅仅在于算法中的循环条件有所不同。
链表、双链表、单循环链表、双循环链表 的实现代码都差不多,区别只是在对指针域的修改。下面,是对单循环链表的实现:
#include <stdio.h> #include <stdlib.h> /*存储结构的定义*/ typedef struct CLinkList { int data ; struct CLinkList * next ; }node; int main() { node * pHead = NULL ; char opp; int find; printf("\n1.初始化链表 \n2.插入结点 \n3.删除结点 \n4.返回结点位置 \n5.遍历链表 \n0.退出 \n请选择你的操作:\n"); while(opp != '0'){ scanf("%c",&opp); switch(opp){ case '1': ds_init(&pHead); printf("\n"); ds_traverse(pHead) ; break; case '2': printf("输入需要插入结点的位置?"); scanf("%d", &find); ds_insert(&pHead,find) ; printf("在位置%d插入值后:\n", find) ; ds_traverse(pHead) ; printf("\n"); break; case '3': printf("输入需要删除的结点位置?"); scanf("%d", &find); ds_delete(&pHead,find) ; printf("删除第%d个结点后:\n", find) ; ds_traverse(pHead) ; printf("\n"); break; case '4': printf("你要查找倒数第几个结点的值?"); scanf("%d", &find); printf("元素%d所在位置:%d\n", find, ds_search(pHead,find)) ; //ListTraverse(L); printf("\n"); break; case '5': ds_traverse(pHead) ; printf("\n"); break; case '0': exit(0); } } return 0 ; } /************************************************************************/ /* 操作 */ /************************************************************************/ /*初始化循环链表*/ void ds_init(node ** pNode) { int item ; node * temp ; node * target ; printf("输入结点的值,输入0完成初始化\n"); while(1) { scanf("%d",&item) ; fflush(stdin) ; if(item == 0) return ; if((*pNode) == NULL) { /*循环链表中只有一个结点*/ *pNode = (node*)malloc(sizeof(struct CLinkList)) ; if(!(*pNode)) exit(0) ; (*pNode)->data = item ; (*pNode)->next = *pNode ; } else { /*找到next指向第一个结点的结点*/ for(target = (*pNode) ; target->next != (*pNode) ; target = target->next) ; /*生成一个新的结点*/ temp = (node *) malloc(sizeof(struct CLinkList)) ; if(!temp) exit(0) ; temp->data = item ; temp->next = *pNode ; target->next = temp ; } } } /*插入结点*/ /*参数:链表的第一个结点,插入的位置*/ void ds_insert(node ** pNode ,int i) { node * temp ; node * target ; node * p ; int item ; int j = 1 ; printf("输入要插入结点的值:"); scanf("%d",&item) ; if(i == 1) { //新插入的结点作为第一个结点 temp = (node *)malloc(sizeof(struct CLinkList)) ; if(!temp) exit(0) ; temp ->data = item ; /*寻找到最后一个结点*/ for(target = (*pNode) ; target->next != (*pNode) ; target = target->next) ; temp->next = (*pNode) ; target->next = temp ; *pNode = temp ; } else { target = *pNode ; for( ; j < (i-1) ; target=target->next,++ j) ; temp = (node *)malloc(sizeof(struct CLinkList)) ; if(!temp) exit(0) ; temp ->data = item ; p = target->next ; target->next = temp ; temp->next = p ; } } /*删除结点*/ void ds_delete(node ** pNode,int i) { node * target ; node * temp ; int j = 1 ; if(i == 1) { //删除的是第一个结点 /*找到最后一个结点*/ for(target = *pNode ; target->next != *pNode ;target = target->next) ; temp = *pNode ; *pNode = (*pNode)->next ; target->next = *pNode ; free(temp) ; } else { target = *pNode ; for( ; j < i-1 ; target= target->next,++j) ; temp = target->next ; target->next = temp->next ; free(temp) ; } } /*返回结点所在位置*/ int ds_search(node * pNode,int elem) { node * target ; int i = 1 ; for(target = pNode ; target->data != elem && target->next != pNode ; ++i , target = target->next) ; if(target->next == pNode) /*表中不存在该元素*/ return 0 ; else return i ; } /*遍历*/ void ds_traverse(node * pNode) { node * temp ; temp = pNode ; printf("***********链表中的元素******************\n"); do { printf("%4d ",temp->data) ; }while((temp = temp->next) != pNode) ; printf("\n") ; }
你可以全部代码拷到IDE运行。
延伸阅读
此文章所在专题列表如下:
- 结构之美:定义一个线性表
- 结构之美:线性表的查找、插入与删除操作
- 结构之美:线性表的链式存储结构——链表
- 结构之美:单链表的初始化、创建与遍历
- 结构之美:单链表的头结点与头指针
- 结构之美:使用头插法创建单链表
- 结构之美:使用尾插法创建单链表
- 结构之美:单链表的销毁删除
- 结构之美:查找单链表指定位置结点的数据
- 结构之美:在单链表指定位置插入数据
- 结构之美:删除单链表指定位置的数据
- 结构之美:单链表逆序
- 结构之美:判断单链表中是否有环
- 结构之美:获取单链表倒数第N个结点值
- 单循环链表的初始化、创建、删除、查找与遍历
- 结构之美:双向循环链表的结构与定义
本文地址:http://www.nowamagic.net/librarys/veda/detail/1875,欢迎访问原出处。
大家都在看