詳しくはC++を理解して、リンク表の並べ替えアルゴリズムを実現します。
一、チェーンの並べ替え
最も簡単で直接的な方法(直接泡が出たり、並べ替えを選択したり、交換結点ではなく、データ領域だけを交換します。)
以下では、この並べ替えアルゴリズムの時間の複雑さについて議論します。バブル順序を使用しているので、その時間は二重のサイクルで消費するので、時間の複雑さはO(n*n)で、この効率はあまりにも低いです。ˇˍˇ) もう一つの方法でチェーンの並べ替えを実現したいです。
二、他のチェーンの並べ替え方式
私たちは並べ替えアルゴリズムを議論する時、データを配列に保存して討論します。順序構造の下で、多くの効率的な並べ替えアルゴリズムを採用できます。これはチェーンテーブルの並べ替え方法です。まずチェーンテーブルの内容を数セットに保存します。私たちはその配列を並べ替え(最速はnlog(n)))、最後はチェーンテーブル(時間はO(n)))に保存します。計算によって,その時間は(O(nlogn)の複雑さを得ることができます。この速度は順序構造とほぼ同じです。許容できます。
図に示すように、データ量が10000の時、第二の並べ替えアルゴリズムは第一の種類より28倍ぐらい速いことが明らかになっています。
四、以下は交換結点によってチェーンの並べ替えを実現します。
まず交換結点の関数を作成します。結点の交換は主に結点の指針領域の問題を考慮しています。その中で隣接する二つの結点は特殊な場合で、特に考慮してください。まず、結点交換の構想図を描きます。
まず、隣接する二つの結点交換の考え方を示します。
以下は普通の場合の交換です。
最後に、チェーンの反転を実現するいい方法を追加します。(ヘッドファイルの中でチェーンの長さを計算してみてください。いろいろな経験があります。)
出力結果:
以上はC+++リンクの並べ替えアルゴリズムを詳細に解説しました。C+チェーンの並べ替えアルゴリズムに関する資料は他の関連記事に注目してください。
最も簡単で直接的な方法(直接泡が出たり、並べ替えを選択したり、交換結点ではなく、データ領域だけを交換します。)
// , ,
void Listsort(Node* & head) {
int i = 0;
int j = 0;
//
Node * L = head;
//
Node * p;
Node * p1;
//
if (head->value == 0)return;
for (i = 0; i < head->value - 1; i++) {
L = head->next;
for (j = 0; j < head->value - i - 1; j++) {
//
p = L;
p1 = L->next;
// ,
if (p->value > p1->value) {
Elemtype temp = p->value;
p->value = p1->value;
p1->value = temp;
}
L = L->next;
}
}
}
順序付けの中で速度が比較的速いのは、データドメインのアドレスが接続されていることを要求しているからです。順序構造に適合しています。チェーン構造の場合、前後の二つの比較的多い並べ替えアルゴリズムしか使えません。私達はここでは交換の結点がない順序付けです。この方式は簡単で、分かりやすく、配列並び替えの時も同じです。後は交換点による並べ替えを書きます。以下では、この並べ替えアルゴリズムの時間の複雑さについて議論します。バブル順序を使用しているので、その時間は二重のサイクルで消費するので、時間の複雑さはO(n*n)で、この効率はあまりにも低いです。ˇˍˇ) もう一つの方法でチェーンの並べ替えを実現したいです。
二、他のチェーンの並べ替え方式
私たちは並べ替えアルゴリズムを議論する時、データを配列に保存して討論します。順序構造の下で、多くの効率的な並べ替えアルゴリズムを採用できます。これはチェーンテーブルの並べ替え方法です。まずチェーンテーブルの内容を数セットに保存します。私たちはその配列を並べ替え(最速はnlog(n)))、最後はチェーンテーブル(時間はO(n)))に保存します。計算によって,その時間は(O(nlogn)の複雑さを得ることができます。この速度は順序構造とほぼ同じです。許容できます。
void Listsort_1(Node* & head) {
int i = 0;
int j = 0;
//
Node * L = head;
//
if (head->value == 0)return;
Elemtype * copy = new Elemtype[head->value];
// ,
for (i = 0; i < head->value; i++) {
L = L->next;
copy[i] = L->value;
}
// STL sort
sort(copy, copy + head->value);
L = head;
//
for (i = 0; i < head->value; i++) {
L = L->next;
L->value= copy[i];
}
}
三、二種類の並べ替えの効率を比較する。図に示すように、データ量が10000の時、第二の並べ替えアルゴリズムは第一の種類より28倍ぐらい速いことが明らかになっています。
四、以下は交換結点によってチェーンの並べ替えを実現します。
まず交換結点の関数を作成します。結点の交換は主に結点の指針領域の問題を考慮しています。その中で隣接する二つの結点は特殊な場合で、特に考慮してください。まず、結点交換の構想図を描きます。
まず、隣接する二つの結点交換の考え方を示します。
以下は普通の場合の交換です。
// ( 1)
void swap_node(Node * & head,int i,int j) {
//
if (i<1 || j<1 || i>head->value || j >head->value) {
cout << " " << endl;
return;
}
//
if (i == j)
{
return;
}
//
if (abs(i - j) == 1) {
//
Node * pre;
if (i < j)
pre = getitem(head, i);
else
pre = getitem(head, j);
//
Node * a = pre->next;
//
Node * b = a->next;
// pre
pre->next = b;
// b a
a->next = b->next;
// b a
b->next = a;
return;
}
//
Node * a = getitem(head, i);
//
Node * b = getitem(head, j);
//
Node * p = a->next;
//
Node * q = b->next;
//
Node * p_next = p->next;
//
Node * q_next = q->next;
//a q
a->next = q;
//
q->next = p_next;
//b p
b->next = p;
//
p->next = q_next;
}
ソート時のコードは、交換点が前後の結点で交換されていることを確認してください。交換が完了すると、Lは次の結点に移動されますので、これ以上実行しないでください。L=L->next
// ,
void Listsort_Node(Node* & head) {
int i = 0;
int j = 0;
//
Node * L = head;
//
Node * p;
Node * p1;
//
if (head->value == 0)return;
int flag = 0;
cout << head->value << endl;
for (i = 0; i < head->value - 1; i++) {
L = head->next;
for (j = 0; j < head->value - 1 - i; j++) {
// , , L ,
// :L = L->next;,
if (L->value > L->next->value) {
flag = 1;
swap_node(head, j + 1, j + 2);
}
if (flag == 1) {
flag = 0;
}
else {
L = L->next;
}
}
}
}
はい、今日はここまで書きます。今日は交換点を書くことによって、チェーン時計が本当に人をだましやすいことを発見しました。一時間ぐらいばかにされました。その結点はもう次の結点に移動されたと分かりました。最後に、チェーンの反転を実現するいい方法を追加します。(ヘッドファイルの中でチェーンの長さを計算してみてください。いろいろな経験があります。)
void rollback(Node * & head) {
//
int end = head->value;
int start = 1;
//
//
while (1) {
if (end == start)
return;
swap_node(head, end, start);
--end;
++start;
}
}
皆さん、私が書いたコードについての評価をお願いします。私はやはり直接に完成したコードを貼り付けて出てきたらいいと思います。コードも中に入っています。
include<iostream>
#include<ctime>
#include<cstdlib>
#include<windows.h>
#include<algorithm>
using namespace std;
typedef int Elemtype;
// ,
// ,
// ,
struct Node
{
// , ,
Elemtype value;
//
Node * next;
};
// ,
void InitList(Node * & head) {
head = new Node();
head->value = 0;
head->next = NULL;
}
//
void DestroyList(Node * & head) {
delete head;
head = NULL;
}
//
void ClearList(Node * & head) {
head->value = 0;
head->next = NULL;
}
//
bool Listinsert(Node * & head, int i, Elemtype value) {
//
int j = 0;
Node * L = head;
// ,
if (i<1 || i>head->value + 1)return false;
//
while (j < i - 1) {
L = L->next;
++j;
}
//s
Node * s = new Node();
s->value = value; //
s->next = L->next; //
L->next = s; // ,
//
++head->value;
return true;
}
//
Node * getitem(Node * & head, int i) {
//
//
int j = 0;
Node * L = head;
//
if (i<1 || i >head->value)return NULL;
//
while (j < i - 1) {
L = L->next;
++j;
}
//value = L->next->value;
return L;
}
// , ,
void Listsort(Node* & head) {
int i = 0;
int j = 0;
//
Node * L = head;
//
Node * p;
Node * p1;
//
if (head->value == 0)return;
for (i = 0; i < head->value - 1; i++) {
L = head->next;
for (j = 0; j < head->value - i - 1; j++) {
//
p = L;
p1 = L->next;
// ,
if (p->value > p1->value) {
Elemtype temp = p->value;
p->value = p1->value;
p1->value = temp;
}
L = L->next;
}
}
}
//
void Listsort_by_array(Node* & head) {
int i = 0;
int j = 0;
//
Node * L = head;
//
if (head->value == 0)return;
Elemtype * copy = new Elemtype[head->value];
// ,
for (i = 0; i < head->value; i++) {
L = L->next;
copy[i] = L->value;
}
// STL sort
sort(copy, copy + head->value);
L = head;
//
for (i = 0; i < head->value; i++) {
L = L->next;
L->value = copy[i];
}
}
// ( 1)
void swap_node(Node * & head,int i,int j) {
//
if (i<1 || j<1 || i>head->value || j >head->value) {
cout << " " << endl;
return;
}
//
if (i == j)
{
return;
}
//
if (abs(i - j) == 1) {
//
Node * pre;
if (i < j)
pre = getitem(head, i);
else
pre = getitem(head, j);
//
Node * a = pre->next;
//
Node * b = a->next;
// pre
pre->next = b;
// b a
a->next = b->next;
// b a
b->next = a;
return;
}
//
Node * a = getitem(head, i);
//
Node * b = getitem(head, j);
//
Node * p = a->next;
//
Node * q = b->next;
//
Node * p_next = p->next;
//
Node * q_next = q->next;
//a q
a->next = q;
//
q->next = p_next;
//b p
b->next = p;
//
p->next = q_next;
}
//
void rollback(Node * & head) {
//
int end = head->value;
int start = 1;
//
//
while (1) {
if (end <= start)
return;
swap_node(head, end, start);
--end;
++start;
}
}
void print(Node * & head);
// , ,
// ,
void Listsort_node(Node* & head) {
int i = 0;
int j = 0;
//
Node * L = head;
//
Node * p;
Node * p1;
//
if (head->value == 0)return;
int flag = 0;
for (i = 0; i < head->value - 1; i++) {
L = head->next;
for (j = 0; j < head->value - 1 - i; j++) {
// , , L ,
// :L = L->next;,
if (L->value > L->next->value) {
flag = 1;
swap_node(head, j + 1, j + 2);
}
if (flag == 1) {
flag = 0;
}
else {
L = L->next;
}
}
}
}
void print(Node * & head) {
// , ,
//
Node * L = head;
while (L->next) {
L = L->next;
cout << L->value << " ";
}
cout << endl;
}
int main() {
// , ,
Node * head;
Node * head_array;
Node * head_node;
Node * head_roll;
srand((int)time(NULL)); // ,
//
InitList(head);
InitList(head_array);
InitList(head_node);
InitList(head_roll);
int i;
cout << " " << endl;
int n;
cin >> n;//5
//cout << " " << n << " " << endl;
for (i = 0; i < n; i++) {
Elemtype temp;
temp = rand();
if (!Listinsert(head, i + 1, temp)) {
cout << " " << endl;
}
if (!Listinsert(head_array, i + 1, temp)) {
cout << " " << endl;
}
if (!Listinsert(head_node, i + 1, temp)) {
cout << " " << endl;
}
if (!Listinsert(head_roll, i + 1, temp)) {
cout << " " << endl;
}
}
cout << " " << endl;
print(head);
cout << " " << endl;
rollback(head_roll);
print(head_roll);
cout << " ( )" << endl;
Listsort(head);
print(head);
cout << " ( )" << endl;
Listsort_by_array(head_array);
print(head_array);
cout << " ( )" << endl;
Listsort_node(head_node);
print(head_node);
system("pause");
return 0;
}
運行環境:vs 2015出力結果:
以上はC+++リンクの並べ替えアルゴリズムを詳細に解説しました。C+チェーンの並べ替えアルゴリズムに関する資料は他の関連記事に注目してください。