作者序

  题目均来自于往年试卷,给出的代码都能够编译通过。

例题一:哈希表的使用

  题面: 假设线性表采用顺序存储结构,试实现函数int DelRepeat(),用以删除所有重复元素,并返回删除元素的个数。要求算法的时间复杂度为$O(n)$。线性表结构定义如下:

1
2
3
4
5
6
7
8
9
10
11
class seqList{
private:
int* data;//保存的元素数组
int currentLength;//元素个数
int noData;//数据中不存在的元素

public:
int DelRepeat(){
//add your code here
}
};

  代码实现如下,注意:测试代码未给出,请读者自行构造。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class seqList{
private:
int* data;//保存的元素数组
int currentLength;//元素个数
int noData;//数据中不存在的元素

public:
seqList(int n){//构造函数
currentLength=n;//元素个数
data=new int[n];
cout<<"input data:"<<endl;
for(int i=0;i<n;++i){//获取元素值
cin>>data[i];
}
}

void display(){//展示数组元素
cout<<"the data are:"<<endl;
for(int i=0;i<currentLength;++i){
cout<<data[i]<<"\t";
}
cout<<endl;
}

int delRepeat(int n){//删除重复元素
noData=n;//标记输入数据中不存在的元素
bool* status=new bool[currentLength];
for(int i=0;i<currentLength;++i){//创建判断元素,为真则该位置的数字出现过
status[i]=false;
}
int* hashtable=new int[2*currentLength];//创建哈希表
for(int i=0;i<2*currentLength;++i){//哈希表初始化
hashtable[i]=noData;
}

for(int i=0;i<currentLength;++i){
int pos=data[i]%(2*currentLength);//获得哈希值

while(hashtable[pos]!=noData&&hashtable[pos]!=data[i]) (++pos)%(2*currentLength);//定位到第一个可以插入的位置

if(hashtable[pos]==data[i]){
status[i]=true;//如果有该元素,标记为待删除元素
}
else{
hashtable[pos]=data[i];//没有该元素,插入该元素
}

}//end for

int i=0,j=0;
int newLength=0;
int oldLength=currentLength;
int* tmp=new int[currentLength];//装载没被删去的元素
for(int i=0;i<currentLength;++i){
if(!status[i]){//如果判断数组对应位置为假,保留该数字
tmp[j]=data[i];
++j;
newLength++;
}
}
delete[] data;//内存管理
data=tmp;//数据内容更新
delete[] hashtable;
currentLength=newLength;//更新数组长度

return (oldLength-currentLength);
}
};

  总结: 对于需要反复回溯已遍历元素中某个元素出现与否的,哈希表是一个很好的解决方式,可以减少$O(n)$的算法复杂度。注意哈希表的重点:哈希函数冲突解决

例题二:二叉树

  给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。请完善下列算法,实现将上述两个二叉树合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。注意:合并后的二叉树中结点允许直接使用这两个二叉树上的结点。给出二叉树的定义:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class binaryTree{
private:
struct node{//二叉树的节点类
int value;
node* left;
node* right;
node(int val){//构造函数
value=val;
left=NULL;
right=NULL;
}
};
node* root;//二叉树的根节点

public:
node* mergeTrees(node* t1, node* t2){//合并二树
//add your code here
}
};

  想法是:合并二树可以看成三个过程:合并根节点递归调用合并左右子树。因此,合并二树的操作并不难,只需要注意递归跳出的条件:其中一棵树为空树即可。为了完成代码的检查,我们还需要复习一遍二叉树的构建和层次遍历的知识点。以下代码包含了测试代码,可以直接运行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<iostream>
#include<queue>
using namespace std;

class binaryTree{
private:
struct node{//二叉树的节点类
int value;
node* left;
node* right;
node(int val){//构造函数
value=val;
left=NULL;
right=NULL;
}
};
node* root;//二叉树的根节点

public:
binaryTree(){//基于层次遍历的构造函数
int val;
int lval;
int rval;
cout<<"input the root:";
cin>>val;
cout<<endl;
root=new node(val);
queue<node*> que1;
que1.push(root);
while(!que1.empty()){
node* tmp=que1.front();
que1.pop();
cout<<"input the two children of the given node "<<tmp->value<<":";
cin>>lval>>rval;
cout<<endl;
if(lval){
tmp->left=new node(lval);
que1.push(tmp->left);
}
if(rval){
tmp->right=new node(rval);
que1.push(tmp->right);
}
}
cout<<"binarytree has been built!"<<endl;
}

binaryTree(node* r){//给定根节点的构造函数
root=r;
}

void display(){//层次遍历
queue<node> que1;
que1.push(*root);
while(!que1.empty()){
node tmp=que1.front();
que1.pop();
cout<<tmp.value<<" ";
if(tmp.left){
que1.push(*(tmp.left));
}
if(tmp.right){
que1.push(*(tmp.right));
}
}
cout<<"display completed!"<<endl;
}

node* findRoot(){//返回二叉树根节点的位置
return root;
}

node* mergeTrees(node* t1, node* t2){//合并二树
if(!t1) return t2;//递归跳出条件,即其中一棵树是空树
if(!t2) return t1;

node* t3=new node(t1->value+t2->value);
t3->left=mergeTrees(t1->left,t2->left);//假定该函数能够完成合并二树的操作,只需要对左右子树递归调用
t3->right=mergeTrees(t1->right,t2->right);

return t3;

}
};

int main(){
binaryTree tree1;
tree1.display();
binaryTree tree2;
tree2.display();//构建两棵树并展示之
binaryTree tree3(tree1.mergeTrees(tree1.findRoot(),tree2.findRoot()));//合并子树
tree3.display();

return 0;
}

例题三:拓扑排序

  题面: 学生需要修读完所有的课程才能毕业,这些课程之间有先导关系(比如要修读数据结构,必须先修读程序设计思想方法)。假设任意一门课程可以在任何一个学期给满足条件的学生选修,且学生每个学期可以选修的课程数不限。先给出一些课程与课程之间的关系,求能够修完所有课程的最少学期数。

  输入格式: 第1行:n m //正整数n ,代表课程的数量。非负整数m代表要给出几个先导关系。第2行到第1+m行: a b //每行两个整数:代表要选修编号为a的课程,必须先修读编号为b的课程。

  输出格式: 一个整数,即修完所有课程的最少学期数。

  思路: 本题可以参考拓扑排序的方式,即:选取入度为零的点,将其移除,然后更新有向图;再移除入度为零的点,如此循环。实现的代码如下,主函数也已经给出,且能够编译通过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<iostream>
#include<queue>
using namespace std;

class adjListGraph{
private:
struct edgeNode{
int end;
edgeNode* next;
edgeNode(int e,edgeNode* n=NULL){
end=e;
next=n;
}
};

struct verNode{
int ver;
edgeNode* head;

verNode(int val=0){
ver=val;
head=NULL;
}
};

verNode* verList;
int Vers;
int* inDegree;//入度统计数组

public:
adjListGraph(int vSize){//构造函数
Vers=vSize;
verList=new verNode[Vers+1];
inDegree=new int[Vers+1];
for(int i=1;i<=Vers;++i){
verList[i].ver=i;
inDegree[i]=0;
}
}

void insert(int end,int in){
verList[in].head=new edgeNode(end,verList[in].head);
inDegree[end]++;//入度增加
}

int topSort(){
int counter=0;
int remain=Vers;//剩余未被删除的元素个数,用于判断循环结束
int current;//当前将要出队的元素
queue<verNode> que1;

while(remain!=0){
for(int i=1;i<=Vers;++i){
if(inDegree[i]==0){
que1.push(verList[i]);//入度为零的点入队
}
}//end for
while(!que1.empty()){
current=que1.front().ver;
que1.pop();
edgeNode*p=verList[current].head;
while(p){
inDegree[p->end]--;//该出队元素所指向的元素入度自减
p=p->next;
}
remain--;
inDegree[current]=-1;//已修完的课在下一次循环不需要被读取
}
counter++;//完成后计数器增加
}

return counter;
}
};

int main(){
int n,m;//课程数量、先导关系
cin>>n>>m;
adjListGraph graph(n);
for(int i=1;i<=m;++i){
int a,b;
cin>>a>>b;
graph.insert(a,b);
}

cout<<graph.topSort()<<endl;

return 0;
}

  上述程序中指定队列的原因是,为了区分出每一学期修了多少门课。每一个学期进行一次统一的入队操作,而后出队直至队空为止。