[資料構造論]Cで接続リストを作成する

試験の時間はもうすぐです.
今度はやはり一時的に仏足を抱くようだ...
ガストンのデザインをしたので、ほとんど時間を割いて授業を受けることができませんでした.ハハ...
中間試験の後、初めて資料構造論書を読みましたが、幸い今月はコードテストに入り、いろいろな資料構造を勉強して試験範囲に入りました.(DFS/BFS、heapqなど)
今日はCで接続リストを作ります

接続リスト

接続リストは、オブジェクトのサイズを動的に変更し、削除または挿入時にデータを移動する必要がないオブジェクトです.チェーンかと思って理解しました

これからは、ノードという用語でブロックを表します.
上図には、A、B、C、Dの4つのノードを含む接続リストが表示されます.
BとCの間にノードを追加する場合は、2つのノード間のチェーンを一時的に切断し、Bからのチェーンを新しく追加したノードに掛け、新しく追加したノードとCを新しいチェーンに接続するだけです.
同様に、データCを削除する場合は、CとCからのチェーンを削除して、BのチェーンをDに接続すればよいのではないでしょうか.
では、ノードには何が必要ですか?まず上の図のA B C Dのようなデータが必要ですよね?
次に、次のノードへのチェーンが必要です.通常、これらのチェーンはlinkと呼ばれます.
次のノードを指しますか?これは何を意味しますか?これが住所です.linkはポインタ変数を使用する必要があります.
次に、これらの情報に基づいて、接続リストのListNodeコンポーネントを定義します.

宣言と接続

ListNodeの定義

typedef char element;

typedef struct ListNode {
   element data;
   struct ListNode *link;
} ListNode;

これで実施できます.ノードの構造が宣言され、ノードが作成されていないことに注意してください.

空白リストノードの作成

[単純接続](Simple Connection)リストのすべてのノードは、1つのヘッダポインタだけで見つかります.
ポインタheadの定義:

ListNode *head=NULL;

このようにヘッダポインタを宣言すると、ヘッダポインタがNULLである簡単な接続リストが作成されたと考えられます.
今回はノードを作成しましょうか?

head ListNodeにデータを割り当てる

head=(ListNode *)malloc(sizeof(ListNode));
head->data="A";
head->link=NULL;

malloc()を使用すると、ダイナミックメモリ割り当てです.その後、headという名前のListNodeにデータを指定できます.後のノードが存在しないため、linkはNULLに設定されます.現在のステータスは次のとおりです.

次に、ノードを接続し続けましょう.
pという名前のListNodeを作成して「B」というデータを割り当てましょうか?

ListNode *p;
p=(ListNode *)malloc(sizeof(ListNode));
p->data="B";
p->link=NULL;

今感じていますか?
以前作成したhead ListNodeと現在作成しているp ListNodeを接続します

ListNode間の接続

head->link=p;

思ったより簡単かな?このように、現在の状態を下図に示します.

接続リスト関数

実装する接続リストの関数は次のとおりです.

insert first():リストの先頭に項目を挿入する関数

insert():リストの間に項目を挿入するための関数

delete first():リストの最初の項目を削除するための関数

delete():リストから項目を削除する関数

print list():関数

、アクセスリストからすべてのアイテムを出力

insert_first()

insert first()から始めましょう.
以前headというやつが最初のノードを指していましたよね?新しいノードを作成し、現在のhead値を新しいノードのリンクに保存し、新しく作成したノードを指します.
アルゴリズムは次のとおりです.
insert_first(head,value):
1, p->malloc()
2,p->データ<-value//新しく作成したノードに値を割り当てる
3,p->リンク<-head//新しく作成したノードのリンクは既存head
4,headは<-p//先頭の要素なのでheadに変更
5, return head
次のコードとして表示します.

ListNode * insert_first(ListNode *head, element value){
  ListNode *p=(ListNode *)malloc(sizeof(ListNode));
  p->data=value;
  p->link=head;
  head=p;
  return head;
}

よく考えてみると、わかりやすいです:)

insert()

上記のinsert first()を理解していれば、insert()も簡単に理解できます.パラメータとして、入る位置の前のノードが必要です.
「新しく加入したノードにBからのチェーンを掛けて、新しく加入したノードとCを新しいチェーンに接続すればいい」と言いました.って言ったでしょ?
アルゴリズムは次のとおりです.
insert(head,pre,value):
1, p->malloc()
2, p->data <- value
3、p->リンク<-pre->リンク//以前のノード接続のリンクが新しいpのリンクに変更されました
4,pre->link<-p//以前のノードがpにリンクされました
5、head//戻るいつもhead!
コードによる実装:

ListNode * insert(ListNode *head, ListNode *pre ,element value){
  ListNode *p=(ListNode *)malloc(sizeof(ListNode));
  p->data=value;
  p->link=pre->link;
  pre->link=p;
  return head;
}

delete_first()

データを挿入する関数を知っている以上、今度は削除関数を知っているのではないでしょうか.delete first()を実装しましょう.
挿入とは少し違います.今回はfree()というメモリリターンメソッドを使用する必要があります.delete first()なのでheadに指定されたノードを削除すべきでしょうか?headは失われてはいけない要素なので、「削除」というListNodeを作成し、既存のheadの値を「削除」ノードに移動し、headの値を次のノードへのリンクに変更して「削除」に戻るだけです.
アルゴリズムは次のとおりです.
delete_first(head):
1, removed <- head
2, head <- head->link
3,free(削除)/remove戻り
4、head//戻るいつもhead!
その上でコードを実装してみましょうか?

ListNode * delete_first(head){
  ListNode *removed;
  if(head==NULL) return NULL; => 이미 head 요소가 없는 경우
  head=removed->link;
  free(removed);
  return head;
}

delete()

delete()もdelete first()と同じメカニズムを有する.
しかしながら、中間処理のため、preという既存のパラメータ、例えば類似のinsert()が必要である.
アルゴリズムは次のようになります.
delete(head,pre):
1, removed <- pre->link
2, pre->link <- removed->link
3, free(removed)
4, return head
今は分かりやすいでしょう?
すぐにコードの作成を始めます.

ListNode * delete_first(head){
  ListNode *removed;
  removed=pre->link; 
  pre->link=removed->link;
  free(removed);
  return head;
}

print()

接続リストだとprint()も特別な顔をしています一度理解していただくと感じやすくなります
まずfor反復文を使用してノードにアクセスしprintfを処理する必要があります.
for文はいつまで繰り返されますか?NULL値に遭遇するまでheadから繰り返さなければなりません.また,p=p->linkという演算を繰り返す.ソースコードの作成を開始します.

for(ListNode *p=head; p!=NULL;p=p->link)
   printf("%d->",p->data);
printf("NULL \n");   

おもしろいですか?🤗

LinkedListコード

上記の関数に基づいて接続リストを実装します.

#include <stdio.h>
#include <stdlib.h>

typedef int element;
typedef struct ListNode{
    element data;
    struct ListNode *link;
} ListNode;

void error(char *message){
    fprintf(stderr,"%s\n",message);
    exit(1);
}

ListNode* insert_first(ListNode *head,element value){
    ListNode *p=(ListNode *)malloc(sizeof(ListNode));
    p->data=value;
    p->link=head;
    head=p;
    return head;
}

ListNode* insert(ListNode *head,ListNode* pre, element value){
    ListNode *p=(ListNode *)malloc(sizeof(ListNode));
    p->data=value;
    p->link=pre->link;
    pre->link=p;
    return head;
}

ListNode* delete_first(ListNode *head){
    ListNode *removed;
    if(head==NULL) return NULL;
    removed=head;
    head=removed->link;
    free(removed);
    return head;
}

ListNode* delete(ListNode *head,ListNode *pre){
    ListNode *removed;
    removed=pre->link;
    pre->link=removed->link;
    free(removed);
    return head;
}

void print_list(ListNode *head){
    for (ListNode *p=head;p!=NULL;p=p->link){
        printf("%d->",p->data);
    }
    printf("NULL\n");
}
int main() {
    ListNode *head=NULL;

    for(int i=0;i<5;i++){
        head=insert_first(head,i);
        print_list(head);
    }
    for(int i=0;i<5;i++){
        head=delete_first(head);
        print_list(head);
    }

    return 0;
}

実行結果は次のとおりです.
0->NULL
1->0->NULL
2->1->0->NULL
3->2->1->0->NULL
4->3->2->1->0->NULL
3->2->1->0->NULL
2->1->0->NULL
1->0->NULL
0->NULL
NULL

🤔 接続リストを使用する理由

私は歩きながら探していたが、この問題は開発者の面接でよく見られることに気づいた.接続リストと配列の違いを結びつけて整理することが役に立つと思います.

アレイの主な違いとメリットとデメリット

「接続」リストには、論理順にデータが入力されます.しかし、物理アドレスは連続していません.
インデックス付き配列とは異なり、接続リストには、インデックスではなく現在の位置の前の位置と次の位置が記憶されます.その欠点は、データに一度にアクセスできず、接続されたリンクに従ってデータにアクセスしなければならず、配列よりも速度が遅いことです.アレイに比べて実装の難易度が高いのも欠点です.
ただし、データの挿入/削除は論理アドレスを変更するだけで済むため、データの挿入/削除は容易です.

n/a.結論

データアクセスが頻繁で、挿入/削除の可能性が低い場合は、配列を使用することをお勧めします.
データを挿入/削除する頻度がデータにアクセスする頻度より高い場合は、接続リストを使用することをお勧めします.

の最後の部分

初めて接続リストに触れたとき、資料の構造に対する理解は少し下がりましたか?そう思うよ
一方、ポインタの概念をよく定義すると、スタックやキューよりも理解しやすいと思います.
長い議論を読んでいただき、ありがとうございました.