劍指offer例題分享--4

　　前言：擱置許久的更新要繼續開始了！前一段時間一直在忙項目和C++的學習，是以擱置了！要改變注意了，要用C++進行編寫了，因為要不斷練習C++！

　　面試題15：

書中要求隻能周遊連結清單一次，是以代碼如下：

#include<iostream>
#include<cstdlib>
using namespace std;

struct ListNode
{
    int data;
    ListNode * next;
};

typedef struct ListNode  linknode_t; 
typedef struct ListNode* linklist_t;
linknode_t *CreateLink()         // 建立空的連結清單  傳回值 連結清單的首位址
{    
    linknode_t *H;
    H = (linklist_t)malloc(sizeof(linknode_t)); 
    
    H->next = NULL;
    return H;
}   
void InitLink(linknode_t *H)        // 初始化一個空的連結清單  
{
    linknode_t *r, *p;
    int i;
    r = H;                     //  r 指向 隊尾位置 
    for(i = 0; i < 5; i++)
    {
        p = (linknode_t *)malloc(sizeof(linknode_t));
        p->data = i+1;
        p->next = NULL;         // 沒有下一個節點
        r->next = p;            // 将p 放在 r 的後面
        r = p;                  //  r 指向新的隊尾
    }
    
}

void ShowLink(linknode_t* H)           // 從隊首->隊尾 列印所有節點
{
    linknode_t *p;
    p = H->next;
  while(p != NULL){        
        cout << " " << p->data;
        p = p->next;   
    }
    cout << endl;
}

ListNode *FindKthToTail(ListNode *pListHead,unsigned int k)
{
    if(pListHead == NULL || k == 0)
        return NULL;

    ListNode *pAhead = pListHead;
    ListNode *pBehind = NULL;

    for(unsigned int i=0;i<k-1;++i)
    {
        if(pAhead->next != NULL)
            pAhead = pAhead->next;
        else
        {
            return NULL;
        }
    }

    pBehind = pListHead;
    while(pAhead->next != NULL)
    {
        pAhead = pAhead->next;
        pBehind = pBehind->next;
    }
    
    return pBehind;
}

int main()
{
    linknode_t *H = CreateLink();
    InitLink(H);
    ShowLink(H);
    
    linknode_t *S = FindKthToTail(H,2);
    cout << "data:" << S->data << endl;
    
    return 0;
}

　　總結：要熟練對單連結清單的使用！當我們用一個指針不能解決問題，可以嘗試用兩個指針周遊連結清單，可以讓其中一個指針周遊的速度快一些（比如一次在連結清單上走兩步），或者讓它在連結清單上走若幹步！

　　面試題16：

　　主要考察連結清單的反轉：

　　代碼如下：

#include<iostream>
#include<cstdlib>
using namespace std;

struct ListNode
{
    int data;
    ListNode * next;
};

typedef struct ListNode  linknode_t; 
typedef struct ListNode* linklist_t;
linknode_t *CreateLink()         // 建立空的連結清單  傳回值 連結清單的首位址
{    
    linknode_t *H;
    H = (linklist_t)malloc(sizeof(linknode_t)); 
    
    H->next = NULL;
    return H;
}   
void InitLink(linknode_t *H)        // 初始化一個空的連結清單  
{
    linknode_t *r, *p;
    int i;
    r = H;                     //  r 指向 隊尾位置 
    for(i = 0; i < 4; i++)
    {
        p = (linknode_t *)malloc(sizeof(linknode_t));
        p->data = i+1;
        p->next = NULL;         // 沒有下一個節點
        r->next = p;            // 将p 放在 r 的後面
        r = p;                  //  r 指向新的隊尾
    }
    
}

void ShowLink(linknode_t* H)           // 從隊首->隊尾 列印所有節點
{
    linknode_t *p;
    p = H->next;
  while(p != NULL){        
        cout << " " << p->data;
        p = p->next;   
    }
    cout << endl;
}

ListNode *ReverseList(ListNode *pHead)
{
    ListNode *pReversedHead = NULL;
    ListNode *pNode = pHead;
    ListNode *pPrev = NULL;
    while(pNode != NULL)
    {
        ListNode *pNext = pNode->next;

        if(pNext == NULL)
            pReversedHead = pNode;

        pNode->next = pPrev;
        pPrev = pNode;
        pNode = pNext;
    }

    return pReversedHead;
}

int main()
{
    linknode_t *H = CreateLink();
    InitLink(H);
    ShowLink(H);
    
    linknode_t *S = ReverseList(H);
    ShowLink(S);    
    
    return 0;
}

　　面試17：

　　題目如下：

　　代碼如下：

#include<iostream>
#include<cstdlib>
using namespace std;

struct ListNode
{
    int data;
    ListNode * next;
};

typedef struct ListNode  linknode_t; 
typedef struct ListNode* linklist_t;
linknode_t *CreateLink()         // 建立空的連結清單  傳回值 連結清單的首位址
{    
    linknode_t *H;
    H = (linklist_t)malloc(sizeof(linknode_t)); 
    
    H->next = NULL;
    return H;
}   
void InitLink(linknode_t *H,int n=1)        // 初始化一個空的連結清單  
{
    linknode_t *r, *p;
    int i;
    r = H;                     //  r 指向 隊尾位置 
    for(i = 0; i < 4; i+=n)
    {
        p = (linknode_t *)malloc(sizeof(linknode_t));
        p->data = i+n;
        p->next = NULL;         // 沒有下一個節點
        r->next = p;            // 将p 放在 r 的後面
        r = p;                  //  r 指向新的隊尾
    }
    
}

void ShowLink(linknode_t* H)           // 從隊首->隊尾 列印所有節點
{
    linknode_t *p;
    p = H->next;
  while(p != NULL){        
        cout << " " << p->data;
        p = p->next;   
    }
    cout << endl;
}

ListNode *Merge(ListNode *pHead1,ListNode *pHead2)
{
    //魯棒性處理,空指針會造成程式崩潰
    if(pHead1 == NULL)
        return pHead2;
    else if(pHead2 == NULL)
        return pHead1;

    ListNode * pMergedHead = NULL;

    if(pHead1->data < pHead2->data)
    {
        pMergedHead = pHead1;
        pMergedHead->next = Merge(pHead1->next,pHead2);//遞歸處理
    }
    else
    {
        pMergedHead = pHead2;
        pMergedHead->next = Merge(pHead1,pHead2->next);//遞歸處理
    }

    return pMergedHead;
}

int main()
{
    linknode_t *H = CreateLink();
    InitLink(H);
    linknode_t *H1 = CreateLink();
    InitLink(H1,2);
    ShowLink(H);
    ShowLink(H1);
    
    linknode_t *S = Merge(H->next,H1->next);    
    while(S != NULL){        
        cout << " " << S->data;
        S = S->next;   
    }
    cout << endl;
    
    return 0;
}

　　總結：了解遞歸部分的思想。

　　面試題18：

　　面試題18是關于二叉樹的，先簡單介紹一下二叉樹吧。　

　　　二叉樹特點：第i層最多節點的個數 2^(i-1)

　　樹的深度 h , 樹節點最多 2^h-1

　　周遊二叉樹方法:先序周遊中序周遊後序周遊,具體周遊方法介紹可以在網上找，這裡就不具體介紹了。

　　程式中三種方法都寫出來了，但隻用了先序周遊。

#include<iostream>
#include<cstdlib>
using namespace std;

struct BinaryTreeNode
{
    int data;                                                    //節點資料
    BinaryTreeNode *lchild,*rchild;        //左孩子、右孩子
};
typedef struct BinaryTreeNode tree_t;

/******
    構造一個二叉樹 遞歸實作
    參數：形參1：開始值，形參2：結束值
 ******/
tree_t *CreateTree(int i, int max) 
{
    //遞歸結束條件
    if(i > max)
    {
        return NULL;  //  == return 0;
    }
    
    tree_t *T;

    T = (tree_t *)malloc(sizeof(tree_t));    

    T->data = i;
    T->lchild = CreateTree(2*i, max); 
    T->rchild = CreateTree(2*i+1, max);
    return T;
}

//先序周遊輸出二叉樹
void FirstRoot_DLR(tree_t *p)
{
    if(p == NULL)
        return ;
    cout << " " << p->data;    
    FirstRoot_DLR(p->lchild);
    FirstRoot_DLR(p->rchild);
}

//中序周遊輸出二叉樹 程式中未使用
void MiddleRoot_DLR(tree_t *p)
{
    if(p == NULL)
        return;
    
    MiddleRoot_DLR(p->lchild);
    cout << " " << p->data;    
    MiddleRoot_DLR(p->rchild);
}

//後序周遊輸出二叉樹 程式中未使用
void LastRoot_DLR(tree_t *p)
{
    if(p == NULL)
        return;
    
    LastRoot_DLR(p->lchild);    
    LastRoot_DLR(p->rchild);
    cout << " " << p->data;
}

bool DoesTree1HaveTree2(tree_t *pRoot1,tree_t *pRoot2)
{
    //樹B為空直接不檢查
    if(pRoot2 == NULL)
        return true;

    if(pRoot1 == NULL)
        return false;

    if(pRoot1->data != pRoot2->data)
        return false;

    return DoesTree1HaveTree2(pRoot1->lchild,pRoot2->lchild)&&DoesTree1HaveTree2(pRoot1->rchild,pRoot2->rchild);
}

bool HasSubtree(tree_t *pRoot1,tree_t *pRoot2)
{
    bool result = false;

    if(pRoot1!=NULL && pRoot2!=NULL)
    {
        result = DoesTree1HaveTree2(pRoot1,pRoot2);
        if(!result)
            HasSubtree(pRoot1->lchild,pRoot2);
        if(!result)
            HasSubtree(pRoot1->rchild,pRoot2);
    }
    return result;
}

int main()
{
    tree_t *T1 = CreateTree(1,4);
    FirstRoot_DLR(T1);
    cout << endl;
    tree_t *T2 = CreateTree(1,2);
    FirstRoot_DLR(T2);
    cout << endl;
    //使用boolalpha輸出為bool類型
    cout << boolalpha <<HasSubtree(T1,T2) << endl; 
    
    return 0;
}

　　總結：書中第三章主要強調了代碼的規範性、完整性和魯棒性，魯棒性例如對空指針的判斷和處理...,用連結清單和二叉樹做的例子，要熟悉掌握這兩種資料結構!

作者：

柳德維

出處：

https://www.cnblogs.com/liudw-0215/

-------------------------------------------

個性簽名：獨學而無友，則孤陋而寡聞。做一個靈魂有趣的人！

如果覺得這篇文章對你有小小的幫助的話，記得在右下角點個“推薦”哦，部落客在此感謝！

萬水千山總是情，打賞一分行不行，是以如果你心情還比較高興，也是可以掃碼打賞部落客，哈哈哈(っ•̀ω•́)っ⁾⁾！

劍指offer例題分享--4

繼續閱讀

C語言第四章自述2第四章選擇結構程式設計

面試題:vector和map的差別，異同。空間分布，100萬資料存哪個比較合适。一、疊代器差別二、vector三、Map、Set四、vector_map 為什麼比map效率高五、如何選擇六、容器選擇原則七、效率對比

C++ 多線程用條件變量确定線程的執行順序而不是使用 sleep(1)

POJ 1284 Primitive Roots (歐拉函數&原根定理)

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

成員函數初始化清單

2021-08-13c++——類之操作符重載

swmm與lisflood-fp源碼如何一起編譯 CMake指令

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

C++ 第十五周報告1--《冒泡法排序》

C++實作簡單順序表

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述