4

それらがどのように機能するかを理解しようとしていますが、多くの困難があります。それらを直感的に説明したり、トピックを始めたばかりの人に適していると思われるリソースを提供したりしたい人はいますか?

だから私はこれを持っているとしましょう：

struct node
{
   int nodeNum;
   nodes *next;
}

「ヘッド」ノードを作成するには、次のnode *head = new node;ようにします。リンクされたリストが のようになるようにしここに画像の説明を入力ます。割り当て後:

head->nodeNum = 10;
head->next = NULL;

私たちは持っていここに画像の説明を入力ます。ノードを挿入する関数を書きたい場合は、次のように記述できます。

void insert(node *previousNode, int num)
{
    previousNode = new node;
    previousNode->nodeNum = num;
    previousNode->next = NULL;
}

たとえば、insert(head, 20);新しいリストは次のようになりここに画像の説明を入力ます。

すべてが正しい場合、この情報を使用して、リストからノードを検索および/または削除するにはどうすればよいですか? head = head->next;たとえば、ノードのトラバースは、説明したように直感的ではありません。これはどのように作動しますか？

このトピックを理解しやすくするためのアドバイスをいただければ幸いです。みんな助けてくれてありがとう！

4

6 に答える 6

3

挿入機能が正しく機能しません。リストに追加せずに新しいノードを作成し、関数が戻ったときにそれを失います（メモリリークが発生します）：

head -> 10 -> NULL     becomes    head -> 10 -> NULL
                                  (lost)  20 -> NULL

代わりに、リストの古い末尾を新しいノードにリンクし、古いノードの後に​​新しいノードを挿入する必要があります。

void insert(node * prev, int num) {
    node * new_node = new node;
    new_node->nodeNum = num;
    new_node->next = prev->next;  // add the old tail after the new node
    prev->next = new_node;        // add the new node after the old node
}

insert(head, 20); // insert 20 after the head
// head -> 10 -> NULL   becomes    head -> 20 -> 10 -> NULL

この情報を使用して、リストからノードを検索または削除するにはどうすればよいですか?

反復するには、見ている要素への独自のポインターを維持します。これは から始まり、最後に到達する (つまりnull になる)までポインターheadに従います。nextnext

for (node * n = head; n; n = n->next) {
    if (n->nodeNum == 20) {
        std::cout << "Found node 20!\n";
        break;
    }
}

単方向リストからノードを削除するには、そのnextポインターを更新するために、ノードの前にそのノードへのポインターが必要です。

void remove_next(node * prev) {
    if (prev->next) {
        node * next = prev->next->next;  // Get the tail after the removed node
        delete prev->next;
        prev->next = next;               // Add the tail after the remaining node
    }
}

remove_next(head);
// head -> 20 -> 10 -> NULL    becomes    head -> 10 -> NULL
于 2012-11-28T12:08:32.370 に答える
3

あなたの問題はここにあります：

void insert(node *previousNode, int num)
{
previousNode = new node;
previousNode->nodeNum = num;
previousNode->next = NULL;
}

insert(head, 20);

このコードが previousNode = new node;行うことは次のとおりです。ノードへのポインターを作成し、そのポインターを previousNode に割り当てます。PreviousNode はコピー ヘッドとして開始されましたが、現在は何か新しいものを指しています。ここで、新しいノードに値を割り当てます。つまり、この挿入の実装は挿入しません。

あなたがしたいことは、次のようなものです：

void better_insert(node *previousNode, int num)
{
    node *post_node = new node;    #create a brand new pointer to a brand new node
    post_node->nodeNum = num;      #give it a number
    post_node->next = previousNode->next; #we want previousNode to be behind new node
    previousNode->next = post_node;     
}

これが何をするか: 新しいノードを作成し、新しいポインタでそれを指した後、それに番号を付けます。次は、ポインタが指している場所を整理することです...

リンクされたリストでいくつかのノードを振るふりをしましょう。小文字はすべてポインタですよね？

a->next = b

ここで、 nodeが のx後に来aて、番号が 10 であるとします... `better_insert(a, 10) を呼び出します

post_node新しいノード (ノード x) を指し、10 が割り当てられます。

私たちが欲しい：

a->next = x
x->next = b

我々は持っています：

a->next = b
x->next = null

関数の最後の 2 行は、請求書に収まるまでシャッフルするだけです

というわけで詳しく…

我々は持っています：

a->next = b
x->next = null

したがって、次のように呼びます。

post_node->next = previousNode->next; #we want previousNode to be behind new node

a->next = b x->next = b

今、私たちは呼び出します:

previousNode->next = post_node;

最終的には次のようになります。

a->next = x
x->next = b

または他の「言葉」で：

a->next = x
a->next->next = b
于 2012-11-28T12:11:56.507 に答える
2

コードでより多くの変数を使用する必要があります。insert操作は2 つのノードを変更します。前のノードは新しいノードを指すように変更する必要があり、新しいノードを作成して、前のノードの後のノードを指すようにする必要があります (NULL の場合とそうでない場合があります)。

void insert(node *previousNode, int num)
{
    node *newnode = new node;
    newnode->nodeNum = num;
    newnode->next = previousNode->next;
    previousNode->next = newnode;
}

リストをトラバースするには、あるノードから次のノードに変更できる「現在のノード」を追跡します。

while (currentNode != 0) {
    do_something_with(currentNode);
    currentNode = currentNode->next;
}

もちろん、do_something_withがノードを削除すると、後でそこから進むことはできません。また、単方向リストからノードを削除するには、ノードの前にそのノードへのポインターが必要です。その場合、ループは 1 つだけではなく、現在と前の 2 つのノードを追跡する可能性があります。

于 2012-11-28T12:09:33.730 に答える
1

通常、リンクされたリストのノードには番号が含まれていません。これは通常、データと次のノードへのポインタで構成されます。また、コードにタイプミスがないようにする必要があります。

typedef Data int;

struct node
{
   Data data; // some Data
   node *next;   // pointer to the next node
}

一般に、指定したノードの後に​​新しいノードを追加するのではなく、リストに追加する必要があります。void insert(node *previousNode, int num)署名は、指定された前のノードの後に​​新しいノードが必要であることを示唆しています。

技術的には、3 つの方法で新しいノードをリストに追加できます。リストの最初または最後、または途中のどこかに。最初に追加するのが最も速くて簡単です。

void insert(Data num)
{
    node* tmp = new node;  //make a new node
    tmp->data = num;       //fill in data
    tmp->next = head;      //set the next element of new one to be the current head
    head = tmp;            //set new element as the head
}

このようにして、新しい要素をリストの前に置きます。常に一方向リンク リストを先頭から最後までトラバースします。

void print_all()
{
   node* current = head;      // start at head
   while(current != NULL){    // while element exists
     cout << current->data << ' ';   //print its data
     current = current->next; //move to the next one
   }
}

データのボックスと の矢印の付いた写真があると非常に理解しやすいですnode* next。

それは初心者向けです。insertリストが最初は空である特殊なケースを処理するには、関数を変更する必要があります。すなわちhead == NULL。

また、オブジェクト指向の方法で実装することを強くお勧めします。class Listを利用した書き方struct node。

class List {
  private:
    node* head;
  public:
    List();
    void insert(data);
    void print_all();
}

これらの機能を実装してみてください。私の経験から、この方法で物事を行うと、データ構造とコンテナーについての考え方を整理するのに役立ちます。

于 2012-11-28T12:14:27.357 に答える
1

あなたが使っている用語はあなたを混乱させています。願わくば、この例えがあなたをさらに混乱させないことを願っています。基本的に、リンクされたリストをこの恐ろしい出入り口のセットとして想像してください。1 つの出入り口に入ると、後ろで閉まり、その部屋にあるものしか見えないか、次の部屋に行くことができます。この廊下の外からは、入り口がどこにあるのかしかわかりません。

したがって、リンクされたリスト構造の外側からは、入り口であるポインタしかわかりませんll_node *head;。内部にheadは、いくつかのデータと、リンクされたリストの次のノードへのポインターがあります。そのリンクされたリストをたどるのは、廊下の入り口から始めて、head探しているノードが見つかるまで一度に 1 つの廊下に入るだけです。

ll_node *current_location = head;
while (current_location != NULL)
{
   // if we are at the node that you were hoping to reach, exit.
   if (current_location->nodeNum == target_data_im_looking_for)
   {
      break;
   }
   // this isn't the node you're looking for, go to the next one.
   current_location = current_location->next;
}

同様に、ノードを挿入すると、リンクされたリストの最後までトラバースし (までcurrent_location->next == NULL)、最後の要素の次のポインターを、作成した新しいのメモリ位置に置き換える必要がありll_nodeます。学習する機会があるので、私はあなたのためにそれを実装しませんが、ここにはあなたが望む場所に到達するのに十分なものがあります.

于 2012-11-28T12:06:48.930 に答える
0

上記のリストには、nodeNum などの情報がほとんどありません。より多くのイオン形成を保持する必要があります。たとえば、値 nodeNum = 10 のノードでは、そのノードから取得したい他の情報があるはずです。そのため、ユーザーが呼び出すときに

node* search(node *head,int num){
      node *temp = head;//copy node reference into temp variable
      while (temp != NULL){
            if (temp->nodeNum == num){
               return temp;
            }
            temp = temp->next;
      }

}

ノードでそのノードのデータを取得できます

 res = search(head,10);

削除用

bool delete(node *head,int num){
      node *temp = head;//copy node reference into template
      node *prev = NULL;
      bool isDelete = false;
      while (temp != NULL){
            if (temp->nodeNum == num){
               break;
            }else
               prev = temp;
               temp = temp->next;
            }
      }
      if (temp != NULL){
          prev-> next = temp->next;//maintain list
          delete temp;
          isDelete = true;
      }
      return  isDelete;
}
于 2012-11-28T12:17:22.683 に答える