算法与数据结构之三----循环链表

/**************************************************************** 文件内容：线性表之循环链表操作 版本V1.0 说明：单链表必需从头结点开始遍历，而循环链表可以从任何地方都可以遍历，只不过只能想后遍历 循环链表的特点： 1.链表头指针和尾指针相接，也就是说没有头指针，也没有尾指针（也没有NULL指针，单链表尾指针为NULL） 2.从任何一个地方开始遍历都可以找到某一个节点X 创建方法： 方法1.先建立两个单链表，然后将一个单链表的头指针链接到另外一个单链表的尾指针。 方法2：在后插入法建立单链表的基础上，每创建一个节点，尾指针总是指向头指针。 判断一个链表是否是循环链表的方法： 对链表进行遍历，如果能找到某个指针域指向NULL，则为单链表，否则就是双链表 循环链表特性： 1.循环链表无法求长度，因为是无限长度的 2.循环链表是无法遍历完毕的，因为是无限长度的 3.循环链表插入，删除，查找跟单链表没有任何区别，只不过单链表有头指针，循环链表没有 头指针，或者说循环链表中任意一个节点指针都是头指针。 作者：HFL 时间：2013-12-25  *****************************************************************/  #include<stdio.h> #include<malloc.h> #include <windows.h> //#define RELEASE_VERSION  //release版本开关 //#define TRIDiTION /*inlude<malloc.h> stdlib.h 包含malloc.h*/ #ifdef RELEASE_VERSION #define  Log  #else #define  Log  printf #endif /*为了提高程序的可移植性，千万不能使用裸露的数据类型*/ #ifndef UINT32  typedef unsigned int UINT32 ; #endif #ifndef INT32  typedef  int  INT32 ; #endif typedef struct CNode { INT32 data; struct CNode *next; }Cnode,*Linklist; /**************************************************************** 函数功能：创建一个循环链表，由单链表中初始化链表2（即尾部创建一个链表）派生而来                         输入参数:  无 返回值：链表的标头指针  说明：要引入一个新的指针变量，用于链接前后节点       在后插入建立单链表的基础上，每次创建一个节点，就将尾指针指向头指针 作者:HFL  时间：2013-12-24  ************T*****************************************************/  Linklist Creat_Clinklist() { Linklist L=NULL; Cnode *s; Cnode *probe =NULL; INT32 x;     scanf("%d",&x); while(x!=0) {  s=(struct CNode *)malloc(sizeof(Cnode));  if(NULL==s) { Log(" sorry,Malloc is failed\n"); } else { Log(" Malloc is successed!\n"); if(L== NULL) { L = s;  //第一个节点就必需保存投节点 } else { probe->next = s; //第二个节点开始，要引入一个临时指针，来暂存上一个节点地址，一遍链接前后两个节点 } probe = s;  //每次创建一个新节点，节点都必需重新移动。 s->data = x ; s->next = L; scanf("%d",&x); } } return L; } /**************************************************************** 函数功能：前面插入法构建但链表（即头部创建一个链表）                         输入参数:  无 返回值：链表的标头指针  作者:HFL  时间：2013-12-22  *****************************************************************/  Linklist Head_Creat_Linklist() { Linklist L=NULL; Cnode *s; INT32 x;     scanf("%d",&x); while(x!=0) {  s=(struct CNode *)malloc(sizeof(CNode));  if(NULL==s) { Log(" sorry,Malloc is failed\n"); } else { Log(" Malloc is successed!\n"); s->data = x ;/*一定要注意第一个节点，且一定要注意先后顺序*/ s->next = L; L=s; scanf("%d",&x); } } return L; } /**************************************************************** 函数功能：创建循环链表2                         输入参数:  无 返回值：链表的标头指针  说明：先创建两个单链表，然后将两个单链表对接即可 作者:HFL  时间：2013-12-22  *****************************************************************/  Linklist Creat_Clinklist_by_dtod() { Linklist temp1 = NULL ; Linklist L1 = NULL ; Linklist temp2 = NULL; Linklist L2 = NULL; L1 =Head_Creat_Linklist();     L2 = Head_Creat_Linklist(); if ( NULL == L1 || NULL == L2 ) return NULL; temp1 = L1,temp2 = L2; while(NULL != temp1->next) //注意是temp->next 而不是temp temp1 = temp1->next;     while(NULL != temp2->next) temp2 = temp2->next;     temp1->next = L2; temp2->next = L1; return L2; } /**************************************************************** 函数功能：遍历整个链表                         输入参数:  链表任意节点指针 返回值：无  说明：遍历不能影响原来链表的结构。 作者:HFL  时间：2013-12-24  ************T*****************************************************/  void List_Clinklist(Linklist L) {   Linklist temp = L;//不能使用L指针，否则将链表头指针移动，链表被破坏，故使用一个临时指针来变量 INT32 i = 0; while(NULL!=temp) { printf("the data[%d]=%d\n",++i,temp->data); //L->next=L->next->next; temp = temp->next; Sleep(1000); } return ; } void main() {   Linklist L; Log("*******************************\n"); Log("*                             *\n"); Log("*   Creat CLinklist is start ! *\n"); Log("*                             *\n"); Log("*******************************\n");    // L = Creat_Clinklist(); L = Creat_Clinklist_by_dtod(); if(!L)    {   Log(" the Creat CLinklist is failed\n");    }    else    {     Log(" the Creat Linklist is secuseed\n");    }     Log("*******************************\n"); Log("*                             *\n"); Log("*   List CLinklist is start ! *\n"); Log("*                             *\n"); Log("*******************************\n");     List_Clinklist(L); }