根据嵌入式系统软件设计需要的“数据结构”知识编写而成。书中基本内容有:常用线性数据结构在嵌入式系统中的实现和相关算法;树和图在嵌入式系统中的实现和相关算法;排序和查找算法等。
本书从嵌入式系统的实际硬件环境出发,用通俗易懂的语言代替枯燥难懂的理论解释,结合嵌入式系统的应用实例,使读者在比较轻松的条件下将“数据结构”的基本知识学到手。
本书可作为从事嵌入式系统软件设计的电子技术人员自学“数据结构”的教材,也可供高等院校电子技术类专业本科生、研究生作为教学参考书。

第1章 概述
11.1 数据结构的基本概念1
1.1.1 数据和信息1
1.1.2 数据元素1
1.1.3 数据对象2
1.1.4 数据结构2
1.2 逻辑结构2
1.2.1 线性结构2
1.2.2 树形结构3
1.2.3 图状或网状结构3
1.2.4 纯集合结构4
1.3 存储结构4
1.3.1 顺序存储4
1.3.2 链状存储4
1.3.3 索引存储5
1.3.4 散列存储6
1.4 算法7
1.4.1 算法的描述7
1.4.2 算法的特征8
1.4.3 算法的评价10
1.4.4 算法效率的衡量方法 11
1.4.5 算法的存储空间需求12
1.5 嵌入式系统软件中数据结构的特点13

第2章 线性表14
2.1 线性表的定义14
2.1.1 线性表的逻辑结构定义14
2.1.2 线性表的运算15
2.2 顺序表15
2.2.1 顺序表的定义16
2.2.2 顺序表上的基本运算16
2.3 链表22
2.3.1 单链表22
2.3.2 循环链表35
2.3.3 双链表36
2.4 线性表的应用实例39

第3章 队列44
3.1 队列的定义44
3.1.1 队列的逻辑结构定义44
3.1.2 队列的基本运算44
3.2 循环队列45
3.2.1 顺序队列45
3.2.2 循环队列的概念47
3.2.3 循环队列的运算48
3.3 链队列51
3.3.1 链队列的定义51
3.3.2 链队列的基本运算52
3.4 队列的应用实例57

第4章 堆栈60
4.1 堆栈的定义60
4.1.1 堆栈的逻辑结构定义60
4.1.2 堆栈的基本运算60
4.2 堆栈的使用61
4.2.1 顺序栈61
4.2.2 链栈65
4.3 堆栈的应用实例69

第5章 串73
5.1 串的定义73
5.1.1 串的基本概念73
5.1.2 串的存储结构74
5.2 串的主要操作76
5.3 串的应用实例85

第6章 数组86
6.1 数组的定义86
6.1.1 N维数组的定义86
6.1.2 数组的存储方式87
6.1.3 数组元素的寻址88
6.2 稀疏矩阵的压缩存储89
6.2.1 三元组顺序表90
6.2.2 十字链表93
6.3 稀疏矩阵运算的上机体验96
6.4 数组的应用实例100

第7章 树与二叉树104
7.1 树的定义104
7.1.1 树的逻辑结构定义104
7.1.2 树的逻辑表示105
7.1.3 树的基本术语106
7.2 二叉树的定义106
7.2.1 二叉树的逻辑结构定义106
7.2.2 二叉树的性质108
7.3 二叉树的遍历108
7.3.1 二叉树的存储结构108
7.3.2 二叉链表的生成与输出110
7.3.3 遍历二叉树112
7.3.4 上机体验119
7.4 树的应用实例120

第8章 图124
8.1 图的定义124
8.1.1 图的逻辑结构定义1248.1.2 图的基本术语124
8.2 图的储存126
8.2.1 邻接矩阵存储126
8.2.2 邻接表存储128
8.3 图的遍历129
8.3.1 深度优先搜索遍历129
8.3.2 广度优先搜索遍历131
8.3.3 上机体验132
8.4 图的*小生成树134
8.4.1 生成树与*小生成树1348.4.2 普里姆算法134
8.4.3 克鲁斯卡尔算法138
8.4.4 上机体验140
8.5 *短路径141
8.5.1 路径的概念141
8.5.2 从一个顶点到其余各顶点的*短路径142
8.5.3 每对顶点之间的*短路径145
8.5.4 上机体验148
8.6 图的应用实例149

第9章 排序150
9.1 插入排序150
9.1.1 排序原理150
9.1.2 程序设计151
9.1.3 算法分析1539.2 选择排序153
9.2.1 排序原理153
9.2.2 程序设计154
9.2.3 算法分析155
9.3 冒泡排序156
9.3.1 排序原理156
9.3.2 程序设计1579.3.3 算法分析158
9.4 排序操作上机体验159
9.5 排序方法的选择162
9.6 排序的应用实例163

第10章 查找167
10.1 顺序查找167
10.2 折半查找167
10.3 索引查找16910.4 查找操作上机体验171
10.5 查找的应用实例174
参考文献176
……

嵌入式系统在各行各业的应用越来越广,我国从事嵌入式系统开发的人员也越来越多,从我国主要的几种电子杂志上可以看出,有关嵌入式系统应用的文章也越来越多。
在开发一种嵌入式系统产品时,主要工作是做两方面的设计:硬件设计和软件设计。在硬件设计方面,各个半导体公司竞相推出各种高性能、低功耗、低成本的CPU和外围芯片,这使我们在进行硬件设计时可以很快地得到*先进的芯片。在这种情况下,硬件设计的外部条件越来越好,集成度越来越高,在实现相同功能的情况下线路越来越简化。在软件设计方面,虽然开发工具和程序设计语言也在不断提高,但技术人员本身的软件素质无疑起决定作用。因此,软件设计水平在嵌入式系统产品开发的过程中占有重要的地位,直接影响到产品的功能和竞争能力。我国目前绝大多数从事嵌入式系统开发的技术人员基本上不是计算机专业毕业的,有的可能没有上过大学,他们未接受过系统的软件基础理论教育,软件设计水平仍不太高。在软件开发过程中,他们只是不自觉地采用了一些规律性的设计方法,或者模仿别人的程序设计方法,而有更多成熟的基本方法没有被掌握,开发出来的软件水平不高,致使产品的功能和可靠性受到一定的制约。
软件设计是一门科学,有其自身的规律,也有很多成熟的理论和算法。要学习就要选教材,而目前能选到的软件方面的教材都是专为计算机专业编写的教材。这些教材起点较高,偏重理论叙述,未考虑嵌入式系统的硬件特点,对于广大嵌入式系统开发人员来说不是十分适合,学起来会感到比较抽象和吃力。
出于提高我国广大嵌入式系统开发人员软件素质的愿望,我们决定编写一本适合自学软件理论基础“数据结构”的书。该书起点要求不高,只要掌握C语言并已从事了一段时间嵌入式系统开发工作的人员就可以看懂。学完本书后,对软件设计的主要基础理论“数据结构”就能初步掌握,在进行软件设计时,可以减少很多盲目性,并为更系统、更深入地学习其他计算机软件设计理论打下良好基础。
本书第1章介绍数据结构的基本概念;第2章介绍线性表的知识和应用;第3章介绍队列的知识和应用;第4章介绍堆栈的知识和应用;第5章介绍串的知识和应用;第6章介绍数组的知识和应用;第7章介绍树的知识和应用;第8章介绍图的知识和应用;第9章介绍排序的知识和应用;第10章介绍查找的知识和应用。在编写过程中,我们的原则是:尽量结合嵌入式系统的应用实例,采用通俗易懂的叙述方式,介绍*基本的核心内容。
陆玲编写了本书第1~8章的内容,周航慈编写第9章、第10章和前8章的应用实例。周航慈负责全书的策划、内容安排、文稿修改和审定。
在本书的编写过程中,得到北京航空航天大学出版社的大力支持,何立民教授给予了无私的帮助,在此表示衷心感谢!周立功先生在本书的策划过程中起了很大促进作用,在此也表示衷心感谢!
由于水平有限,书中错误及不足之处敬请广大读者予以指正,不胜感谢!