程序员面试秘笈之⑧"/>
C和C++程序员面试秘笈之⑧
本系列博客基于董山海的<C和C++程序员面试秘笈>，旨在记录，欢迎交流，可联系 zywang@shu.edu !
第八章：数据结构
文章目录
- 1、面试题1
- 2、面试题2
- 3、面试题3
- 4、面试题4
- 5、面试题5
- 6、面试题6
- 7、面试题7
- 8、面试题8
- 9、面试题9
- 10、面试题10
- 11、面试题11
- 12、面试题12
- 13、面试题13
- 14、面试题14
- 15、面试题15
- 16、面试题16
- 17、面试题17
- 18、面试题18
- 19、面试题19
- 20、面试题20
- 21、面试题21
- 22、面试题22
- 24、面试题24
- 25、面试题25
- 26、面试题26
- 27、面试题27
- 28、面试题28
- 29、面试题29
- 28、面试题28
1、面试题1
编程实现一个单链表的建立：
#include <iostream>
#include <stdio.h>
using namespace std;//
typedef struct node {int data; //节点内容node *next; //下一个节点
}node;//创建单链表
node *create() {int i = 0; //链表中数据的个数node *head, *p, *q;int x = 0;head = (node*)malloc(sizeof(node)); //创建头节点//while (1) {printf("Please input the data: ");scanf("%d", &x);if (x == 0) //data为0时创建结束break;p = (node *)malloc(sizeof(node));p->data = x;//if (++i == 1) { //链表只有一个元素head->next = p; //连接到 head 后面}else {q->next = p; //连接到链表尾端}q = p; //q指向末节点}q->next = NULL; //链表的最后一个指针为 NULLreturn head;
}
使用 while 循环每次从终端读入一个整型数据，并调用 malloc 动态分配链表节点内存存储这个整型数据，然后插到单链表的末尾。最后，当数据为 0 时表示插入数据结束。此时把末尾节点的 next 指针置为 NULL。
2、面试题2
编程实现一个单链表的测长：
#include <iostream>
#include <stdio.h>
using namespace std;//
typedef struct node {int data; //节点内容node *next; //下一个节点
}node;int length(node *head) {int len = 0;node *p;p = head->next;while (p != NULL) {len++;p = p->next;}return len;
}
3、面试题3
编程实现一个单链表的打印
#include <iostream>
#include <stdio.h>
using namespace std;//
typedef struct node {int data; //节点内容node *next; //下一个节点
}node;void print(node *head) {node *p;int index = 0;//如果链表为空if (head->next == NULL) {printf("Link is empty!\n");return;}//p = head->next;while (p != NULL) {printf("The %dth node is: %d\n", ++index, p->data);p = p->next;}
}
4、面试题4
编程实现一个单链表节点的查找：
#include <iostream>
#include <stdio.h>
using namespace std;//
typedef struct node {int data; //节点内容node *next; //下一个节点
}node;//查找单链表 pos 位置的节点，返回节点指针
//pos 从 0 开始，0 返回 head 节点
node *search_node(node *head, int pos) {node *p = head->next;//if (pos < 0) { //pos 位置不正确printf("incorrect position to search node!\n");return NULL;}//if (pos == 0) { //在head位置，返回headreturn head;}//if (p == NULL) {printf("Link is empty!\n"); //链表为空return NULL;}//while (--pos) {if ((p = p->next) == NULL) {printf("incorrect position to search node!\n");break;}}return p;
}
5、面试题5
编程实现一个单链表节点的插入：
#include <iostream>
#include <stdio.h>
using namespace std;//
typedef struct node {int data; //节点内容node *next; //下一个节点
}node;node *search_node(node *head, int pos) {node *p = head->next;//if (pos < 0) { //pos 位置不正确printf("incorrect position to search node!\n");return NULL;}//if (pos == 0) { //在head位置，返回headreturn head;}//if (p == NULL) {printf("Link is empty!\n"); //链表为空return NULL;}//while (--pos) {if ((p = p->next) == NULL) {printf("incorrect position to search node!\n");break;}}return p;
}//在单链表 pos 位置处插入节点，返回链表头指针
//在 pos 从 0 开始计算，0 表示插入到 head 节点后面
node *insert_node(node *head, int pos, int data) {node *item = NULL;node *p;//item = (node *)malloc(sizeof(node));item->data = data;//插入链表头后面if (pos == 0) {head->next = item; //head后面为item，指针为NULL，data为datareturn head;}//p = search_node(head, pos);//if (p != NULL) {item->next = p->next;p->next = item; //item表示指针地址}return head;
}
向单链表中某个位置（第 pos 个节点）之后插入节点，分为插入链表首部、插入到链表中间、以及链表尾端3种情况。
6、面试题6
编程实现一个单链表节点的删除：
#include <iostream>
#include <stdio.h>
using namespace std;//
typedef struct node {int data; //节点内容node *next; //下一个节点
}node;node *search_node(node *head, int pos) {node *p = head->next;//if (pos < 0) { //pos 位置不正确printf("incorrect position to search node!\n");return NULL;}//if (pos == 0) { //在head位置，返回headreturn head;}//if (p == NULL) {printf("Link is empty!\n"); //链表为空return NULL;}//while (--pos) {if ((p = p->next) == NULL) {printf("incorrect position to search node!\n");break;}}return p;
}//删除单链表的 pos 位置的节点，返回链表头指针
//pos 从1开始计算，1 表示删除 head 后的第一个节点
node *delete_node(node *head, int pos) {node *item = NULL;node *p = head->next;//链表为空if (p == NULL) {printf("Link is empty()!\n");return NULL;}//p = search_node(head, pos - 1);//这边注意第一句话if (p != NULL&&p->next != NULL) {item = p->next;p->next = item->next;delete item;}return head;
}
7、面试题7
实现一个单链表的逆置：
#include <iostream>
#include <stdio.h>
using namespace std;//
typedef struct node {int data; //节点内容node *next; //下一个节点
}node;//
node *reverse(node *head) {node *p, *q, *r;//链表为空if (head->next == NULL) {return head;}//p = head->next;q = p->next; //保存原第2个节点p->next = NULL; //保存原第1个节点为末节点//遍历，各个节点的next指针反转while (q != NULL) {r = q->next;q->next = p;p = q;q = r;}//新的第1个节点为原末节点head->next = p;return head;
}
遍历一遍链表，利用一个辅助指针，在存储的过程中当前指针指向的下一个元素，然后将当前节点元素的指针反转后，利用已经存储的指针往后继续遍历。
8、面试题8
寻找单链表的中间元素：
#include <iostream>
#include <stdio.h>
using namespace std;//
typedef struct node {int data; //节点内容node *next; //下一个节点
}node;//
node *search(node *head) {int i = 0, j = 0;node *current = NULL;node *middle = NULL;//current = middle = head->next;while (current !=NULL){if (i / 2 > j) {j++;middle = middle->next;}i++;current = current->next;}return middle;
}
假设 mid 指向当前已经扫描的子链表的中间元素，cur 指向当前已扫描链表的末节点，那么继续扫描移动 cur 到 cur->next，这时只需要判断一下应不应该移动 mid 到 mid ->next 就行了。
9、面试题9
单链表的正向排序：
#include <iostream>
#include <stdio.h>
using namespace std;//
typedef struct node {int data; //节点内容node *next; //下一个节点
}node;//
node* InserSort(void) {int data = 0;struct node *head = NULL;struct node *New, *Cur, *Pre;//while (1) {printf("please input the data\n");scanf("%d", &data);//输入0结束if (data == 0) {break;}//新分配一个node节点New = (struct node*)malloc(sizeof(struct node)); //分配一个node内存New->data = data;New->next = NULL;//第一次循环时对头节点赋值if (head == NULL) {head = New;continue;}//head之前插入节点if (New->data <= head->data) {New->next = head;head = New;continue;}//找到需要插入的位置Cur = head;while (New->data > Cur->data&&Cur->next != NULL) {Pre = Cur;Cur = Cur->next;}//位置在中间//把New节点插入到Pre和Cur之间if (Cur->data >= New->data) {Pre->next = New;New->next = Cur;}else { //位置在末尾Cur->next = New;}}return head;
}
10、面试题10
判断链表是否存在环形链表的问题：
#include <iostream>
#include <stdio.h>
using namespace std;//
typedef struct node {int data; //节点内容node *next; //下一个节点
}node;//判断是否存在回环
//如果存在，start存放回环开始的节点
bool IsLoop(node* head, node **start) {node* p1 = head, *p2 = head;//head为NULL或者链表为空时，返回falseif (head == NULL || head->next == NULL) {return false;}//do {p1 = p1->next; //p1走一步p2 = p2->next->next; //p2走两步} while (p2&&p2->next&&p1 != p2);//if (p1 == p2) {*start = p1; //p1为回环开始节点return true;}else {return false;}
}
设置两个指针 p1、p2。每次循环 p1 向前走一步， p2 向前走两步。直到 p2 碰到 NULL 指针或者两个指针相等时结束循环。如果两个指针相等，则说明存在环。
11、面试题11
有序单链表的合并：
已知两个链表 head1 和 head2 各自有序，请把它们合并成一个链表，依然有序。使用非递归方法以及递归方法。
#include <iostream>
#include <stdio.h>
using namespace std;//
typedef struct node {int data; //节点内容node *next; //下一个节点
}node;int length(node *head) {int len = 0;node *p;p = head->next;while (p != NULL) {len++;p = p->next;}return len;
}//非递归的方法
//只需要把较短链表的各个元素有序地插入到较长的链表之中
node* insert_node(node *head, node *item) { //head != NULLnode *p = head;node *q = NULL;//始终指向P之前的节点while (p->data < item->data && p != NULL) {q = p;p = p->next;}//插入到原头节点之前。这边注意if (p == head) {item->next = p;return item;}//插入到q与p之间q->next = item;item->next = p;return head;
}/*两个有序链表进行合并*/
node* merge(node* head1, node* head2) {node* head; //合并后的头指针node *p;node *nextP; //指向p之后//有一个链表为空的情况，直接返回另一个链表if (head1 == NULL) {return head2;}else if (head2 == NULL) {return head1;}//两个链表都不为空if (length(head1) >= length(head2)) { //选取较短的链表，这样进行的插入次数要少些head = head1;p = head2;}else {head = head2;p = head1;}//while (p != NULL) {nextP = p->next;head = insert_node(head, p);p = nextP;}return head;
}
这里 insert_node() 函数是有序的插入节点，传入的参数是 node指针类型。然后在 merge() 函数中循环把短链表中所有节点插入到长链表之中。
链表1：1->3->5
链表2：2->4->6
下面介绍递归方法：
- 比较链表1和链表2的第一个节点数据。由于1<2，因此把结果链表头节点指向链表1中第一个节点，即数据1所在的节点；
- 对剩余的链表1（3->5）和链表2再调用本过程，比较得到结果链表的第二个节点，即2与3比较得到2。此时合并后的链表节点为1->2。
如此递归，直到两个链表的表头都被加到结果链表中。
#include <iostream>
#include <stdio.h>
using namespace std;//
typedef struct node {int data; //节点内容node *next; //下一个节点
}node;node *MergeRecursive(node *head1, node *head2) {node *head = NULL;//if (head1 == NULL) {return head2; }//if (head2 == NULL) {return head1;}//if (head1->data < head2->data) {head = head1;head->next = MergeRecursive(head1->next,head2);}else {head = head2;head->next = MergeRecursive(head1, head2->next);}//return head;
}
12、面试题12
循环链表的操作：：
编号为1,2…,N的N个人按顺时针方向围坐一圈，每个人持有一个密码(正整数)，一开始任选一个正整数作为报数上限值 M，从第一个人开始按顺时针方向自1开始按顺序报数，报到M时停止报数。报M的人出列，将他的密码作为新的M值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止，求出列顺序。
思路：
显然当有人退出圆圈后，报数的工作要从下一个人开始继续，而剩下的人仍然是围成一个圆圈的，因此可以使用循环单链表。由于退出圆圈的工作对应着表中节点的删除工作，对于这种删除操作频繁的情况，选用效率较高的链表结构。为了程序指针每一次都指向一个具体的代表一个人的结点而不需要判断。链表不带头节点。所以，对于所有人围成的圆圈所对应的数据结构采用一个不带头节点的循环链表描述。设头指针为p，并根据具体情况移动。
为了记录退出的人的先后顺序，采用一个顺序表进行存储。程序结束后再输出依次退出的人的编号顺序。由于只记录各个节点的data值就可以了，所以定一个整型一维数组。如 int quit[n]；n 为一个根据实际问题定义一个足够大的整数。
#include <iostream>
#include <stdio.h>
using namespace std;//结构体和函数声明
typedef struct node {int data; //节点内容node *next; //下一个节点
}node;//构造节点数量为 n 的单向循环链表
node * node_create(int n) {node *pRet = NULL;//if (0 != n) {int n_idx = 1;node *p_node = NULL;//构造n个node*p_node = new node[n];if (NULL == p_node) {return NULL;}else {memset(p_node, 0, n * sizeof(node)); //初始化内存}//pRet = p_node;while (n_idx < n) {p_node->data = n_idx;p_node->next = p_node + 1;p_node = p_node->next;n_idx++;}p_node->data = n;p_node->next = pRet;}return pRet;
}
//
int main() {node *pList = NULL;node *pIter = NULL;int n = 20;int m = 6;//构造单项循环链表pList = node_create(n);//循环取数pIter = pList;m = m%n;while (pIter != pIter->next) {int i = 1;//取到第m-1个节点for (; i < m - 1; i++) {pIter = pIter->next;}//输出第m个节点的值printf("%d", pIter->next->data);//从链表中删除第m个节点pIter->next = pIter->next->next;pIter = pIter->next;}printf("%d\n", pIter->data);//释放delete[]pList;system("pause");return 0;
}
13、面试题13
编程实现一个双向链表：
#include <iostream>
#include <stdio.h>
using namespace std;//结构体和函数声明
typedef struct DbNode {int data; //节点内容DbNode *left; //前驱节点指针DbNode *right; //后继节点指针
}DbNode;//根据 数据 创建节点，返回新创建的节点，给出数据
DbNode *CreateNode(int data) {DbNode *pnode = (DbNode *)malloc(sizeof(DbNode));pnode->data = data;pnode->left = pnode;pnode->right = pnode;return pnode;
}//创建链表,根据一个节点创建链表的表头，返回表头节点
DbNode *CreateList(int head) {DbNode *pnode = (DbNode *)malloc(sizeof(DbNode));pnode->data = head;pnode->left = pnode;pnode->right = pnode; //让其前驱和后继指针都指向自身return pnode;
}//插入新节点，总是在表尾插入，返回表头节点
DbNode *AppendNode(DbNode *head, int data) { //参数1为链表的头节点DbNode *node = CreateNode(data); //参数2是要插入的节点，其数据为dataDbNode *p = head, *q;//while (p != NULL) {q = p;p = p->right;}q->right = node;node->left = q;//return head;
}
14、面试题14
编程实现一个双向链表的测长：
使用 right 指针进行遍历，直到遇到 NULL 为止。
#include <iostream>
#include <stdio.h>
using namespace std;//结构体和函数声明
typedef struct DbNode {int data; //节点内容DbNode *left; //前驱节点指针DbNode *right; //后继节点指针
}DbNode;//获得链表的长度
int GetLength(DbNode *head) { //参数为链表的表头节点int count = 1;DbNode *pnode = NULL;// head 为 NULL 表示链表空if (head == NULL) {return 0;}pnode = head->right;while (pnode != NULL) {pnode = pnode->right; //使用right指针遍历count++;}return count;
}15、面试题15
编程实现一个双向链表的打印：
#include <iostream>
#include <stdio.h>
using namespace std;//结构体和函数声明
typedef struct DbNode {int data; //节点内容DbNode *left; //前驱节点指针DbNode *right; //后继节点指针
}DbNode;//打印整个链表
void PrintList(DbNode *head) {DbNode *pnode = NULL;//if (head == NULL) {return;}pnode = head;while (pnode != NULL) {printf("%d", pnode->data);pnode = pnode->right;}printf("\n");
}
16、面试题16
编程实现双向链表节点的查找：
#include <iostream>
#include <stdio.h>
using namespace std;//结构体和函数声明
typedef struct DbNode {int data; //节点内容DbNode *left; //前驱节点指针DbNode *right; //后继节点指针
}DbNode;//查找节点，成功则返回满足条件的节点指针，否则返回 NULL
DbNode *FindNode(DbNode *head, int data) { //参数1：链表的表头节点 ，参数2:要查找的节点。其数据为dataDbNode *pnode = head;//链表为空时返回NULLif (head == NULL) {return NULL;}//找到数据或者到达链表末尾，退出while循环while (pnode->right != NULL && pnode->data != data) {pnode = pnode->right;}//没有找到数据为data的节点，返回NULLif (pnode->right == NULL) {return NULL;}//return pnode;
}17、面试题17
编程实现双向链表的插入：
节点 p 后插入一个节点：
分为两种情况：
- 插入位置在中间；
- 插入位置在末尾；
不同：插入位置在中间时需要把 p 的原后继节点的前驱指针指向新插入的节点；
#include <iostream>
#include <stdio.h>
using namespace std;//结构体和函数声明
typedef struct DbNode {int data; //节点内容DbNode *left; //前驱节点指针DbNode *right; //后继节点指针
}DbNode;//根据 数据 创建节点，返回新创建的节点，给出数据
DbNode *CreateNode(int data) {DbNode *pnode = (DbNode *)malloc(sizeof(DbNode));pnode->data = data;pnode->left = pnode;pnode->right = pnode;return pnode;
}//在node节点之后插入新节点
void InsertNode(DbNode *node, int data) {DbNode *newnode = CreateNode(data);DbNode *p = NULL;//node为空的时候直接返回if (node == NULL) {return ;}//node为最后一个节点，接在最后一个节点后面if (node->right == NULL) {node->right = newnode;newnode->left = node;}else { //node为中间节点newnode->right = node->right; //newnode向右连接node->right->left = newnode;node->right = newnode; //newnode向左连接newnode->left = node;}
}
18、面试题18
编程实现一个双向链表节点的删除：
删除头节点、删除中间节点以及删除末节点。
#include <iostream>
#include <stdio.h>
using namespace std;//结构体和函数声明
typedef struct DbNode {int data; //节点内容DbNode *left; //前驱节点指针DbNode *right; //后继节点指针
}DbNode;//根据 数据 创建节点，返回新创建的节点，给出数据
DbNode *CreateNode(int data) {DbNode *pnode = (DbNode *)malloc(sizeof(DbNode));pnode->data = data;pnode->left = pnode;pnode->right = pnode;return pnode;
}
//
//查找节点，成功则返回满足条件的节点指针，否则返回 NULL
DbNode *FindNode(DbNode *head, int data) { //参数1：链表的表头节点 ，参数2:要查找的节点。其数据为dataDbNode *pnode = head;//链表为空时返回NULLif (head == NULL) {return NULL;}//找到数据或者到达链表末尾，退出while循环while (pnode->right != NULL && pnode->data != data) {pnode = pnode->right;}//没有找到数据为data的节点，返回NULLif (pnode->right == NULL) {return NULL;}//return pnode;
}
//删除满足指定条件的节点，返回表头节点，删除失败，返回NULL（失败的原因不存在该节点）
DbNode *DeleteNode(DbNode *head, int data) { //参数1是链表的表头节点DbNode *ptmp = NULL; //参数2是要插入的节点，其数据为data//DbNode *pnode = FindNode(head, data); //查找节点if (pnode == NULL) { //节点不存在，返回NULLreturn NULL;}else if (pnode->left = NULL) { //node为第一个节点head = pnode->right;if (head != NULL) { //链表不为空head->left = NULL;}}else if (pnode->right == NULL) { //node为最后一个节点pnode->left->right = NULL;}else { //node为中间节点pnode->left->right = pnode->right;pnode->right->left = pnode->left;}//释放已被删除的节点空间free(pnode);return head;
}
19、面试题19
实现有序双向循环链表的插入操作：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;//结构体和函数声明
typedef struct DbNode {int data; //节点数据DbNode *left; //前驱节点指针DbNode *right; //后继节点指针
}DbNode;//根据 数据 创建节点，包括头节点和一般节点。创建头节点时，left 和 right 指针都指向本身来形成环状
DbNode *CreateNode(int data) {DbNode *pnode = (DbNode *)malloc(sizeof(DbNode));pnode->data = data;pnode->left = pnode;pnode->right = pnode;return pnode;
}
//插入新节点，总是在表尾插入；返回表头节点
DbNode *AppendNode(DbNode *head, int data) { //参数1是链表的表头结点DbNode *node = CreateNode(data); //参数2是要插入的节点，其数据为data。创建数据为data的新节点DbNode *p = NULL;DbNode *q = NULL;//if (head == NULL) {return NULL;}//q = p = head->right;while (p != head) {q = p;p = p->right;}//q->right = node; //与原最后一个节点互连node->left = q;node->right = head; //与头节点互连，形成环状head->left = node;return head;
}
//打印整个链表，由于属于循环链表，因此遍历回到head节点时结束打印
void PrintList(DbNode *head) {DbNode *pnode = NULL;//if (head == NULL) {return;}printf("%d", head->data);pnode = head ->right;while (pnode != NULL) {printf("%d", pnode->data);pnode = pnode->right;}printf("\n");
}
//插入一个有序链表（从小到大），返回表头。这里插入位置分为表头和非表头两种情况。
//如果是表头，返回的指针是新的节点，否则返回的是原来的表头节点
DbNode *InsertNode(DbNode *head, int data) {DbNode *p = NULL;DbNode *q = NULL;DbNode *node = NULL;//创建数据节点node = CreateNode(data);//空链表，返回新建链表if (head == NULL) {head = node;return node;}//data小于表头数据，插入到表头之前if (head->data > data) { //把新建节点作为表头head->left->right = node; //末节点后继指针指向nodenode->left = head->left; //node的前驱指针指向末节点node->right = head; //node的后继指针指向headhead->left = node; //head的前驱指针指向nodereturn node;}//p = head->right;while (p->data <= data && p != head) {p = p->right;}//p = p->left;q = p->right;//把node插入p和q之间p->right = node;node->left = p;node->right = q;q->left = node;return head;
}int main() {DbNode *head = CreateNode(1);AppendNode(head, 3);AppendNode(head, 6);AppendNode(head, 8);PrintList(head);head = InsertNode(head, 0);PrintList(head);head = InsertNode(head, 4);PrintList(head);head = InsertNode(head, 10);PrintList(head);//system("pause");return 0;
}20、面试题20
删除两个双向循环链表的相同结果：
有两个双向循环链表A，B，知道其头指针分别为 pHeadA，pHeadB。请写一个函数，将两链表中 data 值相同的节点删除。
解析：
- 把 A 中含有的与 B 中相同的数据节点抽出来，组成一个新的链表，如
链表A：1 2 3 4 2 6 4
链表B：10 20 3 4 2 10
新建链表C：2 3 4 - 遍历链表 C，删除 A 和 B 的所有节点。如果 A 含有数据相等的节点（A 有两个 4），且 B 也含有此数据节点（B 也有4），则 A 中数据相等的节点全部被删除。
这个代码还未理解透，稍后补吧！
21、面试题21
编程实现队列的入队、出队、测长、打印：
队列的实现可使用链表和数组，我们本题中使用单链表来实现队列。
#include <stdlib.h>
typedef struct _Node{int data;struct _Node *next; //指向链表下一个指针
}node;typedef struct _Queue {node *front; //对头node *rear; //队尾
}MyQueue;
构造空的队列：
//构造一个空的队列
MyQueue *CreateMyQueue() {MyQueue *q = (MyQueue *)malloc(sizeof(MyQueue));q->front = NULL; //队首置空q->rear = NULL; //队尾指针置空return q;
}
入队、出队、测长、打印：
#include <stdlib.h>
#include <stdio.h>
using namespace std;typedef struct _Node{int data;struct _Node *next; //指向链表下一个指针
}node;typedef struct _Queue {node *front; //对头node *rear; //队尾
}MyQueue;//构造一个空的队列
MyQueue *CreateMyQueue() {MyQueue *q = (MyQueue *)malloc(sizeof(MyQueue));q->front = NULL; //队首置空q->rear = NULL; //队尾指针置空return q;
}//入队，从队尾一端插入节点
MyQueue *enqueue(MyQueue *q, int data) {node *newP = NULL;newP = (node*)malloc(sizeof(node)); //新建节点newP->data = data; //复制节点数据newP->next = NULL;//如果队列为空，则新节点既是队首也是队尾if (q->rear == NULL) {q->front = q->rear = newP;}else { //若队列不为空，则新节点放到队尾，队尾指针指向新节点q->rear->next = newP;q->rear = newP;}return q;
}//出队，从队头一端删除节点
MyQueue *dequence(MyQueue *q) {node *pnode = NULL;pnode = q->front; //指向队头//判断队是否为空if (pnode == NULL) {printf("Empty queue !\n");}else { //新队头q->front = q->front->next;//当删除后队列为空时，对rear置空if (q->front == NULL) {q->rear = NULL;}free(pnode); //删除原队头节点}return q;
}//测长
int GetLength(MyQueue *q) {int nlen = 0;node *pnode = q->front; //指向队头//队列不为空if (pnode != NULL) {nlen = 1;}//遍历队列while (pnode != q->rear) { //队尾不一定是一个链表的末节点pnode = pnode->next; //循环一次，nlen递增1nlen++;}return nlen;
}//打印
void PrintMyQueue(MyQueue *q) {node *pnode = q->front;//队列为空if (pnode == NULL) {printf("Empty Queue!\n");return;}printf("data: ");//遍历队列while (pnode != q->rear) {printf("%d", pnode->data); //打印节点数据pnode = pnode->next;}printf("%d", pnode->data); //打印队尾节点数据
}22、面试题22
队列和栈的区别：
队列：入队和出队；队列在队尾入队，队头出队；FIFO，先进先出
栈：入栈和出栈；入栈和出栈都在栈顶，无法对栈底进行操作；LIFO，后进先出；
24、面试题24
使用单链表实现栈：
class MyStack {
public:MyStack() :top(NULL) {} //默认构造函数void push(MyData data); //进栈void pop(MyData *pData); //出栈bool IsEmpty(); //是否为空栈MyData *top; //栈顶
};class MyData {
public:MyData():data(0),next(NULL){} //默认构造函数MyData(int value):data(value),next(NULL){} //带参数的构造函数int data; //数据域MyData *next; //下一个节点
};
//进栈
void MyStack::push(MyData data) {MyData *pData = NULL;pData = new MyData(data.data); //生成新的节点pData->next = top; //与原来的栈顶节点相连top = pData; //栈顶节点为新加入的节点
}
//判断栈是否为空栈
bool MyStack::IsEmpty() { //如果 top 为空，则返回1，否则返回0return (top == NULL);
}
//出栈，返回栈顶节点内容
void MyStack::pop(MyData *data) {if (IsEmpty()) { //如果为空，则直接返回return;}data->data = top->data; //给传出的参数赋值MyData *p = top; //临时保存原栈顶节点top = top->next; //移动栈顶，指向下一个节点delete p; //释放原栈顶节点内存
}
使用栈实现队列：
stack：先进后出；
queue：先进先出；
#include <stdio.h>
#include <iostream>
using namespace std;class MyStack {
public:MyStack() :top(NULL) {} //默认构造函数void push(MyData data); //进栈void pop(MyData *pData); //出栈bool IsEmpty(); //是否为空栈MyData *top; //栈顶
};class MyData {
public:MyData():data(0),next(NULL){} //默认构造函数MyData(int value):data(0),next(NULL){} //带参数的构造函数int data; //数据域MyData *next; //下一个节点
};
//
class MyQueue {
public:void enqueue(MyData data); //入队void dequeue(MyData &data); //出队bool IsEmpty(); //是否为空
private:MyStack s1; //用于入队MyStack s2; //用于出队
};
//入队
void MyQueue::enqueue(MyData data) {s1.push(data); //只对s1进行栈操作
}
//出队
void MyQueue::dequeue(MyData &data) {MyData temp(0); //局部变量，用于临时存储//if (s2.IsEmpty()) { //如果s2为空，把s1的所有元素push到S2中while (!s1.IsEmpty()) {s1.pop(temp); //弹出s1的元素s2.push(temp); //压入S2中}}if (!s2.IsEmpty()) { //此时如果S2不为空，则弹出s2的栈顶元素s2.pop(data);}
}//队列判空
bool MyQueue::IsEmpty() {return (s1.IsEmpty() && s2.IsEmpty());
}
25、面试题25
用 C++ 实现一个二叉排序树：
二叉排序树（Binary Sort Tree）:二叉查找树（Binary Search Tree）。满足：
- 若它的左子树为空，则左子树上所有节点值均小于根节点的值；
- 若它的右子树非空，则它右子树上所有节点的值均大于根节点的值；
- 左、右子树本身又是一个二叉排序树；
#include <stdio.h>
//节点类定义
class Node {
public:int data; //数据Node *parent; //父亲节点Node *left; //左节点Node *right; //右节点
public:Node() :data(-1), parent(NULL), left(NULL), right(NULL) {};Node(int num) :data(num), parent(NULL), left(NULL), right(NULL) {};
};
//二叉排序树的定义
class Tree {
public:Tree(int num[], int len); //插入num数组前len个数据，根据int数组创建二叉排序树void insertNode1(int data); //插入节点，递归方法void insertNode(int data); //插入节点，非递归方法Node *searchNode(int data); //查找节点void deleteNode(int data); //删除节点以及子树
private:void insertNode(Node* current, int data); //递归插入方法Node *searchNode(Node* current, int data); //递归查找方法void deleteNode(Node* current); //递归删除方法
private:Node* root; //二叉排序树的根节点
};
下面着重介绍每个函数：
创建二叉排序树：首先生成根节点，然后循环调用插入节点的方法对二叉树进行插入操作。
#include <stdio.h>
//节点类定义
class Node {
public:int data; //数据Node *parent; //父亲节点Node *left; //左节点Node *right; //右节点
public:Node() :data(-1), parent(NULL), left(NULL), right(NULL) {};Node(int num) :data(num), parent(NULL), left(NULL), right(NULL) {};
};
//二叉排序树的定义
class Tree {
public:Tree(int num[], int len); //插入num数组前len个数据void insertNode1(int data); //插入节点，递归方法void insertNode(int data); //插入节点，非递归方法Node *searchNode(int data); //查找节点void deleteNode(int data); //删除节点以及子树
private:void insertNode(Node* current, int data); //递归插入方法Node *searchNode(Node* current, int data); //递归查找方法void deleteNode(Node* current); //递归删除方法
private:Node* root; //二叉排序树的根节点
};//插入num数组的前 len 个数据
Tree::Tree(int num[], int len) {root = new Node(num[0]); //建立根节点root//把数组中的其他数组插入到二叉排序树中for (int i = 1; i < len; i++) {insertNode1(num[i]);}
}
使用非递归方法插入节点：
#include <stdio.h>
//节点类定义
class Node {
public:int data; //数据Node *parent; //父亲节点Node *left; //左节点Node *right; //右节点
public:Node() :data(-1), parent(NULL), left(NULL), right(NULL) {};Node(int num) :data(num), parent(NULL), left(NULL), right(NULL) {};
};
//二叉排序树的定义
class Tree {
public:Tree(int num[], int len); //插入num数组前len个数据void insertNode1(int data); //插入节点，递归方法void insertNode(int data); //插入节点，非递归方法Node *searchNode(int data); //查找节点void deleteNode(int data); //删除节点以及子树
private:void insertNode(Node* current, int data); //递归插入方法Node *searchNode(Node* current, int data); //递归查找方法void deleteNode(Node* current); //递归删除方法
private:Node* root; //二叉排序树的根节点
};//插入节点的操作
//非递归方法，插入参数为 data 的节点
void Tree::insertNode1(int data) {Node *p, *par;Node *newNode = new Node(data); //创建节点//查找插入在哪个节点下面p = par = root;while (p != NULL) {par = p; //保存节点if (data > p->data) //如果data大于当前节点的datap = p->right; //下一步到左子节点，否则到右子节点else if (data < p->data)p = p->left;else if (data == p->data) { //不插入重复数据delete newNode;return;}}newNode->parent = par;if (par->data > newNode->data) { //把新节点插入到目标节点的正确位置par->left = newNode;}elsepar->right = newNode;
}
使用递归方法插入节点：
#include <stdio.h>
//节点类定义
class Node {
public:int data; //数据Node *parent; //父亲节点Node *left; //左节点Node *right; //右节点
public:Node() :data(-1), parent(NULL), left(NULL), right(NULL) {};Node(int num) :data(num), parent(NULL), left(NULL), right(NULL) {};
};
//二叉排序树的定义
class Tree {
public:Tree(int num[], int len); //插入num数组前len个数据void insertNode1(int data); //插入节点，递归方法void insertNode(int data); //插入节点，非递归方法Node *searchNode(int data); //查找节点void deleteNode(int data); //删除节点以及子树
private:void insertNode(Node* current, int data); //递归插入方法Node *searchNode(Node* current, int data); //递归查找方法void deleteNode(Node* current); //递归删除方法
private:Node* root; //二叉排序树的根节点
};
//insertNode()使用递归方法
void Tree::insertNode(int data) {if (root != NULL) {insertNode(root, data); //调用递归插入方法}
}//递归插入方法
void Tree::insertNode(Node* current, int data) {//如果data小于当前节点数据，则在当前节点的左子树插入if (data < current->data) {//如果左节点不存在，则新建插入到左节点if (current->left == NULL) {current->left = new Node(data);current->left->parent = current;}else {insertNode(current->left, data); //否则对左节点进行递归调用}}//如果data大于当前节点数据，则在当前节点的右子树插入else if (data > current->data) {//如果右子树不存在，则插入到右子树if (current->right == NULL) {current->right = new Node(data);current->right->parent = current;}else { //如果右子树存在，就对右节点进行递归调用insertNode(current->right, data);}return; //data 等于当前节点数据时，不插入}return;
}
查找节点：
//递归查找方法
Node* Tree::searchNode(Node* current, int data) {//如果data小于当前节点数据，则递归搜索其左子树if (data < current->data) {if (current->left == NULL) { //如果不存在左子树，则返回NULLreturn NULL;}return searchNode(current->left, data);}//如果data大于当前节点数据，则递归搜索其左子树else if (data > current->data) {//如果不存在右子树，则返回NULLif (current->right == NULL) {return NULL;}return searchNode(current->right, data);}//相等，则返回currentreturn current;
}删除节点：
//删除数据为data的节点及其子树
void Tree::deleteNode(int data) {Node *current = NULL;//查找节点current = searchNode(data);if (current != NULL) {deleteNode(current); //删除节点及其子树}
}//删除current节点及其子树的所有节点
void Tree::deleteNode(Node *current) {if (current->left != NULL) { //删除左子树deleteNode(current->left);}if (current->right != NULL) { //删除右子树deleteNode(current->right);}if (current->parent == NULL) { //如果current是根节点，把root置空delete current;root = NULL;return;}//将current父亲节点的相应指针置空if (current->parent->data > current->data) //current为其父节点的左子节点current->parent->left = NULL;elsecurrent->parent->right = NULL; //current为其父节点的右子节点//最后删除此节点delete current;
}
26、面试题26
使用递归和非递归方法实现中序遍历：
中序遍历：左节点–>根节点–>右节点
中序遍历，递归解法：
//中序遍历，递归解法
void Tree::InOrderTree(Node* current) {if (current != NULL) {InOrderTree(current->left);cout << current->data << " ";InOrderTree(current->right);}
}
中序遍历，非递归解法：
- 先将根节点入栈，遍历左子树（左子树全部进栈）；
- 遍历完一个一个左子树返回时（不是全部出去），栈顶元素应为根节点，此时出栈，并打印节点数据；
- 再中序遍历右子树；
//中序遍历，非递归解法
void Tree::InOrderTreeUnRec(Node *root) {stack<Node *> s;Node *p = root; //根节点while (p != NULL || !s.empty()) {while (p != NULL) { //遍历左子树s.push(p); //根节点先入栈，再把遍历的节点全部压栈p = p->left;}//if (!s.empty()) {p = s.top(); //得到栈顶内容s.pop(); //出栈cout << p->data << " "; //打印p = p->right; //指向右子节点，下一次循环就会遍历右子树}}
}
27、面试题27
使用递归和非递归方法实现先序遍历：
先序遍历：根节点–>左节点–>右节点
递归解法：
void Tree::PreOrderTree(Node* current) {if (current != NULL) {cout << current->data << endl;PreOrderTree(current->left);PreOrderTree(current->right);}
}
非递归解法：
void Tree::PreOrderTree(Node* root) {stack<Node *> s;Node *p = root;while (p != NULL || !s.empty()) {while (p != NULL) {cout << p->data << " ";s.push(p);p = p->left;}//if (!s.empty()) {p = s.top();s.pop();p = p->right;}}
}
28、面试题28
使用递归和非递归方法实现后序遍历：
递归方法：
void Tree::PostOrderTree(Node* current) {if (current != NULL) {PostOrderTree(current->left); //遍历左子树PostOrderTree(current->right); //遍历右子树cout << current->data << " "; //打印根节点}
}非递归方法：
假设T为要遍历树的根指针，后序遍历要求在遍历完左、右子树后再访问根。需要判断根节点的左、右子树是否均遍历过。
我们采用标记法，节点入栈时候，需要一个标志 tag 一同入栈（tag 为 0 表示遍历左子树前的现场保护，tag 为1表示右子树前的现场保护）。
首先将 T 和 tag (为0)入栈，遍历左子树；返回时，修改栈顶 tag 为1，遍历右子树，最后访问根节点。
void Tree::PostOrderTreeUnRec(Node* root) {stack<Node *>s;Node *p = root;//while (p != NULL || !s.empty()) {while (p != NULL) {s.push(p); //根节点入栈p = p->left; //左子树入栈}//if (!s.empty()) {p = s.top(); //得到栈顶元素if (p->tag) { //tag为1时cout << p->data << " "; //打印节点数据s.pop(); //出栈p = NULL; //第二次访问标志其右子树已经遍历}else {p->tag = 1; //修改tag为1p = p->right; //指向右节点，下次遍历其左子树}}}
}
29、面试题29
层次遍历算法：
用队列实现，出队！
void Tree::LevelOrderTree(Node* root) {queue<Node *>q; //定义队列q，它的元素为Node* 型指针Node *ptr = NULL;q.push(root);while (!q.empty()) {ptr = q.front(); //根节点入队q.pop(); //出队cout << ptr->data << " ";if (ptr->left != NULL) {q.push(ptr->left);}if (ptr->right != NULL) {q.push(ptr->right);}}
}
28、面试题28
判断给定的二叉树是否是二叉排序树：
中序遍历的结果就是排序二叉树的排序输出：
这段程序的核心就是：使用一个 lastvalue 来记录上一个节点的数据。如果出现 lastvalue 大于或者等于当前出队的节点值，则返回 false；否则一直入队和出队。如果 lastValue 始终小于当前出队的节点值，则是升序排序，返回 true。
//使用中序遍历二叉树是否为排序二叉树
bool IsSortedTree(Tree tree) {int lastValue = 0;stack<Node *>s;Node *p = tree.root;//while (p != NULL || !s.empty()) {while (p != NULL) {s.push(p); //遍历左子树p = p->left; //把遍历的左节点全部压栈}//if (!s.empty()) {p = s.top(); //得到栈顶内容s.pop(); //出栈if (lastValue == 0 || lastValue < p->data) {lastValue = p->data; //如果是第一次弹出或者lastvalue小于}else if (lastValue >= p->data) {//如果lastvalue大于当前节点值，则返回falsereturn false;}p = p->right; //指向右子节点，下一次循环就会中序遍历右子树}}return true;
}
更多推荐
C和C++程序员面试秘笈之⑧
发布评论