【解決方法】リンクリストの実装でどこが間違っていますか?


間違ったフォーラムにいる場合はまずお詫びします。インターネット上ですでに何千ものリンクリストの実装が利用可能であることは知っていますが、特定の実装でどこが間違っているのかを議論して確認できる場所を探しています。そのため、アルゴリズムの考え方を改善できます。

DSAの学習を始めたばかりで、リンクリストを実装しようとしています。 いくつかのチュートリアルを見てきましたが、リンクリストの概念はかなり明確ですが、リンクリストを実装しようとすると問題に直面しています。

このデータ構造の理解に従ってコードを書きましたが、最初の要素が追加された後は機能していないようです。

私が試したこと:

C++
// LINKEDLIST
#include <stdio.h>
#include <stdlib.h>

struct Node {
	int data;
	struct Node* next_node;
};

struct Node* head_ptr = NULL; // linkedlist is empty initially

void addData(int val, struct Node* ptr_h) { // always head node will be passed to parameter
	struct Node* temp;

	if(ptr_h == NULL) {
		head_ptr = (struct Node*)malloc(sizeof(struct Node));
		temp = head_ptr;

		temp->data = val;
		temp->next_node = NULL;
	}
	else if(ptr_h != NULL) {
		temp = ptr_h;
		while(temp != NULL) {
			temp = temp->next_node;
		}
		temp = (struct Node*)malloc(sizeof(struct Node));
		temp->data = val;
		temp->next_node = NULL;
	}
}

int main(int argc, char const *argv[])
{
	addData(5, head_ptr);
	addData(7, head_ptr);
	addData(6, head_ptr);
	addData(6, head_ptr);

	int i = 0;
	struct Node* address = head_ptr;
	while(address != NULL) {
		i++;
		printf("%d\n", address->data);
		printf("%p\n", address->next_node);
		address = address->next_node;
	}
	printf("count is : %d\n", i);
	return 0;
}

という名前の関数を書きました addData() その目的は要素を追加することです。 ヘッドポインターがありますhead_ptr リンクリストの開始点を参照するために、常に手元に置いておくつもりです。

ロジックはいつでも addData() が呼び出されると、リストが空であるか、すでに初期化されているかどうかがチェックされます (これは、ヘッド ポインターが NULL を参照しているかどうかをチェックすることによって実行されます)。
NULL を参照する場合、一部のメモリは動的に割り当てられます。 malloc() そしてその head_ptr (最初は NULL) にこのアドレスが割り当てられます。 これに続いて、渡されたパラメーターに従って次のノードのデータ要素を割り当てます addData()、および同じ次のノードのポインター要素が次のように割り当てられます NULL リストがそこで終了することを示します。
私の理解によると、この多くのコードは正常に機能しています。 main()、最初の要素を出力します。

問題は次のコード ブロックにあると思います。 head_ptr 等しくない NULL、一時変数 temp その値が割り当てられ、次のアドレスが割り当てられます。 NULL. この後、一部のメモリは再び動的に割り当てられます malloc()、およびそのアドレスはに割り当てられます temp この変数は、関数パラメーターを介して渡される値として次のノードのデータ要素を設定するために使用され、同じ次のノードのポインター要素は NULL として設定され、リストがそこで終了することを示します。

の中に main()、カウンターを置いています i=0、およびポインターを反復処理し、各ノードのデータとポインター要素を出力します。 最初の要素を出力しますが、ポインタ要素は NULL 最初の要素が追加された後、それ以上の要素が追加されなかったことを示し、変数 i ループが停止すると、too は 1 になります。

出力は次のとおりです。

「ターミナル」
5
(nil)
count is : 1

私はコードを何度も調べましたが、どこが間違っているのか理解できません。 私は、どこが間違っているのかを理解できる方向に進むのを手伝ってくれるような、ある種の議論を期待しています.

解決策 2

0x01AA そうです、新しく作成したノードをリストに追加するのを忘れていました。
さらに、最初の挿入時に「ヘッド」ポインターを更新する必要があります。 たとえば、次のようにしてください。

C
void addData(int val, struct Node ** pphead)
{
  struct Node * temp = *pphead;

  if ( ! temp )
  {
    temp = (struct Node *) malloc(sizeof (*temp));
    temp->data = val;
    temp->next_node = NULL;
    *pphead = temp;
  }
  else
  {
    // here temp != NULL
    while (temp->next_node)
    {
      temp = temp->next_node;
    }

    temp->next_node = (struct Node *) malloc(sizeof(*temp));
    temp->next_node->data = val;
    temp->next_node->next_node = NULL;
  }
}

int main(int argc, char const *argv[])
{
  addData(5, &head_ptr);
  addData(7, &head_ptr);
  addData(6, &head_ptr);
  addData(6, &head_ptr);
//...

解決策 1

最初:チェックする必要はありません else if(ptr_h != NULL). シンプルな else で十分です。

次に、else 部分のコードは次のようになります。

else
{
   temp= ptr_h;
   while(temp->next_node != NULL)
   {
      temp= temp->next_node;
   }
   // At this point, temp points to the last existing element.
   temp->next_node= (struct Node*)malloc(sizeof(struct Node));
   temp->next_node->data = val;
   temp->next_node->next_node = NULL;
}

ところで。 私は使うだろう new それ以外の malloc

私が間違っていないことを願っています。

コメント

タイトルとURLをコピーしました