剑指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;
}

　　总结：书中第三章主要强调了代码的规范性、完整性和鲁棒性，鲁棒性例如对空指针的判断和处理...,用链表和二叉树做的例子，要熟悉掌握这两种数据结构!