数据结构-链表3-循环链表
LinkList.h
#ifndef LINKLIST_H
#define LINKLIST_H
#define _CRT_SECURE_NO_WARNINGS
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
//链表小结点
typedef struct CIRCLELINKNODE {
struct LinkNode *next;
}CircleLinkNode;
//链表结构体
typedef struct CIRCLELINKLIST {
CircleLinkNode head;
int size;
}CircleLinkList;
//打印回调
typedef void(*PRINTNODE)(CircleLinkNode*);
//比较回调
typedef int(*COMPARENODE)(CircleLinkNode*, CircleLinkNode*);
#define COMPARENODE_TRUE 1
#define COMPARENODE_FALSE 0
//初始化链表
CircleLinkList* Init_LinkList();
//插入
void InsertByPos_LinkList(CircleLinkList *clist, int pos, CircleLinkNode *data);
//根据位置删除元素
void RemoveByPos_LinkList(CircleLinkList *clist, int pos);
//根据值去删除
void RemoveByValue_LinkList(CircleLinkList *clist, CircleLinkNode* data, COMPARENODE compare);
//查找
int FindByValue_LinkList(CircleLinkList *clist, CircleLinkNode *data, COMPARENODE compare);
//返回第一个元素
CircleLinkNode* Front_LinkList(CircleLinkList *clist);
//返回链表大小
int GetSize_LinkList(CircleLinkList *clist);
//打印结点
void Print_LinkList(CircleLinkList *clist, PRINTNODE print);
//释放链表内存
void FreeSpace_LinkList(CircleLinkList *clist);
//是否为空
int IsEmpty_LinkList(CircleLinkList *clist);
#endif
LinkList.c
#include"LinkList.h"
//初始化链表
CircleLinkList* Init_LinkList()
{
CircleLinkList * clist = (CircleLinkList*)malloc(sizeof(CircleLinkList));
clist->head.next = &(clist->head); //循环链表 指向自己
clist->size = 0;
return clist;
}
//插入
void InsertByPos_LinkList(CircleLinkList *clist, int pos, CircleLinkNode *data)
{
if (clist == NULL)
{
return;
}
if (pos<0 || pos>clist->size)
{
pos=clist->size;
}
if (data == NULL)
{
return;
}
//根据位置查找前一个结点
//辅助指针变量
//辅助结点:插入节点的前一个结点
CircleLinkNode *pCurrent = &(clist->head);
for (int i = 0; i < pos; i++)
{
pCurrent=pCurrent->next;
}
//新数据插入链表
data->next=pCurrent->next;
pCurrent->next = data;
clist->size++;
}
//根据位置删除
void RemoveByPos_LinkList(CircleLinkList *clist, int pos)
{
if (clist == NULL)
{
return;
}
if (pos<0 || pos>clist->size)
{
return;
}
//根据pos找上一个结点
//辅助结点:插入节点的前一个结点
CircleLinkNode *pCurrent = &(clist->head);
for (int i = 0; i < pos; i++)
{
//pCurrent->next = pCurrent;
pCurrent = pCurrent->next;
}
//缓存当前结点的下一个结点
CircleLinkNode *pNext = pCurrent->next;
pCurrent->next = pNext->next;
//等价pCurrent->next = pCurrent->next->next;
clist->size--;
}
//根据值去删除
void RemoveByValue_LinkList(CircleLinkList *clist, CircleLinkNode* data, COMPARENODE compare) {
if (clist == NULL)
{
return;
}
if (data == NULL)
{
return;
}
//循环链表,不能一直循环
CircleLinkNode* pPre = &(clist->head);
CircleLinkNode* pCurrent = pPre->next;
int i = 0;
for (i = 0; i < clist->size; i++)
{
if (compare(pCurrent,data) == COMPARENODE_TRUE)
{
pPre->next = pCurrent->next;
break;
}
pPre = pCurrent;
pCurrent = pPre->next;
}
clist->size--;
}
//获得第一个元素
CircleLinkNode* Front_LinkList(CircleLinkList *clist)
{
if (clist == NULL)
{
return NULL;
}
return clist->head.next;
}
//是否为空
int IsEmpty_LinkList(CircleLinkList *clist) {
if (clist == NULL)
{
return -1;
}
if (clist->size == 0)
return COMPARENODE_TRUE;
return COMPARENODE_FALSE;
}
//查找
int FindByValue_LinkList(CircleLinkList *clist, CircleLinkNode *data, COMPARENODE compare)
{
if (clist == NULL)
{
return -1;
}
if (data==NULL)
{
return -1;
}
//辅助结点:插入节点的前一个结点
CircleLinkNode *pCurrent = clist->head.next;
int flag = -1;
for (int i = 0; i < clist->size; i++)
{
if (compare(pCurrent, data) == COMPARENODE_TRUE)
{
flag = i;
break;
}
pCurrent = pCurrent->next;
}
/*while (pCurrent != NULL)
{
if (compare(pCurrent, data) == 0)
{
flag = index;
break;
}
index++;
pCurrent = pCurrent->next;
if (pCurrent->next ==&( pCurrent->head))
{
pCurrent->next = pCurrent;
}
}*/
return flag;
}
//返回链表大小
int GetSize_LinkList(CircleLinkList *clist)
{
if (clist == NULL)
{
return -1;
}
return clist->size;
}
//打印
void Print_LinkList(CircleLinkList *clist, PRINTNODE print)
{
if (clist == NULL)
{
return;
}
CircleLinkNode *pCurrent = clist->head.next;
for (int i = 0; i < clist->size; i++)
{
if (pCurrent == &(clist->head))
{
pCurrent = pCurrent->next;
printf("------------\n");
}
print(pCurrent);
pCurrent = pCurrent->next;
}
printf("---------------\n");
/*
if (pCurrent == &(clist->head))
pCurrent = pCurrent->next;*/
return;
}
//释放链表内存
void FreeSpace_LinkList(CircleLinkList *clist)
{
if (clist == NULL)
{
return;
}
free(clist);
}
循环链表.c
#include"LinkList.h"
typedef struct PERSON
{
CircleLinkNode node;
char name[64];
int age;
}Person;
void print(CircleLinkNode *data)
{
Person *p = (Person*)data;
printf("Name:%s age:%d\n", p->name, p->age);
}
int compare(CircleLinkNode *node1, CircleLinkNode *node2)
{
Person *p1 = (Person*)node1;
Person *p2 = (Person*)node2;
//if (p1->age == p2->age && p1->name == p2->name)
if(strcmp(p1->name,p2->name)==0 && p1->age==p2->age)
{
return COMPARENODE_TRUE;
}
return COMPARENODE_FALSE;
}
int main()
{
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;
CircleLinkList *clist = Init_LinkList();
InsertByPos_LinkList(clist, 100, (CircleLinkNode *)&p1);
InsertByPos_LinkList(clist, 100, (CircleLinkNode *)&p2);
InsertByPos_LinkList(clist, 100, (CircleLinkNode *)&p3);
InsertByPos_LinkList(clist, 100, (CircleLinkNode *)&p4);
InsertByPos_LinkList(clist, 100, (CircleLinkNode *)&p5);
//打印
Print_LinkList(clist,print);
Person pDel;
strcpy(pDel.name, "ccc");
pDel.age = 30;
//根据值删除
RemoveByValue_LinkList(clist,(CircleLinkNode*)&pDel, compare);
//打印
printf("删除ccc后打印---------------------\n");
Print_LinkList(clist, print);
int pos=FindByValue_LinkList(clist, (CircleLinkNode *)&p2,compare);
printf("bbb的位置:%d\n ",pos);
FreeSpace_LinkList(clist);
system("pause");
return 0;
}
//////////////////////////////运行结果//////////////////////////
/*
Name:aaa age:10
Name:bbb age:20
Name:ccc age:30
Name:ddd age:40
Name:eee age:50
---------------
删除ccc后打印---------------------
Name:aaa age:10
Name:bbb age:20
Name:ddd age:40
Name:eee age:50
---------------
bbb的位置:1
请按任意键继续. . .
*/
运行结果: