按字母顺序插入双向链表

Question

我目前正在尝试创建一个双向链表，按字母顺序对插入的 char 值进行排序，但是由于用于比较数据值的循环，它没有正确更新以前的节点。

这是我当前的插入代码：

void insert(ListNodePtr *sPtr, char value)
{
    ListNodePtr newPtr; /* pointer to new node */
    ListNodePtr previousPtr; /* pointer to previous node in list */
    ListNodePtr currentPtr; /* pointer to current node in list */

    newPtr = (ListNode*)malloc(sizeof(ListNode)); /* create node */

    if (newPtr != NULL) { /* is space available */
        newPtr->data = value; /* place value in node */
        newPtr->nextPtr = NULL; /* node does not link to another node */
        newPtr->prevPtr = NULL;

        previousPtr = NULL;
        currentPtr = *sPtr;

        /* loop to find the correct location in the list */
        while (currentPtr != NULL && value > currentPtr->data) {
            previousPtr = currentPtr; /* walk to ...   */
            currentPtr = currentPtr->nextPtr; /* ... next node */
        } /* end while */

          /* insert new node at beginning of list */
        if (previousPtr == NULL) {
            newPtr->nextPtr = *sPtr;
            *sPtr = newPtr;
        } /* end if */
        else { /* insert new node between previousPtr and currentPtr */
            previousPtr->nextPtr = newPtr;
            newPtr->prevPtr = previousPtr;
            newPtr->nextPtr = currentPtr;
        } /* end else */
    } /* end if */
    else {
        printf("%c not inserted. No memory available.\n", value);
    } /* end else */
} /* end function insert */

这是我的节点结构：

/* self-referential structure */
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* */

这是我的打印功能：

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 */

这是我得到的输出：

output when entering chars in ascending order of ASCII value 正常工作

but when I add a larger value and then a value smaller than that one 它不会打印正确的先前值。

过去几天我一直在研究这个问题，试图弄清楚该怎么做，但我找不到其他人遇到过的任何相关情况，所以我很感激能得到任何帮助。谢谢！

P.S。这是一个硬件作业，我通常不会寻求帮助，但是这本书没有提到双向链表，更没有提到如何用它们按字母顺序插入数据，所以我现在真的很想寻求帮助，我我会很乐意利用任何我能得到的信息为我指明正确的方向！

Answer 1

你忘记给一个指针赋值了。由于这是一项硬件作业，我只会给你一个提示。考虑所有插入的情况。您应该计算四种情况，具体取决于 previousPtr 和 currentPtr 是否在 insert 函数中的 while 循环之后 NULL：

previousPtr和currentPtr都是NULL。（空列表）
只有 previousPtr 是 NULL。（您正在添加到列表中）
只有currentPtr是NULL。（您正在追加到列表中）
previousPtr 和 currentPtr 都不是 NULL。（在两个现有节点之间插入）

您的代码正确处理了案例 1-3，但在案例 4 上失败了，因为您没有分配所有需要分配的指针。对于双向链表，情况 4 需要分配四个指针：previousPtr->next、newNode->prevPtr、newNode->nextPtr 和 ?????。

按字母顺序插入双向链表

alphabetically sorted insertion into doubly-linked list

c

doubly-linked-list