1

リンクされたリストでは、一連のステートメントなどmallocを追加せずに余分なノードを作成しないようにしています。if私は次のものを持っています：

polynomial create()
{
    polynomial head = NULL;
    polynomial temp = NULL;
    int numTerms, coefficient, exponent;
    int counter = 0;

    printf("Enter the number of terms in the polynomial: ");
    scanf ("%d", &numTerms);
    printf("\n");

    if (numTerms == 0) {
        head = malloc(sizeof(term));
        head->coef = 0; head->exp = 0; head->next = NULL;
        return head;
    }
    while (numTerms != counter) {
        // Ask for input
        printf("Enter the coefficient and exponent of term %d: ", (counter + 1));
        scanf("%d %d", &coefficient, &exponent);
        printf("\n");

        // Create the term
        if (temp == NULL) temp = malloc(sizeof(term));
        temp->coef = coefficient; temp->exp = exponent; temp->next = NULL;
        //if((numTerms - 1) != counter) temp->next = malloc(sizeof(term)); -- this is my workaround
        printf("Created: %d %d\n", temp->coef, temp->exp);

        // If this is the first node created, mark the head
        if (counter == 0) head = temp;
        // Increment the list and counter
        temp = temp->next;
        counter ++;
    }
    return head;
}

しかし、多項式を印刷すると (そのために完全に機能する関数があります)、次のようになります。

Polynomial 1: 3x^4--> この場合、head->next への参照は NULL です

そこで、次の回避策を試しました。新しいノードに事前にメモリを割り当てますが、これがユーザー入力の最後の反復になる場合に限ります。これは、次の方法で実現されます。

temp->next = NULL;と置き換えます

if((numTerms - 1) != counter) temp->next = malloc(sizeof(term));

これnumTerms - 1は「余分なノード」の追加を防ぎ、malloc は temp->next への参照を維持します。ifチェックを使用せず、常に余分なメモリを割り当てると、次のようになります。

Polynomial 1: 3x^4 - 7x^2 + 5 + 10621224x^10617028

temp->next への参照が失われる原因となる割り当てのどの部分が欠けていますか? 私は一般的にポインターとメモリ管理が本当にひどいので、これはおそらくひどい質問です。

4

2 に答える 2

4

あなたはこれを必要以上に難しくしています。以下に準拠するリンクリストの単純なノードポピュレーションを考えてみましょう:

  • NULL は空のリストを意味すると仮定します
  • 割り当てごとにテストする必要なく、ヘッド ポインターを割り当てます。
  • ノードごとに 1 つだけ割り当てが必要です。
  • ノードはエントリ順にリストに表示されます。リストの最初のノードは最初に入力したノード、2 番目のノードは 2 番目に入力したノードなどです。

それで、一般的なアルゴリズムと、それがコードにどのように適応するかについては、以下を参照してください。

struct node
{
    // your fields here
    struct node *next;
};

struct node* populate_list()
{
    struct node *head = NULL;
    struct node **pp = &head;
    int i=0, count=0;

    // TODO: set count: get your insertion limit here. 

    // now run the insertion loop
    for (i=0; i<count; ++i)
    {
        struct node *p = malloc(sizeof(*p));

        // TODO: initialize your node members here

        // save to our current tail-pointer, which is initially
        //  also the head pointer. then advance to the new tail
        //  pointer and continue the loop
        *pp = p;
        pp = &p->next;
    }

    // terminate the list.
    *pp = NULL;

    // and return the head pointer.
    return head;
}

注:pわかりやすくするためだけに存在します。そのループ本体を次のように簡単に減らすことができます。これは完全に有効です。

    // now run the insertion loop
    for (i=0; i<count; ++i)
    {
        *pp = malloc(sizeof(**pp));

        // TODO: initialize your node members here
        //  using (*pp)->member for access

        // save next pointer and continue.    
        pp = &(*pp)->next;
    }

コードの適応

これを行う方法がわかったので、コードを次のように大幅に削減します。

polynomial create()
{
    polynomial head = NULL;
    polynomial *pp = &head;

    int numTerms, coefficient, exponent;
    int counter = 0;

    // prompt for valid number of terms.
    printf("Enter the number of terms in the polynomial: ");
    scanf ("%d", &numTerms);

    while (numTerms != counter)
    {
        // Ask for input
        printf("Enter the coefficient and exponent of term %d: ", (counter + 1));
        if (scanf("%d %d", &coefficient, &exponent) == 2)
        {
            *pp = malloc(sizeof(**pp));
            (*pp)->coef = coefficient;
            (*pp)->exp = exponent;
            pp = &(*pp)->next;
            ++counter;
        }
        else
        {   // eat the line and try again.
            scanf("%*[^\n]\n")
        }
    }
    *pp = NULL;

    return head;
}
于 2013-10-06T22:27:10.923 に答える
0

また、上記のような中置式を格納するには、二分木を使用した方がはるかにうまく機能することがわかります。操作 (+、-、​​、/、^) でツリーのノードを示し、括弧ツリーも持っています (その下にあるものはすべて括弧で囲まれた式です。

式をスキャンすると、再帰的に実行できるツリーが作成されます。

ツリーの出力は、深さ優先、左ノード右トラバーサルを使用して行われます。

于 2013-10-07T19:16:11.030 に答える