3

我正在尝试创建一个将 char* 添加到 LinkedList 的方法，以确保 linkedList 始终按字母顺序排序。我得到了定义 LinkedItem 结构的代码：

// Define our list item as 'struct ListItem', and also 
// typedef it under the same name.
typedef struct ListItem {
  char *s;
  struct ListItem *p_next;
} ListItem;

我还获得了一种将项目添加到列表开头的方法：

// Adds a new item to the beginning of a list, returning the new
// item (ie the head of the new list *)
ListItem* add_item(ListItem *p_head, char *s) {  
    // Allocate some memory for the size of our structure.
    ListItem *p_new_item = malloc(sizeof(ListItem));
    p_new_item->p_next = p_head;       // We are the new tail.
    p_new_item->s = s;     // Set data pointer. 
    return p_new_item;
}

现在这是我的代码，我将在之后解释更多：

ListItem* addSortedItem(ListItem *p_head, char *s){         
    if(p_head==NULL)//if the list is empty, we add to the beginning
        return add_item(p_head,s);
    ListItem* p_new_item = malloc(sizeof(ListItem));
    ListItem *p_current_item = p_head; //makes a pointer to the head of the list


    while (p_current_item) {    // Loop while the current pointer is not NULL
        printf("entering while loop with current=%s\n",p_current_item->s);
        // now we want to look at the value contained and compare it to the value input     
        if(aThenB(s,p_current_item->s)!=TRUE){
            // if A goes after B, we want to go on to look at the next element
            p_current_item=p_current_item->p_next;
        } else if (aThenB(s,p_current_item->s)==TRUE) {printf("entered elseif\n");      
            p_head=add_item(p_current_item,s);
            return p_head;          
        } else {printf("WHY DID WE EVER REACH THE ELSE!?"); return p_head;}
    }
}

现在，如果 A 和 B 的正确排序顺序是 A，然后是 B，则 aThenB(StringA,StringB) 返回 TRUE，否则返回 false - 相等也是一个选项，我只是没有让它工作得足够好以允许它： -)

我的测试数据（即"sheep i"i 从 0 到 10）发生的情况是，要么我只返回一个元素，要么我随机跳过元素，具体取决于订单输入。我可以包含更多代码，但它有点乱。

我认为我的问题源于没有完全理解指针以及它们是如何工作的——我想确保 p_head 始终指向头部，而 p_current 正在遍历列表。但是当 p_current 到达最后一个元素时，我也会遇到段错误，所以我不确定我哪里出错了。

感谢您就如何让我的代码正确返回提供任何帮助:-)

编辑： addSortedItem() 在 main 方法的以下块中调用：

    // The empty list is represented by a pointer to NULL.
    ListItem *p_head = NULL;
    ListItem *p_head2=NULL;
    // Now add some items onto the beginning of the list.
    int i;
    for (i=0; i<NO_ITEMS; i++) {

    // Allocate some memory for our string, and use snprintf to
    // create a formatted string (see GNU API docs) much like printf
    // but instead writing to memory rather than the screen.
    char* s = malloc(MAX_DATA_CHARS);
    snprintf(s, (size_t) MAX_DATA_CHARS, "sheep %d", i);
    p_head = addSortedItem(p_head, s);
    }
4

3 回答 3

1

在链表的中间或末尾添加新元素时出错。在您的addStoredItem函数中，您创建了一个从 newItem 到 currentItem 的指针，但您没有考虑到从前一个元素到 newItem 的链接

调用前的初始链表addStoredItem

item1-->item2-->item4-->item5

链表调用addStoredItem后添加item3

item1-->item2-->item4-->item5
                ^
                |
                item3

如您所见，您已经在从item4开始的子链表的头部添加了新项目，但是您没有从item2链接到item3 ， 因此我们必须保留指向前一个项目的指针才能完成链接.

该add_item()功能允许在头部添加项目

如果您尝试在链表的末尾添加项目，同样的事情

item1-->item2-->item4-->item5    NULL
                                 ^
                                 |
                                 item6

item6已添加为单独的头，并且没有从item5（上一个）到 item6（新）的链接

所以你的addStoredItem()功能可以像这样固定

ListItem* addSortedItem(ListItem *p_head, char *s){         
    if(p_head==NULL)//if the list is empty, we add to the beginning
        return add_item(p_head,s);
    struct ListItem* p_new_item = malloc(sizeof(ListItem));
    ListItem *p_current_item = p_head; //makes a pointer to the head of the list
    ListItem *p_prev_item = NULL; //FIXED

    while (p_current_item) {    // Loop while the current pointer is not NULL
        printf("entering while loop with current=%s\n",p_current_item->s);
        // now we want to look at the value contained and compare it to the value input     
        if(aThenB(s,p_current_item->s)!=TRUE){
            // if A goes after B, we want to go on to look at the next element
            p_prev_item = p_current_item; //FIXED
            p_current_item=p_current_item->p_next;
        } else if (aThenB(s,p_current_item->s)==TRUE) {printf("entered elseif\n");      
            break;        
        } else {printf("WHY DID WE EVER REACH THE ELSE!?"); return p_head;}
    }

    if (p_prev_item!=NULL) //FIXED
        p_prev_item->p_next=add_item(p_current_item,s); //FIXED
    else //FIXED
        p_head=add_item(p_current_item,s);//FIXED
    return p_head; //FIXED
}

固定线用//FIXED

于 2012-10-10T16:42:44.580 回答
0

首先，您的p_headis NULL，因此当您输入addSortedItem函数时，您会创建列表并添加第一个字符串。没关系。
但是，在添加第二项（在您的情况下是“羊 1”）后，您进入while (p_current_item)循环。调用aThenB返回FALSE，然后您转到下一个元素，即.. NULL！确实，此时的p_head样子是这样的：

p_head {
s = "sheep 0",
p_next = NULL
}

您的while条件不正确，您退出了函数，没有添加任何内容。
您可以在第一个条件中添加一个条件if：

if (p_current_item->next == NULL)
  p_current_item->next = addSortedItem(NULL, s);
else
  p_current_item = p_current_item->next;

另外，这样说p_head=add_item(p_current_item,s);是不对的。假设您的列表类似于：

"sheep 1" -> "sheep 2" -> "sheep 4" -> "sheep 5"

如果你添加“sheep 3”，你会得到这个：

"sheep 1" -> "sheep 2" -> "sheep 3" -> "sheep 4" -> "sheep 5"
                          ^
                          |
                          p_head

您将无法再添加“sheep 0”。不要将返回值addSortedItem作为新的返回p_head

于 2012-10-10T15:46:47.377 回答
0

支持的东西：

#define FALSE 0
#define TRUE 1
#define aThenB(a,b) (strcmp(a,b) <=0 ? TRUE : FALSE)

通过修改函数的签名以接受指向指针的指针，可以避免所有特殊情况。

void addSortedItem(ListItem **pp_head, char *s){         
    ListItem *p_new_item ;

    for (       ;*pp_head; pp_head = &(*pp_head)->p_next) {    
        if (aThenB(s,(*pp_head)->s)==FALSE) break;
    }

    p_new_item = malloc(sizeof *p_new_item);
    p_new_item->s = s;

    p_new_item->p_next = *pp_head;
    *pp_head = p_new_item;
}

调用者应该这样做：

ListItem *root = NULL;
addSortedItem( &root, "sheep#0");
于 2012-10-10T17:14:33.040 回答