前言：搁置许久的更新要继续开始了！前一段时间一直在忙项目和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;
}
总结：书中第三章主要强调了代码的规范性、完整性和鲁棒性，鲁棒性例如对空指针的判断和处理...,用链表和二叉树做的例子，要熟悉掌握这两种数据结构!
-------------------------------------------
个性签名：独学而无友，则孤陋而寡闻。做一个灵魂有趣的人！
如果觉得这篇文章对你有小小的帮助的话，记得在右下角点个“推荐”哦，博主在此感谢！
万水千山总是情，打赏一分行不行，所以如果你心情还比较高兴，也是可以扫码打赏博主，哈哈哈(っ•̀ω•́)っ⁾⁾！
