[チェーンテーブル]O(1)時間にチェーンテーブルノードを削除する

3022 ワード
チェーン？メーター
タイトル:チェーンテーブルのヘッダポインタとノードポインタを指定し、O(1)時間にそのノードを削除します.チェーンテーブルノードの定義は次のとおりです.
struct ListNode
{
    int m_nKey;
    ListNode* m_pNext;
};
関数の宣言は次のとおりです.
void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);
 
分析:これは広く伝わるGoogleの面接問題で、私たちのプログラミングの基本功を効果的に考察することができて、また私たちの反応速度を考察することができて、更に重要なのは、私たちの時間の複雑さに対する理解を考察することができます.
チェーンテーブルでノードを削除するには、チェーンテーブルのヘッダノードから削除するノードを順番に検索し、見つけてから削除します.順序検索が必要なので,時間的複雑さは自然にO(n)である.
 
削除するノードを最初から検索する必要があるのは、削除するノードの前のノードを得る必要があるからです.私たちは考えを変えてみました.与えられたノードから次のノードを得ることができます.このとき、私たちが実際に削除したのは次のノードです.私たちは実際に削除したノードの前のノードを得たので、完全に実現できます.もちろん、削除する前に、所定のノードの次のノードのデータを所定のノードにコピーする必要があります.このとき,時間複雑度はO(1)である.
 
削除したノードがチェーンテーブルの末尾にあり、次のノードがない場合は、どうすればいいのでしょうか.チェーンテーブルのヘッダノードから開始し、ついでに所定のノードのシーケンスノードを取得し、削除操作を完了します.このときの時間的複雑さはO(n)である.
 
そのテーマはO(1)時間で削除操作を完了する必要があることを要求しています.私たちのアルゴリズムは要求に合わないのではないでしょうか.実際,チェーンテーブルに合計n個のノードがあると仮定すると,我々のアルゴリズムはn−1の合計で時間複雑度がO(1)であり,与えられたノードがチェーンテーブルの末尾にある場合にのみ時間複雑度がO(n)である.平均時間複雑度[(n−1)*O(1)+O(n)]/nは,依然としてO(1)である.
前の分析に基づいて、次のコードを書くのは難しくありません.
参照コード:
///////////////////////////////////////////////////////////////////////

// Delete a node in a list

// Input: pListHead - the head of list

//        pToBeDeleted - the node to be deleted

///////////////////////////////////////////////////////////////////////

void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted)

{

      if(!pListHead || !pToBeDeleted)

            return;

 

      // if pToBeDeleted is not the last node in the list

      if(pToBeDeleted->m_pNext != NULL)

      {

            // copy data from the node next to pToBeDeleted

            ListNode* pNext = pToBeDeleted->m_pNext;

            pToBeDeleted->m_nKey = pNext->m_nKey;

            pToBeDeleted->m_pNext = pNext->m_pNext;

 

            // delete the node next to the pToBeDeleted

            delete pNext;

            pNext = NULL;

      }

      // if pToBeDeleted is the last node in the list

      else

      {

            // get the node prior to pToBeDeleted

            ListNode* pNode = pListHead;

            while(pNode->m_pNext != pToBeDeleted)

            {

                  pNode = pNode->m_pNext;            

            }

 

            // deleted pToBeDeleted

            pNode->m_pNext = NULL;

            delete pToBeDeleted;

            pToBeDeleted = NULL;

      }

}

 
コードを簡潔に見せるために、上記のコードは、(1)与えられたノードがチェーンテーブルにあること、(2)指定された削除するノードはチェーンテーブルのヘッダノードではない.最初の仮定を考慮しないと,コードのロバスト性に影響を及ぼす.2番目の仮定では、リスト全体に1つのノードしかない場合、コードに問題があります.しかし、この仮定は、一部のチェーンテーブルの実装では、実際のチェーンテーブルノードではなく、仮想チェーンテーブルヘッダが作成されるため、あまり過言ではありません.これで削除するノードがチェーンテーブルのヘッダノードであるはずがありません.もちろん、面接では、これらの仮説を面接官と交流することができます.そうすると、面接官はやはり私たちの考えが行き届いていると思っています.
 
FROM:
http://zhedahht.blog.163.com/blog/static/254111742007112255248202/
Javaウィジェットのカスタムチェーンテーブルの実装
チェーン時計の経典の筆記試験問題