チェーンテーブル逆シーケンスアルゴリズム
質問:
チェーンテーブルを指定します.逆順にしてください.すなわち、チェーンテーブルが本来1->2->3->4->5->nullである、逆順後が5->4->3->2->1->nullである.
解法1:反復アルゴリズム
反復アルゴリズムは効率が高いが,コードは再帰アルゴリズムよりやや長い.再帰アルゴリズムはコード量が少ないが,難易度もやや高く,注意深く書かないと書き間違えやすい.
反復アルゴリズムの考え方は,チェーンテーブルを遍歴し,チェーンテーブルノードnextの指向を変更し,遍歴が完了すると,チェーンテーブルの逆順序も完了する.コードは次のとおりです.
解法2:再帰アルゴリズム
再帰アルゴリズムの実現原理:元のチェーンテーブルが1,2,3,4であると仮定すると、まず逆シーケンスの後の2,3,4が4,3,2になり、その後ノード1を逆シーケンスの4,3,2の後にリンクし、4,3,2,1を形成し、チェーンテーブル全体の逆シーケンスを完了する.コードは次のとおりです.
C++の参照タイプを使用すると、コードは少し単純になります.コードは次のとおりです.
チェーンテーブルを指定します.逆順にしてください.すなわち、チェーンテーブルが本来1->2->3->4->5->nullである、逆順後が5->4->3->2->1->nullである.
解法1:反復アルゴリズム
反復アルゴリズムは効率が高いが,コードは再帰アルゴリズムよりやや長い.再帰アルゴリズムはコード量が少ないが,難易度もやや高く,注意深く書かないと書き間違えやすい.
反復アルゴリズムの考え方は,チェーンテーブルを遍歴し,チェーンテーブルノードnextの指向を変更し,遍歴が完了すると,チェーンテーブルの逆順序も完了する.コードは次のとおりです.
struct node {
int data;
struct node* next;
};
typedef struct node* pNode;
pNode reverse(pNode head)
{
pNode current = head;
pNode next = NULL, result = NULL;
while (current != NULL) {
next = current->next;
current->next = result;
result = current;
current = next;
}
return result;
}
値を返さなければ、パラメータをポインタのポインタに変更し、チェーンテーブルのヘッダノード値を直接変更することができます(C++で参照を直接渡すほうが便利です).次のコードを書くことができます.void reverse2(struct node** headRef)
{
pNode current = *headRef;
pNode next = NULL, result = NULL;
while (current != NULL) {
next = current->next;
current->next = result;
result = current;
current = next;
}
*headRef = result;
}
解法2:再帰アルゴリズム
再帰アルゴリズムの実現原理:元のチェーンテーブルが1,2,3,4であると仮定すると、まず逆シーケンスの後の2,3,4が4,3,2になり、その後ノード1を逆シーケンスの4,3,2の後にリンクし、4,3,2,1を形成し、チェーンテーブル全体の逆シーケンスを完了する.コードは次のとおりです.
void reverseRecur(struct node** headRef)
{
if (*headRef == NULL) return;
pNode first, rest;
first = *headRef; // first={1,2,3,4}
rest = first->next; // rest={2,3,4}
if (rest == NULL) return;
reverseRecur(&rest); //rest {4,3,2}
first->next->next = first; //
first->next = NULL;
*headRef = rest; //
}
C++の参照タイプを使用すると、コードは少し単純になります.コードは次のとおりです.
void reverseRecur(pNode& p)
{
if (!p) return;
pNode rest = p->next;
if (!rest) return;
reverseRecur(rest);
p->next->next = p;
p->next = NULL;
p = rest;
}