循环链表

迈不过友情╰ 2022-04-17 02:42 197阅读 0赞

## 循环链表 ##

*  循环链表的原理：最后一个节点的next指向头节点，而不是NULL  
    ![在这里插入图片描述][20181114202301997.png]

--------------------

## 实例代码 ##

circle\_list.h

#include <stdio.h>
    #include <stdlib.h>
    
    
    typedef struct CIRCLELISTNODE
    { 
    		struct  CIRCLELISTNODE* next;
    		
    }ListNode;
    
    
    
    
    typedef struct CIRCLELIST { 
    		ListNode* head;
    		ListNode* tail;
    		int size;	
    }ListInfo;
    
    
    typedef void(*PRINT)(ListNode*);
    typedef int (*COMPARE)(ListNode*,ListNode*);
    
    
    
    ListInfo* Init_List();
    
    void Push_Back(ListInfo* list, ListNode* data);
    
    void Insert_list(ListInfo* list,int pos,ListNode* data);
    
    void RemoveByPos_list(ListInfo* list,int pos);
    
    void RemoveByValue_list(ListInfo* list,ListNode* data,COMPARE compare);
    
    int Find_list(ListInfo* list,ListNode* data,COMPARE compare);
    
    void Print(ListInfo* list,PRINT print);

circle\_list.c

#include "../include/list.h"
    
    
    ListInfo* Init_List()
    { 
    	ListInfo* clist = (ListInfo*)malloc(sizeof(ListInfo));
    	clist->head =( ListNode*) malloc(sizeof(ListNode));
    	clist->tail=( ListNode*) malloc(sizeof(ListNode));
    
    	clist->head->next = clist->head;
    	clist->tail->next = clist->head;
    
    	clist->size =0;
    
    	return clist;
    }
    
    
    void Push_Back(ListInfo* list, ListNode* data)
    { 
    	if(list == NULL)return;
    	if(data == NULL)return;
    
    	ListNode* pCurrent = list->tail;
    
    	data->next = pCurrent->next;
    	list->tail->next = data;
    	list->tail = data;
    
    	list->size++;	
    }
    
    
    void Insert_list(ListInfo* list,int pos,ListNode* data)
    { 
    	if(list == NULL)return;
    	if(data == NULL)return;
    	if(pos<0 || pos > list->size)
    	{ 
    		pos = list->size;
    	}
    
    	ListNode* pCurrent = list->head;
    	for(int i=0; i<pos; i++)
    	{ 
    		pCurrent = pCurrent->next;
    	}
    
    	data->next = pCurrent->next;
    	pCurrent->next = data;
    
    	if(pos == list->size)//插入尾部，需要改变尾部指针
    	{ 
    		list->tail = data;
    	}
    
    	list->size++;
    }
    
    
    
    
    void RemoveByPos_list(ListInfo* list,int pos)
    { 
    	if(list == NULL)return;	
    	if(pos < 0 || pos>=list->size)return;
    
    	ListNode* pCurrent = list->head;
    	for(int i=0;i<pos;i++)
    	{ 
    		pCurrent = pCurrent->next;
    	}
    
    	ListNode* pNext = pCurrent->next;
    	pCurrent->next = pNext->next;
    
    	if(pos == list->size)
    		list->tail = pCurrent;
    	list->size--;
    
    }
    
    
    void RemoveByValue_list(ListInfo* list,ListNode* data,COMPARE compare)
    { 
    	if(list == NULL) return;
    	if(data == NULL) return;
    	int flag=0;
    	
    	ListNode* pCurrent=list->head;
    
    	for(int i=0; i<list->size; i++)
    	{ 
    		flag =i;
    		if(compare(pCurrent->next,data))
    		{ 
    			pCurrent->next = pCurrent->next->next;
    			break;
    		}	
    	
    	    pCurrent =pCurrent->next;
    	}
    	if(flag == list->size -1)//删除的是最后一个，则需要改变tail值
    		list->tail = pCurrent;
    
    	list->size--;
    }
    
    
    int Find_list(ListInfo* list,ListNode* data,COMPARE compare)
    { 
    	int flag=0;
    
    	if(list == NULL) return -1;
    	if(data == NULL) return -1;
    
    	ListNode* pCurrent=list->head->next;
    
    	for(int i=0; i<list->size; i++)
    	{ 
    		if(compare(pCurrent,data))
    		{ 
    			flag=i;
    			break;
    		}
    		pCurrent = pCurrent->next;
    	}	
    
    return flag;
    }
    
    
    
    
    
    
    void Print(ListInfo* list,PRINT print)
    { 
    
    	if(list==NULL) return;
    	
    	ListNode* pCurrent = list->head->next;
    	for(int i=0; i<list->size; i++)
    	{ 
    		if(pCurrent == list->head)//循环到头节点了
    		{ 
    			pCurrent = pCurrent->next;
    		}
    		print(pCurrent);
    		pCurrent = pCurrent->next;
    	}
    
    
    }

main.c

#include <stdio.h> 
    #include <string.h>
    #include <stdlib.h>
    #include "../include/list.h"
    
    typedef struct PERSON
    { 
    	ListNode node;
    	char name[64];
    	int age;
    	int score;
    	
    }Person;
    
    void MyPrint(ListNode* data)
    { 
    	Person* p =(Person*)data;
    	printf("name: %s,age: %d,score: %d\n",p->name,p->age,p->score);
    }
    
    
    int MyCompare(ListNode* data1,ListNode* data2)
    { 
    	Person* p1 =(Person*)data1;
    	Person* p2 =(Person*)data2;
    
    	if(p1->age==p2->age && p1->name==p2->name && p1->score == p2->score)
    	{ 
    		return 1;
    	}
    
    	else
    	{ 
    		return  0;
    	}
    
    }
    
    int main(void)
    { 
    	ListInfo* list = Init_List();
    
    	Person p1,p2,p3,p4,p5;
    	
    	strcpy(p1.name,"aaa");
    	strcpy(p2.name,"bbb");
    	strcpy(p3.name,"ccc");
    	strcpy(p4.name,"ddd");
    	strcpy(p5.name,"eee");
    
    	p1.age = 10;
    	p2.age = 20;
    	p3.age = 30;
    	p4.age = 40;
    	p5.age = 50;
    
    	p1.score =100;
    	p2.score =200;
    	p3.score =300;
    	p4.score =400;
    	p5.score =500;
    
    	Insert_list(list, 100,(ListNode*)&p2);//在最后一位插入
    	Insert_list(list, 100,(ListNode*)&p3);
    	Insert_list(list,0,(ListNode*)&p1);//在第0位插入
    
    	Push_Back(list,(ListNode*)&p4);//插入最后
    	Push_Back(list,(ListNode*)&p5);
    	Print(list,MyPrint);
    	
    	printf("----删除第一个和最后一个------\n");
    	RemoveByPos_list(list,0);
    	RemoveByPos_list(list,3);
    	Print(list,MyPrint);
    	
    	printf("-----删除ddd-----\n");
    	RemoveByValue_list(list,(ListNode*)&p4,MyCompare);
    	Print(list,MyPrint);
    	printf("----------\n");
    
    	int pos=Find_list(list,(ListNode*)&p3,MyCompare);
    	printf("ccc pos: %d\n",pos);
    
           
    	return 0;
    }

结果：  
![在这里插入图片描述][20181114201755501.png]

[20181114202301997.png]: /images/20220417/c8f0f7e74d4a4fcda32a9d5f03c62c59.png
[20181114201755501.png]: /images/20220417/da87ffe80ce7436e9f3b9ea471f3f65a.png