c - 为什么我的 C 循环双端队列程序无法退出打印功能？

Question

已关闭。此问题需要 debugging details 。目前不接受答案。

---

编辑问题以包含 desired behavior, a specific problem or error, and the shortest code necessary to reproduce the problem 。这将有助于其他人回答问题。

已关闭 6 年前。

Improve this question

我正在用 C 语言进行循环链表双端队列分配。代码运行良好并且输出符合预期，但由于某种原因在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;
 }

列表和链接结构:

 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

Answer 1

无法重现。这段代码工作得很好(修复内存泄漏留给读者练习)。此代码不会执行 circularListRemoveFront 和 circularListRemoveBack (因为您没有粘贴它们的代码)，因此很可能其中一个或两个都是罪魁祸首。

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

<小时/>

编辑:

在粘贴代码后添加了 circularListRemoveBack 和 circularListRemoveFront。代码有效，您一定有一些本地问题。请复制、粘贴和编译，尝试一下是否有效。

输出为:

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;
}