多任务下的数据结构与算法

2006-4  

华中科技  

周伟明  

380  

无  

本书和传统同类书籍的区别是除了介绍基本的数据结构容器如栈、队列、链表、树、二叉树、红黑树、AVL树和图之外，引进了多任务；还介绍了将任意数据结构容器变成支持多任务的方法；另外，还增加了复合数据结构和动态数据结构等新内容的介绍。在复合数据结构中不仅介绍了哈希链表、哈希红黑树、哈希AVL树等容器，还介绍了复合数据结构的通用设计方法；在动态数据结构中主要介绍了动态环形队列、动态等尺寸内存管理算法。在内存管理中介绍了在应用程序层实现的内存垃圾回收算法、内存泄漏检查和内存越界检查的方法等。本书选取的内容均侧重于在实际中有广泛应用的数据结构和算法，有很好的商业使用价值。 本书大部分章节中都列举并介绍了应用实例，如用AVL树等容器实现的搜索引擎、用数组实现HOOK管理、用链表实现的短信息系统中的CACHE管理、用哈希表实现WebServer中的CACHE文件管理和用哈希AVL树实现抗DoS／DDoS攻击等。 书中重点介绍了软件的各种质量特性如时间效率和空间效率之间的关系，介绍了如何在各种质量特性间取得均衡的原则，并介绍了各种数据结构算法的应用场合和范围。 本书介绍的所有数据结构及算法都以不同复杂程度给出其编码实现。为了便于读者自学，每章末附有小结和思考练习题。 本书可供高校计算机及相关专业作为教学参考书，对从事软件开发与应用的科研人员、工程技术人员以及其他相关人员也具有较高的参考价值。

周伟明，作者有较丰富的实践经验，曾工作于美国加州的DASCOM Inc公司（现为IBM的全资子公司）和国内某大型电信设备研发公司等各名企业，一直从事网络安全软件、网络服务器软件，机器翻译软件、工作软件、嵌入式系统软件等研发工作，亲自写过的源代码愈40万行。

1 绪论 　1.1 引言　1.2 C语言编程常见问题分析　　1.2.1 参数校验问题　　1.2.2 return语句的问题　　1.2.3 while循环和for循环的问题　　1.2.4 if语句的多个判断问题　　1.2.5 goto语句问题　　1.2.6 switch…case和if…elseif的效率区别　1.3 任意数据类型处理　　1.3.1 任意数据类型处理的设计方法　　1.3.2 任意数据类型处理的实例　　1.3.3 任意数据类型处理的回调函数封装　1.4 多任务介绍　　1.4.1 多任务简介　　1.4.2 锁的概念　　1.4.3 Windows下常用多任务操作函数　　1.4.4 Linux/Unix下常用多任务操作函数　　1.4.5 VxWorks下常用多任务操作函数　　1.4.6 多任务函数的封装　1.5 软件设计简介　　1.5.1 软件设计历史简述　　1.5.2 微观设计学原理简介2 数组　2.1 栈　　2.1.1 栈的基本概念　　2.1.2 栈的编码实现　　2.1.3 多任务栈的实现　2.2 队列　　2.2.1 队列的基本概念和接口　　2.2.2 环形队列（Queue）　　2.2.3 STL中的动态队列（STL∷deque）　　2.2.4 动态环形队列 　　2.2.5 各种队列的时间效率测试及分析 　　2.2.6 各种队列的适用范围 　　2.2.7 关于时间效率和空间效率的原则　2.3 排序表　　2.3.1 排序算法介绍 　　2.3.2 快速排序算法　　2.3.3 排序表的设计　　2.3.4 非递归的快速排序算法　　2.3.5 快速排序算法的复杂度分析　　2.3.6 二分查找算法　2.4 实例：HOOK管理功能的实现　　2.4.1 单个函数的HOOK实现　　2.4.2 多个函数的HOOK实现　　2.4.3 HOOK功能的应用简介　　2.4.4 HOOK使用的注意事项 　本章小结　习题与思考 3 链表　3.1 单向链表　　3.1.1 单向链表的存储表示　　3.1.2 单向链表的接口设计　　3.1.3 单向链表的基本功能编码实现　3.2 单向链表的逐个节点遍历　　3.2.1 单向链表逐个节点遍历基本概念　　3.2.2 单向链表逐个节点遍历编码实现　3.3 单向链表的排序　　3.3.1 插入排序　　3.3.2 归并插入排序 　　3.3.3 基数排序 　3.4 双向链表 　　3.4.1 双向链表的基本概念　　3.4.2 双向链表的设计　　3.4.3 双向链表的编码实现　3.5 使用整块内存的链表　　3.5.1 整块内存链表的基本概念 　　3.5.2 整块内存链表的编码实现　3.6 实例：使用链表管理短信息系统的CACHE 　　3.6.1 短信息系统的CACHE管理基本概念　　3.6.2 短信息系统的发送和接收分析 　　3.6.3 短信息系统CACHE管理的编码实现 　本章小结　习题与思考4 哈希表5 树6 复合二叉树7 图8 多任务算法9 内存管理算法附 参考答案

书评`

无

多任务下的数据结构与算法 PDF格式下载

我买了一本,最近不小心把书掉到公交车上忘记拿了,准备还买一本，书中代码看起很舒服这书不适合处学者,本书每一章有个应用实例，如搜索引擎、用数组实现HOOK管理、用链表实现的短信息系统中的CACHE管理、用哈希表实现WebServer中的CACHE文件管理和用哈希AVL树实现抗DoS/DDoS攻击等。这本书的主题虽然是被无数次重复过的数据结构和算法，但是由于加了一个“多任务”的帽子，就焕发出了光芒。多核时代已经到来，所以我们过去的很多经验都需要刷新了。这本书的作者显然在这方面有很丰富的经验，书中从多任务的观点出发，针对很多传统的数据结构和算法设计都作了探讨。比如提到STL中传统的iterator在多任务情况下要么会出错，要么会导致分时效率低下，并且给出一个新的iterator，以适应多任务的要求。可见确实是经验之谈。不过最令我感到震动的，是这位作者对COM的严厉批判。说实话，我见过抱怨COM难用的，我自己也经常抱怨COM不好理解，但从来没见过对COM持否定和严厉批判态度的。这位作者在他的书中这样写道：“对于模板库，或者任何一种技术，都得看应用的场合。其实，任何一种思想和方法的滥用都会导致严重的后果。就像设计模式的滥用一样。例如，COM的滥用导致现在软件质量的严重下降。COM的设计可以说是软件史上最严重的一次设计失误，COM的设计违反了软件设计的基本原理，但就这样一个设计居然被推广到整个业界使用，造成的危害实在太大了。我们可以看到，很多常用的软件的BUG越来越多，动不动就死掉或要求发送错误报告什么的，很多情况估计都是拜COM所赐。虽然微软现在再也不敢提COM了，但它的副作用短期内仍然难以消除，特别是在中国，谈到设计时很多人现在还在言必称组件。”（1.1节）“即使是一些著名大公司开发的软件依然达不到很高的质量，经常出现版本升级越高BUG越多的情况。也许有人会问，这不是在危言耸听吧？其实读者只要看看自己手头经常在用的操作系统和办公软件就知道为什么说这句话了。”（1.5节）“像前面提到的COM一样，实际上是一种设计模式，但是被不加限制地推广给用户使用，而大部分用户的水平还没有上升到懂得在什么情况下该使用什么设计模式那么高的层次，后果便是设计模式被滥用，于是我们看到大型软件的质量是越来越糟糕。”（1.5节）坦率的说，我对于作者的观点是不赞成的，我手上没有证据表明是COM导致了微软软件质量的下降（真的下降了吗？至少我不觉得今天的Word2003比10年前的Word95更容易崩溃。）。不过我赞赏这位作者敢于说出自己真实想法的勇气。因为怕得罪人，或者怕被人拍扳转，而不敢把自己的想法说出来，是我们中国开发者的一个毛病。对什么事情有了看法，敢于说出来，而且敢于写在正式发表的文章和图书里面，这在今天是需要勇气的。只有勇于提出异议，才能够引起争论，加强认识。也许，你揭穿的真的就是狗皮膏药，皇帝的新衣。可惜的是，作者在做出一些论断的时候，并没有给出确凿的论据。也许是因为这本书的主题并不是“组件技术批判”，不宜离题太远吧。不过我很希望作者有机会能把自己的观点系统地阐述一番，并且产生一些争论。不管怎样，这对于提升大家的认识还是大有好处的。也希望听到其他朋友对于COM以及这位作者的观点讲出自己的看法。

虽然跟《多核计算与程序设计》中的内容有些重叠，但讲的比较细，把各种数据结构讲的很明白。

这是一本讲数据结构的好书，里面有很多代码举例，值得推荐

个人研发读研做了好几年，感觉这本书，是作者用心写的，算法编程角度读者必有收益

算法设计不错，很适合想提高水平的程序员。

作者写的挺详细的，目前正在阅读中，感觉比学校的所谓的教科书好多了

喜欢看"著"的书，这样的书很好，这是作者用心写的书，当然，不太适合初学者，需要有一些编程的功底，不过，也可以拿来提高一下素养。

印刷不错，还没来得及看，期待中。

对于初学者和资深程序员，或者是系统分析专家，都是很不错的选择，需要细细品位。

作者心血之作，值得一看

为什么每次买的书书面都脏兮兮的？？

收藏了很久，发现降价了，立刻下单。当当很给力。

很好，需要有些基础的人看

写的不错的一本书，和市面上泛滥的算法图书相比，给人耳目一新的感觉，个人认为不是很适合初学者

书不错，作者的经验写实，有参考价值，希望多一点这样的书出来。

书的印刷不错，不过最近买书太多，内容还没仔细看

书已收到，是正版的。总打来说不错，就是边边角角有些脏、有些干胶。。。

说句实话，是看着一起买便宜才买的

如果是有经验的程序员，还是可以发现里面还是有些隐藏的bug的，这点确实是遗憾

数据结构方面的书，值得一看、

看了第一章，有点兴趣，估计不错