数据结构--循环链表

    链表中最后一个结点的指针指向第一个结点。在这个链表中，若首指针为head，最后一个结点的判断条件为：p->next == head。

             


注意：单链表的最后一个元素的next为null 而循环链表的最后一个元素的next为第一个元素地址

---循环单链表的操作和实现
1、打印链表
2、获得最后一个结点
3、找到值为x的结点
4、在i位置插入一个结点
5、在数据y之后插入一个x结点
6、删除值为x的结点


1、打印链表

#include"linklist.h"  
  
void display_link_list(node *head)
{  
    if(head == NULL)
    {  
        printf("the list is empty!\n");  
    }
    else
    {  
        node *ptr = head->next;    
        printf("%5d",head->info);  
        while(ptr != head)        //如果采用ptr->next != head 的方法无法判断最后一个元素！  
        {    
            printf("5%d",ptr->info);  
            ptr = ptr->next;  
        }  
    }  
}  



2、获得最后一个结点

#include"linklist.h"  
  
node* get_rear(node *head){  
    node* ptr = head;  
    while(ptr &&ptr->next != head) {  
        ptr= ptr->next;  
    }  
    return head;  
}  


3、找到值为x的结点

#include"linklist.h"  
  
node *find_node_clink(node* head,datatype x){  
    node*ptr = head->next;  
    if(head->info != x){   //如果第一个元素就是就直接走else返回  
        while(ptr != head && ptr->info != x){  
            ptr= ptr->next;  
        }  
        if(ptr == head){   //处理没有找到的情况  
            ptr = NULL;  
        }   
        return ptr;  
    }else{  
        return head;  
    }  
}  



4、在i位置插入一个结点

#include"linklist.h"  
  
node* insert_link_list_index(node *head,int index,datatype x){  
    if(index<0){  
        printf("index error\n");  
        exit(1);  
    }  
    if(index == 0){        //在链表头插入  
        node *p = (node*) malloc(sizeof(node));  
        node *rear;  
        p->info = x;  
        if(!head){        //空链表的处理  
            head = p;  
            p->next = head;  
            return head;  
        }else{            //正常在链表头插入的处理  
            rear = get_rear(head);  
            rear->next = p;  
            p->next = head;  
            head = p  
            return head;  
        }  
    }  
    else{                 //在链表中插入的处理  
        node *ptr= find_node(head,index-1);  
        node* q = (node*)malloc(sizeof(node));  
        q->info = x;  
        q->next = ptr->next;  
        ptr->next = q;  
        return head;  
    }  
}  




5、在数据y之后插入一个x结点

#include"linklist.h"  
  
node* intsert_node_yx(node *head,datatype x,datatype y){  
    node *q=find_node_clink(head,y);         //此处调用的是第3个函数  
    if(!q){  
        printf("not found the node %d\n");  
        return head;  
    }  
    node *p = (node*)malloc(sizeof(node));  
    p->info = x;  
    p->next= q->next;  
    q->next = p;  
    return head;  
}  


6、删除值为x的结点

#include"linklist.h"  
  
node* del_link_list_node(node* head,datatype x){  
    if(!head){  
        printf("the list is empty\n");  
        return head;  
    }  
    node* ptr=head,*pre=NULL;  
    while(ptr->next != head && ptr->info != x){  
        pre = ptr;  
        ptr=ptr->next;  
    }  
    if(ptr->info != x){          //判断最后一个元素的同时也判断了是否找到元素  
        printf("no data\n");  
    }else if(!pre){              //第一个元素就是x  
        pre = get_rear(head);    //不要忘了尾指针指头  
        head=ptr->next;  
        pre->next =ptr;  
    }else{                       //在链表中的情况  
        pre->next= ptr->next;  
    }  
    free(ptr);  
    return head;  
}