在链表中按字母顺序插入新节点

Question

我一直在阅读，我仍然有困难理解链表。我的问题是，由于某种原因，当我遍历列表以确定列表中的任何结构是否具有相同的名称或年龄时，它会删除列表，或者当我试图向列表中添加新节点时，它也会被删除。

这个列表是动态的，所以我不是基于任何类型的计数，而是基于用户决定输入多少结构。

任何指示将不胜感激。

int add(char* name, char* genderValueString, char* breed, int age, float weight)
{
int result;
int count = 0;
gender curGen = 1;

struct dog *temp = malloc(sizeof(struct dog));
strcpy(temp->name, name);
strcpy(temp->breed, breed);
temp->age = age;
temp->weight = weight;
if (strcmpi(genderValueString, "male") == 0) {
    curGen = 0;
}
temp->genderValue = curGen;

if (list == NULL) {
    temp->next = list;
    list = temp;
    result = 1;
}
else {
    while (list != NULL) {
        if (strcmpi(list->name, name) == 0 && list->age == age) {
            result = 0;
        }
        else {
            result = 1;
        }
        list = list->next;
    }

    if (result == 1) {
        while (list != NULL) {
            if (strcmpi(list->name, name) > 0 || list->age > age) {
                struct dog *prev = list;
                list = temp;
                list->next = prev;              
            }   
            list = list->next;
        }

    }
}

return result;
}

Answer 1

我想象你的变量list是一个全局变量，它代表列表的头。

你代码中的主要问题是你在while循环(list = list->next)中修改了list，这意味着你失去了对头部的跟踪。

你现在能做的(也许)是声明另一个变量，它是头的副本，你可以安全地修改。

例如:

struct dog *list_tmp;
...
for (list_tmp = list; list_tmp != NULL; list_tmp = list_tmp->next)
{
    if (strcmpi(list->name, name) == 0 && list->age == age) {
        result = 0;
    }
    ...
}

对你的两个循环也这样做。

但是底线，永远不要修改list，因为它似乎是列表头的唯一副本;)

Answer 2

我在Visual Studio 2013中进行了测试。您需要跟踪列表当前的头部。我将这个全局命名为doglist。然后使用一个局部变量list来遍历列表。有一个棘手的情况——当你在列表头之前插入时，你需要使它成为新的列表头。

struct dog
{
    char name[50];
    int genderValue;  
    char breed[50];
    int age;
    float weight;
    struct dog * next;
};
struct dog *doglist = NULL;
int dogadd(char* name, char* genderValueString, char* breed, int age, float weight)
{
    struct dog * list = doglist;    // save head of list
    int count = 0;
    int curGen = 1;
    struct dog *temp = (dog *)malloc(sizeof(struct dog));
    strcpy(temp->name, name);
    strcpy(temp->breed, breed);
    temp->age = age;
    temp->weight = weight;
    if (strcmpi(genderValueString, "male") == 0) {
        curGen = 0;
    }
    temp->genderValue = curGen;
    if (list == NULL) {
        temp->next = list;
        doglist = temp;
        return 1;
    }
    while (list != NULL) {
        if (strcmpi(list->name, name) == 0 && list->age == age) {
            return 0;
        }
        list = list->next;
    }
    list = doglist;             // restore the head of the list
    struct dog * prev = NULL;   // keep the previous list node so we can point it to the inserted entry
    while (list != NULL) {
        int nameCompare = strcmpi(list->name, name);
        if ( nameCompare > 0 || (nameCompare == 0 && list->age > age) ) {
            temp->next = list;
            if (prev != NULL)
                prev->next = temp;
            // if we are inserting before the current head of the list we need to make this the new head
            if (list == doglist)
                doglist = temp;
            list = temp;
            return 1;
        }
        if (list->next == NULL) {
            // Nothing greater than this, so add it to end
            list->next = temp;
            temp->next = NULL;
            return 1;
        }
        prev = list;
        list = list->next;
    }
    return 0;
}
void main()
{
    dogadd("Sybil", "female", "red heeler", 7, 40.1);
    dogadd("Pepi", "male", "chihuahua", 5, 3.3);
    dogadd("Goliath", "male", "bulldog", 9, 20.5);
    dogadd("Harry", "male", "golden retriever", 9, 35.6);
    dogadd("ZsaZsa", "female", "poodle", 3, 10.5);
    dogadd("Bruce", "male", "german shepherd", 9, 42.7);
    dogadd("Sybil", "female", "red heeler", 7, 40.1); // check it isn't added again
    struct dog * list = doglist;
    while (list != NULL) {
        printf("Dog name=%s sex=%d, breed=%s, age=%d, weight=%fn", list->name, list->genderValue, list->breed, list->age, list->weight);
        list = list->next;
    }
}