5

私に似た問題を検索しようとしましたが、あまり助けが見つかりませんでした。

このタイプの構造体のリンク リストがあります。

struct PCB {
    struct PCB *next;
    int reg1, reg2;
};

最初に、この方法で互いにリンクされた 10 個の PCB 構造体を作成します。

for(i=20;i<=30;i++) {
        curr = (struct PCB *)malloc(sizeof(struct PCB));
        curr->reg1 = i;
        curr->next  = head;
        head = curr;
    }

次に、さらに 20 個の PCB 構造体を作成する必要がありますが、それらのreg1値は を使用して生成する必要がありますrand()。私は現在それをやっています：

for (j = 0;j<20;j++) {
        curr = (struct PCB *)malloc(sizeof(struct PCB));
        curr->reg1 = rand()%100;
        curr->next  = head;
        head = curr;
    }

ただし、これらの PCB 構造体をランダムなreg1値でリンク リストに挿入する場合は、それらをリンク リストに順番に挿入する必要があります (挿入ソート)。単一リンクのリンクされたリストでこれにアプローチする最良の方法は何ですか? ありがとう

編集:最初からリンクされたリストをループできるように、最初に作成された構造体を追跡しています:

// create root struct to keep track of beginning of linked list
root = (struct PCB *)malloc(sizeof(struct PCB));
root->next = 0;  
root->reg1 = 20;

head = NULL;

// create first 10 structs with reg1 ranging from 20 to 30
for(i=21;i<=30;i++) {
    curr = (struct PCB *)malloc(sizeof(struct PCB));
    // link root to current struct if not yet linked
    if(root->next == 0){
        root->next = curr;
    }
    curr->reg1 = i;
    curr->next  = head;
    head = curr;
}

次に、挿入ソートが必要な追加の 10 個の PCB 構造体を作成しているとき:

// create 20 more structs with random number as reg1 value
    for (j = 0;j<20;j++) {
        curr = (struct PCB *)malloc(sizeof(struct PCB));
        curr->reg1 = rand()%100;
        // get root for looping through whole linked list
        curr_two = root;
        while(curr_two) {
            original_next = curr_two->next;
            // check values against curr->reg1 to know where to insert
            if(curr_two->next->reg1 >= curr->reg1) {
                // make curr's 'next' value curr_two's original 'next' value
                curr->next = curr_two->next;
                // change current item's 'next' value to curr
                curr_two->next = curr;
            }
            else if(!curr_two->next) {
                curr->next = NULL;
                curr_two->next = curr;
            }
            // move to next struct in linked list
            curr_two = original_next;
        }
        head = curr;
    }

しかし、これはすぐに私のプログラムをクラッシュさせました。

4

2 に答える 2

6

「最良の」方法は、おそらく挿入用の新しい関数を実装することです。nextこの関数は、ノードの値が挿入するノード以下であるノードが見つかるまでリストを反復処理し、新しいノードをそのノードの前に置きnextます。

この機能はどうですか：

void insert(struct PCB **head, const int reg1, const int reg2)
{
    struct PCB *node = malloc(sizeof(struct PCB));
    node->reg1 = reg1;
    node->reg2 = reg2;
    node->next = NULL;

    if (*head == NULL)
    {
        /* Special case, list is empty */
        *head = node;
    }
    else if (reg1 < (*head)->reg1)
    {
        /* Special case, new node is less than the current head */
        node->next = *head;
        *head = node;
    }
    else
    {
        struct PCB *current = *head;

        /* Find the insertion point */
        while (current->next != NULL && reg1 < current->next->reg1)
            current = current->next;

        /* Insert after `current` */
        node->next = current->next;
        current->next = node;
    }
}

次のように呼び出します。

insert(&root, rand() % 100, 0);
于 2013-04-11T22:36:15.740 に答える
3

@Joachim の簡略版は次のとおりです。

void insert(struct PCB **head, const int reg1, const int reg2)
{
    struct PCB *new ;
        /* Find the insertion point */
    for (       ;*head; head = & (*head)->next)
    {
        if ((*head)->reg1 > reg1) break;
    }

    new = malloc(sizeof *new );
    new->reg1 = reg1;
    new->reg2 = reg2;
    new->next = *head;
   *head = new;
}

アイデアは単純です:特別なケースは必要ありません。どのような場合でも: ポインターを変更する必要があります。これは、ルート ポインター、テール ポインター、または LL の中間にあるポインターである可能性があります。どのような場合でも:

  • 新しいノードは実際にこのポインタを盗みます:
  • それはそれ自体を指すようにします
  • 以前の値を後続として採用します (それをその->nextポインターに割り当てます。
于 2013-04-11T23:44:16.147 に答える