代码之家 › 专栏 › 技术社区 › Andrea Colo

使用尾部指针在链表末尾插入,然后打印链表会导致无限循环

tail infinite-loop linked-list pointers c

Andrea Colo · 技术社区 · 7 年前

我正在创建一个程序: 1) 阅读一些以“STOP”结尾的单词 2) 使用尾部指针在链表的末尾插入它们中的每一个 3) 然后打印每个单词

当我尝试打印列表时,输出是第一个插入单词的无限循环。

 //max len of a word in input
#define WORD 20 

//define a node for a linked list
typedef struct node_l{
    char string[WORD+1];
    struct node_l *next;
}Node_L;

Node_L *newNode_L(char *word);
char *readword(void);
void printList(Node_L *list);
void insertNode_L(Node_L **list, Node_L **tail, char *word);
int main(){
    Node_L *root = NULL;
    Node_L *tail = NULL;
    char *word = readword();
    while(strcmp(word,"STOP")!=0){
        insertNode_L(&root,&tail, word);
        word = readword();
    }
    printList(root);
    return 0;
}

/*given head and tail pointer and a word:
    -creates a node containing the word
    -insert at the end of the linked list
*/
void insertNode_L(Node_L **list, Node_L **tail, char *word){
    Node_L *temp = newNode_L(word);
    if(*list==NULL){
        *tail = *list = temp;
    }else{
        Node_L *t = *tail;
        t->next = *tail;
        *tail = temp;
    }
}

//given a word returns a new node(linked list type) containing that word
Node_L *newNode_L(char *word){
    Node_L *node = malloc(sizeof(Node_L));
    if(node==NULL){
        printf("malloc failure\n");
        exit(EXIT_FAILURE);
    }
    strcpy(node->string, word);
    node->next = NULL;
    return node;
}

/*function that: 
    -first skips non alphabetical characters
    -reads every char until a not alphabetical character is inserted
    -returns a pointer to the first char of the new created string
*/
char *readword(void){
    int startWlen = 2;
    char *word= malloc(startWlen);
    //skips whitespace and char that are not alphabetical
    int c = getchar();
    while(!isalpha(c)){
        c = getchar();
    }
    int i=0;
    while(isalpha(c)){
        //realloc if necessary
        if(i==startWlen){
            startWlen*=2;
            char *temp = realloc(word, startWlen);
            if(temp==NULL){
                printf("realloc failure\n");
                exit(EXIT_FAILURE);
            }
            word = temp;
        }
        word[i]=c;
        i++;
        c = getchar();
    }
    //realloc if necessary for '\0' char
    if(i==startWlen){
        startWlen+=1;
        char *p =realloc(word,startWlen+1);
        if (p == NULL){
            printf("realloc failure\n");
            exit(EXIT_FAILURE);
        }else{
            word = p;
        }
    }
    word[i]='\0';
    return word;

}

//TRAVERSING A LINKED LIST
void printList(Node_L *list){
    int i=0;
    Node_L *p = list;
    while(p!=NULL){
        printf("%s is in pos %d \n", p->string,i);
        p = p->next;
        i++;
        if(i ==10) break; //to limit infinite loop
    }
}

例子:

 INPUT:train rocket ball STOP
    OUTPUT:
    train 
    train 
    train 
    train 
    train 
    train 
    train 
    train 
    train 
    train

提前感谢

注意:就像回答中所说的那样,问题在于插入函数; 现在,我在这里发布了它的更正版本:

void insertNode_L(Node_L **list, Node_L **tail, char *word){
    Node_L *temp = newNode_L(word);
    if(*list==NULL){
        *tail = *list = temp;
    }else{
        (*tail)->next = temp;
        *tail = temp;
    }
}

3 回复 | 直到 7 年前

meaning-matters 7 年前

使您的列表双重链接。以下是我1999年的实施情况:

/*
 *      List.c - doubly linked list library
 *
 *  DESCRIPTION
 *      This module contains routines to create and maintain doubly linked
 *      lists of data objects.  A list can be used for storing data object 
 *      pointers or integer values (except zero).
 *
 *      The application using this library only has to deal with a single list
 *      pointer and its data objects.  It does not have to deal with list nodes 
 *      as is often seen, neither do the the data objects need to supply space 
 *      for list pointers (often called <pNext> and <pPrev>).  This list type
 *      is generally called to be 'non-intrusive'.
 *      The price paid for this convenience is that nodes can not be accessed
 *      randomly, which means that deleting a node may require a linear search.
 *      The list does however keeps a pointer to the last accessed list node;
 *      the supplied set of operations relative to this node still makes this 
 *      kind of list very useful for many applications without (much) perfor-
 *      mance loss compared to 'more traditional' linked lists in C.
 *
 *  NOTES
 *      Doing something that is not allowed, or entering a condition that is
 *      regarded as an error, will result in a 'failed assertion', when this
 *      module has been built with DEBUG defined.  The routine descriptions 
 *      tell what to watch out for.
 *
 *  INTERNAL
 *      The idea of using a dummy node was taken from "Obfuscated C and Other
 *      Mysteries" by Don Libes, John Wiley & Sons - 1993, chapter 11.  It
 *      results in simpler list operation code.
 *
 *                                              down-->           <--up
 *                                             after-->           <--before
 *      
 *                                   +-------------------- - --------------+
 *                                   |                                     |
 *      +--------------+             V         Head Node        Tail Node  |
 *      |              |         +-------+     +-------+        +-------+  |
 *      |        pHead---------->|/pNext------>| pNext---- - -->| pNext----+
 *      |              |         |///////|     |       |        |       |
 *      |    pNodeLast--->?   +----pPrev/|<------pPrev |<- - -----pPrev |
 *      |              |      |  |///////|     |       |        |       |
 *      |        count |      |  |/pData/|     | pData |     +->| pData |
 *      |              |      |  +-- | --+     +-- | --+     |  +-- | --+
 *      +--------------+      |      |             |         |      |
 *                            |      V             V         |      V
 *                            |     ###           ###        |     ###
 *        //// = Dummy Node   |     ###           ###        |     ###
 *                            |                              |
 *         ### = User Data    +--------------------------- - +
 *
 *      Notice that pList->pHead->pPrev points to the tail of the list; this
 *      is used a number of times in the code below.
 *
 *      For efficiency some short code fragments show up a number of times
 *      in different routines, instead of nesting the routines.
 *
 *  INCLUDE FILES
 *      List.h
 *
 *  COPYRIGHT
 *      You are free to use, copy or modify this software at your own risk.
 *
 *  AUTHOR
 *      meaning-matters
 *
 *  MODIFICATION HISTORY
 *      1999/04/12 MM       Thorough test and debugging; beta release.
 *      1999/03/09 MM       Composed.
 *
 *****************************************************************************/

#include <stdlib.h>
#include "List.h"
#include "Assert.h"     /* includes "Except.h" which defines return() macro */


/******************************************************************************
 *
 *      ListCreate - create empty list
 *
 *  DESCRIPTION
 *      This routine creates an empty list.
 *
 *  SIDE EFFECTS
 *      None.
 *
 *  RETURNS
 *      Pointer to empty list.
 */
List * ListCreate(void)
{
    List *      pList;

    pList = malloc(sizeof(List));

    pList->pHead = malloc(sizeof(ListNode));

    pList->pHead->pNext = pList->pHead->pPrev = pList->pHead;

    pList->pNodeLast = NULL;
    pList->count = 0;

    return pList;
}


/******************************************************************************
 *
 *      ListDestroy - free list but not user data
 *
 *  DESCRIPTION
 *      This routine frees the list handle and the nodes, but does not free 
 *      the user data.
 *
 *  SIDE EFFECTS
 *      None.
 *
 *  RETURNS
 *      N/A.
 */
void ListDestroy(
    List *      pList)          /* pointer to list */
{
    ListNode *  pNode;

    assert(pList != NULL);

    pNode = pList->pHead->pNext;
    while (pNode != pList->pHead)
    {
        ListNode *      pNext;

        pNext = pNode->pNext;
        free(pNode);
        pNode = pNext;
    }

    free(pList->pHead);
    free(pList);
}


/******************************************************************************
 *
 *      ListDestroyData - free list including user data
 *
 *  DESCRIPTION
 *      This routine frees the list handle and the nodes, and does also free 
 *      the user data using free(); the caller is responsible that all of this 
 *      user data was allocated with routines compatible with free().
 *
 *  SIDE EFFECTS
 *      None.
 *
 *  RETURNS
 *      N/A.
 */
void ListDestroyData(
    List *      pList)          /* pointer to list */
{
    ListNode *  pNode;

    assert(pList != NULL);

    pNode = pList->pHead->pNext;
    while (pNode != pList->pHead)
    {
        ListNode *      pNext;

        pNext = pNode->pNext;
        free(pNode->pData);
        free(pNode);
        pNode = pNext;
    }

    free(pList->pHead);
    free(pList);
}


/******************************************************************************
 *
 *      ListAddHead - add node to head of list
 *
 *  DESCRIPTION
 *      This routine adds the specified data object value at the head of the 
 *      specified list.  The last accessed list node is set to the added
 *      node.
 *
 *  SIDE EFFECTS
 *      None.
 *
 *  RETURNS
 *      N/A.
 */
void ListAddHead(
    List *      pList,          /* pointer to list */
    void *      pData)          /* data object value */
{
    ListNode *  pNode;

    assert(pList != NULL);

    pNode = malloc(sizeof(ListNode));

    pNode->pData = pData;
    (pNode->pNext = pList->pHead->pNext)->pPrev = pNode;
    (pList->pHead->pNext = pNode)->pPrev = pList->pHead;

    pList->pNodeLast = pNode;
    pList->count++;
}


/******************************************************************************
 *
 *      ListAddTail - add node to tail of list
 *
 *  DESCRIPTION
 *      This routine adds the specified data object value at the tail of the 
 *      specified list.  The last accessed list node is set to the added
 *      node.
 *
 *  SIDE EFFECTS
 *      None.
 *
 *  RETURNS
 *      N/A.
 */
void ListAddTail(
    List *      pList,          /* pointer to list */
    void *      pData)          /* data object value */
{
    ListNode *  pNode;

    assert(pList != NULL);

    pNode = malloc(sizeof(ListNode));

    pNode->pData = pData;
    (pNode->pPrev = pList->pHead->pPrev)->pNext = pNode;
    (pList->pHead->pPrev = pNode)->pNext = pList->pHead;

    pList->pNodeLast = pNode;
    pList->count++;
}


/******************************************************************************
 *
 *      ListAddBefore - add node before last accessed node
 *
 *  DESCRIPTION
 *      This routine adds the specified data object value in the specified
 *      list just before the node that was last accessed by one of the 
 *      routines from this library that set it.  'Before' means towards the
 *      head of the list.  The last accessed list node is set to the added
 *      node.
 *
 *      Nothing happens when the last accessed list node is not set; this
 *      causes a failed assertion when DEBUG defined.
 *
 *  SIDE EFFECTS
 *      None.
 *
 *  RETURNS
 *      N/A.
 */
void ListAddBefore(
    List *      pList,          /* pointer to list */
    void *      pData)          /* data object value */
{
    ListNode *  pNode;

    assert(pList != NULL);
    validate(pList->pNodeLast != NULL, NOTHING);

    pNode = malloc(sizeof(ListNode));

    pNode->pData = pData;
    (pNode->pPrev = pList->pNodeLast->pPrev)->pNext = pNode;
    (pList->pNodeLast->pPrev = pNode)->pNext = pList->pNodeLast;

    pList->pNodeLast = pNode;
    pList->count++;
}


/******************************************************************************
 *
 *      ListAddAfter - add node after last accessed node
 *
 *  DESCRIPTION
 *      This routine adds the specified data object value in the specified
 *      list right after the node that was last accessed by one of the
 *      routines from this library that set it.  'After' means towards the
 *      tail of the list.  The last accessed list node is set to the added
 *      node.
 *
 *      Nothing happens when the last accessed list node is not set; this
 *      causes a failed assertion when DEBUG defined.
 *
 *  SIDE EFFECTS
 *      None.
 *
 *  RETURNS
 *      N/A.
 */
void ListAddAfter(
    List *      pList,          /* pointer to list */
    void *      pData)          /* data object value */
{
    ListNode *  pNode;

    assert(pList != NULL);
    validate(pList->pNodeLast != NULL, NOTHING);

    pNode = malloc(sizeof(ListNode));

    pNode->pData = pData;
    (pNode->pNext = pList->pNodeLast->pNext)->pPrev = pNode;
    (pList->pNodeLast->pNext = pNode)->pPrev = pList->pNodeLast;

    pList->pNodeLast = pNode;
    pList->count++;
}


/******************************************************************************
 *
 *      ListRemoveHead - remove head node from list
 *
 *  DESCRIPTION
 *      This routine removes the head list node from the specified list.  The
 *      last accessed list node is reset.
 *
 *      It is not allowed to pass this routine an empty list.
 *
 *  SIDE EFFECTS
 *      None.
 *
 *  RETURNS
 *      Removed data object value.
 */
void * ListRemoveHead(
    List *      pList)          /* pointer to list */
{
    void *      pData;
    ListNode *  pNode;

    assert(pList != NULL);
    validate(pList->count > 0, NULL);

    pNode = pList->pHead->pNext;

    pData = pNode->pData;
    (pList->pHead->pNext = pNode->pNext)->pPrev = pList->pHead;
    free(pNode);

    pList->pNodeLast = NULL;
    pList->count--;

    return pData;
}


/******************************************************************************
 *
 *      ListRemoveTail - remove tail node from list
 *
 *  DESCRIPTION
 *      This routine removes the tail list node from the specified list.  The
 *      last accessed list node is reset.
 *
 *      It is not allowed to pass this routine an empty list.
 *
 *  SIDE EFFECTS
 *      None.
 *
 *  RETURNS
 *      Removed data object value.
 */
void * ListRemoveTail(
    List *      pList)          /* pointer to list */
{
    void *      pData;
    ListNode *  pNode;

    assert(pList != NULL);
    validate(pList->count > 0, NULL);

    pNode = pList->pHead->pPrev;

    pData = pNode->pData;
    (pList->pHead->pPrev = pNode->pPrev)->pNext = pList->pHead;
    free(pNode);

    pList->pNodeLast = NULL;
    pList->count--;

    return pData;
}


/******************************************************************************
 *
 *      ListRemove - remove specified node from list
 *
 *  DESCRIPTION
 *      This routine removes the node with the specified data object value
 *      The last accessed list node is reset.
 *
 *      It is an error if the specified node is not in the list.  It is not
 *      allowed to pass this routine an empty list.
 *
 *  SIDE EFFECTS
 *      None.
 *
 *  RETURNS
 *      Removed data object value.
 */
void * ListRemove(
    List *      pList,          /* pointer to list */
    void *      pData)          /* data object value */
{
    ListNode *  pNode;

    assert(pList != NULL);
    validate(pList->count > 0, NULL);

    pNode = pList->pHead->pNext;
    while (pNode != pList->pHead && pNode->pData != pData)
        pNode = pNode->pNext;
    validate(pNode->pData == pData, NULL);

    pNode->pNext->pPrev = pNode->pPrev;
    pNode->pPrev->pNext = pNode->pNext;
    free(pNode);

    pList->pNodeLast = NULL;
    pList->count--;

    return pData;
}


/******************************************************************************
 *
 *      ListRemoveLast - remove last accessed node from list
 *
 *  DESCRIPTION
 *      This routine removes the node which was last accessed by one of the
 *      routines in this library that set it.  Subsequently the last accessed
 *      list node is set to the next node for convenience.
 *
 *      It is an error if the last accessed node was not set by one of the
 *      routines in this library.  It is not allowed to pass this routine an
 *      empty list.
 *
 *  SIDE EFFECTS
 *      None.
 *
 *  RETURNS
 *      Removed data object value.
 */
void * ListRemoveLast(
    List *      pList)          /* pointer to list */
{
    void *      pData;
    ListNode *  pNext;

    assert(pList != NULL);
    validate(pList->pNodeLast != NULL, NULL);

    pData = pList->pNodeLast->pData;

    pNext = pList->pNodeLast->pNext;

    pList->pNodeLast->pNext->pPrev = pList->pNodeLast->pPrev;
    pList->pNodeLast->pPrev->pNext = pList->pNodeLast->pNext;
    free(pList->pNodeLast);

    pList->pNodeLast = pNext;
    pList->count--;

    return pData;
}


/******************************************************************************
 *
 *      ListHead - get head data object value
 *
 *  DESCRIPTION
 *      This routine returns the user data object value of the head node of
 *      the specified list.  The last accessed list node is reset if the list
 *      is empty, otherwise it is set to the list head.
 *
 *  SIDE EFFECTS
 *      None.
 *
 *  RETURNS
 *      Head data object value, or NULL if empty.
 */
void * ListHead(
    List *      pList)          /* pointer to list */
{
    assert(pList != NULL);

    if (pList->count == 0)
        return NULL;
    else
        return 0, (pList->pNodeLast = pList->pHead->pNext)->pData;
}


/******************************************************************************
 *
 *      ListTail - get tail data object value
 *
 *  DESCRIPTION
 *      This routine returns the user data object value of the tail node of
 *      the specified list.  The last accessed list node is reset if the list
 *      is empty, otherwise it is set to the list tail.
 *
 *  SIDE EFFECTS
 *      None.
 *
 *  RETURNS
 *      Head data object value, or NULL if empty.
 */
void * ListTail(
    List *      pList)          /* pointer to list */
{
    assert(pList != NULL);

    if (pList->count == 0)
        return NULL;
    else
        return 0, (pList->pNodeLast = pList->pHead->pPrev)->pData;
}


/******************************************************************************
 *
 *      ListLast - get last accessed data object value
 *
 *  DESCRIPTION
 *      This routine returns the user data object value of the last accessed
 *      node of the specified list.  The last accessed list node is not
 *      affected.
 *
 *      When the last accessed list node is not set, which is also the case
 *      when the list is empty, NULL is returned.
 *
 *  SIDE EFFECTS
 *      None.
 *
 *  RETURNS
 *      Last accessed data object value, or NULL if not set.
 */
void * ListLast(
    List *      pList)          /* pointer to list */
{
    assert(pList != NULL);

    if (pList->pNodeLast == NULL)
        return NULL;
    else
        return pList->pNodeLast->pData;
}


/******************************************************************************
 *
 *      ListNext - get next data object value
 *
 *  DESCRIPTION
 *      This routine returns the user data object value of the next node
 *      with respect to the last accessed list node.  The last accessed list
 *      node is set to the next node, or is reset if the tail is passed.
 *
 *      It is an error if the last accessed list node is not set; which is
 *      also the case when the list is empty.
 *
 *  SIDE EFFECTS
 *      None.
 *
 *  RETURNS
 *      Next data object value, or NULL if already at tail.
 */
void * ListNext(
    List *      pList)          /* pointer to list */
{
    assert(pList != NULL);
    validate(pList->pNodeLast != NULL, NULL);

    if ((pList->pNodeLast = pList->pNodeLast->pNext) == pList->pHead)
    {
        pList->pNodeLast = NULL;
        return NULL;
    }
    else        
        return pList->pNodeLast->pData;
}


/******************************************************************************
 *
 *      ListPrev - get previous data object value
 *
 *  DESCRIPTION
 *      This routine returns the user data object value of the previous node
 *      with respect to the last accessed list node.  The last accessed list 
 *      node is set to the previous node, or is reset if the head is passed.
 *
 *      It is an error if the last accessed list node is not set; which is
 *      also the case when the list is empty.
 *
 *  SIDE EFFECTS
 *      None.
 *
 *  RETURNS
 *      Next data object value, or NULL if already at head.
 */
void * ListPrev(
    List *      pList)          /* pointer to list */
{
    assert(pList != NULL);
    validate(pList->pNodeLast != NULL, NULL);

    if ((pList->pNodeLast = pList->pNodeLast->pPrev) == pList->pHead)
    {
        pList->pNodeLast = NULL;
        return NULL;
    }
    else        
        return pList->pNodeLast->pData;
}


/******************************************************************************
 *
 *      ListCount - report number of nodes in list
 *
 *  DESCRIPTION
 *      This routine returns the number of nodes in the specified list.
 *
 *  SIDE EFFECTS
 *      None.
 *
 *  RETURNS
 *      Number of nodes in list.
 */
int ListCount(
    List *      pList)          /* pointer to list */
{
    assert(pList != NULL);

    return pList->count;
}


/******************************************************************************
 *
 *      ListFind - find list node
 *
 *  DESCRIPTION
 *      This routine finds the node with the specified data object value.  If
 *      nothing was found the last accessed list node is not affected, 
 *      otherwise it is set to the found node.
 *
 *  SIDE EFFECTS
 *      None.
 *
 *  RETURNS
 *      Found data object value, or NULL if not found or empty list.
 */
void * ListFind(
    List *      pList,          /* pointer to list */
    void *      pData)          /* data object value */
{
    ListNode *  pNode;

    assert(pList != NULL);

    pNode = pList->pHead->pNext;
    while (pNode != pList->pHead && pNode->pData != pData)
        pNode = pNode->pNext;

    if (pNode->pData == pData)
    {
        pList->pNodeLast = pNode;
        return pData;
    }
    else
        return NULL;
}


/******************************************************************************
 *
 *      ListSplitBefore - split list just before last node
 *
 *  DESCRIPTION
 *      This routine splits up the specified list in two parts.  The split is
 *      made just before the last accessed list node.  A new list is created
 *      for the part before the last accessed node.  The last accessed list
 *      node for the original list is not affected.  And the last accessed
 *      list node for the new list is reset.
 *
 *      It is not allowed to pass this routine an empty list.  If the list
 *      contains only one node, the new list will be empty.
 *
 *  SIDE EFFECTS
 *      None.
 *
 *  RETURNS
 *      Pointer to new list containing nodes before original last accessed
 *      list node.
 */
List * ListSplitBefore(
    List *      pListOrg)       /* pointer to original list */
{
    List *      pListNew;
    ListNode *  pNodeOrg;

    assert(pListOrg != NULL);
    validate(pListOrg->count > 0, NULL);
    validate(pListOrg->pNodeLast != NULL, NULL);

    pListNew = malloc(sizeof(List));

    pListNew->pHead = malloc(sizeof(ListNode));
    pListNew->pHead->pData = NULL;
    pListNew->count = 0;

    pNodeOrg = pListOrg->pHead->pNext;
    while (pNodeOrg != pListOrg->pNodeLast)
    {
        pListOrg->count--;
        pListNew->count++;

        pNodeOrg = pNodeOrg->pNext;
    }

    if (pListNew->count == 0)
    {
        pListNew->pHead->pPrev = pListNew->pHead->pNext = pListNew->pHead;
    }
    else
    {
        /* connect list part to new list */
        pListNew->pHead->pNext = pListOrg->pHead->pNext;
        pListNew->pHead->pNext->pPrev = pListNew->pHead;
        pListNew->pHead->pPrev = pListOrg->pNodeLast->pPrev;
        pListNew->pHead->pPrev->pNext = pListNew->pHead;

        /* bind last accessed node and original dummy node together */
        pListOrg->pHead->pNext = pListOrg->pNodeLast;
        pListOrg->pNodeLast->pPrev = pListOrg->pHead;
    }

    pListNew->pNodeLast = NULL;

    return pListNew;
}


/******************************************************************************
 *
 *      ListSplitAfter - split list just after last node
 *
 *  DESCRIPTION
 *      This routine splits up the specified list in two parts.  The split is
 *      made just after the last accessed list node.  A new list is created
 *      for the part after the last accessed node.  The last accessed list
 *      node for the original list is not affected.  And the last accessed
 *      list node for the new list is reset.
 *
 *      It is not allowed to pass this routine an empty list.  If the list
 *      contains only one node, the new list will be empty.
 *
 *  SIDE EFFECTS
 *      None.
 *
 *  RETURNS
 *      Pointer to new list containing nodes after original last accessed
 *      list node.
 */
List * ListSplitAfter(
    List *      pListOrg)       /* pointer to original list */
{
    List *      pListNew;
    ListNode *  pNodeOrg;

    assert(pListOrg != NULL);
    validate(pListOrg->count > 0, NULL);
    validate(pListOrg->pNodeLast != NULL, NULL);

    pListNew = malloc(sizeof(List));

    pListNew->pHead = malloc(sizeof(ListNode));
    pListNew->pHead->pData = NULL;
    pListNew->count = 0;

    pNodeOrg = pListOrg->pNodeLast->pNext;
    while (pNodeOrg != pListOrg->pHead)
    {
        pListOrg->count--;
        pListNew->count++;

        pNodeOrg = pNodeOrg->pNext;
    }

    if (pListNew->count == 0)
    {
        pListNew->pHead->pPrev = pListNew->pHead->pNext = pListNew->pHead;
    }
    else
    {
        /* connect list part to new list */
        pListNew->pHead->pNext = pListOrg->pNodeLast->pNext;
        pListNew->pHead->pNext->pPrev = pListNew->pHead;
        pListNew->pHead->pPrev = pListOrg->pHead->pPrev;
        pListNew->pHead->pPrev->pNext = pListNew->pHead;

        /* bind last accessed node and original dummy node together */
        pListOrg->pNodeLast->pNext = pListOrg->pHead;
        pListOrg->pHead->pPrev = pListOrg->pNodeLast;
    }

    pListNew->pNodeLast = NULL;

    return pListNew;
}


/******************************************************************************
 *
 *      ListConcat - concatenate two lists
 *
 *  DESCRIPTION
 *      This routine concatenates the second list <pListAdd> to the tail of
 *      the first list <pListDst>.  Either list (or both) may be empty.  After
 *      the operation the <pListAdd> handle is destroyed.  The last accessed 
 *      list node of the resulting list is reset.
 *
 *  SIDE EFFECTS
 *      None.
 *
 *  RETURNS
 *      List pointer <pListDst> containing the nodes of both lists.
 */
List * ListConcat(
    List *      pListDst,       /* pointer to destination list */
    List *      pListAdd)       /* pointer to list to be added at tail */
{
    assert(pListDst != NULL);
    assert(pListAdd != NULL);

    switch (((pListAdd->count > 0) << 1) | (pListDst->count > 0))
    {
    case 0:
        /* both lists empty */

        break;

    case 1:
        /* destination list not empty and add list empty */

        break;

    case 2:
        /* destination list empty and add list not empty */

        pListDst->pHead->pNext = pListAdd->pHead->pNext;
        pListDst->pHead->pNext->pPrev = pListDst->pHead;
        pListDst->pHead->pPrev = pListAdd->pHead->pPrev;
        pListDst->pHead->pPrev->pNext = pListDst->pHead;
        break;

    case 3:
        /* both lists not empty */

        pListAdd->pHead->pPrev->pNext = pListDst->pHead;
        pListDst->pHead->pPrev->pNext = pListAdd->pHead->pNext;
        pListAdd->pHead->pNext->pPrev = pListDst->pHead->pPrev;
        pListDst->pHead->pPrev = pListAdd->pHead->pPrev;
        break;
    }

    pListDst->pNodeLast = NULL;
    pListDst->count += pListAdd->count;

    free(pListAdd->pHead);
    free(pListAdd);

    return pListDst;
} 

/* end of List.c */

以下是标题的基本部分:

#ifndef _LIST_H
#define _LIST_H

typedef struct _ListNode        ListNode;
struct _ListNode
{
    ListNode *  pNext;          /* next node ('down', 'after') */
    ListNode *  pPrev;          /* next node ('up', 'before') */
    void *      pData;          /* pointer to user data */
};

typedef struct _List    List;   /* doubly linked list */
struct _List
{
    ListNode *  pHead;          /* pointer to dummy list head node */
    ListNode *  pNodeLast;      /* pointer to last accessed node */
    int         count;          /* number of user nodes in list */
};

我知道这是一个有点不标准的答案。但我认为看到另一种实现方式会有所帮助。

Rishav Agarwal 7 年前

问题出在 else 阻止您的 insertNode_L (...) 方法应该是这样的

(*tail)->next = temp;
*tail = temp;

在您的代码中

Node_L *t = *tail;
t->next = *tail;    // This makes tail point to itself resulting in an infinite loop
*tail = temp;

Aditya 7 年前

您的模型表明*tail为NULL,是指向将来添加的节点(而不是列表中的最后一项)的指针。插入完毕后,您必须重新分配尾部。

Node_L *temp = newNode_L(word);
if(*list==NULL){
    *tail = *list = temp;
    tail = temp->next;
}