文档章节

Head First C学习日志 第六章 最高机密 二叉树和valgrind工具

AlexTuan
 AlexTuan
发布于 2016/02/23 23:13
字数 1598
阅读 59
收藏 2

程序会从根节点开始提问,其左右子树为疑犯名字或另外一个问题。先看数据结构:

typedef struct node {
	char *question;
	struct node *no;
	struct node *yes;
} node;

一个递归结构,内容很简单,一个char*指针,两个node指针。

节点的创建函数:

node *create(char *question) {
	node *n = malloc(sizeof(node));
	n->question = strdup(question);
	n->no = NULL;
	n->yes = NULL;
	return n;
}

先分配空间,然后拷贝question字符串常量,两个node指针置空。

节点的销毁函数:

void release(node *n) {
	if (n) {
		if (n->no)
			release(n->no);
		if (n->yes)
			release(n->yes);
		if (n->question)
			free(n->question);
		free(n);
	}
}

从输入节点开始遍历,递归销毁其子树,释放n->question字符串,最后释放n。

一个通用的判断输入y/n的函数:

int yes_no(char *question) {
	char answer[3];
	printf("%s? (y/n):", question);
	fgets(answer, 3, stdin);
	if (answer[sizeof(answer) - 1] == '\n')
		answer[sizeof(answer) - 1] = 0;
	return answer[0] == 'y';
}

如果输入y返回1,输入其他字符返回0。

以上代码比较简单,二叉树的创建主要在主要在主函数里。

这段代码比较长,分开贴:

char question[80];
	char suspect[20];
	node *start_node = create("Does suspect have a mustache");
	start_node->no = create("Loretta Barnsworth");
	start_node->yes = create("Vinny the Spoon");

	node *current;

创建接收用户输入的question和suspect字符串。

创建根节点,并初始化一个问题,“疑犯有胡子么”。

将根节点的两个子树初始化为“Loretta Barnworth”和“Vinny the Spoon”。

定义一个current指针,用做活动指针,连接二叉树。

外层循环:

do {
}while(yes_no("Run again"));

至少执行一次,如果用户在yes_no函数输入y,则重复执行。

循环体:

current = start_node;
		while (1) {
		......
		}

将current指向起始节点,并执行while(1)循环的内容,一个if else条件判断,第一个if:

if (yes_no(current->question)) {
				if (current->yes)
					current = current->yes;
				else {
					printf("SUSPECT IDENTIFIED\n");
					break;
				}
			}

yes_no打印问题(或疑犯名)并要求用户输入,如果用户选择y,则进入子条件判断:当前节点current->yes是否存在,如果存在,将current=current->next,会进入下一次循环,如果不存在current->yes,则表示当前节点就是疑犯节点(疑犯节点没有子树),输出“SUSPECT IDENTIFIED”,跳出本层循环

下一个条件,如果用户在yes_no时输入了n(本文中不输入y一律认为输入n)

else if (current->no) {
				current = current->no;
			}

判断该节点是否存在no子树,如果存在,将current=current->no,进入下一次循环。

最后一个条件,在yes_no()时输入了n,但是又没有no子树,表示我们已存在的数据中,并没有我们想定位的疑犯信息,那么会进入新建步骤:

else {
				/*Make the yes-node the new suspect name*/
				printf("Who's the suspect? ");
				fgets(suspect, 20, stdin);
				if (suspect[sizeof(suspect) - 1] == '\n')
					suspect[sizeof(suspect) - 1] = 0;
				node *yes_node = create(suspect);
				current->yes = yes_node;
				/*Make the no-node a copy of this question*/
				node *no_node = create(current->question);
				current->no = no_node;
				/*The replace this question with the new question*/
				printf("Give me a question that is TRUE for %s but not for %s ", suspect, current->question);
				fgets(question, 80, stdin);
				if (question[sizeof(question) - 1] == '\n')
					question[sizeof(question) - 1] = 0;
				/*while replacing,the old block for 'question' must be freed*/
				current->question = strdup(question);
				break;
			}

程序输出:“Who's the suspect?”

输入疑犯名字,然后进行以下几步操作:

  1. 创建一个新节点(疑犯节点)yes_node

  2. 将当前节点(疑犯节点)current->yes=yes_node

  3. 创建一个新节点(疑犯节点),与当前节点问题(实际上是疑犯名)相同,no_node,并将当前节点的current->no=no_node;注意,此时有两个节点的question(疑犯名)相同,当前节点和以当前节点疑犯名命名的新节点。

  4. 输入一个新问题,对你给出的新疑犯是true,对当前节点的老疑犯为false

  5. 将当前节点的current->question(疑犯名)指向你新输入的question的拷贝,strdup(question)。

程序最后release(start_node),销毁整个二叉树。

第一部分,二叉树的动态创建到此为止,接下来是用valgrind检查内存泄漏。


用valgrind检查内存泄漏:

安装valgrind:brew install valgrind 就这么简单,强烈安利homebrew。

使用valgrind检查:输入命令 valgrind --leak-check=full ./spies

➜  spies valgrind --leak-check=full ./spies
==1165== Memcheck, a memory error detector
==1165== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==1165== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
==1165== Command: ./spies
==1165==
Does suspect have a mustache? (y/n):n
Loretta Barnsworth? (y/n):n
Who's the suspect? Johnny
==1165== Conditional jump or move depends on uninitialised value(s)
==1165==    at 0x100000D62: main (in ./spies)
==1165==
Give me a question that is TRUE for Johnny
 but not for Loretta Barnsworth He burns
==1165== Conditional jump or move depends on uninitialised value(s)
==1165==    at 0x100000E01: main (in ./spies)
==1165==
Run again? (y/n):n

注意一定要对初始化后的子树做一些改动才能复现。

结果:

==1165==
==1165== HEAP SUMMARY:
==1165==     in use at exit: 42,915 bytes in 420 blocks
==1165==   total heap usage: 530 allocs, 110 frees, 50,093 bytes allocated
==1165==
==1165== 19 bytes in 1 blocks are definitely lost in loss record 8 of 82
==1165==    at 0x100008EBB: malloc (in /usr/local/Cellar/valgrind/3.11.0/lib/valgrind/vgpreload_memcheck-amd64-darwin.so)
==1165==    by 0x1001ECDDE: strdup (in /usr/lib/system/libsystem_c.dylib)
==1165==    by 0x100000B57: create (in ./spies)
==1165==    by 0x100000C61: main (in ./spies)
==1165==
==1165== LEAK SUMMARY:
==1165==    definitely lost: 19 bytes in 1 blocks
==1165==    indirectly lost: 0 bytes in 0 blocks
==1165==      possibly lost: 0 bytes in 0 blocks
==1165==    still reachable: 4,096 bytes in 1 blocks
==1165==         suppressed: 38,800 bytes in 418 blocks
==1165== Reachable blocks (those to which a pointer was found) are not shown.
==1165== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==1165==
==1165== For counts of detected and suppressed errors, rerun with: -v
==1165== Use --track-origins=yes to see where uninitialised values come from
==1165== ERROR SUMMARY: 3 errors from 3 contexts (suppressed: 16 from 16)

导致内存泄漏的函数给我们列举出来了,书中给的例子里结果中有行号,可是用的版本没有,只有检查这些函数在程序中的调用及其上下文

按照书中的解释,第一次不对二叉树作改动的情况下,并没有出现内存泄漏,因此create函数没有问题,这也是一种定位方法,控制可变量。

问题出在current->question = strdup(question);因为在这步之前,current->question是不为空的,它已经指向了某块堆内存,现在给它新赋值,那块内存就找不到了。所以我们要在current->question = strdup(question)之前,先free(current->question)。

© 著作权归作者所有

AlexTuan
粉丝 4
博文 27
码字总数 17966
作品 0
程序员
私信 提问
敏捷教练成长记:寒风凛冽第七周

这是第七周,话不多说,继续坚持。 上周计划完成情况 1、敏捷方面读不少于50页的书或者文章。 - 精读《Scrum精髓》第三章和前言,大概45页。 2、实践方面-有点偏离计划 - 修改几个故障单。 ...

转型实践者
2017/12/17
0
0
最全BAT算法面试130题:阿里、百度、腾讯、京东、美团、今日头条

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/t4i2b10X4c22nF6A/article/details/86133621 【百度、阿里、腾讯、京东、美团、今日头条】等公司都会必考关于...

JAVA高级架构v
01/09
0
0
最全BAT算法面试100题:阿里、百度、腾讯、京东、美团、今日头条

第一:复杂度估算和排序算法(上) 1) 时间复杂度和空间复杂度 2)认识对数器 3)冒泡排序 4)选择排序 5)插入排序 6)如何分析递归过程的时间复杂度 7)归并排序 8)小和问题 第二:复杂度...

编程SHA
04/25
72
0
valgrind安装及使用方法详解

Valgrind manual: http://valgrind.org/docs/manual/manual.html valgrind介绍: l Valgrind查找内存泄露利器 Valgrind是一个GPL的软件,用于Linux(For x86, amd64 and ppc32)程序的内存调......

shzwork
05/14
8
0
linux c 内存泄露检测工具valgrind

Linux c/c++上常用内存泄露检测工具有valgrind, Rational purify。Valgrind免费。Valgrind 可以在 32 位或 64 位 PowerPC/Linux 内核上工作。 Valgrind工具包包含多个工具,如Memcheck,Cach...

悬崖
2014/08/29
184
0

没有更多内容

加载失败,请刷新页面

加载更多

nginx学习笔记

中间件位于客户机/ 服务器的操作系统之上,管理计算机资源和网络通讯。 是连接两个独立应用程序或独立系统的软件。 web请求通过中间件可以直接调用操作系统,也可以经过中间件把请求分发到多...

码农实战
今天
5
0
Spring Security 实战干货:玩转自定义登录

1. 前言 前面的关于 Spring Security 相关的文章只是一个预热。为了接下来更好的实战,如果你错过了请从 Spring Security 实战系列 开始。安全访问的第一步就是认证(Authentication),认证...

码农小胖哥
今天
13
0
JAVA 实现雪花算法生成唯一订单号工具类

import lombok.SneakyThrows;import lombok.extern.slf4j.Slf4j;import java.util.Calendar;/** * Default distributed primary key generator. * * <p> * Use snowflake......

huangkejie
昨天
13
0
PhotoShop 色调:RGB/CMYK 颜色模式

一·、 RGB : 三原色:红绿蓝 1.通道:通道中的红绿蓝通道分别对应的是红绿蓝三种原色(RGB)的显示范围 1.差值模式能模拟三种原色叠加之后的效果 2.添加-颜色曲线:调整图像RGB颜色----R色增强...

东方墨天
昨天
11
1
将博客搬至CSDN

将博客搬至CSDN

算法与编程之美
昨天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部