末尾からチェーンテーブルを印刷
1627 ワード
このようなチェーンテーブルの問題は時々発生しますが、特定の方法で処理されていますか.以下に使用可能なアルゴリズムを示します.
1つ目:チェーンテーブルの構造を変更する
アイデア:
1.末尾からチェーンテーブルを印刷するなら、チェーンテーブルを逆置きにしましょう
2.逆置きチェーンテーブルを印刷する;
これは簡単で、直接コードをつけます.
方法2:借用スタック
アイデア:
1.末尾から印刷を開始するので、最初から遍歴を開始する場合は、先に遍歴した後に印刷するのがちょうどいいスタックの特徴です.
2.ループが完了したら、すべてのノードがスタックに入り、その後、スタックを出て印刷します.
すると、下の簡単なコードがまた出てきました.
アイデア:
1.再帰はスタックを使うという考え方で、スタックを思いつく以上、再帰も思いつく
コード:
教えを仰ぐ
1つ目:チェーンテーブルの構造を変更する
アイデア:
1.末尾からチェーンテーブルを印刷するなら、チェーンテーブルを逆置きにしましょう
2.逆置きチェーンテーブルを印刷する;
これは簡単で、直接コードをつけます.
void PrintListRevers(ListNode* pHead)
{
//1.
ListNode* newHead = NULL;
ListNode* cur = pHead;
while (cur)
{
ListNode* tmp = cur;
cur = cur->m_pNext;
tmp->m_pNext = newHead;
newHead = tmp;
}
//2.
ListNode* tmp = newHead;
while (tmp)
{
cout << tmp->m_nValue << " ";
}
cout << endl;
}
は簡単ですが、チェーンテーブルの元の構造を変えるのは辛くありません.これは読み取り操作だけをするべきではありません.だから、下のアルゴリズムがあります.方法2:借用スタック
アイデア:
1.末尾から印刷を開始するので、最初から遍歴を開始する場合は、先に遍歴した後に印刷するのがちょうどいいスタックの特徴です.
2.ループが完了したら、すべてのノードがスタックに入り、その後、スタックを出て印刷します.
すると、下の簡単なコードがまた出てきました.
void PrintListRevers(ListNode* pHead)
{
std::stack<ListNode*> nodes;
ListNode* pNode = pHead;
while(pNode != NULL)
{
nodes.push(pNode);
pNode = pNode->m_pNext;
}
while(!nodes.empty())
{
pNode = nodes.top();
printf("%d\t", pNode->m_nValue);
nodes.pop();
}
}
方法3:再帰アイデア:
1.再帰はスタックを使うという考え方で、スタックを思いつく以上、再帰も思いつく
コード:
void PrintListRevers(ListNode* pHead)
{
if(pHead != NULL)
{
if (pHead->m_pNext != NULL)
{
PrintListRevers(pHead->m_pNext);
}
//printf
printf("%d\t", pHead->m_nValue);
}
}
しかし、再帰的な欠点は明らかで、辺が長すぎるとスタックオーバーフローなどの問題が発生し、慎重に使用します!教えを仰ぐ