剣指offerノート面接問題6----チェーンテーブルを印刷したことがない

5291 ワード

タイトル:チェーンテーブルのヘッダノードを入力し、ヘッダから各ノードの値を逆に印刷します。チェーンテーブルノードは次のように定義されます。

struct ListNode{
    int m_nKey;
    ListNode* m_pNext;
}

テスト例:

  • 機能テスト(入力されたチェーンテーブルには複数のノードがあり、入力されたチェーンテーブルには1つのノードしかありません).
  • 特殊入力テスト(入力されたチェーンヘッダ接点ポインタはnullptr).

  • テストコード:

    void Test(ListNode* pHead)
    {
        PrintList(pHead);
        PrintListReversingly_Iteratively(pHead);
        printf("
    "); PrintListReversingly_Recursively(pHead); } // 1->2->3->4->5 void Test1() { printf("
    Test1 begins.
    "); ListNode* pNode1 = CreateListNode(1); ListNode* pNode2 = CreateListNode(2); ListNode* pNode3 = CreateListNode(3); ListNode* pNode4 = CreateListNode(4); ListNode* pNode5 = CreateListNode(5); ConnectListNodes(pNode1, pNode2); ConnectListNodes(pNode2, pNode3); ConnectListNodes(pNode3, pNode4); ConnectListNodes(pNode4, pNode5); Test(pNode1); DestroyList(pNode1); } // : 1 void Test2() { printf("
    Test2 begins.
    "); ListNode* pNode1 = CreateListNode(1); Test(pNode1); DestroyList(pNode1); } // void Test3() { printf("
    Test3 begins.
    "); Test(nullptr); }

    本題のポイント:

  • 応募者の一方向チェーンテーブルに対する理解とプログラミング能力を調べる.
  • 応募者の循環、再帰、スタックの3つの相互関連概念に対する理解を調べる.

  • 実装コード:

    /***********************************List.h*********************************/
    struct ListNode
    {
        int       m_nValue;
        ListNode* m_pNext;
    };
    
    ListNode* CreateListNode(int value);
    void ConnectListNodes(ListNode* pCurrent, ListNode* pNext);
    void PrintListNode(ListNode* pNode);
    void PrintList(ListNode* pHead);
    void DestroyList(ListNode* pHead);
    void AddToTail(ListNode** pHead, int value);
    void RemoveNode(ListNode** pHead, int value);
    
    /*************************************List.cpp***********************************/
    #include "list.h"
    #include 
    #include 
    
    ListNode* CreateListNode(int value)
    {
        ListNode* pNode = new ListNode();
        pNode->m_nValue = value;
        pNode->m_pNext = nullptr;
        return pNode;
    }
    
    void ConnectListNodes(ListNode* pCurrent, ListNode* pNext)
    {
        if(pCurrent == nullptr)
        {
            printf("Error to connect two nodes.
    "); exit(1); } pCurrent->m_pNext = pNext; } void PrintListNode(ListNode* pNode) { if(pNode == nullptr) { printf("The node is nullptr
    "); } else { printf("The key in node is %d.
    ", pNode->m_nValue); } } void PrintList(ListNode* pHead) { printf("PrintList starts.
    "); ListNode* pNode = pHead; while(pNode != nullptr) { printf("%d\t", pNode->m_nValue); pNode = pNode->m_pNext; } printf("
    PrintList ends.
    "); } void DestroyList(ListNode* pHead) { ListNode* pNode = pHead; while(pNode != nullptr) { pHead = pHead->m_pNext; delete pNode; pNode = pHead; } } void AddToTail(ListNode** pHead, int value) { ListNode* pNew = new ListNode(); pNew->m_nValue = value; pNew->m_pNext = nullptr; if(*pHead == nullptr) { *pHead = pNew; } else { ListNode* pNode = *pHead; while(pNode->m_pNext != nullptr) pNode = pNode->m_pNext; pNode->m_pNext = pNew; } } void RemoveNode(ListNode** pHead, int value) { if(pHead == nullptr || *pHead == nullptr) return; ListNode* pToBeDeleted = nullptr; if((*pHead)->m_nValue == value) { pToBeDeleted = *pHead; *pHead = (*pHead)->m_pNext; } else { ListNode* pNode = *pHead; while(pNode->m_pNext != nullptr && pNode->m_pNext->m_nValue != value) pNode = pNode->m_pNext; if(pNode->m_pNext != nullptr && pNode->m_pNext->m_nValue == value) { pToBeDeleted = pNode->m_pNext; pNode->m_pNext = pNode->m_pNext->m_pNext; } } if(pToBeDeleted != nullptr) { delete pToBeDeleted; pToBeDeleted = nullptr; } } /***************************PrintlistInReversedOrder.cpp******************************/ #include "..\Utilities\List.h" #include void PrintListReversingly_Iteratively(ListNode* pHead) { std::stack nodes; ListNode* pNode = pHead; while(pNode != nullptr) { nodes.push(pNode); pNode = pNode->m_pNext; } while(!nodes.empty()) { pNode = nodes.top(); printf("%d\t", pNode->m_nValue); nodes.pop(); } } void PrintListReversingly_Recursively(ListNode* pHead) { if(pHead != nullptr) { if (pHead->m_pNext != nullptr) { PrintListReversingly_Recursively(pHead->m_pNext); } printf("%d\t", pHead->m_nValue); } } int main() { Test1(); Test2(); Test3(); int a; scanf("%d", &a); return 0; }