データ構造でーたこうぞう:接続リストせつぞくりすと

接続リストバー

データを格納して表現するリスト型資料構造の1つです.
ここで、接続リストには複数のノードが含まれ、ノードにはデータが含まれ、各ノードにはデータの一部が含まれ、次のノードの位置を指す参照データ情報が含まれます.

ノード実装

// C++ 구현
typdef struct node{
    DataType data;
    node * next_node;
}node;

ノード自体の実現は難しくない.変数と次のノードへのポインタまたは参照者を宣言するだけでノードになります.
データ型はいかなる形式にも制限されず、1つのノードに複数のデータ変数が含まれていても構わない.勝手にしろ

リスト内のADT

私が作成した接続リストのADTは次のとおりです.

class LinkedList{
private:
    node * head;
    node * make_new_node(int data);
public:
    LinkedList();
    ~LinkedList();
    void insert_node(int data);
    void insert_node(int data, int target_nodes_data);
    void print_list();
    void search_node(int target_nodes_data);
    void delete_node(int target_nodes_data);
    bool is_empty();
}

各関数の役割と実現は以下の通りである.

node * make_new_node(int data){
   node * new_node = new node();
   new_node->data = data;
   new_node->next_node = nullptr;
   return new_node;
}

この関数は、新しいノードを作成してアドレスを返すことができます.各挿入関数にはいくつかの新しいノードがコードを生成し、不便で乱れているように見えるので、個別の関数に分離します.

LinkedList() { head = nullptr; }

ジェネレータの役割は、クラスが持つヘッダポインタを空のポインタに初期化することです.もしヘッドポインタがあなたのポインタであれば、リストが空であることを意味するので、私はポインタであなたを初期化しました.

~LinkedList(){
    node * delete_target;
    while(cur){
        delete_target = head;
        head = head->next_node;
        std::cout << delete_target->data << " 삭제됨" << std::endl;
        delete delete_target;
    }
    head = nullptr;
}

消滅者は残りのノードを順次迂回し、すべて削除します.リストのノードが動的に割り当てられ、書き込まれているため、クリアしないとメモリが漏洩する可能性があります.
カーソルに空のポインタがある場合は、これが最後のノードであることを示し、巡視を停止して関数を終了します.

void insert_node(int data){
   node * cur = head;
   while(cur->next_node)
       cur = cur->next_node;
   cur->next_node = make_new_node(data);
}

新しいノードの挿入を生成する関数は、2つの関数を上書きします.1つは、最後に新しいノードを挿入する関数であり、もう1つは、ターゲットノードを指定し、そのノードの真後ろに新しいノードを挿入する関数です.
上の関数は、最後に新しいノードの関数を挿入し、カーソルのnext nodeがnullptrになるまで次のノードを参照し続けます.カーソルのnext nodeがnullptrの場合、ノードが最後のノードであることを示し、ノードのnext nodeは新しく作成されたノードを指します.

void insert_node(int data, int target_nodes_data){
    node * cur = head;
    while(cur->next_node){
        if(cur->data == target_nodes_data){
            node * new_node = make_new_node(data);
            new_node->next_node = cur->next_node;
            cur->next_node = new_node;
            return;
        }
        cur = cur->next_node;
    }
   
    cur->next_node = make_new_node(data);

この関数は、ターゲットノードを指定し、そのノードの後ろに新しいノードを作成することによって挿入されるオーバーロード関数です.ターゲットノードは、データを持つノードを検索してナビゲートし、発見された場合はノードの後ろに挿入し、ない場合は最後に直接挿入します.
新しいノードを挿入するときnew_node->next_node = cur->next_node;先にやった理由は下図のようです

上の図に示すように、カーソルが向いているターゲットノードのみが、新しい挿入ノードの次のノードアドレスに関する情報を持っています.しかし、この状態で、まずターゲットノードを新しく作成したノードに指し示すのでしょうか.

上の図に示すように、カーソルが指す次のノードでは、検索方法が失われます.失われたノードのアドレス情報は、カーソルが指すターゲットノードのみが持つためです.
だからこんなことを防ぐために.

まず、新しく作成したノードは、カーソルが指すターゲットノードの次のノードを指します.

次に、カーソルが指すターゲットノードを新しく作成したノードに向けます.これにより、参照が失われる問題を回避できます.

void print_list(){
    node * cur = head;
    while(cur){
        std::cout << cur->data << ' ';
        cur = cur->next_node;
    }
    std::cout << std::endl;
}

これは出力リストの簡単な関数です.カーソルがnullptrを指す前に、次のノードを参照し、そのノードのデータを出力します.

void search_node(int target_nodes_data){
    node * cur = head;
    while(cur){
        if(cur->data == target_nodes_data){
            std::cout << cur->data << "를 발견함" << std::endl;
            return;
        }
        cur = cur->next_node;
    }
    // 찾으려는 노드가 존재하지 않을 경우
    std::cout << "해당 노드가 존재하지 않습니다" << std::endl;
}

関数として、ノードに対応するデータがあるかどうかを探索し、ノードを順次巡回し、ノードが存在する場合は検出されたノードを出力し、検出されない場合は存在しないメッセージを送信し、終了します.

void delete_node(int target){
    node * cur = head;
    node * prev = nullptr;

    // 만일 삭제 대상 노드가 맨 앞의 노드일 경우
    if(cur->data == target_nodes_data){
        head = head->next_node;
        std::cout << cur->data << " 삭제" << std::endl;
        delete cur;
        return;
    }

    // 삭제 대상 노드가 헤드 노드가 아닐 경우
    while(cur){
        // 노드를 찾았을 경우
        if(cur->data == target_nodes_data){
            prev->next_node = cur->next_node;
            std::cout << cur->data << " 삭제" << std::endl;
            delete cur;
            return;
        }
        // 찾는 노드가 아니면
        prev = cur;
        cur = cur->next_node;
    }

    std::cout << "대상 노드가 없습니다" << std::endl;

この関数は、削除されたノードを検索して削除する関数です.削除するノードが見つからない場合は、ノードが見つからないというメッセージが表示され、終了します.
この関数は、上の中間にノードを挿入する関数と同様に、最初にターゲットノードを削除するとリストが中断するため、ターゲットノードを削除する前に、前のノードprevノードが削除ターゲットの次のノードを指し、削除ターゲットノードが削除されます.
理解しにくい場合は、上の図を逆順で見ると分かりやすいですか?

リスト内のアクション結果

では、このリストの動作結果を見てみましょう.

int main(int argc, char * argv[]){
    LinkedList list;
    
    for (int i = 0; i < 5; i++)
        list.insert_node((i + 1) * 10);
    list.insert_node(100, 30);
    list.insert_node(200, 90);
    // 10 20 30 100 40 50 200
    list.print_list();
    
    list.search_node(10); // 10을 찾음
    list.search_node(100); // 100을 찾음
    list.search_node(1000); // 해당 노드를 찾지 못함
    
    list.delete_node(50); // 50삭제
    list.print_list();
    list.delete_node(300); // 해당 노드를 찾지 못함
    
    return 0;
}

よく動く