为什么我的 C、Circular Deque 程序不会退出打印功能?

Why won't my C, Circular Deque program exit the print function?

我正在 C 中执行 Circular Linked List Deque 赋值。代码运行良好并且输出符合预期,但由于某些原因在 circularListReverse()

之后
void circularListReverse(struct CircularList* list)
{
     assert(!circularListIsEmpty(list));

     struct Link *curLink;
     struct Link *tempLink;

     curLink = list->sentinel;

     do {
         tempLink = curLink->next;
         curLink->next = curLink->prev;
         curLink->prev = tempLink;
         curLink = tempLink;
     } while (curLink != list->sentinel);
}

在列表上调用,circularListPrint()

void circularListPrint(struct CircularList* list)
 {
     assert(!circularListIsEmpty(list));
     struct Link *newLink = list->sentinel->next;
     while(newLink != list->sentinel) {
         printf("%g ", newLink->value);
         newLink = newLink->next;
     }
     printf("\n");  //This prints, so it exits the loop
 } 

函数在打印所有预期结果后挂起。经过几个小时的故障排除后,我发现程序退出了执行打印的 while 循环,但没有退出该功能。在调用反向函数之前,此函数确实可以正常工作。为什么挂了?

驱动如下:

 #include "circularList.h"
 #include <stdio.h>

 int main()
 {  
     struct CircularList* deque = circularListCreate(); 
     circularListAddBack(deque, (TYPE)1);
     circularListAddBack(deque, (TYPE)2);
     circularListAddBack(deque, (TYPE)3);
     circularListAddFront(deque, (TYPE)4);
     circularListAddFront(deque, (TYPE)5);
     circularListAddFront(deque, (TYPE)6);
     circularListPrint(deque);                //Works fine
     printf("%g\n", circularListFront(deque));
     printf("%g\n", circularListBack(deque));

     circularListRemoveFront(deque);
     circularListRemoveBack(deque);
     circularListPrint(deque);

     circularListReverse(deque);
     circularListPrint(deque);  //HANGS

     //Debug
     printf("\nEnd of print\n"); //This does NOT print, so function never exits

     circularListDestroy(deque);

    return 0;
 }

列表和Link结构:

 struct Link
 {
     TYPE value;
     struct Link * next;
     struct Link * prev;
 };

 struct CircularList
 {
     int size;
     struct Link* sentinel;
 };

添加函数:

 static void addLinkAfter(struct CircularList* list, struct Link* link, TYPE value)
 {
     assert(link != NULL);
     struct Link *newLink = createLink(value);
     newLink->prev = link;
     newLink->next = link->next;

     newLink->next->prev = newLink;
     link->next = newLink;

     list->size++;
 }

 /**
  * Adds a new link with the given value to the front of the deque.
  */
 void circularListAddFront(struct CircularList* list, TYPE value)
 {
     assert(list != NULL);
     addLinkAfter(list, list->sentinel, value);
 }

 /**
  * Adds a new link with the given value to the back of the deque.
  */
 void circularListAddBack(struct CircularList* list, TYPE value)
 {
     assert(list != NULL);
     addLinkAfter(list, list->sentinel->prev, value);
 }

创建循环列表:

 /**
  * Allocates and initializes a list.
  */
 struct CircularList* circularListCreate()
 {
     struct CircularList* list = malloc(sizeof(struct CircularList));
     init(list);
     return list;
 }

 /**
  * Allocates the list's sentinel and sets the size to 0.
  * The sentinel's next and prev should point to the sentinel itself.
  */
 static void init(struct CircularList* list)
 {
     assert(list != 0);

     list->sentinel = (struct Link *)malloc(sizeof(struct Link));
     assert(list->sentinel != 0);

     list->sentinel->next = list->sentinel;
     list->sentinel->prev = list->sentinel;
     list->size = 0;
     list->sentinel->value = 0;
 }

删除:

 static void removeLink(struct CircularList* list, struct Link* link)
 {
     // FIXME: you must write this
     assert(!circularListIsEmpty(list));
     assert(link != NULL);
     link->prev->next = link->next;
     link->next->prev = link->prev;
     free(link);
     list->size--;
 }

 /**
  * Removes the link at the front of the deque.
  */
 void circularListRemoveFront(struct CircularList* list)
 {
     assert(!circularListIsEmpty(list));
     removeLink(list, list->sentinel->next);

 }

 /**
  * Removes the link at the back of the deque.
  */
 void circularListRemoveBack(struct CircularList* list)
 {
     assert(!circularListIsEmpty(list));
     removeLink(list, list->sentinel->prev);
 }

输出为

 6 5 4 1 2 3
 6
 3
 5 4 1 2
 2 1 4 5
 //Cursor sits here and program doesn't exit

无法重现。这段代码工作正常(修复 reader 练习留下的内存泄漏)。此代码不执行 circularListRemoveFrontcircularListRemoveBack(因为您没有粘贴它们的代码),因此它们中的一个或两个可能是罪魁祸首。

我的代码与 circularListCreate 实现不同(最初没有粘贴它的代码)但这不太可能是问题所在。


编辑:

在粘贴代码后添加了 circularListRemoveBackcircularListRemoveFront。代码有效,您一定有一些本地问题。请复制粘贴编译,试试是否可行。

输出为:

6 5 4 1 2 3

5 4 1 2

2 1 4 5

#include <stdio.h>
#include <stdlib.h>

#define TYPE double
struct Link
 {
     double value;
     struct Link * next;
     struct Link * prev;
 };

 struct CircularList
 {
     int size; 
     struct Link* sentinel;
 };
 
 void circularListReverse(struct CircularList* list)
 {
     struct Link *curLink;
     struct Link *tempLink;

     curLink = list->sentinel;

     do {
         tempLink = curLink->next;
         curLink->next = curLink->prev;
         curLink->prev = tempLink;
         curLink = tempLink;
     } while (curLink != list->sentinel);
}
void circularListPrint(struct CircularList* list)
 {
     struct Link *newLink = list->sentinel->next;
     while(newLink != list->sentinel) {
         printf("%g ", newLink->value);
         newLink = newLink->next;
     }
     printf("\n");  //This prints, so it exits the loop
 } 

struct Link* createLink(TYPE value)
{
    struct Link *l = malloc(sizeof(struct Link));
    l->value = value;
    return l;
}

static void addLinkAfter(struct CircularList* list, struct Link* link, TYPE value)
 {
     struct Link *newLink = createLink(value);
     newLink->prev = link;
     newLink->next = link->next;

     newLink->next->prev = newLink;
     link->next = newLink;

     list->size++;
 }

 /**
  * Adds a new link with the given value to the front of the deque.
  */
 void circularListAddFront(struct CircularList* list, TYPE value)
 {
     addLinkAfter(list, list->sentinel, value);
 }

 /**
  * Adds a new link with the given value to the back of the deque.
  */
 void circularListAddBack(struct CircularList* list, TYPE value)
 {
     addLinkAfter(list, list->sentinel->prev, value);
 }

static void removeLink(struct CircularList *list, struct Link *link)
{
    link->prev->next = link->next;
    link->next->prev = link->prev;
    free(link);
    list->size--;
}

 void circularListRemoveBack(struct CircularList* list)
{
    removeLink(list, list->sentinel->prev);
}

 void circularListRemoveFront(struct CircularList* list)
{
    removeLink(list, list->sentinel->next);
}

struct CircularList* create()
{
    struct CircularList *l = malloc(sizeof(*l));
    l->sentinel = malloc(sizeof(*l->sentinel));
    l->sentinel->prev = l->sentinel->next = l->sentinel;
    l->size = l->sentinel->value = 0;
}
int main(void) {
     struct CircularList* deque = create();
     circularListAddBack(deque, (TYPE)1);
     circularListAddBack(deque, (TYPE)2);
     circularListAddBack(deque, (TYPE)3);
     circularListAddFront(deque, (TYPE)4);
     circularListAddFront(deque, (TYPE)5);
     circularListAddFront(deque, (TYPE)6);
     circularListPrint(deque);                //Works fine

     circularListRemoveFront(deque);
     circularListRemoveBack(deque);
     circularListPrint(deque);
     
     circularListReverse(deque);
     circularListPrint(deque);  //HANGS

     //Debug
     printf("\nEnd of print\n"); //This does NOT print, so function never exits

    return 0;
}