浅谈动态规划(二)——进阶题

上一次的动态规划的文章中(浅谈动态规划(一)——从lintcode刷题入门),借助lintcode上两个简单且典型的例子(Triangle和Climbing Stairs),阐述了动态规划的两个特点:1)最优子结构,和2)子问题重叠。这回来讲讲最近做lintcode上的几个难度稍微大一些的题目。这些题目也很符合动态规划的那两个特点。

先来看看第一个题目。

1.Paint Fence(栅栏染色)

题目描述:
There is a fence with n posts, each post can be painted with one of the k colors. You have to paint all the posts such that no more than two adjacent fence posts have the same color. Return the total number of ways you can paint the fence.
Notice: n and k are non-negative integers.

例子:
Given n=3, k=2 return 6

     post 1, post 2, post 3
way1    0      0       1
way2    0      1       0
way3    0      1       1
way4    1      0       0
way5    1      0       1
way6    1      1       0

题目中要求给n个栅栏涂颜色,有k种颜色可以选择,限制条件是最多可以有两个相邻的栅栏颜色相同。

解题思路:
令ways[i]( n = 1, 2, 3, ..., n )表示涂到第i个栅栏时的所有的方法数。这样,题目就符合动态规划的两个特征(参考之前的那篇文章分析),就可以用动态规划求解。那么我们在涂第i个栅栏的时候,有两种涂色方式:1)和第i-1个栅栏的颜色相同;2)和第i-1个栅栏的颜色不同。在1)方式下,因为要保证最多只有两个相邻的栅栏颜色相同,所以第i个栅栏的颜色和第i-2个栅栏的颜色必然是不同的,那么此时有ways[i-2] * (k-1)中填涂的方式。在2)方式下,不需要考虑之前的栅栏的颜色,只要保证和i-1个栅栏颜色不同即可,此时有ways[i-1] * (k-1)中方法。所以有状态转移方程:

ways[i] = ways[i-2] * (k-1) + ways[i-1] * (k-1)

同时发现,每次只要用到相邻的3个栅栏的方法数就可以了,这样可以减少空间的使用。所以代码为:

int numWays(int n, int k) {
	// Write your code here
	if (n == 0 || k == 0)
		return 0;
		
	if (n == 1)
		return k;
	if (n == 2)
		return k * k;
		
	int ways[3] = {0}; // 辅助数组,只使用3个变量即可
	ways[0] = k;
	ways[1] = k * k;
		
	// 动态规划步骤
	for (int i = 2; i < n; i++)
	{
		ways[2] = (k-1) * (ways[0] + ways[1]); // 依据相邻的两个栅栏的填涂方法数来求解第3个栅栏的填涂方法数
		ways[0] = ways[1];
		ways[1] = ways[2];
	}
		
	return ways[2];
}

这道题虽然也是简单的,但是因为限制条件的运用比较巧妙,所以给贴出来了。接下来看看下一题。

2.House Robber(打劫房屋)

题目描述:
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

例子:
Given [3, 8, 4], return 8.

题目要求从n个房屋中找出一些房屋取走里面财产,找到财产最大的总值,限制条件是不能有相邻的房屋同时被偷盗。

这道题虽然是道中等题,不过思路也很清晰,动态规划的两个特征也非常明显。令money[i]( i = 1, 2, ..., n )表示在偷第i个房屋时的最大值,那么在偷第i个房屋时,需要比较的只是money[i-1]和money[i-2] + A[i]值的大小(A[i]是第i个房屋的财产值),因为相邻的两个房屋不可能同时被偷。所以,状态转移方程为:

money[i] = max(money[i-1], money[i-2] + A[i])

同样,我们发现每次比较时,只需要保留最近两次的最大值即可,那么优化后的代码为:

long long houseRobber(vector<int> A) {
	// write your code here
	int n = A.size();

	if (n == 0)
		return 0;
	
	if (n == 1)
		return A[0];
	
	// 辅助数组
	long long money[3] = {0};
	money[0] = 0;
	money[1] = A[0];
	
	// 动态规划步骤
	for (int i = 2; i <= n; i++)
	{
		money[2] = max(A[i-1] + money[0], money[1]);
		money[0] = money[1];
		money[1] = money[2];
	}
	
	return money[2];
}

最后来看第3题。

3.Paint House(房屋染色)

题目描述:
There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.

Notice: All costs are positive integers.

例子:

Given costs = [[14,2,11],[11,14,5],[14,3,10]] return 10

house 0 is blue, house 1 is green, house 2 is blue, 2 + 5 + 3 = 10

题目要求给n个房子粉刷颜色,找到最小的费用。粉刷时有3种颜色可供选择,而粉刷不同的颜色的费用是不同的,限制条件是相邻的两个房子的颜色不能相同。这道题目其实和上一道题目有点类似,均为相邻的两个有限制,不过这个在动态规划的时候,比较的是粉刷的不同的颜色。同样的方法,令value[i][j](i = 1, 2, ..., n; j = 1, 2, 3)表示正在粉刷第i个房子的时候颜色为j时的总费用(之前粉刷的位置均保证了费用最小)。为了避免相邻的两个房子粉刷的颜色相同,在粉刷每一层的时候,还要和前一层粉刷的颜色比较。那么在粉刷第i个房屋颜色为j时的状态转移方程为:

value[i][j] = min(costs[i][j] + value[i-1][k]), k = 1, 2, 3; k != j

上式中k是上一层粉刷不同颜色到达最小值时的不同颜色。在粉刷时要保证相邻的两层颜色不相同,所以k != j。

有了状态转移方程,题目的代码就好写了:

int minCost2(vector<vector<int> > &costs)
{
	int n = costs.size();

	if (n == 0)
		return 0;
	
	int i, j, k;
	int temp;
	int minValue = INT_MAX;
			
	for (j = 0; j < 3; j++) 
            if (minValue > costs[0][j])
	        minValue = costs[0][j];
					   
	if (n == 1)
		return minValue;

	vector<vector<int> > value(n, vector<int>(3, INT_MAX)); // 辅助数组,初始化时每个位置均为INT_MAX

	// 动态规划步骤
	for (i = 0; i < n; i++)
	{
		if (i == 0)
		{
			for (j = 0; j < 3; j++)
				value[i][j] = costs[i][j];

			continue;
		}

		// 找出相邻两层不相同时,粉刷不同颜色的最小值
		for (j = 0; j < 3; j++)
		{
			minValue = INT_MAX;
			for (k = 0; k < 3; k++) // 上一层粉刷不同颜色时对应的最小值
			{
				if (k == j) // 跳过相同颜色
					continue;
				// 找出最小值
				temp = costs[i][j] + value[i-1][k];
				if (temp < minValue)
					minValue = temp;
			}
			value[i][j] = minValue;
		}
	}

	// 找出粉刷完最后一个房屋时的最小费用
	minValue = INT_MAX;
	for (j = 0; j < 3; j++) 
            if (minValue > value[n-1][j])
		minValue = value[n-1][j];

	return minValue;
}

同样,代码也可以优化以减少空间消耗,在这里就不再将最后结果贴出来了。

好了,这就是这次的全部内容。这些题目是我在刷lintcode中遇到的动态规划特征比较明显的题目,且比《浅谈动态规划(一)——从lintcode刷题入门》里面的一些题目稍微难点。希望能够给初接触动态规划的童鞋一点参考。

参考资料:
lintcode
1.Paint Fence(栅栏染色)
2.House Robber(打劫房屋)
3.Paint House(房屋染色)

windows下MatConvNet深度学习框架的搭建

MatConvNet是Matlab下用于机器视觉的一个工具包,主要应用是CNN网络,当然其他的网络也涉及到了。MatConvNet简洁、高效,可以用于图片分类、分割和人脸识别等等深度学习的功能。具体的可以参见官网的介绍。

在搭建环境的过程中,发现如今网上对其的资源不太多,所以在这做一个总结。以beta22版本为例。

过程分为下面几个步骤:
1.MatConvNet的下载
2.GPU模式的使用
3.测试

1.MatConvNet的下载

在其官网的页面进行下载,解压到适当的位置。

运行其中“matconvnet-1.0-beta22\examples\vggfaces”路径下的cnn_vgg_faces.m文件,会出现下面的结果,那么说明已经可以使用了。在运行前最好把其中要下载的一些内容给放到对应的文件夹下,这样可以节省一点等待的时间。

01

2.GPU模式的使用

官网的这个页面中,提到了搭建GPU的方式。

首先,安装CUDA,在这个页面有下载。记得下载和自己系统以及显卡支持的CUDA。

接下来,要下载cuDNN(The NVIDIA CUDA Deep Neural Network library)。cuDNN是用于GPU加速的一个库函数。在这个页面有下载。

然后把解压好的cuDNN放在合适的文件夹下,建议在MatConvNet下建立local文件夹,同时把cuDNN文件夹中bin文件夹下的cudnn64_5.dll文件复制到matconvnet-1.0-beta22\matlab\mex文件夹下。

最后,在MatConvNet文件夹下建立compileGPU.m文件,其中内容如下。记得把对应的路径给改成自己电脑中的路径。

addpath matlab;

%% with cudnn
vl_compilenn('enableGpu', true, ...
                'cudaRoot', 'C:\Program Files\NVIDIA GPU Computing Toolkit\CUDA\v8.0', ...  % CUDA的安装路径
                'cudaMethod', 'nvcc', 'enableCudnn', 'true', ...
                'cudnnRoot', 'E:\postgraduate\project\Machine Learning\Deep Learning\CNN\matconvnet-1.0-beta22\local\cudnn');   % cuDNN的路径

出现下面图片中类似的结果,就代表成功了。

02

4.测试

还是根据官网的这个页面,在命令行窗口输入vl_testnn命令,测试非GPU模式,会出现下面的内容。

04

接下来测试GPU模式,在命令行窗口输入vl_testnn('gpu', true),会有类似上面的内容出现。这就是成功了,GPU模式下的速度提示还是很明显的,一般都会有十倍以上。

06

到此,MatConvNet的安装就结束了。

同时,把我在安装过程中遇到的一个问题的解决方式给写一下。在安装cuDNN的时候,可能会遇到如下的错误“Error using mex nvcc fatal : Unsupported gpu architecture 'compute_21'”,其中21可以为其他不能被10整除的数字。这个时候可以把matconvnet-1.0-beta22\matlab下的vl_compilenn.m文件中的732行的代码中"%s"改为向下取10的整数倍。

比如,原代码为

  cudaArch = ...
      sprintf('-gencode=arch=compute_%s,code=\\\"sm_%s,compute_%s\\\" ', ...
              arch_code, arch_code, arch_code) ;

可以改为

  cudaArch = ...
      sprintf('-gencode=arch=compute_20,code=\\\"sm_20,compute_20\\\" ', ... 
              arch_code, arch_code, arch_code) ;

这样,经常遇到的问题就能解决了。

 

浅谈动态规划(一)——从lintcode刷题入门

动态规划是算法中比较常见的一种分析问题的方式,最近看算法看到这,带着lintcode上面的题目,在这写个总结。

首先从一个lintcode上面简单的题目开始。

Climbing Stairs(爬楼梯)

题目描述:
假设你正在爬楼梯,需要n步你才能到达顶部。但每次你只能爬一步或者两步,你能有多少种不同的方法爬到楼顶部?

样例:
比如n=3,1+1+1=1+2=2+1=3,共有3中不同的方法,所以返回 3。

这是一道非常具有代表性的动态规划的一道问题。

令f[n]记录到达第n阶台阶的方法数。假设你还有最后一步就能到达第n阶台阶,那么最后一步,你可以选择两种方式:1)踏一步以及,2)踏两步。如果是踏一步,那么你要从第n-1阶台阶踏出,此时的方法数是 f[n-1];如果是踏两步,那么你要从第n-2阶台阶出发,此时的方法数是f[n-2]。所以爬到第n级台阶的方法总数有f[n] = f[n-1] + f[n-2]种。状态转移方程:

f[n] = f[n-1] + f[n-2]

这样可以写出解答的递归形式:

int climbStairs(int n) {
	// write your code here
	if (n <= 1)
		return 1;
	else 
		return climbStairs(n-1) + climbStairs(n-2);
}

此时我们发现可以用一个一维数组来记录之前出现的结果,这样可以省去递归中不必要的空间开销:

int climbStairs(int n) {
	// write your code here
	vector<int> f(n+1);

	f[0] = 1;
	f[1] = 1;

	for (int i = 2; i <= n; i++)
		f[i] = f[i-1] + f[i-2];

	return f[n];
}

其实,这个还可以进一步优化,因为每一步都只需要前两个台阶的结果,所以可以用两个变量来代替一维数组。

int climbStairs(int n) {
	// write your code here
	if (n == 1 || n == 0)
		return 1;
	
	int ways1 = 1;
	int ways2 = 1;
	int ways = 0;
	
	int i = 2;
	while (i <= n)
	{
		ways = ways1 + ways2;
		
		ways1 = ways2;
		ways2 = ways;
		
		i++;
	}
	
	return ways;
}

接下来,我们再来看一题。

Triangle(数字三角形)

题目描述:
给定一个数字三角形,找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上。

样例
比如,给出下列数字三角形:

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

从顶到底部的最小路径和为11 ( 2 + 3 + 5 + 1 = 11)。

分析问题,我们发现可以用二维数组来计算到最底层每个位置的最小路径和,令第i层下标为j的位置上最小路径和为f[i][j]。那么,第i层下标为j位置的值f[i][j],只和i-1层位置j-1下标的最小路径和f[i-1][j-1]以及j位置的最小路径和f[i-1][j]有关。即,f[i][j] = min(f[i-1][j-1],  f[i-1][j])。所以状态转移方程为:

f[i][j] = min(f[i-1][j-1],  f[i-1][j])

同时,发现每次的结果只与上面一层的结果有关,所以省去二维数组,只用一维数组作为辅助。代码为:

int minimumTotal(vector<vector<int> > &triangle) {
	// write your code here
	if (triangle.size() == 0)
		return 0;
		
	vector<int> f(triangle[triangle.size() - 1].size());
	
	// 动态规划过程
	f[0] = triangle[0][0];
	for (int i = 1; i < triangle.size(); i++) 
        { 
                for (int j = triangle.size()-1; j >= 0; j--)
		{
			if (j == 0)
				f[j] = f[j] + triangle[i][j];
			else if (j == triangle[i].size()-1)
				f[j] = f[j-1] + triangle[i][j];
			else
				f[j] = min(f[j-1], f[j]) + triangle[i][j];
		}
	}
	
	// 从辅助数组中找出最小值
	int result;
	result = f[0];
	for (int i = 1; i < f.size(); i++)
		result = min(result, f[i]);
		
	return result;
}

分析这两道题目,发现它们有两个共同的特征:
1.最优子结构:一个问题的最优解包含其子问题的最优解。
2.子问题重叠:一个问题的子问题都是相同的。那么这些子问题可以用同样的方式解决,每次将解决的子问题给记录到表中,在计算之后的问题时查找前面的结果来计算当前问题。这也就是“动态规划”名称的由来了。

在climbing stairs问题中,到达每个位置的方法个数,和之前的所有方法是相关联的。即,到达第n阶台阶的所有的方法个数,同时需要找出第n-1阶台阶的所有的方法以及第n-2阶台阶的所有的方法,以此类推。如果之前的问题找出的不是所有的方法数,那么第n阶台阶找出的结果也不是所有的方法数目。而且,第n阶台阶的求解方式和之前的台阶的求解方式是相同的。

在triangle问题中,每个位置的最小路径和需要知道前一层此位置和下一个位置的最小路径和,如果前一层的结果不是最小路径和,那么此层求出的就不是最小路径和。同样,每层问题的求解方式和之前层问题的求解方式是相同的。

所以,这也就是《算法导论》一书中表述的动态规划的两个特征:
1.最优子结构
2.子问题重叠

参考资料:

1.lintcode
Triangle
Climbing Stairs

2.《算法导论(第三版)》。
第15章动态规划

计算机入门的一点经验和对迷茫的一些分析

最近感觉自己在计算机方面有点入门了,而且恰好前几天和研一的新生聚餐,被问道一些所谓的“经验”方面的问题,所以在这里总结一下在前一个阶段自学计算机的一些尝试,也希望给看到这篇博文的自学计算机方面的人一点参考吧。

首先说明一下,自考研到目前为止,自己看过的书籍(这里所指的看过,是几乎都看完了或者看完至少一大半以上,这样我才能对书做一个评价)。

考研考的是东南大学计算机的自主命题935,科目包括数据结构,计组,操作系统。我用的书是根据统招408来的那三本,即:

同时参考了程杰所作的那本《大话数据结构》,不过当时没敲代码(这点很不对)。当时备考还用过配套的王道的那三本书,就不一一列出了。

复试是C++笔试,用过的书分别是:

之后研一,看过的书分别有:

现在正在开始补数据结构算法方面的内容,看的是《数据结构与算法分析——C语言描述(原书第2版)》

我所经历过的阶段这里也说明一下,如果你也是这些方面的初学者,也许有点参考意义。

  1. 上网搜集资料,查找经验。网上的推荐书籍有一堆,每个方面的书籍都有很多经典之作,比如计算机入门必看CSAPP啦,C语言是K&R啦,C++是《C++Primer》啦,算法必须看《算法导论》啦,SICP绝对是培养编程思维的神书之类的。总之,网上有浩若烟海的经典书籍是必读的。然后,每本书自己都想细读一番。
  2. 自己实践。显然,在本科阶段把上面这些书自己研究一遍还有点可能,但是在研究生这个阶段,有了导师给布置的任务,而且还是初学者,不太可能把这些一一翻阅。于是开始找一条收益较高的方案。网上推荐的是快速入门C++看《Accelerated C++》,我也是从这本书开始重新敲C++代码的。同时快速的翻看了一遍《CSAPP》。
  3. 入门,有了自己的学习方向。这也就是现在了,当然以后的方向可能还有变化,不过确实现在感觉对计算机编程方面自学有了一点感悟了。

如果你也是初学者,我的一些建议是:

  • 看书尽量找国外书籍看,国内的书籍大多数不适合自学。
  • 如果你的基础确实不太多,可以从以下思路考虑:一门编程语言,数据结构和算法,操作系统,计算机网络。当然,这个更多的是针对互联网企业的后台开发岗位吧,确实我对前端和APP开发不了解。
  • 每个方向的书籍两本就好,一般书籍的侧重可能不同,交叉着看能帮助理解。如果书籍太多的话,可能就会脱离自己上机实践了。前期你不可能看完那么多书的。经典书后面的课后习题,尽量做。
  • 编程语言和算法互相学习可能效果更好一点。比如看数据结构的时候用编程语言自己实现一遍,多用一些编程语言的一些知识要点。同时,看到数据结构,算法的时候,可以考虑到lintcode上面刷刷类似的题目。
  • 从网上大神的反馈和校招的情况看,编程能力、算法等基础很重要。

推荐的书籍以及考虑的参考顺序:

编程语言方面,因为我是看的C/C++,所以对JAVA不太懂,不过熟悉哪门语言都是要大量的敲代码,而不仅仅是看书。下面C/C++如果没时间就先看C++吧。看C的话主要是关注指针那块。

  1. 《C程序设计语言(第2版)》K&R那本
  2. 《C和指针》。上面那本书讲的太精炼了,参照这本书可以对C有一个了解
  3. 《Accelerated C++》。这本书最大的好处是把C++很多常用的语法和STL的一些用法给呈现出来了,而不像普通的C++书籍那样按部就班罗列知识点。
  4. 《C++大学教程》。和上面那本书对照着看。

再强调一遍,编程语言练习也就是自己多敲代码才是重要的,不要抱着书看完一遍又看一遍。

数据结构和算法:

  1. 《大话数据结构》,程杰。入门算是不错的书了,有C的代码,自己敲过一遍理解更深。
  2. 《数据结构与算法分析——C语言描述(原书第2版)》。我选这本书是因为它比较薄,上来直接啃《算法导论》我个人感觉有点太难了。

计算机基础书籍:

  1. 《深入理解计算机系统》。这本书入门计算机绝对没问题,包括了操作系统,汇编,硬件,还有网络的一些简单的东西,现在既然硬件那块需求不大,可以暂时不看吧。

我这条路在入门上面绝对能走通,不过每个人选择的书籍可能不同,也不用都照着来。方向大抵如此,同时,给出一个我看过的较全的书单:《程序员必读书单 1.0》。同样,这个书单也是仅作参考,前期你不可能都掌握的。别贪全,前期要把那些常常出现的问题给解决。

同时,再把自己所说的“入门”给定义或者说明一下,给你一个参照,以防你也是初学,而我又太low,把你带坑里。

之前,我敲代码时出错了是照着书上给的代码改自己的代码。有些确实是不懂,有些是感觉进度确实不能太慢,不然容易陷入细节的思考,还有就是时间拉太长了可能会学了后面的忘了前面的。现在,敲代码会自己设置断点改错,能够明白一些C语言的指针方面错误所在了。

简单的说就是:之前是被动输入,现在能主动输入了。即,把一些从前学过的C++、数据结构的知识进行组合,实现一些自己想到的功能,并且改错的时候能想通一些指针的特性了。这样融合起来学习,能够更好的理解书上的知识。

所以我感觉自己入门了。

我博客中前两篇文章的内容是二叉树的实现,本来其实感觉太简单不想贴出来的,不过想想可以给这篇文章做个铺垫。不信你可以对照着看一下,把《二叉树的实现以及相关操作C/C++》中的代码改写成《二叉树类的实现》中的类,就会遇到很多难题。我自己写的时候想避开《C++大学教程》上的一些方式,不过最后还是没避开,用其他方式我实现不了。当然,也许你写的代码会比我的更简洁。

同样,这里给出一个我看过的不错的入门建议,可以参考:如何从只会 C++ 语法的水平到达完成项目编写软件的水平?。我有空也会尝试的。

最后想到昨天有几个新生说迷茫,正好我也借这篇文章谈谈这个话题吧。

迷茫很正常。研一的新生可能因为刚刚开学,环境变了,同时看到以前的同学或者现在这个行业工作的人们工资很高,而自己能力不足,对未来有点担心。同时,可能是有了导师的直接管理而且感觉导师分配的任务和自己想要尝试的事情不太有交集。简单地说,其实迷茫就是对未来或多或少的担忧。

未来谁知道呢?对吧。没发生的总是没发生,谁也不能说自己的努力方向一定正确,自己的愿景一定实现。

仔细观察我们可以发现,除了大学之前我们没有过太多的迷茫感,在高考填志愿那时开始,很多人多少都会对未来有些迷茫了。因为在那之前,我们更多是在既定的轨道被动进行教育的。我们在规定的时间上课,规定的时间放学,规定的时间完成作业,每隔一段时间会被排名,从而评估你的成绩。更重要的是,那个时候我们不用直接为自己的行为负责,因为父母会给我们埋单。大学之后,我们要进行更多的选择,对自己的行为负责。同时,评估人的标准渐渐变得不那么单一了:有的人社团混的很好,人际交往让人羡慕;有的人会玩乐器,乐队在自己学校小有名气;有的人竞赛屡获佳绩,让人自愧不如。这些都会使我们努力的方向迷失,从而感觉迷茫。

现在,可能你迷茫的是一些学习方法。未来,你可能还会迷茫自己的择业,孩子的学校选择,不同城市到底安家到哪,等等。

那么在迷茫的时候,该做些什么呢?

  1. 上网搜集你所想要努力方向的资料,查找经验。
  2. 进行实践。
  3. 将自己的实践和努力的成果进行分析,修正。
  4. 重复进行2,3步。

然后,你也会找到自己的方向的。所以我在开始将我努力的过程给描述了一遍。

这里再分享一个经验:迷茫的最大敌人是拖延。

相信聪明的你,能更快地找到属于自己的那条道路。

二叉树类的实现

最近看数据结构看到二叉树的时候,自己实现了一下,同时写成了类,正好复习一下以前看C++的一些知识。代码如下。

// BiTNode.h
// 参照《c++大学教程》中P639页编写
// 模版结点BiTNode类的声明

#ifndef BITNODE_H
#define BITNODE_H

// 声明BiNTree类型
template<typename NODETYPE> class BiTree;

template<typename NODETYPE>
class BiTNode
{
	// 声明友元BiNTree类,使得BiTree类可以访问BiTNode类中的private成员
	friend class BiTree<NODETYPE>;

public:
	BiTNode(const NODETYPE &d) 
		: lchild(0), 
			data(d),
			rchild(0)
	{
	}

	NODETYPE getData() const
	{
		return data;
	}

private:
	BiTNode<NODETYPE> *lchild;
	NODETYPE data;
	BiTNode<NODETYPE> *rchild;
};

#endif
// BiTree.h
// 链表二叉树类模版的定义

#ifndef BITREE_H
#define BITREE_H

#include <iostream>
#include <iomanip>
#include "BiTNode.h"
#include <queue>
#include <stack>
using namespace std;

typedef int Status;

#define OK	1
#define ERROR	0
#define TRUE	1
#define FALSE	0

template<typename NODETYPE>
class BiTree
{
public:
	BiTree();

	void CreateBiTree();
	void DestroyBiTree();
	Status BiTreeEmpty();
	NODETYPE Root();

	int BiTreeDepth();
	int BiTreeDepthNonRecursion();

	void PreOrderTraverse();
	void PreOrderNonRecursion();
	void InOrderTraverse();
	void InOrderNonRecursion();
	void PostOrderTraverse();
	void PostOrderNonRecursion();
	void LevelOrderTraverse();

	void PrintLast();
	void PrintByDepth();

private:
	BiTNode<NODETYPE> *rootPtr;

	// utility function
	void visit(BiTNode<NODETYPE> *p);
	void CreateBiTreeHelper(BiTNode<NODETYPE> **T);
	void DestroyBiTreeHelper(BiTNode<NODETYPE> **T);
	int BiTreeDepthHelper(BiTNode<NODETYPE> *T);

	// 用helper函数的原因是对二叉树进行遍历要传入参数
	void PreOrderTraverseHelper(BiTNode<NODETYPE> *T);
	void InOrderTraverseHelper(BiTNode<NODETYPE> *T);
	void PostOrderTraverseHelper(BiTNode<NODETYPE> *T);
};

template<typename NODETYPE>
BiTree<NODETYPE>::BiTree()
{
	rootPtr = 0;
}

template<typename NODETYPE>
Status BiTree<NODETYPE>::BiTreeEmpty()
{
	if (rootPtr)
		return FALSE;
	else
		return TRUE;
}

template<typename NODETYPE>
void BiTree<NODETYPE>::CreateBiTree()
{
	CreateBiTreeHelper(&rootPtr);
}

// 按前序输入二叉树中结点的值(一个字符)
// #表示空树,构造二叉链表表示二叉树T。
template<typename NODETYPE>
void BiTree<NODETYPE>::CreateBiTreeHelper(BiTNode<NODETYPE> **T)
{
	NODETYPE val;

	cin >> val;

	if (val == '#')
		*T = NULL;
	else
	{
		*T = new BiTNode<NODETYPE>(val);
		CreateBiTreeHelper(&(*T)->lchild);
		CreateBiTreeHelper(&(*T)->rchild);
	}
}

template<typename NODETYPE>
void BiTree<NODETYPE>::DestroyBiTree()
{
	DestroyBiTreeHelper(&rootPtr);
}

template<typename NODETYPE>
void BiTree<NODETYPE>::DestroyBiTreeHelper(BiTNode<NODETYPE> **T)
{
	if (*T)
	{
		if ((*T)->lchild)
			DestroyBiTreeHelper(&(*T)->lchild);
		if ((*T)->rchild)
			DestroyBiTreeHelper(&(*T)->rchild);
		free(*T);
		*T = NULL;
	}
}

template<typename NODETYPE>
int BiTree<NODETYPE>::BiTreeDepth()
{
	return BiTreeDepthHelper(rootPtr);
}

template<typename NODETYPE>
int BiTree<NODETYPE>::BiTreeDepthHelper(BiTNode<NODETYPE> *T)
{
	int i, j;

	if (!T)
		return 0;

	if (T->lchild)
		i = BiTreeDepthHelper(T->lchild);
	else 
		i = 0;
	if (T->rchild)
		j = BiTreeDepthHelper(T->rchild);
	else
		j = 0;

	return i > j ? i+1 : j+1;
}

template<typename NODETYPE>
NODETYPE BiTree<NODETYPE>::Root()
{
	if (!rootPtr)
		return ' ';
	else
		return rootPtr->data;
}

// 借用层次遍历的思想,实现非递归形式求出二叉树深度
template<typename NODETYPE>
int BiTree<NODETYPE>::BiTreeDepthNonRecursion()
{
	if (!rootPtr)
		return 0;

	BiTNode<NODETYPE> *p; // 工作指针,每次记录从队列队首弹出的结点
	BiTNode<NODETYPE> *back; // 记录每层二叉树的最右边的结点。此结点在每次遍历一层之后的队列队尾
	int level = 0; // 层数,初始值为0
	queue<BiTNode<NODETYPE> *> Q;

	Q.push(rootPtr);
	back = Q.back();
	while (!Q.empty())
	{
		p = Q.front();
		Q.pop();

		if (p->lchild)
			Q.push(p->lchild);
		if (p->rchild)
			Q.push(p->rchild);

		if (p == back) // 如果p == 每层的最右边的结点,则层数+1,同时重新赋值队尾结点
		{
			level++;
			if (!Q.empty()) // 如果队列为空,则下一步的操作出错。主要用于防止最后一个结点弹出队列之后的那次操作
				back = Q.back();
		}
	}

	return level;
}

template<typename NODETYPE>
void BiTree<NODETYPE>::PreOrderTraverse()
{
	PreOrderTraverseHelper(rootPtr);
}

template<typename NODETYPE>
void BiTree<NODETYPE>::PreOrderTraverseHelper(BiTNode<NODETYPE> *T)
{
	if (!T)
		return;

	visit(T);
	PreOrderTraverseHelper(T->lchild);
	PreOrderTraverseHelper(T->rchild);
}

// 前序遍历非递归形式
template<typename NODETYPE>
void BiTree<NODETYPE>::PreOrderNonRecursion()
{
	if (!rootPtr)
		return;

	BiTNode<NODETYPE> *p;
	stack<BiTNode<NODETYPE> *> S; // 借助栈实现非递归的前序遍历

	p = rootPtr;
	while (p || !S.empty())
	{
		while (p) 
		{
			visit(p); // 在每次入栈之前进行访问
			S.push(p);
			p = p->lchild;
		}
		if (!S.empty())
		{
			p = S.top();
			S.pop();
			p = p->rchild;
		}
	}
}

template<typename NODETYPE>
void BiTree<NODETYPE>::InOrderTraverse()
{
	InOrderTraverseHelper(rootPtr);
}

template<typename NODETYPE>
void BiTree<NODETYPE>::InOrderTraverseHelper(BiTNode<NODETYPE> *T)
{
	if (!T)
		return;

	InOrderTraverseHelper(T->lchild);
	visit(T);
	InOrderTraverseHelper(T->rchild);
}

template<typename NODETYPE>
void BiTree<NODETYPE>::InOrderNonRecursion()
{
	if (!rootPtr)
		return;

	BiTNode<NODETYPE> *p;
	stack<BiTNode<NODETYPE> *> S;

	p = rootPtr;
	while (p || !S.empty())
	{
		while (p)
		{
			S.push(p);
			p = p->lchild;
		}
		if (!S.empty())
		{
			p = S.top();
			S.pop();
			visit(p); // 在每次出栈之时进行访问
			p = p->rchild;
		}
	}
}

template<typename NODETYPE>
void BiTree<NODETYPE>::PostOrderTraverse()
{
	PostOrderTraverseHelper(rootPtr);
}

template<typename NODETYPE>
void BiTree<NODETYPE>::PostOrderTraverseHelper(BiTNode<NODETYPE> *T)
{
	if (!T)
		return;

	PostOrderTraverseHelper(T->lchild);
	PostOrderTraverseHelper(T->rchild);
	visit(T);
}

template<typename NODETYPE>
void BiTree<NODETYPE>::PostOrderNonRecursion()
{
	if (!rootPtr)
		return;

	BiTNode<NODETYPE> *p;
	BiTNode<NODETYPE> *r; // 用于记录栈中弹出的结点的右子树是否访问过
	stack<BiTNode<NODETYPE> *> S;

	p = rootPtr;
	r = NULL;
	while (p || !S.empty())
	{
		while (p)
		{
			S.push(p);
			p = p->lchild;
		}
		if (!S.empty())
		{
			p = S.top();
			if (p->rchild && p->rchild != r) // 此结点的右子树尚未入栈
			{
				p = p->rchild;
				S.push(p);
				p = p->lchild;
			}
			else
			{
				S.pop();
				visit(p); // 每次出栈时访问结点
				r = p;
				p = NULL;
			}
		}
	}

}

template<typename NODETYPE>
void BiTree<NODETYPE>::LevelOrderTraverse()
{
	if (!rootPtr)
		return;

	BiTNode<NODETYPE> *p;
	BiTNode<NODETYPE> *back; // 操作中记录队列尾部的指针
	queue<BiTNode<NODETYPE> *> Q; // 使用辅助队列

	Q.push(rootPtr);
	back = Q.back();
	while (!Q.empty())
	{
		p = Q.front();
		Q.pop();
		visit(p);

		if (p->lchild)
			Q.push(p->lchild);
		if (p->rchild)
			Q.push(p->rchild);
	}
}

template<typename NODETYPE>
void BiTree<NODETYPE>::PrintLast()
{
	if (!rootPtr)
		return;

	BiTNode<NODETYPE> *p;
	BiTNode<NODETYPE> *back; // 操作中记录队列尾部的指针
	queue<BiTNode<NODETYPE> *> Q; // 使用辅助队列

	Q.push(rootPtr);
	back = Q.back();
	while (!Q.empty())
	{
		p = Q.front();
		Q.pop();

		if (p->lchild)
			Q.push(p->lchild);
		if (p->rchild)
			Q.push(p->rchild);

		if (p == back)
		{
			visit(p);
			if (!Q.empty())
				back = Q.back(); // 更新back指针的位置
		}
	}
}

template<typename NODETYPE>
void BiTree<NODETYPE>::PrintByDepth()
{
	if (!rootPtr)
		return;

	BiTNode<NODETYPE> *p;
	BiTNode<NODETYPE> *back; // 操作中记录队列尾部的指针
	queue<BiTNode<NODETYPE> *> Q; // 使用辅助队列

	Q.push(rootPtr);
	back = Q.back();
	while (!Q.empty())
	{
		p = Q.front();
		Q.pop();
		visit(p);

		if (p->lchild)
			Q.push(p->lchild);
		if (p->rchild)
			Q.push(p->rchild);

		if (p == back)
		{
			cout << endl;
			if (!Q.empty())
				back = Q.back(); // 更新back指针的位置
		}
	}
}

template<typename NODETYPE>
void BiTree<NODETYPE>::visit(BiTNode<NODETYPE> *p)
{
	cout << left << setw(5) << p->data;
}

#endif

为了省事,main函数有些代码直接使用了前面一篇文章里面c的代码。

// main.h
#include <iostream>
#include "BiTree.h"
using namespace std;

int main()
{
	int i;
	BiTree<char> T;
	char e1;
	
	//StrAssign(str,"ABDH#K###E##CFI###G#J##");

	T.CreateBiTree();

	printf("构造空二叉树后,树空否?%d(1:是 0:否) 树的深度: %d\n",T.BiTreeEmpty(), T.BiTreeDepthNonRecursion());
	e1 = T.Root();
	printf("二叉树的根为: %c\n",e1);

	printf("\n前序遍历二叉树:\n");
	//T.PreOrderTraverse();
	T.PreOrderNonRecursion();

	printf("\n中序遍历二叉树:\n");
	T.InOrderTraverse();
	//T.InOrderNonRecursion();

	printf("\n后序遍历二叉树:\n");
	//T.PostOrderTraverse();
	T.PostOrderNonRecursion();

	printf("\n层次遍历二叉树:\n");
	T.LevelOrderTraverse();

	printf("\n每行二叉树的最右边的结点为:\n");
	T.PrintLast();

	printf("\n按层次输出每行的结点:\n");
	T.PrintByDepth();

	T.DestroyBiTree();
	printf("\n清除二叉树后,树空否?%d(1:是 0:否) 树的深度=%d\n",T.BiTreeEmpty(),T.BiTreeDepth());
	i = T.Root();
	if(!i)
		printf("树空,无根\n");

	getchar();
	getchar();
	return 0;
}

写这个代码的时候,感觉自己计算机编程入门了——之前写代码主要都是照着书写,出错了更多都是照着书查找错误。写这个二叉树类的时候有个地方指针出错了,自己设断点改错,改了很久。所以入门的一些经验在下面一篇文章里面谈谈吧。

参考资料:
1.《大话数据结构》
2.《C++大学教程(第七版)》

二叉树的实现以及相关操作C/C++

夏天看机器学习之余,把C语言给过了一遍,现在开始数据结构的学习了。最近看的二叉树,照着书实现了一下。

其中包括二叉树的一些基本操作:初始化,建立,销毁,判空,深度和几种遍历。因为书上没给出非递归的遍历的非递归形式,自己这边给总结一下。代码本来是用C写的,但是其中有些功能的实现需要用到队列或者栈,直接调用C++的STL了。如下是相关代码。



#include "string.h"
#include "stdio.h"    
#include "stdlib.h"   
#include "math.h"  
#include <queue>
#include <stack>
using namespace std;

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 100 /* 存储空间初始分配量 */

typedef int Status;

typedef char TElemType;
TElemType Nil = ' ';

/* 用于构造二叉树********************************** */
int index=1;
typedef char String[24]; /*  0号单元存放串的长度 */
String str;

Status StrAssign(String T,char *chars)
{ 
	int i;
	if(strlen(chars)>MAXSIZE)
		return ERROR;
	else
	{
		T[0]=strlen(chars);
		for(i=1;i<=T[0];i++)
			T[i]=*(chars+i-1);
		return OK;
	}
}
/* ************************************************ */

typedef struct BiTNode
{
	TElemType data;
	struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

Status InitBiTree(BiTree *T);
void CreateBiTree(BiTree *T);
void DestroyBiTree(BiTree *T);
Status BiTreeEmpty(BiTree T);
TElemType Root(BiTree T);
TElemType Value(BiTree p);
void visit(BiTree T);

int BiTreeDepth(BiTree T);
int BiTreeDepthNonRecursion(BiTree T);
int BiTreeDepthNonRecursion2(BiTree T);

void PreOrderTraverse(BiTree T);
void PreOrderNonRecursion(BiTree T);
void InOrderTraverse(BiTree T);
void InOrderNonRecursion(BiTree T);
void PostOrderTraverse(BiTree T);
void PostOrderNonRecurion(BiTree T);
void LevelOrderTraverse(BiTree T);

void PrintLastInEachLevel(BiTree T);
void PrintLevelOrderByLevel(BiTree T);

int main()
{
	int i;
	BiTree T;
	TElemType e1;
	InitBiTree(&T);
	
	//StrAssign(str,"ABDH#K###E##CFI###G#J##");

	CreateBiTree(&T);

	printf("构造空二叉树后,树空否?%d(1:是 0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepthNonRecursion2(T));
	e1=Root(T);
	printf("二叉树的根为: %c\n",e1);

	printf("\n前序遍历二叉树:\n");
	PreOrderTraverse(T);
	//PreOrderNonRecursion(T);

	printf("\n中序遍历二叉树:\n");
	InOrderTraverse(T);
	//InOrderNonRecursion(T);

	printf("\n后序遍历二叉树:\n");
	PostOrderTraverse(T);
	//PostOrderNonRecurion(T);

	printf("\n层次遍历二叉树:\n");
	//LevelOrderTraverse(T);
	PrintLevelOrderByLevel(T);
	printf("\n输出每层的最后一个结点:\n");
	PrintLastInEachLevel(T);
	
	DestroyBiTree(&T);
	printf("\n清除二叉树后,树空否?%d(1:是 0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
	i=Root(T);
	if(!i)
		printf("树空,无根\n");
	
	getchar();
	getchar();
	return 0;
}

//* 构造空二叉树T */
Status InitBiTree(BiTree *T)
{
	*T = NULL;
	return OK;
}

// 按前序输入二叉树中结点的值(一个字符)
// #表示空树,构造二叉链表表示二叉树T。 
void CreateBiTree(BiTree *T)
{
	TElemType ch;

	scanf("%c", &ch);

	if (ch == '#')
		(*T) = NULL;
	else
	{
		*T = (BiTree)malloc(sizeof(BiTNode));
		if (!*T)
			exit(OVERFLOW);
		(*T)->data = ch;
		CreateBiTree(&(*T)->lchild);
		CreateBiTree(&(*T)->rchild);
	}
}

// 初始条件: 二叉树T存在。操作结果: 销毁二叉树T 
void DestroyBiTree(BiTree *T)
{
	if (*T)
	{
		if ((*T)->lchild)
			DestroyBiTree(&(*T)->lchild);
		if ((*T)->rchild)
			DestroyBiTree(&(*T)->rchild);
		free(*T);
		*T = NULL;
	}
}

// 初始条件:二叉树存在
// 操作结果:若T为空,则返回TRUE;否则返回FALSE
Status BiTreeEmpty(BiTree T)
{
	if (!T)
		return TRUE;
	else
		return FALSE;
}

// 初始条件:二叉树存在
// 操作结果:返回T的根
TElemType Root(BiTree T)
{
	if (!T)
		return Nil;
	else
		return T->data;
}

// 初始条件:节点存在
// 操作结果:输出结点的数据域
void visit(BiTNode *p)
{
	if (p)
		printf("%c ", p->data);
}

// 初始条件:二叉树存在
// 操作结果:返回二叉树深度
// 递归实现
int BiTreeDepth(BiTree T)
{
	if (!T)
		return 0;

	int i, j;

	if (T->lchild)
		i = BiTreeDepth(T->lchild); // 递归求出左子树高度
	else
		i = 0;

	if (T->rchild)
		j = BiTreeDepth(T->rchild); // 递归求出右子树高度
	else
		j = 0;

	return i > j ? i+1 : j+1;
}

// 求二叉树高度的非递归形式
int BiTreeDepthNonRecursion(BiTree T)
{
	if (!T)
		return 0;

	queue<BiTNode *> Q; // 借助队列实现层次遍历,从而求出高度
	BiTNode *p; // 记录队列头部
	BiTNode *back; // 记录队列尾部指针
	int level = 0; // 队列高度

	Q.push(T);
	back = Q.back();
	while (!Q.empty())
	{
		p = Q.front();
		Q.pop();

		if (p->lchild)
			Q.push(p->lchild);
		if (p->rchild)
			Q.push(p->rchild);

		if (p == back)
		{
			level++;
			if (!Q.empty()) // 防止最后Q为空时出错
				back = Q.back();
		}
	}

	return level;
}

// 求二叉树高度的非递归形式
int BiTreeDepthNonRecursion2(BiTree T)
{
	BiTNode *Q[MAXSIZE]; // 借助队列实现层次遍历,从而求出高度。此时用数组实现队列
	int level = 0; // 二叉树高度
	int last = 0; // 每层次最后一个结点
	int front = -1; // 队列头指针
	int rear = -1; // 队列尾指针
	BiTNode *p;

	Q[++rear] = T;
	last = rear;
	while (front < rear) // 队列不空
	{
		p = Q[++front];

		if (p->lchild)
			Q[++rear] = p->lchild;
		if (p->rchild)
			Q[++rear] = p->rchild;

		if (front == last)
		{
			level++;
			if (front < rear)
				last = rear;
		}
	}

	return level;
}

// 初始条件:二叉树存在
// 操作结果:前序遍历二叉树
void PreOrderTraverse(BiTree T)
{
	if (!T)
		return;

	visit(T);
	PreOrderTraverse(T->lchild);
	PreOrderTraverse(T->rchild);
}

// 前序遍历非递归形式
void PreOrderNonRecursion(BiTree T)
{
	if (!T)
		return;

	stack<BiTNode *> S; // 借助栈实现非递归遍历
	BiTNode *p;

	p = T;
	while (p || !S.empty())
	{
		while (p)
		{
			S.push(p);
			visit(p); // 在每次入栈时进行访问
			p = p->lchild;
		}
		if (!S.empty())
		{
			p = S.top(); 
			S.pop();
			p = p->rchild;
		}
	}
}

// 初始条件:二叉树存在
// 操作结果:中序遍历二叉树
void InOrderTraverse(BiTree T)
{
	if (!T)
		return;

	InOrderTraverse(T->lchild);
	visit(T);
	InOrderTraverse(T->rchild);
}

// 中序遍历二叉树非递归形式
void InOrderNonRecursion(BiTree T)
{
	if (!T)
		return;

	stack<BiTNode *> S;
	BiTNode *p;
	
	p = T;
	while (p || !S.empty())
	{
		while (p)
		{
			S.push(p);
			p = p->lchild;
		}
		if (!S.empty())
		{
			p = S.top();
			S.pop();
			visit(p); // 每次从栈中弹出的时候访问结点
			p = p->rchild;
		}
	}
}


// 初始条件:二叉树存在
// 操作结果:后序递归遍历二叉树
void PostOrderTraverse(BiTree T)
{
	if (!T)
		return;

	PostOrderTraverse(T->lchild);
	PostOrderTraverse(T->rchild);
	visit(T);
}

// 后序遍历非递归形式
// 难点是分清栈中弹出根结点时,是从左子树弹出还是右子树弹出。所以使用辅助指针r。
void PostOrderNonRecurion(BiTree T)
{
	if (!T)
		return;

	stack<BiTNode *> S;
	BiTNode *p;
	BiTNode *r; // 用指针r记录最近访问的结点

	p = T;
	r = NULL;
	while (p || !S.empty())
	{
		while (p)
		{
			S.push(p);
			p = p->lchild;
		}
		if (!S.empty())
		{
			p = S.top();
			if (p->rchild && p->rchild != r) // 如果右子树存在,且未访问过
			{
				p = p->rchild;
				S.push(p);
				p = p->lchild;
			}
			else
			{
				S.pop();
				visit(p);
				r = p;
				p = NULL;
			}
		}
	}
}

// 初始条件:二叉树存在
// 操作结果:层次遍历二叉树
void LevelOrderTraverse(BiTree T)
{
	if (!T)
		return;

	queue<BiTNode *> Q; // 借助队列实现层次遍历
	BiTNode *p;

	Q.push(T);
	while (!Q.empty())
	{
		p = Q.front();
		Q.pop();
		visit(p); // 每次弹出的时候访问结点

		if (p->lchild)
			Q.push(p->lchild);
		if (p->rchild)
			Q.push(p->rchild);
	}
}

// 初始条件:二叉树存在
// 操作结果:访问每层二叉树最右边的结点
void PrintLastInEachLevel(BiTree T)
{
	if (!T) // 如果树为空,则返回
		return;

	queue<BiTNode *> Q;
	BiTNode *p;
	BiTNode *back; // 指向每层最后一个结点的指针

	Q.push(T);
	back = Q.back();
	while (!Q.empty())
	{
		p = Q.front();
		Q.pop();

		if (p->lchild)
			Q.push(p->lchild);
		if (p->rchild)
			Q.push(p->rchild);

		if (p == back)
		{
			visit(p);
			if (!Q.empty())
				back = Q.back();
		}
	}
}

// 初始条件:二叉树存在
// 操作结果:分行输出每层二叉树的结点
void PrintLevelOrderByLevel(BiTree T)
{
	if (!T)
		return;

	queue<BiTNode *> Q;
	BiTNode *p;
	BiTNode *back; // 记录每层最右边的结点,从而实现分行输出

	Q.push(T);
	back = Q.back();
	while (!Q.empty())
	{
		p = Q.front();
		Q.pop();
		visit(p);

		if (p->lchild)
			Q.push(p->lchild);
		if (p->rchild)
			Q.push(p->rchild);

		if (p == back)
		{
			putchar('\n');
			if (!Q.empty())
				back = Q.back();
		}
	}
}

本身感觉现在这些在计算机专业里面应该是太基础的东西了,不想贴出来的,但是确实这个算是一个里程碑吧——感觉自己对编程有点入门了。下一篇会把用类实现的二叉树的代码贴上来,之后再写点自学编程上面的一些感悟或者说一些经验吧。

参考资料:

1.《大话数据结构》

顺序单链表插入新节点的一种方法

在学习链表的时候我们都接触过单链表插入新结点的问题。其中有一类就是在顺序链表中插入新节点,并保持链表的递增或者递减性质。

最近看《C和指针》一书中提到了一种方法,我个人感觉不错,并且思想非常好。

这是最常见的思维:

//sll_node.h  
  
typedef struct Node  
{  
    int value;  
    Node *next;  
} Node;  
#include "sll_node.h"  
#include <stdio.h>  
  
#define TRUE    1  
#define FALSE   0  
  
// insertNode:把newValue的值插入到递增排序的链表中,正确返回TRUE,错误返回FALSE  
// rootp是链表的头指针。  
int insertNode(Node **rootp, int newValue)  
{  
    Node *newNode; // 新节点的指针  
    Node *previous; // 当前指针的前一个指针  
    Node *current; // 当前指针  
  
    current = *rootp; // 初始化  
    previous = NULL;  
  
    // 查找插入的位置  
    while (current != NULL && current->value < newValue)
    {
        previous = current;
        current = current->next;
    }
  
    // 给新节点分配空间  
    newNode = (Node *)malloc(sizeof(Node));  
    if (newNode == NULL)  
        return FALSE;  
    newNode->value = newValue;  
  
    // 更改新节点的前驱和后继节点  
    newNode->next = current;  
    if (previous == NULL) // 此时插入节点的为链表中第一个节点,修改头指针  
        *rootp = newNode;  
    else  
        previous->next = newNode;

    return TRUE;
}

我以前编写的时候也会用这样的方法:一个当前指针和指向当前指针之前的指针,这样需要讨论原链表是否为空。书中提到了一种抽象,每次插入新的节点,都是改变一个指向这个新节点的指针以及指向下一个节点,这样可以省略讨论插入的节点是否为第一个节点的步骤。代码如下:

#include "sll_node.h"
#include <stdio.h>

#define	FALSE	0
#define TRUE	1

// insertNode2:把newValue的值插入到递增排序的链表中,正确返回TRUE,错误返回FALSE
// nextp是指向当前节点的指针,最初是头指针
int insertNode2(Node **nextp, int newValue)
{
	Node *newNode; // 新节点指针
	Node *current; // 当前节点指针

	current = *nextp; // 最初当前节点为nextp指针指向的节点
	// 查找新插入节点的位置
	while (current != NULL && current->value < newValue)
	{
		nextp = &current->next;
		current = current->next;
	}

	// 为新节点分配内存
	newNode = (Node *)malloc(sizeof(Node));
	if (newNode == NULL)
		return FALSE;
	newNode->value = newValue;

	// 统一了插入的步骤。即:每次插入,都是前一个指针指向新节点,新节点指向下一个节点
	*nextp = newNode;
	newNode->next = current;

	return TRUE;
}

main函数

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "sll_node.h"

int insertNode(Node **rootp, int newValue);
int insertNode2(Node **nextp, int newValue);

int main()
{
	srand(time(0));

	Node *head = (Node *)malloc(sizeof(Node));
	head->next = NULL;

	for (int i = 0; i < 5; i++)
	{
		int temp = rand() % 50;
		printf("%d\n", temp);
		//insertNode(&head,temp);
		insertNode2(&head,temp);
	}
	
	Node *p = head->next;
	while (p != NULL)
	{
		printf("%d\n", p->value);
		p = p->next;
	}

	getchar();
	getchar();
	return 0;
}

因为我个人没有经过正经的课堂训练,自己考研才接触编程、数据结构之类的。看了很多对自学编程提的建议都是多编写,并且要有抽象的思想,所以将这个方法写了下来,可能对很对科班出身的人不算什么问题了吧。

我感觉这个抽象很好,希望是给自己编程道路的一个好的开端吧:)

同时,因为我在初学时发现测试代码也会花费很多时间,所以将完成的代码都贴了上来,而不仅仅是函数,希望也能帮助到更多的想我这样的初学者吧。