如何从双向链表中删除节点
how to delete node from doubly-linked list
我目前正在尝试从双向链表中删除一个节点,但是当只剩下一个项目时,它会在第 11 行 (*sPtr)->prevPtr = NULL;
上尝试删除它时抛出访问冲突异常。这是我当前的删除功能:
char del(ListNodePtr *sPtr, char value)
{
ListNodePtr previousPtr; /* pointer to previous node in list */
ListNodePtr currentPtr; /* pointer to current node in list */
ListNodePtr tempPtr; /* temporary node pointer */
/* delete first node */
if (value == (*sPtr)->data) {
tempPtr = *sPtr; /* hold onto node being removed */
*sPtr = (*sPtr)->nextPtr; /* de-thread the node */
(*sPtr)->prevPtr = NULL;
if ((*sPtr)->nextPtr != NULL) {
free(tempPtr); /* free the de-threaded node */
}
return value;
} /* end if */
else {
previousPtr = *sPtr;
currentPtr = (*sPtr)->nextPtr;
/* loop to find the correct location in the list */
while (currentPtr != NULL && currentPtr->data != value) {
previousPtr = currentPtr; /* walk to ... */
currentPtr = currentPtr->nextPtr; /* ... next node */
} /* end while */
/* delete node at currentPtr */
if (currentPtr != NULL) {
tempPtr = currentPtr;
previousPtr->nextPtr = currentPtr->nextPtr;
free(tempPtr);
return value;
} /* end if */
} /* end else */
return '[=10=]';
}
编辑:我将按照下面的顺序添加我的主要功能和我的打印功能,以便更好地了解我正在尝试做的事情,以便可以重新打开我的问题:
这是我的 listNode 结构的主要功能:
struct listNode {
char data; /* each listNode contains a character */
struct listNode *nextPtr; /* pointer to next node*/
struct listNode *prevPtr; /* pointer to previous node*/
}; /* end structure listNode */
typedef struct listNode ListNode; /* synonym for struct listNode */
typedef ListNode *ListNodePtr; /* synonym for ListNode* */
/* prototypes */
void insert(ListNodePtr *sPtr, char value);
char del(ListNodePtr *sPtr, char value);
int isEmpty(ListNodePtr sPtr);
void printList(ListNodePtr currentPtr);
void printReverse(ListNodePtr currentPtr);
void instructions(void);
int main(void)
{
ListNodePtr startPtr = NULL; /* initially there are no nodes */
int choice; /* user's choice */
char item; /* char entered by user */
instructions(); /* display the menu */
printf("? ");
scanf("%d", &choice);
/* loop while user does not choose 3 */
while (choice != 3) {
switch (choice) {
case 1:
printf("Enter a character: ");
scanf("\n%c", &item);
insert(&startPtr, item); /* insert item in list */
printList(startPtr);
printReverse(startPtr);
break;
case 2:
/* if list is not empty */
if (!isEmpty(startPtr)) {
printf("Enter character to be deleted: ");
scanf("\n%c", &item);
/* if character is found, remove it */
if (del(&startPtr, item)) { /* remove item */
printf("%c deleted.\n", item);
printList(startPtr);
printReverse(startPtr);
} /* end if */
else {
printf("%c not found.\n\n", item);
} /* end else */
} /* end if */
else {
printf("List is empty.\n\n");
} /* end else */
break;
default:
printf("Invalid choice.\n\n");
instructions();
break;
} /* end switch */
printf("? ");
scanf("%d", &choice);
} /* end while */
printf("End of run.\n");
return 0; /* indicates successful termination */
} /* end main */
这是我的 printReverse 和 printList 函数:
void printList(ListNodePtr currentPtr)
{
/* if list is empty */
if (currentPtr == NULL) {
printf("List is empty.\n\n");
} /* end if */
else {
printf("The list is:\n");
/* while not the end of the list */
while (currentPtr != NULL) {
printf("%c --> ", currentPtr->data);
currentPtr = currentPtr->nextPtr;
} /* end while */
printf("NULL\n\n");
} /* end else */
} /* end function printList */
void printReverse(ListNodePtr currentPtr)
{
/* if list is empty */
if (currentPtr == NULL) {
printf("List is empty.\n\n");
} /* end if */
else {
printf("The list in reverse is:\n");
while (currentPtr->nextPtr != NULL)
currentPtr = currentPtr->nextPtr;
/* while not the beginning of the list */
while (currentPtr != NULL) {
printf("%c --> ", currentPtr->data);
currentPtr = currentPtr->prevPtr;
} /* end while */
printf("NULL\n\n");
} /* end else */
} /* end function printList */
我真的希望这能让我更清楚地了解正在发生的一切,因为过去 3 天我一直坚持这个问题,而且我在网上几乎找不到任何话题来谈论如何做我的事情'我在做,因为列表在插入和删除时按字母顺序排序。
因此,如果有人可以尝试告诉我出了什么问题,以及为什么在尝试删除列表中的最后一项时它会在第 11 行抛出访问冲突异常,我将非常感激。谢谢!
我认为你把事情搞得太复杂了。您没有将 "list" 类型与 "node" 类型分开,但我认为如果您只是 return 替换,则无需传递指向指针的指针即可。
您可能想要编写一个 "find" 方法来处理查找字符和 return 指向该节点的指针。
/**
Delete the node containing value from the list starting with start.
If value is not found in list, then the list is unchanged. Returns
a replacement value for start, which may be needed if the value is
contain in the start node.
*/
ListNodePtr del(ListNodePtr start, char value)
{
ListNodePtr curr;
for (curr = start; curr && curr->data != value; curr = curr->nextPtr) {
// skip this node
}
if (!curr) {
// Value not found in list. List is unchanged.
return start;
}
/* Compute return value */
if (curr == start) {
start = start->nextPtr;
}
/* Remove curr node from chain */
if (curr->prevPtr) {
curr->prevPtr->nextPtr = curr->nextPtr;
}
if (curr->nextPtr) {
curr->nextPtr->prevPtr = curr->prevPtr;
}
free(curr);
return start;
}
我终于意识到我的问题了。 Visual Studio 不允许我使用断点,但那是因为我没有意识到我将它设置为 "Release" 而不是 "Debug"。为此,我跟踪了指针,找出它们在哪里断开链接或链接到错误的指针,并提出了这个解决方案:
/* Delete a list element */
char del(ListNodePtr *sPtr, char value)
{
ListNodePtr previousPtr; /* pointer to previous node in list */
ListNodePtr currentPtr; /* pointer to current node in list */
ListNodePtr tempPtr; /* temporary node pointer */
/* delete first node */
if (value == (*sPtr)->data) {
tempPtr = *sPtr; /* hold onto node being removed */
*sPtr = (*sPtr)->nextPtr; /* de-thread the node */
if(*sPtr != NULL) /* if the list is not empty */
(*sPtr)->prevPtr = NULL; /* the previos pointer is null*/
free(tempPtr); /* free the de-threaded node */
return value;
} /* end if */
else {
previousPtr = *sPtr;
currentPtr = (*sPtr)->nextPtr;
/* loop to find the correct location in the list */
while (currentPtr != NULL && currentPtr->data != value) {
previousPtr = currentPtr; /* walk to ... */
currentPtr = currentPtr->nextPtr; /* ... next node */
} /* end while */
/* delete node at currentPtr */
if (currentPtr != NULL) {
tempPtr = currentPtr;
previousPtr->nextPtr = currentPtr->nextPtr;
if(previousPtr->nextPtr != NULL) /* if the next pointer isn't null */
previousPtr->nextPtr->prevPtr = currentPtr->prevPtr; /* the previous pointer of the next pointer is the previous pointer of the current pointer */
free(tempPtr);
return value;
} /* end if */
} /* end else */
return '[=10=]';
} /* end function delete */
删除最后一个节点后,您的代码没有检查新头节点是否为空,因此当您尝试将头节点的下一个指针设置为空时,代码会崩溃。
固定代码(运行在valgrind
下无泄漏无错误):
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
struct listNode
{
char data;
struct listNode *nextPtr;
struct listNode *prevPtr;
};
typedef struct listNode ListNode;
typedef ListNode *ListNodePtr;
void insert(ListNodePtr *sPtr, char value);
char del(ListNodePtr *sPtr, char value);
int isEmpty(ListNodePtr sPtr);
void printList(ListNodePtr currentPtr);
void printReverse(ListNodePtr currentPtr);
static void ins_check(ListNode **list, char c)
{
printf("Inserting [%c] (%p)\n", c, (void *)*list);
insert(list, c);
printList(*list);
printReverse(*list);
}
static void del_check(ListNode **list, char c)
{
printf("Deleting [%c] (%p)\n", c, (void *)*list);
if (del(list, c) != c)
printf("Did not find [%c] in list.\n", c);
printList(*list);
printReverse(*list);
}
int main(void)
{
ListNodePtr startPtr = NULL;
printList(startPtr);
printReverse(startPtr);
ins_check(&startPtr, 'a');
ins_check(&startPtr, 'b');
ins_check(&startPtr, 'c');
del_check(&startPtr, 'c');
del_check(&startPtr, 'a');
del_check(&startPtr, 'b');
assert(startPtr == 0);
printf("End of run.\n");
return 0;
}
void printList(ListNodePtr currentPtr)
{
if (currentPtr == NULL)
printf("List is empty.\n");
else
{
printf("The list is: ");
while (currentPtr != NULL)
{
printf("%c --> ", currentPtr->data);
currentPtr = currentPtr->nextPtr;
}
printf("NULL\n");
}
}
void printReverse(ListNodePtr currentPtr)
{
if (currentPtr == NULL)
printf("List is empty (even in reverse).\n");
else
{
printf("The list in reverse is: ");
while (currentPtr->nextPtr != NULL)
currentPtr = currentPtr->nextPtr;
while (currentPtr != NULL)
{
printf("%c --> ", currentPtr->data);
currentPtr = currentPtr->prevPtr;
}
printf("NULL\n");
}
}
char del(ListNodePtr *sPtr, char value)
{
ListNodePtr previousPtr;
ListNodePtr currentPtr;
ListNodePtr tempPtr;
assert(*sPtr != 0);
if (value == (*sPtr)->data)
{
tempPtr = *sPtr;
printf("Deleting 1: [%c] (node = %p, next = %p, prev = %p\n", tempPtr->data,
(void *)tempPtr, (void *)tempPtr->nextPtr, (void *)tempPtr->prevPtr);
*sPtr = (*sPtr)->nextPtr;
if (*sPtr != 0) // Crucial change!
(*sPtr)->prevPtr = NULL;
free(tempPtr);
return value;
}
else
{
previousPtr = *sPtr;
currentPtr = (*sPtr)->nextPtr;
while (currentPtr != NULL && currentPtr->data != value)
{
previousPtr = currentPtr;
currentPtr = currentPtr->nextPtr;
}
if (currentPtr != NULL)
{
assert(previousPtr != 0);
tempPtr = currentPtr;
printf("Deleting 2: [%c] (node = %p, next = %p, prev = %p\n", tempPtr->data,
(void *)tempPtr, (void *)tempPtr->nextPtr, (void *)tempPtr->prevPtr);
previousPtr->nextPtr = currentPtr->nextPtr;
free(tempPtr);
return value;
}
else
printf("Did not find [%c]\n", value);
}
return '[=10=]';
}
void insert(ListNode **list, char value)
{
ListNode *node = malloc(sizeof(*node));
if (node == 0)
{
fprintf(stderr, "Out of memory\n");
exit(EXIT_FAILURE);
}
node->data = value;
node->nextPtr = 0;
node->prevPtr = 0;
if (*list != 0)
{
node->nextPtr = *list;
assert((*list)->prevPtr == 0);
(*list)->prevPtr = node;
}
*list = node;
}
示例运行:
List is empty.
List is empty (even in reverse).
Inserting [a] (0x0)
The list is: a --> NULL
The list in reverse is: a --> NULL
Inserting [b] (0x7fccc3503070)
The list is: b --> a --> NULL
The list in reverse is: a --> b --> NULL
Inserting [c] (0x7fccc3503090)
The list is: c --> b --> a --> NULL
The list in reverse is: a --> b --> c --> NULL
Deleting [c] (0x7fccc35030b0)
Deleting 1: [c] (node = 0x7fccc35030b0, next = 0x7fccc3503090, prev = 0x0
The list is: b --> a --> NULL
The list in reverse is: a --> b --> NULL
Deleting [a] (0x7fccc3503090)
Deleting 2: [a] (node = 0x7fccc3503070, next = 0x0, prev = 0x7fccc3503090
The list is: b --> NULL
The list in reverse is: b --> NULL
Deleting [b] (0x7fccc3503090)
Deleting 1: [b] (node = 0x7fccc3503090, next = 0x0, prev = 0x0
List is empty.
List is empty (even in reverse).
End of run.
注意包装函数(ins_check()
和 del_check()
)的使用和固定数据的使用,以便于测试(无需输入)。还要注意正在发生的事情的打印。
我希望您的 insert()
与我设计的有点相似——真正的 MCVE (How to create a Minimal, Complete, and Verifiable Example?) or SSCCE (Short, Self-Contained, Correct Example) 会提供该功能。
请注意,'new' 代码遵循 Is it a good idea to typedef
pointers 建议的限制——简洁的答案是 "No"(对于非不透明数据指针)。
请注意,对于单向链表,您的删除函数尽可能复杂,但可以简单得多,因为双向链表中的每个节点都知道自己的前任节点。这个版本也可以正常工作:
char del(ListNodePtr *sPtr, char value)
{
assert(*sPtr != 0);
ListNode *curr = *sPtr;
while (curr != NULL)
{
if (curr->data == value)
{
if (curr->prevPtr != NULL)
curr->prevPtr->nextPtr = curr->nextPtr;
if (curr->nextPtr != NULL)
curr->nextPtr->prevPtr = curr->prevPtr;
if (*sPtr == curr)
*sPtr = curr->nextPtr;
free(curr);
return value;
}
curr = curr->nextPtr;
}
printf("Did not find [%c]\n", value);
return '[=12=]';
}
我目前正在尝试从双向链表中删除一个节点,但是当只剩下一个项目时,它会在第 11 行 (*sPtr)->prevPtr = NULL;
上尝试删除它时抛出访问冲突异常。这是我当前的删除功能:
char del(ListNodePtr *sPtr, char value)
{
ListNodePtr previousPtr; /* pointer to previous node in list */
ListNodePtr currentPtr; /* pointer to current node in list */
ListNodePtr tempPtr; /* temporary node pointer */
/* delete first node */
if (value == (*sPtr)->data) {
tempPtr = *sPtr; /* hold onto node being removed */
*sPtr = (*sPtr)->nextPtr; /* de-thread the node */
(*sPtr)->prevPtr = NULL;
if ((*sPtr)->nextPtr != NULL) {
free(tempPtr); /* free the de-threaded node */
}
return value;
} /* end if */
else {
previousPtr = *sPtr;
currentPtr = (*sPtr)->nextPtr;
/* loop to find the correct location in the list */
while (currentPtr != NULL && currentPtr->data != value) {
previousPtr = currentPtr; /* walk to ... */
currentPtr = currentPtr->nextPtr; /* ... next node */
} /* end while */
/* delete node at currentPtr */
if (currentPtr != NULL) {
tempPtr = currentPtr;
previousPtr->nextPtr = currentPtr->nextPtr;
free(tempPtr);
return value;
} /* end if */
} /* end else */
return '[=10=]';
}
编辑:我将按照下面的顺序添加我的主要功能和我的打印功能,以便更好地了解我正在尝试做的事情,以便可以重新打开我的问题:
这是我的 listNode 结构的主要功能:
struct listNode {
char data; /* each listNode contains a character */
struct listNode *nextPtr; /* pointer to next node*/
struct listNode *prevPtr; /* pointer to previous node*/
}; /* end structure listNode */
typedef struct listNode ListNode; /* synonym for struct listNode */
typedef ListNode *ListNodePtr; /* synonym for ListNode* */
/* prototypes */
void insert(ListNodePtr *sPtr, char value);
char del(ListNodePtr *sPtr, char value);
int isEmpty(ListNodePtr sPtr);
void printList(ListNodePtr currentPtr);
void printReverse(ListNodePtr currentPtr);
void instructions(void);
int main(void)
{
ListNodePtr startPtr = NULL; /* initially there are no nodes */
int choice; /* user's choice */
char item; /* char entered by user */
instructions(); /* display the menu */
printf("? ");
scanf("%d", &choice);
/* loop while user does not choose 3 */
while (choice != 3) {
switch (choice) {
case 1:
printf("Enter a character: ");
scanf("\n%c", &item);
insert(&startPtr, item); /* insert item in list */
printList(startPtr);
printReverse(startPtr);
break;
case 2:
/* if list is not empty */
if (!isEmpty(startPtr)) {
printf("Enter character to be deleted: ");
scanf("\n%c", &item);
/* if character is found, remove it */
if (del(&startPtr, item)) { /* remove item */
printf("%c deleted.\n", item);
printList(startPtr);
printReverse(startPtr);
} /* end if */
else {
printf("%c not found.\n\n", item);
} /* end else */
} /* end if */
else {
printf("List is empty.\n\n");
} /* end else */
break;
default:
printf("Invalid choice.\n\n");
instructions();
break;
} /* end switch */
printf("? ");
scanf("%d", &choice);
} /* end while */
printf("End of run.\n");
return 0; /* indicates successful termination */
} /* end main */
这是我的 printReverse 和 printList 函数:
void printList(ListNodePtr currentPtr)
{
/* if list is empty */
if (currentPtr == NULL) {
printf("List is empty.\n\n");
} /* end if */
else {
printf("The list is:\n");
/* while not the end of the list */
while (currentPtr != NULL) {
printf("%c --> ", currentPtr->data);
currentPtr = currentPtr->nextPtr;
} /* end while */
printf("NULL\n\n");
} /* end else */
} /* end function printList */
void printReverse(ListNodePtr currentPtr)
{
/* if list is empty */
if (currentPtr == NULL) {
printf("List is empty.\n\n");
} /* end if */
else {
printf("The list in reverse is:\n");
while (currentPtr->nextPtr != NULL)
currentPtr = currentPtr->nextPtr;
/* while not the beginning of the list */
while (currentPtr != NULL) {
printf("%c --> ", currentPtr->data);
currentPtr = currentPtr->prevPtr;
} /* end while */
printf("NULL\n\n");
} /* end else */
} /* end function printList */
我真的希望这能让我更清楚地了解正在发生的一切,因为过去 3 天我一直坚持这个问题,而且我在网上几乎找不到任何话题来谈论如何做我的事情'我在做,因为列表在插入和删除时按字母顺序排序。
因此,如果有人可以尝试告诉我出了什么问题,以及为什么在尝试删除列表中的最后一项时它会在第 11 行抛出访问冲突异常,我将非常感激。谢谢!
我认为你把事情搞得太复杂了。您没有将 "list" 类型与 "node" 类型分开,但我认为如果您只是 return 替换,则无需传递指向指针的指针即可。
您可能想要编写一个 "find" 方法来处理查找字符和 return 指向该节点的指针。
/**
Delete the node containing value from the list starting with start.
If value is not found in list, then the list is unchanged. Returns
a replacement value for start, which may be needed if the value is
contain in the start node.
*/
ListNodePtr del(ListNodePtr start, char value)
{
ListNodePtr curr;
for (curr = start; curr && curr->data != value; curr = curr->nextPtr) {
// skip this node
}
if (!curr) {
// Value not found in list. List is unchanged.
return start;
}
/* Compute return value */
if (curr == start) {
start = start->nextPtr;
}
/* Remove curr node from chain */
if (curr->prevPtr) {
curr->prevPtr->nextPtr = curr->nextPtr;
}
if (curr->nextPtr) {
curr->nextPtr->prevPtr = curr->prevPtr;
}
free(curr);
return start;
}
我终于意识到我的问题了。 Visual Studio 不允许我使用断点,但那是因为我没有意识到我将它设置为 "Release" 而不是 "Debug"。为此,我跟踪了指针,找出它们在哪里断开链接或链接到错误的指针,并提出了这个解决方案:
/* Delete a list element */
char del(ListNodePtr *sPtr, char value)
{
ListNodePtr previousPtr; /* pointer to previous node in list */
ListNodePtr currentPtr; /* pointer to current node in list */
ListNodePtr tempPtr; /* temporary node pointer */
/* delete first node */
if (value == (*sPtr)->data) {
tempPtr = *sPtr; /* hold onto node being removed */
*sPtr = (*sPtr)->nextPtr; /* de-thread the node */
if(*sPtr != NULL) /* if the list is not empty */
(*sPtr)->prevPtr = NULL; /* the previos pointer is null*/
free(tempPtr); /* free the de-threaded node */
return value;
} /* end if */
else {
previousPtr = *sPtr;
currentPtr = (*sPtr)->nextPtr;
/* loop to find the correct location in the list */
while (currentPtr != NULL && currentPtr->data != value) {
previousPtr = currentPtr; /* walk to ... */
currentPtr = currentPtr->nextPtr; /* ... next node */
} /* end while */
/* delete node at currentPtr */
if (currentPtr != NULL) {
tempPtr = currentPtr;
previousPtr->nextPtr = currentPtr->nextPtr;
if(previousPtr->nextPtr != NULL) /* if the next pointer isn't null */
previousPtr->nextPtr->prevPtr = currentPtr->prevPtr; /* the previous pointer of the next pointer is the previous pointer of the current pointer */
free(tempPtr);
return value;
} /* end if */
} /* end else */
return '[=10=]';
} /* end function delete */
删除最后一个节点后,您的代码没有检查新头节点是否为空,因此当您尝试将头节点的下一个指针设置为空时,代码会崩溃。
固定代码(运行在valgrind
下无泄漏无错误):
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
struct listNode
{
char data;
struct listNode *nextPtr;
struct listNode *prevPtr;
};
typedef struct listNode ListNode;
typedef ListNode *ListNodePtr;
void insert(ListNodePtr *sPtr, char value);
char del(ListNodePtr *sPtr, char value);
int isEmpty(ListNodePtr sPtr);
void printList(ListNodePtr currentPtr);
void printReverse(ListNodePtr currentPtr);
static void ins_check(ListNode **list, char c)
{
printf("Inserting [%c] (%p)\n", c, (void *)*list);
insert(list, c);
printList(*list);
printReverse(*list);
}
static void del_check(ListNode **list, char c)
{
printf("Deleting [%c] (%p)\n", c, (void *)*list);
if (del(list, c) != c)
printf("Did not find [%c] in list.\n", c);
printList(*list);
printReverse(*list);
}
int main(void)
{
ListNodePtr startPtr = NULL;
printList(startPtr);
printReverse(startPtr);
ins_check(&startPtr, 'a');
ins_check(&startPtr, 'b');
ins_check(&startPtr, 'c');
del_check(&startPtr, 'c');
del_check(&startPtr, 'a');
del_check(&startPtr, 'b');
assert(startPtr == 0);
printf("End of run.\n");
return 0;
}
void printList(ListNodePtr currentPtr)
{
if (currentPtr == NULL)
printf("List is empty.\n");
else
{
printf("The list is: ");
while (currentPtr != NULL)
{
printf("%c --> ", currentPtr->data);
currentPtr = currentPtr->nextPtr;
}
printf("NULL\n");
}
}
void printReverse(ListNodePtr currentPtr)
{
if (currentPtr == NULL)
printf("List is empty (even in reverse).\n");
else
{
printf("The list in reverse is: ");
while (currentPtr->nextPtr != NULL)
currentPtr = currentPtr->nextPtr;
while (currentPtr != NULL)
{
printf("%c --> ", currentPtr->data);
currentPtr = currentPtr->prevPtr;
}
printf("NULL\n");
}
}
char del(ListNodePtr *sPtr, char value)
{
ListNodePtr previousPtr;
ListNodePtr currentPtr;
ListNodePtr tempPtr;
assert(*sPtr != 0);
if (value == (*sPtr)->data)
{
tempPtr = *sPtr;
printf("Deleting 1: [%c] (node = %p, next = %p, prev = %p\n", tempPtr->data,
(void *)tempPtr, (void *)tempPtr->nextPtr, (void *)tempPtr->prevPtr);
*sPtr = (*sPtr)->nextPtr;
if (*sPtr != 0) // Crucial change!
(*sPtr)->prevPtr = NULL;
free(tempPtr);
return value;
}
else
{
previousPtr = *sPtr;
currentPtr = (*sPtr)->nextPtr;
while (currentPtr != NULL && currentPtr->data != value)
{
previousPtr = currentPtr;
currentPtr = currentPtr->nextPtr;
}
if (currentPtr != NULL)
{
assert(previousPtr != 0);
tempPtr = currentPtr;
printf("Deleting 2: [%c] (node = %p, next = %p, prev = %p\n", tempPtr->data,
(void *)tempPtr, (void *)tempPtr->nextPtr, (void *)tempPtr->prevPtr);
previousPtr->nextPtr = currentPtr->nextPtr;
free(tempPtr);
return value;
}
else
printf("Did not find [%c]\n", value);
}
return '[=10=]';
}
void insert(ListNode **list, char value)
{
ListNode *node = malloc(sizeof(*node));
if (node == 0)
{
fprintf(stderr, "Out of memory\n");
exit(EXIT_FAILURE);
}
node->data = value;
node->nextPtr = 0;
node->prevPtr = 0;
if (*list != 0)
{
node->nextPtr = *list;
assert((*list)->prevPtr == 0);
(*list)->prevPtr = node;
}
*list = node;
}
示例运行:
List is empty.
List is empty (even in reverse).
Inserting [a] (0x0)
The list is: a --> NULL
The list in reverse is: a --> NULL
Inserting [b] (0x7fccc3503070)
The list is: b --> a --> NULL
The list in reverse is: a --> b --> NULL
Inserting [c] (0x7fccc3503090)
The list is: c --> b --> a --> NULL
The list in reverse is: a --> b --> c --> NULL
Deleting [c] (0x7fccc35030b0)
Deleting 1: [c] (node = 0x7fccc35030b0, next = 0x7fccc3503090, prev = 0x0
The list is: b --> a --> NULL
The list in reverse is: a --> b --> NULL
Deleting [a] (0x7fccc3503090)
Deleting 2: [a] (node = 0x7fccc3503070, next = 0x0, prev = 0x7fccc3503090
The list is: b --> NULL
The list in reverse is: b --> NULL
Deleting [b] (0x7fccc3503090)
Deleting 1: [b] (node = 0x7fccc3503090, next = 0x0, prev = 0x0
List is empty.
List is empty (even in reverse).
End of run.
注意包装函数(ins_check()
和 del_check()
)的使用和固定数据的使用,以便于测试(无需输入)。还要注意正在发生的事情的打印。
我希望您的 insert()
与我设计的有点相似——真正的 MCVE (How to create a Minimal, Complete, and Verifiable Example?) or SSCCE (Short, Self-Contained, Correct Example) 会提供该功能。
请注意,'new' 代码遵循 Is it a good idea to typedef
pointers 建议的限制——简洁的答案是 "No"(对于非不透明数据指针)。
请注意,对于单向链表,您的删除函数尽可能复杂,但可以简单得多,因为双向链表中的每个节点都知道自己的前任节点。这个版本也可以正常工作:
char del(ListNodePtr *sPtr, char value)
{
assert(*sPtr != 0);
ListNode *curr = *sPtr;
while (curr != NULL)
{
if (curr->data == value)
{
if (curr->prevPtr != NULL)
curr->prevPtr->nextPtr = curr->nextPtr;
if (curr->nextPtr != NULL)
curr->nextPtr->prevPtr = curr->prevPtr;
if (*sPtr == curr)
*sPtr = curr->nextPtr;
free(curr);
return value;
}
curr = curr->nextPtr;
}
printf("Did not find [%c]\n", value);
return '[=12=]';
}