如何使此列表成为循环列表?

Question

代码是下一个，我希望列表中的最后一项始终指向列表开头的指针，即使我更改它或删除它，但我不知道如何。我对这个有点陌生。

这是我拥有的完整代码，具有插入和删除列表中的元素的函数以及用于指令的函数并打印

#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
struct listNode {
char data;
struct listNode *nextPtr;
};
typedef struct listNode LISTNODE;
typedef LISTNODE *LISTNODEPTR;
char delete(LISTNODEPTR *, char);
int isEmpty(LISTNODEPTR);
void printList(LISTNODEPTR);
void instructions(void);
LISTNODE *addtoList(LISTNODEPTR *sPtr, char value);
int main() {
LISTNODEPTR startPtr = NULL;
int choice;
char item;
instructions();
printf("? ");
scanf("%d", &choice);
while (choice != 3) {
switch (choice) {
case 1:
printf("Enter a character: ");
scanf("n%c", &item);
insert(&startPtr, item);
printList(startPtr);
break;
case 2:
if (!isEmpty(startPtr)) {
printf("Enter character to be deleted: ");
scanf("n%c", &item);
if (delete (&startPtr, item)) {
printf("%c deleted.n", item);
printList(startPtr);
} else
printf(
"List is empty or the element doesn´t exist.nn");
break;
default:
printf("Invalid choice.nn");
instructions();
break;
}
}
printf("? ");
scanf("%d", &choice);
}
printf("End of run.n");
return 0;
}
void instructions(void) {
printf(
"Enter your choice:n"
"1 to insert an element into the list.n"
"2 to delete an element from the list.n"
"3 to end.n");
}
char delete(LISTNODEPTR *sPtr, char value) {
LISTNODEPTR previousPtr, currentPtr, tempPtr;
// if (value == (*sPtr)->data){
if (value == (*sPtr)->data) {
tempPtr = *sPtr;
*sPtr = (*sPtr)->nextPtr;
free(tempPtr);
return value;
} else {
previousPtr = *sPtr;
currentPtr = (*sPtr)->nextPtr;
while (currentPtr != NULL && currentPtr->data != value) {
previousPtr = currentPtr;
currentPtr = currentPtr->nextPtr;
}
if (currentPtr != NULL) {
tempPtr = currentPtr;
previousPtr->nextPtr = currentPtr->nextPtr;
free(tempPtr);
return value;
}
}
return '';
}
int isEmpty(LISTNODEPTR sPtr) { return sPtr == NULL; }
void printList(LISTNODEPTR currentPtr)
{
if (currentPtr == NULL) printf("List is empty. nn");
while (currentPtr != NULL) {
printf("%p %c -->", currentPtr, currentPtr->data);
currentPtr = currentPtr->nextPtr;
}
printf("NULLnn");
}
LISTNODE *addtoList(LISTNODE *sPtr, char value)
{
LISTNODE* temp = malloc(sizeof(LISTNODE));
if(temp == NULL) 
{
printf("%d not inserted. No memory available.n", value);
exit(0);
}
else
{
temp->data = value;
temp->nextPtr = NULL;       
}
if(sPtr == NULL)
{
sPtr = temp;
return sPtr;
}
else
if(sPtr != NULL && sPtr->nextPtr == NULL) 
{
sPtr->nextPtr = temp;
return sPtr;
}
else
if (sPtr != NULL && sPtr->nextPtr != NULL) 
{
LISTNODE* Head = sPtr;
while(Head->nextPtr != NULL)
{
Head = Head->nextPtr;
}
Head->nextPtr = temp;
return sPtr;
}
else
{
printf("Unknown state of Listnn");
exit(0);
}
}

Answer 1

使用循环列表跟踪尾部似乎具有最少的特殊情况，并且允许在O(1)中在前面或后面插入和删除前面。删除一个节点需要获取它们之前的节点。因此，迭代最好使用存储的指向前一个节点的指针来完成。

所以我做了2个结构体:一个ListNode，它保存了一个指向下一个节点和数据的指针。还有一个List，它保存着一个指向列表尾部的指针。尽管在循环列表中尾部是任意的

在需要更新List.tail的情况下，总是通过传递List *来完成对列表的操作。不改变列表的操作取const List *，如printList()。

#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct ListNode
{
struct ListNode *next;
char data;
} ListNode;
typedef struct List
{
ListNode *tail;
} List;
bool isEmpty(const List *list)
{
return list->tail == NULL;
}
void printList(const List *list)
{
if (isEmpty(list)) {
printf("List is empty.nn");
return;
}
// iteration works by keeping a pointer to the previous node
// so we start at the tail to print the first node
// it ends when the tail has been visited
ListNode *p = list->tail;
do {
p = p->next;
printf("%p %c -->", p, p->data);
} while(p != list->tail);
printf("nn");
}
char delete(List *list, char value)
{
if (isEmpty(list)) return '';
ListNode *p = list->tail;
do {
ListNode *q = p->next;
if (q->data == value) {
// remove q from list
p->next = q->next;
// are we removing the last node?
if (p == q) list->tail = NULL;
// if q is the tail set the tail to the previous node
if (list->tail == q) list->tail = p;
free(q);
return value;
}
p = q;
} while(p != list->tail);
return '';
}
// add value to the end of the list
void insert(List *list, char value)
{
// allocate node
ListNode *node = malloc(sizeof(ListNode));
if (node == NULL) 
{
printf("'%c' not inserted. No memory available.n", value);
exit(0);
}
node->data = value;
// if list is empty point the tail at the new node
if (isEmpty(list)) {
list->tail = node;
}
// point the node at the head of the list
node->next = list->tail->next;
// point the tail node at the new node
list->tail->next = node;
// update the tail to the new node
list->tail = node;
}
void instructions(void);
int main() {
List list = { NULL };
int choice;
char item;
instructions();
do {
printf("? ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter a character: ");
scanf("n%c", &item);
insert(&list, item);
printList(&list);
break;
case 2:
if (!isEmpty(&list)) {
printf("Enter character to be deleted: ");
scanf("n%c", &item);
if (delete (&list, item)) {
printf("'%c' deleted from list.n", item);
printList(&list);
} else {
printf("'%c' not found in list.n", item);
}
} else {
printf("List is empty.nn");
}
break;
case 3:
break;
default:
printf("Invalid choice.nn");
instructions();
break;
}
} while (choice != 3);
printf("End of run.n");
return 0;
}
void instructions(void)
{
printf(
"Enter your choice:n"
"1 to insert an element into the list.n"
"2 to delete an element from the list.n"
"3 to end.n");
}