1

Think は新しい要素を名前順に挿入する機能です。if を使って、最初に挿入する条件とそれ以外の条件を分ける方法がわかりました。しかし、if と while を 1 つの while ループにマージするように求められました。ポインターへのポインターを使用して挿入関数を1つの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

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

いくつかのオプションがあります。

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* 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` と書くところにだけ書きます。

ノード ポインターへのポインターを使用するという考え方は、1 レベルの間接化を追加することで、呼び出し元の関数からヘッド ポインターにアクセスして変更できるようにすることです。ノード ポインターを渡すだけの場合、そのポインターへのすべての変更は関数に対してローカルであり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;

*pnext前のノードのポインタのアドレスを保持します。p「whence」ポインターです。処理中のコードを指すポインターのアドレスを保持します。つまり、空のリストはもはや特別なケースではありません。

関数は、新しいヘッド ポインターを返す必要があります。割り当てるのを忘れがちで、コールに冗長性が追加されます。ポインターからポインターへのアプローチもこれを修正します。

ポインターへのポインターを引数として受け取る関数を使用した場合、挿入コードは次のようになります。

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 に答える