配列に続いて、2番目に人気のあるデータ構造はリンクリストです。リンクリストは線形データ構造であり、各ノードに値とチェーン内の次のノードへのポインタが含まれるノードのチェーンで構成されます。この記事では、Cでリンクリストを実装する方法を見てみましょう。
Cのリンクリストとは何ですか？
リンクリストは線形データ構造です。すべてのリンクリストには、データセクションと、ノードと呼ばれるリスト内の次の要素のアドレスを保持するアドレスセクションの2つの部分があります。
リンクリストのサイズは固定されておらず、データ項目はリスト内の任意の場所に追加できます。欠点は、ノードに到達するために、最初のノードから必要なノードまでずっとトラバースする必要があることです。リンクリストは配列に似ていますが、配列とは異なり、メモリに順番に格納されません。
リンクリストの最も一般的なタイプは次のとおりです。
リンクリストの例
形式：[データ、アドレス]
頭-> [3,1000]-> [43,1001]-> [21,1002]
マージソート擬似コードc ++
この例では、番号43はロケーション1000に存在し、アドレスは前のノードに存在します。これは、リンクリストがどのように表されるかです。
基本的なリンクリスト機能
Cのリンクリストに実装できる関数は複数あります。サンプルプログラムを使用して、それらを理解してみましょう。まず、リストを作成して表示し、任意の場所に挿入し、場所を削除します。次のコードは、リストで操作を実行する方法を示しています。
#include #include void create（）void display（）void insert_begin（）void insert_end（）void insert_pos（）void delete_begin（）void delete_end（）void delete_pos（）struct node {int info struct node * next} struct node * start = NULL int main（）{int choice while（1）{printf（ 'n MENU n'）printf（ 'n 1.Create n'）printf（ 'n 2.Display n'）printf（ 'n 3.Insert at開始n '）printf（' n 4.最後に挿入n '）printf（' n 5.指定された位置に挿入n '）printf（' n 6.最初から削除n '）printf（' n7。削除末尾からn '）printf（' n 8.指定した位置から削除n '）printf（' n 9.Exit n '）printf（' n ----------------- --------------------- n '）printf（' Enter your choice：t '）scanf（'％d '、＆choice）switch（choice）{case 1 ：create（）ブレークケース2：display（）ブレークケース3：insert_begin（）ブレークケース4：insert_end（）ブレークケース5：insert_pos（）ブレークケース6：delete_begin（）ブレークケース7：delete_end（）ブレークケース8： delete_pos（）break case 9：exit（0）break default：printf（ 'n Wrong Choice：n'）break}} return 0} voi d create（）{struct node * temp、* ptr temp =（struct node *）malloc（sizeof（struct node））if（temp == NULL）{printf（ 'nOut of Memory Space：n'）exit（0） } printf（ 'nノードのデータ値を入力：t'）scanf（ '％d'、＆temp-> info）temp-> next = NULL if（start == NULL）{start = temp} else {ptr = start while（ptr-> next！= NULL）{ptr = ptr-> next} ptr-> next = temp}} void display（）{struct node * ptr if（start == NULL）{printf（ 'nList is empty： n '）return} else {ptr = start printf（' nリスト要素は次のとおりです：n '）while（ptr！= NULL）{printf（'％dt '、ptr-> info）ptr = ptr-> next}}} void insert_begin（）{struct node * temp temp =（struct node *）malloc（sizeof（struct node））if（temp == NULL）{printf（ 'nOut of Memory Space：n'）return} printf（ 'nEnter theノードのデータ値：t '）scanf（'％d '、＆temp-> info）temp-> next = NULL if（start == NULL）{start = temp} else {temp-> next = start start = temp }} void insert_end（）{struct node * temp、* ptr temp =（struct node *）malloc（sizeof（struct node））if（temp == NULL）{printf（ 'nOut of Memory Space：n'）return} p rintf（ 'nノードのデータ値を入力してください：t'）scanf（ '％d'、＆temp-> info）temp-> next = NULL if（start == NULL）{start = temp} else {ptr = start while （ptr-> next！= NULL）{ptr = ptr-> next} ptr-> next = temp}} void insert_pos（）{struct node * ptr、* temp int i、pos temp =（struct node *）malloc（ sizeof（struct node））if（temp == NULL）{printf（ 'nOut of Memory Space：n'）return} printf（ 'n新しいノードを挿入する位置を入力してください：t'）scanf（ '％d' 、＆pos）printf（ 'nノードのデータ値を入力：t'）scanf（ '％d'、＆temp-> info）temp-> next = NULL if（pos == 0）{temp-> next = start start = temp} else {for（i = 0、ptr = startinext if（ptr == NULL）{printf（ 'nPosition not found：[Handle with care] n'）return}} temp-> next = ptr-> next ptr -> next = temp}} void delete_begin（）{struct node * ptr if（ptr == NULL）{printf（ 'nList is Empty：n'）return} else {ptr = start start = start-> next printf（ ' n削除された要素は：％dt '、ptr-> info）free（ptr）}} void delete_end（）{struct node * temp、* ptr if（start == NULL）{printf（' nList is Empty： '）exit （0） } else if（start-> next == NULL）{ptr = start start = NULL printf（ 'n削除された要素は：％dt'、ptr-> info）free（ptr）} else {ptr = start while（ptr- > next！= NULL）{temp = ptr ptr = ptr-> next} temp-> next = NULL printf（ 'n削除された要素は：％dt'、ptr-> info）free（ptr）}} void delete_pos（） {int i、pos struct node * temp、* ptr if（start == NULL）{printf（ 'nリストは空です：n'）exit（0）} else {printf（ 'n削除するノードの位置を入力してください：t '）scanf（'％d '、＆pos）if（pos == 0）{ptr = start start = start-> next printf（' n削除された要素は：％dt '、ptr-> info）free（ptr ）} else {ptr = start for（i = 0inext if（ptr == NULL）{printf（ 'nPosition not Found：n'）return}} temp-> next = ptr-> next printf（ 'n削除された要素は次のとおりです。 ％dt '、ptr-> info）free（ptr）}}}このコードの最初の部分は、構造の作成です。リンクリスト構造は、必要に応じてデータとアドレスを保持できるように作成されます。これは、ノードがどうあるべきかをコンパイラーに知らせるために行われます。
struct node {int info struct node * next}この構造体には、データを保持するためのinfoというデータ変数と、アドレスを指すポインター変数があります。リンクリストで実行できる操作には、次のようなさまざまなものがあります。
- create（）
- 表示（）
- insert_begin（）
- insert_end（）
- ] insert_pos（）
- delete_begin（）
- delete_end（）
- delete_pos（）
これらの関数は、メニュー方式のメイン関数によって呼び出されます。 main関数では、ユーザーがプログラムで実行したい操作に基づいて、ユーザーからの入力を受け取ります。次に、入力はユーザー入力に基づいてスイッチケースに送信されます。
提供された入力に基づいて、関数が呼び出されます。次に、解決する必要のあるさまざまな機能があります。これらの各関数を見てみましょう。
関数の作成
まず、リンクリストを作成するための作成機能があります。これは、リンクリストが作成される基本的な方法です。コードを見てみましょう。
void create（）{struct node * temp、* ptr printf（ 'nEnter the data value for the node：t'）scanf（ '％d'、＆temp-> info）temp-> next = NULL if（start == NULL ）{start = temp} else {ptr = start while（ptr-> next！= NULL）{ptr = ptr-> next} ptr-> next = temp}}出力
最初に、タイプの2つのポインタが作成されます node、ptr、およびtemp 。リンクリストに追加する必要のある値をユーザーから取得し、それを一時変数のinfo部分に格納し、アドレス部分であるnextのtempをnullに割り当てます。リストの開始を保持する開始ポインタがあります。次に、リストの先頭を確認します。リストの開始がnullの場合、開始ポインターにtempを割り当てます。それ以外の場合は、データが追加された最後のポイントまでトラバースします。
このために、ptrに開始値を割り当て、までトラバースします。 ptr-> next = null 。次に、割り当てます ptr-> next 臨時雇用者の住所。同様に、最初に挿入し、最後に挿入し、指定した場所に挿入するためのコードがあります。
イテレータJavaの使用方法
表示機能
表示機能のコードは次のとおりです。
void display（）{struct node * ptr if（start == NULL）{printf（ 'nList is empty：n'）return} else {ptr = start printf（ 'nリスト要素は：n'）while（ptr！= NULL）{printf（ '％dt'、ptr-> info）ptr = ptr-> next}}}出力
表示関数では、最初にリストが空かどうかを確認し、空の場合は戻ります。次のパートでは、開始値をptrに割り当てます。次に、ptrがnullになるまでループを実行し、リストの終わりを指定するptrがnullになるまで、各ノードのデータ要素を出力します。
削除機能
リンクリストからノードを削除するためのコードスニペットは次のとおりです。
void delete_pos（）{int i、pos struct node * temp、* ptr if（start == NULL）{printf（ 'nリストは空です：n'）exit（0）} else {printf（ 'n削除するノード：t '）scanf（'％d '、＆pos）if（pos == 0）{ptr = start start = start-> next printf（' n削除された要素は：％dt '、ptr-> info ）free（ptr）} else {ptr = start for（i = 0inext if（ptr == NULL）{printf（ 'nPosition not Found：n'）return}} temp-> next = ptr-> next printf（ 'nThe削除された要素は次のとおりです：％dt '、ptr-> info）free（ptr）}}}出力
削除プロセスでは、最初にリストが空であるかどうかをチェックし、空である場合は存在します。空でない場合は、削除する位置をユーザーに求めます。ユーザーが位置を入力すると、それが最初の位置であるかどうかを確認し、入力した場合は割り当てます ptr 開始し、開始ポインタを次の場所に移動して、ptrを削除します。の場合 位置がゼロではありません 、次に、0からユーザーが入力してに保存された位置までforループを実行します。 pos 変数。入力された位置が存在しないかどうかを決定するifステートメントがあります。場合 ptrがnullに等しい 、それからそれは存在しません。
私達 ptrをtempに割り当てます forループで、ptrは次の部分に移動します。この後、位置が見つかったとき。の値を保持するためにtemp変数を作成します ptr-> next したがって、ptrをスキップします。その後、ptrが削除されます。同様に、最初と最後の要素の削除に対しても実行できます。
二重リンクリスト
2つあるため、二重リンクリストと呼ばれます。 ポインタ 、1つのポイントは次のノードを指し、他のポイントは前のノードを指します。二重リンクで実行される操作は、単一リンクリストの操作と似ています。基本的な操作のコードは次のとおりです。
#include #include struct Node typedef struct Node * PtrToNode typedef PtrToNode List typedef PtrToNode Position struct Node {int e Position previous Position next} void Insert（int x、List l、Position p）{Position TmpCell TmpCell =（struct Node *）malloc （sizeof（struct Node））if（TmpCell == NULL）printf（ 'Memory out of spacen'）else {TmpCell-> e = x TmpCell-> previous = p TmpCell-> next = p-> next p-> next = TmpCell}} void Delete（int x、List l）{Position p、p1、p2 p = Find（x、l）if（p！= NULL）{p1 = p->前のp2 = p->次のp1- > next = p-> next if（p2！= NULL）//ノードが最後のノードでない場合p2-> previous = p-> previous} else printf（ '要素が存在しません!!! n'）} void Display（List l）{printf（ 'リスト要素は::'）位置p = l-> next while（p！= NULL）{printf（ '％d->'、p-> e）p = p- > next}} int main（）{int x、pos、ch、i List l、l1 l =（struct Node *）malloc（sizeof（struct Node））l-> previous = NULL l-> next = NULL List p = l printf（ 'Lの二重リンクリストの実装IST ADTnn '）do {printf（' nn1。 CREATEn 2. DELETEn 3. DISPLAYn 4.QUITnn選択肢を入力してください:: '）scanf（'％d '、＆ch）switch（ch）{case 1：p = l printf（'挿入する要素を入力してください:: '）scanf （ '％d'、＆x）printf（ '要素の位置を入力してください::'）scanf（ '％d'、＆pos）for（i = 1 inext} Insert（x、l、p）break case 2：p = l printf（ '削除する要素を入力::'）scanf（ '％d'、＆x）Delete（x、p）break case 3：Display （l）break}} while（ch<4) } 出力
Javaでのメソッドオーバーロードの利点
ご覧のとおり、操作の概念は非常に単純です。二重リンクリストは、Cプログラミング言語の単一リンクリストと同じ操作を行います。唯一の違いは、二重にリンクされたリストでリストをより適切にトラバースするのに役立つ別のアドレス変数があることです。
Cの単一および二重リンクリストで基本的な操作を実行する方法を理解していただければ幸いです。
Javaでリンクリストを学びたい場合は、こちらをご覧ください。 。
ご不明な点がございましたら、「Cのリンクリスト」のコメント欄にご質問ください。喜んでお答えいたします。