1

Think 是一个按名称顺序插入新元素的功能。如果我使用 if 来分隔开头插入的条件和其他条件，我知道该怎么做。但是我被要求将 if 和 while 合并到一个 while 循环中。我如何将插入函数集成到一个带有指针的while循环中？

person* insert_sorted(person *people, char *name, int age)
{
    person *p=NULL;//,*t=NULL,*q=NULL;
    person *ptr= people;
    person **ptr2ptr=&ptr;

    p=malloc(sizeof(person));

    if ( p == NULL ){
        printf("malloc() failed\n");
        return NULL;
    }
    else {
        p->name = name;
        p->age = age;

        if ( people == NULL ){ // empty list
            people = p;
            people->next =NULL;
        }
        else{
            *ptr2ptr = ptr;
            while( (*ptr2ptr) !=NULL )
            {
                if ( compare_people(p, people)<=0 )  // insert at the start
                    break;
                else if ( (*ptr2ptr)->next == NULL) //insert at the end
                    break;
                else if ( compare_people(*ptr2ptr, p) <=0 && compare_people( p, (*ptr2ptr)->next)<=0 )//insert at the middle
                    break;
                *ptr2ptr = (*ptr2ptr)->next;
            }
            //insert at the end
            p->next =  (*ptr2ptr)->next;
            (*ptr2ptr)->next = p;

        }
    }
4

6 回答 6

1

e与其尝试person在列表中找到没有后继的元素，不如尝试找到第一个空指针。像这样的东西（未经测试）：

void insert_sorted(person **p, char *name, int age)
{
  while (*p) {
    p = &(*p)->next;
  }
  *p = malloc( ... );
  /* ... */
}

这种问题通常最好用笔和纸然后画几个方框和箭头来解决。这个想法是您的“p”指针不再指向特定的person，而是指向某个指向person.

于 2015-11-03T10:04:06.463 回答
0

可以有几个选项。

如果您可以更改它，我会将 if 移动到 compare_people 函数中。毕竟，添加列表中的第一个元素就像添加一个新的“列表顶部”元素（列表中的最小元素）。我知道这可以被视为“作弊”。确实如此！

您可以创建一个“假”列表元素，该元素将始终被测试为排序列表的第一个（或最后一个）（如使用空名称）。所以列表永远不会是空的，也永远不会有“检查空列表”测试。当然，那个假物品的内容需要符合 compare_people 函数的语义。

实际上，成本略高于当前的 O(n), O(n*log(n))，您可以使用 stdlib.h 中的临时支持结构（如指针数组）和 qsort() 以保持列表排序。

最后，实现插入排序，这将利用原始集合在插入新元素之前已经排序的事实。

于 2015-11-03T10:20:59.907 回答
0

函数可以写成如下方式（不用测试，因为我不知道列表的一些定义）

person * insert_sorted( person **people, char *name, int age )
{
    person *p = malloc( sizeof( person ) );

    if ( p == NULL )
    {
        printf( "malloc() failed\n" );
    }
    else 
    {
        p->name = name;
        p->age = age;

        person *prev = NULL;
        person *current = *people;

        while ( current && !( compare_people( p, current ) < 0 ) )
        {
            prev = current;
            current = current->next;
        }

        p->next = current;
        if ( prev == NULL ) *people = p;
        else prev->next = p;
    }

    return p;
}

并且该函数应该被称为

insert_sorted( &people, name, age );
               ^^^^^^^
于 2015-11-03T10:26:18.273 回答
0

未经测试：

person* insert_sorted(person** people, char *name, int age) {
    person* added = malloc(sizeof(person));
    added->name = name;
    added->age = age;
    added->next = NULL;

    person* previous = NULL;
    person* current = *people;
    while (current && compare_people(current, added) <= 0) {
        previous = current;
        current = current->next;
    }

    if (!people) {
        *people = added;
    } else {
        previous->next = added;
        added->next = current;
    }

    return added;   
}
于 2015-11-03T10:32:17.870 回答
0

您使用指针指针的方式不使用间接。你只写(*ptr2ptr)你通常会写“ptr”的地方。

使用指向节点指针的指针的想法是，通过添加一级间接，您可以从调用函数访问和修改头指针。如果您只是传入一个节点指针，则对该指针的所有更改都是insert函数本地的，并且在必要时不会更新调用函数中列表的头指针。

您的函数签名应该已经将指针传递给节点指针：

void insert(person **p, const char *name, int age);

并这样称呼它：

person *head = NULL;

insert(&head, "Betty", 26);
insert(&head, "Ralph", 23);
insert(&head, "Chuck", 19);
insert(&head, "Alice", 42);
insert(&head, "Simon", 34);

进入函数时，是调用函数中p的地址。head当您遍历列表时

p = &(*p)->next;

*p保存next前一个节点的指针地址。p是一个“whence”指针：它保存指向您正在处理的 ode 的指针的地址。这意味着空列表不再是特殊情况。

您的函数需要返回新的头指针。很容易忘记分配它，它也给调用增加了一些冗余。指针对指针的方法也解决了这个问题。

以下是使用指向指针作为参数的函数的插入代码的样子：

struct person {
    const char *name;
    int age;
    person *next;
};

int compare(const person *p1, const person *p2)
{
    return strcmp(p1->name, p2->name);
}

person *person_new(const char *name, int age)
{
    person *p = malloc(sizeof(*p));

    p->name = name;
    p->age = age;
    p->next = NULL;

    return p;
}

void insert(person **p, const char *name, int age)
{
    person *pnew = person_new(name, age);

    while (*p && compare(*p, pnew) < 0) {
        p = &(*p)->next;
    }

    pnew->next = *p;
    *p = pnew;
}
于 2015-11-03T10:32:35.923 回答
0

在这里我找到了对这个问题最有用的答案：http ://www.mvps.org/user32/linkedlist.html

       ptr2ptr = &people;
        while ( *ptr2ptr!=NULL && compare_people(*ptr2ptr,p) ) {
            ptr2ptr = &(*ptr2ptr)->next;
        }
        p->next = *ptr2ptr;
        *ptr2ptr = p;
于 2015-11-06T10:36:30.227 回答