为什么我的 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 练习留下的内存泄漏)。此代码不执行 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;
}
我正在 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 练习留下的内存泄漏)。此代码不执行 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;
}