ソートされた単一リンクリストを実装するC++プログラム
データ構造では、リンクリストはデータ要素の線形コレクションです。リストの各要素またはノードは、データと次のノードへの参照の2つの項目で構成されます。最後のノードにはnullへの参照があります。リンクリストへのエントリポイントは、リストの先頭と呼ばれます。
リスト内の各ノードは、コンテンツと、リスト内の次のノードへのポインターまたは参照を、単一リンクリストに格納します。単一リンクリストには、前のノードへのポインタや参照は格納されません。
ソートされた単一リンクリストを実装するためのC++プログラムの開発。
アルゴリズム
Begin function createnode() to insert node in the list: It checks whether the list is empty or not. If the list is empty put the node as first element and update head. Initialize the next pointer with NULL. If list is not empty, It creates a newnode and inserts the number in the data field of the newnode. Now the newnode will be inserted in such a way that linked list will remain sorted. If it gets inserted at the last, then the newnode points to NULL. If the newnode inserted at the first, then the linked list starts from there. End Begin function display() to print the list content having n number of nodes: Initialize c = 0. Initialize pointer variable with the start address while (c <= n) Print the node info Update pointer variable Increment c. End
サンプルコード
#include<iostream> using namespace std; struct nod { int d; nod *n; } *p = NULL, *head = NULL, *q = NULL, *np = NULL; int c = 0; void createnode(int n) { np = new nod; np->d = n; np->n = NULL; if (c == 0) { head = np; p = head; p->n = head; c++; } else if (c == 1) { p = head; q = p; if (np->d < p->d) { np->n = p; head = np; p->n = np; } else if (np->d > p->d) { p->n = np; np->n = head; } c++; } else { p = head; q = p; if (np->d < p->d) { np->n = p; head = np; do { p = p->n; } while (p->n != q); p->n = head; } else if (np->d > p->d) { while (p->n != head && q->d < np->d) { q = p; p = p->n; if (p->n == head) { p->n = np; np->n = head; } else if (np->d< p->d) { q->n = np; np->n = p; break; } } } } } void display(int i) { nod *t = head; int c = 0; while (c <= i ) { cout<<t->d<<"\t"; t = t->n; c++; } } int main() { int i = 0, n, a; cout<<"enter the no of nodes\n"; cin>>n; while (i < n) { cout<<"\nenter value of node\n"; cin>>a; createnode(a); i++; } cout<<"sorted singly link list"<<endl; display(n); }
出力
enter the no of nodes 5 enter value of node 6 enter value of node 4 enter value of node 7 enter value of node 3 enter value of node 2 sorted singly link list 2 3 4 6 7 2
-
C++で二重リンクリストのサイズを見つけるプログラム
この問題では、二重にリンクされたリストが与えられます。私たちのタスクは、C++で二重リンクリストのサイズを見つけるプログラムを作成することです。 二重リンクリストは特殊なタイプのリンクリストであり、単一リンクリストと比較して、順方向と逆方向の両方の方法で簡単にナビゲーションできます。以下は、二重リンクリストの概念を理解するための重要な用語です。 リンク-リンクリストの各リンクには、要素と呼ばれるデータを格納できます。 次へ-リンクリストの各リンクには、次と呼ばれる次のリンクへのリンクが含まれています。 前-リンクリストの各リンクには、前と呼ばれる前のリンクへのリンクが含ま
-
隣接リストを実装するC++プログラム
グラフの隣接リスト表現は、リンクリスト表現です。この表現では、リストの配列があります。配列のサイズはVです。ここで、Vは頂点の数です。つまり、V個の異なるリストを格納する配列があると言えます。リストヘッダーが頂点uの場合、uの隣接するすべての頂点を保持することを意味します。 隣接リスト表現の複雑さ この表現は、無向グラフの場合はO(V + 2E)を取り、有向グラフの場合はO(V + E)を取ります。エッジの数を増やすと、必要なスペースも増えます。 入力 : 出力 : アルゴリズム add_edge(adj_list、u、v) 入力 :エッジ{u、v}のuとv、およ