1

文字列といいえを保存するように求められるこの問題に遭遇しました。それに関連付けられており、リストから最小の番号 (およびその文字列) を削除し、その後に格納されている番号 (および文字列) も削除することになっています。入力は、番号と文字列のペアのストリームであり、入力です。 of -1 は、リストから最も小さいものとその上のペアを削除する必要があることを意味します。出力は、最小番号の項目より上の項目の数でなければなりません。例: 2 abcd 1 aabb 3 dbbb -1 o/p 1 (最小値は 1 aabb で、その後に項目が 3 dbbb しかないため、リストには 2 つの ab​​cd しか含まれていません)。別の -1 は o/p 0 として生成されます。連結リストを使用してこれを試しましたが、予想よりも時間がかかるようです。同じためにより良いデータ構造またはアルゴリズムが必要です。これが私のコードです：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct data
    {
        int no,pos;
        char *st;
        struct data *next;
    }data;
void insert(data *start,int n,char *s);
void minimum(data *start);
int total=0,min=100001,posn=0;//total=total no of nodes,rem=nodes after minimum
data *temp;
int main()
    {
        int N,n;
        data *start;
        start=(data*)malloc(sizeof(data));
        start->pos=0;
        start->no=100002;
        start->next=NULL;
        char c,s[16];
        scanf("%d",&N);
        while(N)
            {
                scanf("%d",&n);
                if(n!=-1)
                    {
                        scanf("%c",&c);
                        scanf("%s",s);
                        total++;
                        posn++;
                        insert(start,n,s);
                    }
                else
                    {
                        printf("%d %s\n",total-(temp->next->pos),temp->next->st);
                        posn=temp->pos;
                        total=temp->pos;
                        temp->next=NULL;
                        minimum(start);
                    }
                N--;
            }
    }
void insert(data *start,int n,char *s)
    {
    while(start->next!=NULL)
        start=start->next;
    if(n<=min)
        {
            temp=start;
            min=n;
        }
    start->next=(data*)malloc(sizeof(data));
    start=start->next;
    start->no=n;
    start->st=(char*)malloc(sizeof(char)*(strlen(s)));
    strcpy(start->st,s);
    start->pos=posn;
    start->next=NULL;
    return;
    }
void minimum(data *start)
    {
        min=100001;
        while(start->next!=NULL)
            {
                if(start->next->no<=min)
                    {
                        min=start->next->no;
                        temp=start;
                        start=start->next;
                    }
            }
        return;
    }

どんな助けでも大歓迎です。

4

1 に答える 1

0

さて、ここにあなたのコードに関するいくつかの問題があります:

  1. start=start->next;新しい分が見つかったときだけでなく、すべての反復で実行する必要があります。
  2. リストの先頭が常に欠落しており、反復します（そして次のノードの代わりにwhile(start != NULL)チェックします）。start->no(start実際にそうである場合、それはダミー変数のようです-あなたはそれを見逃しているだけです-それは完全に問題ありません)。
  3. 関数の戻り値の型がありません。minimum()そうであってはなりませんvoid。リストにints が含まれている場合、戻り値の型は である必要がありint、ループを使い果たすときは である必要がありますreturn min;。(添付された最小文字列を返すことに関心がある場合は、追加の変数を保存しchar* minElement、変更時にそれを変更し、ループが終了したときにminそれを返します (minelement )。 (回答をグローバル変数に保存するのは悪い習慣であることに注意してください。より良いアプローチは、関数から返すことです)
  4. min をINT_MAX任意の数値に初期化する必要があります。

最適化の問題について：

最小要素を見つけることだけに関心がある場合、ヒープはまさにそのために設計されたデータ構造です! 最小値を取得するためのシンプルで非常に効率的なデータ構造です。

また、データ構造が削除をサポートしていない場合は、次の疑似コードの行に沿って、各挿入で最小値をキャッシュできることに注意してください。

挿入関数に追加:

if (newValue < min):
   min <- newValue

min は、キャッシュされたを取得するのと同じくらい簡単minです。

于 2012-12-05T08:09:08.727 に答える