0

strcmp() 関数を使用して、ポインター構造体の最初の項目に基づいてアルファベット順にリンクされたリストに新しいノードを挿入する方法の簡単な例を誰でも提供できますか? 本当に答えを探しているわけではありませんが、あいまいな例を使った説明だけでは、直接的な答えを見つけることができなかったので、誰かが私を助けてくれることを願っていました. 前もって感謝します。

4

3 に答える 3

1

リンク リスト ノードが次のようになっているとします。

typedef struct node {
    char* str;
    struct node* next;
} NODE;

アルファベット順に並べ替えられたリンク リストに新しいノードを挿入する場合は、次の 4 つのケースを考慮する必要があります。

  1. リストが空であるため、挿入されるノードは最初/唯一のノードです
  2. 挿入するノードは、リスト内の最初のノードのアルファベット順で前になります
  3. ノードは真ん中に挿入されます
  4. ノードはリストの最後に挿入されます。

ただし、次のことを前提としています。

  1. 空のリストは適切に に設定されNULL、
  2. 挿入するノードはnext適切に設定されていますNULL

最初の 2 つのケースと最後の 2 つのケースを組み合わせて挿入を処理できるため、論理的な選択肢は 1 つだけです。つまり、新しいノードを最初のノードとして挿入するか、リスト内の他のノードとして挿入するかです。

これら 2 つのケースに取り組む簡単なアルゴリズムを次に示します。

algorithm insert

receives: list, pointer to linked list
    toInsert, pointer to new node for insertion

returns: pointer to updated list with new node inserted. 

1. if (list is null OR toInsert->value is less than list->value)  
    1.1 set toInsert->next to list
    1.2 set list to toInsert
2. else
    2.1 set pPre to list
    2.2 set pWalk to list->next
    2.3 loop while (pWalk is not null AND toInsert->value is greater than pPre->value)
        2.3.1 set pPre to pWalk;
        2.3.2 set pWalk to pWalk->next;
    2.4 set pPre->next to toInsert;    
    2.5 set toInsert->next to pWalk;
3. return

これを実装するには、と 条件のstrcmp()両方で使用する必要があります。ifwhile

strcmp()「アルファベット順」ではなく、ASCII 順で文字列を比較することに注意してください。関係する限り、'B'後'A'ですが前に来ます。大文字と小文字を区別しない厳密なアルファベット順の並べ替えが必要な場合は、大文字と小文字を区別しない独自のバージョンを作成し、.'a'strcmp()strcmp()insert()

于 2013-09-12T23:57:49.327 に答える
0

リンクされたリストがすでにアルファベット順にソートされている場合は、新しいノードの後に​​ある必要がある最初のノードまで反復し、その前に新しいノードを挿入する必要があります。next最後のノードのポインターが新しいノードを指している必要があるため、反復の現在のノードの前のノードを覚えておく必要があります。リストのサイズがゼロの場合や境界に挿入する場合など、いくつかのケースを一意に処理する必要がある場合があります。

アルファベット順のソートと ascii によるソートの違いに注意してください。違います。(アルファベット順: 11 > 9、ASCII: 11 < 9)

于 2013-09-12T20:59:59.153 に答える