循环单向链表
所谓的循环，指得是将链表末尾节点的后继指针指向头结点。比如，单向链表变成循环链表的示意 图如下所示：
循环链表的操作跟普通链表操作基本上是一致的，只要针对循环特性稍作修改即可。
-
sclist.h
#ifndef __SCLIST_H #define __SCLIST_H typedef int DATA; typedef struct node { DATA data; struct node *next; }NODE; // 链表创建 int sclist_create(NODE**,DATA); // 链表数据添加 int sclist_insert(NODE** head,DATA data); // 链表数据查询 NODE* sclist_find(const NODE* head,DATA data); // 链表数据更新 int sclist_update(const NODE* head,DATA old,DATA newdata); // 链表数据遍历 void sclist_showAll(const NODE* head); // 链表数据删除 #endif -
sclist.c
#include "sclist.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
@function: int sclist_create(NODE** head,DATA data);
@berif: 创建单项链表
@argument: head: 指向头指针变量的地址，用来接收首节点地址
data: 存储在节点中的数据
@return : 成功返回 0
失败返回 -1
*/
int sclist_create(NODE** head,DATA data)
{
if(*head)
return -1;
NODE* p = (NODE*)malloc(sizeof(NODE));
if(!p)
{
return -1;
}
p -> data = data;
p -> next = p;
*head = p;
return 0;
}
NODE* sclist_findtail(const NODE* head)
{
const NODE* p = head, *q = NULL;
while(p)
{
q = p;
p = p -> next;
if(p == head)
break;
}
return (NODE*)q;
}
/*
@function: int sclist_insert(NODE** head,DATA data);
@berif: 向链表节点值为pos的位置插入一个节点数据data
@argument: head: 指向头指针变量的地址
data: 存储在新节点中的数据
@return : 成功返回 0
失败返回 -1
*/
int sclist_insert(NODE** head,DATA data)
{
NODE* tail = sclist_findtail(*head);
if(!tail)
return sclist_create(head,data);
NODE *pNew = (NODE*)malloc(sizeof(NODE));
if(!pNew)
return -1;
pNew -> data = data;
pNew -> next = *head;
tail -> next = pNew;
// *head = pNew;
return 0;
}
/*
@function: NODE* sclist_find(const NODE* head,DATA data);
@berif: 查找链表数据data
@argument: head: 指向头指针变量
data: 待查找的数据
@return : 成功返回节点的地址
失败返回NULL
*/
NODE* sclist_find(const NODE* head,DATA data)
{
const NODE* p = head;
while(p)
{
if(memcmp(&(p -> data),&data,sizeof(DATA)) == 0)
{
return (NODE*)p;
}
p = p -> next;
if(p == head)
break;
}
return NULL;
}
/*
@function: int sclist_update(const NODE* head,DATA old,DATA newdata);
@berif: 更新链表数据old 为 newdata
@argument: head: 指向头指针变量
old: 待更新的节点数据
newdata: 更新后的节点数据
@return : 成功返回 0
失败返回 -1
*/
int sclist_update(const NODE* head,DATA old,DATA newdata)
{
NODE* p = NULL;
if(!(p = sclist_find(head,old)))
return -1;
p -> data = newdata;
return 0;
}
/*
@function: void sclist_showAll(const NODE* head);
@berif: 遍历链表数据
@argument: head: 指向头指针变量
@return : 无
*/
void sclist_showAll(const NODE* head)
{
const NODE* p = head;
while(p)
{
printf("%d ",p -> data);
p = p -> next;
if(p == head)
break;
}
printf("\n");
}
/*
@function: int sclist_delete(NODE** head,DATA data);
@berif: 删除链表中节点值为data的节点
@argument: head: 指向头指针变量的地址
data: 删除节点中的数据
@return : 成功返回 0
失败返回 -1
*/
int sclist_delete(NODE** head,DATA data)
{
NODE *p = *head, *q = NULL;
if(!p)
return -1;
NODE* tail = sclist_findtail(*head);
if(memcmp(&(p -> data),&data,sizeof(DATA)) == 0)
{
if(*head == tail)
{
*head = NULL;
free(p);
return 0;
}
tail -> next = (*head) -> next;
*head = p -> next;
free(p);
return 0;
}
while(p)
{
if(memcmp(&(p -> data),&data,sizeof(DATA)) == 0)
{
q -> next = p -> next;
free(p);
return 0;
}
q = p;
p = p -> next;
if(p == *head)
break;
}
return -1;
}
/*
@function: void sclist_destroy(NODE** head);
@berif: 回收链表
@argument: head: 指向头指针变量的地址
@return : 无
*/
void sclist_destroy(NODE** head)
{
NODE* tail = sclist_findtail(*head);
if(!tail)
{
return ;
}
tail -> next = NULL; //将单向循环链表拆成单向链表
NODE* p = *head, *q = NULL;
while(p)
{
q = p;
p = p -> next;
free(q);
}
*head = NULL;
}
-
sclist_main.c
#include <stdio.h> #include <stdlib.h> #include "sclist.h" #define DELETE extern int play_game(NODE** head,DATA num); int main(int argc,char** argv) { NODE* head = NULL; if(sclist_create(&head,888) < 0) { puts("create failed"); return -1; } sclist_insert(&head,999); sclist_insert(&head,222); sclist_insert(&head,666); sclist_insert(&head,777); sclist_showAll(head); DATA data ; while(0) { #ifdef DELETE printf("请输入要删除的数据:"); scanf("%d",&data); if(data == -1) break; if(sclist_delete(&head,data) < 0) { puts("删除失败,请重试"); continue; } sclist_showAll(head); #else NODE *pFind = NULL; DATA newdata = 512; printf("请输入要查找的数据:"); scanf("%d",&data); if(data == -1) break; // if(!(pFind = slist_find(head,data))) if(slist_update(head,data,newdata) == -1) { puts("查找的数据不存在,请重试"); continue; } //printf("查找数据:%d 内存地址:%p\n",pFind -> data, &(pFind -> data)); slist_showAll(head); #endif } sclist_destroy(&head); puts("====销毁后====="); sclist_showAll(head); puts("====PlayGame====="); NODE* pHead = NULL; for(int i = 1; i <= atoi(argv[1]); i++) sclist_insert(&pHead,i); sclist_showAll(pHead); DATA last = play_game(&pHead,5); printf("最后一个元素:%d\n",last); sclist_destroy(&pHead); puts("====销毁后====="); sclist_showAll(pHead); return 0; }
这段代码使用了一个单向循环链表，实现了链表的创建、插入、删除、查找、更新、销毁等功能，并且还包含一个玩游戏的函数。
首先，在main函数中创建了一个链表，初始值为888。并且插入了几个元素(999, 222, 666, 777)。然后通过循环，可以选择删除某个元素或者查找某个元素进行更新。如果选择删除操作，会提示输入要删除的数据，并对链表进行删除操作。如果选择更新操作，会提示输入要查找的数据，并输入新的数据进行更新操作。在每次操作后，都会展示链表中的所有元素。
接下来，通过调用play_game函数来玩游戏。在play_game函数中，会根据给定的步长，不断遍历链表并删除指定步长的元素，直到链表只剩下最后一个元素为止。最后，输出最后一个元素的值。
最后，销毁链表并展示销毁后的链表。