嵌入式系统软件设计中的数据结构

根据嵌入式系统软件设计需要的“数据结构”知识编写而成。书中基本内容有：常用线性数据结构在嵌入式系统中的实现和相关算法；树和图在嵌入式系统中的实现和相关算法；排序和查找算法等。本书从嵌入式系统的实际硬件环境出发，用通俗易懂的语言代替枯燥难懂的理论解释，结合嵌入式系统的应用实例，使读者在比较轻松的条件下将“数据结构”的基本知识学到手。本书可作为从事嵌入式系统软件设计的电子技术人员自学“数据结构”的教材，也可供高等院校电子技术类专业本科生、研究生作为教学参考书。 目 录第1 章 概述11.1 数据结构的基本概念11.1.1 数据和信息11.1.2 数据元素11.1.3 数据对象21.1.4 数据结构21.2 逻辑结构21.2.1 线性结构21.2.2 树形结构31.2.3 图状或网状结构31.2.4 纯集合结构41.3 存储结构41.3.1 顺序存储41.3.2 链状存储41.3.3 索引存储51.3.4 散列存储61.4 算法71.4.1 算法的描述71.4.2 算法的特征81.4.3 算法的评价101.4.4 算法效率的衡量方法 111.4.5 算法的存储空间需求121.5 嵌入式系统软件中数据结构的特点13第2 章 线性表142.1 线性表的定义142.1.1 线性表的逻辑结构定义142.1.2 线性表的运算152.2 顺序表152.2.1 顺序表的定义162.2.2 顺序表上的基本运算162.3 链表222.3.1 单链表222.3.2 循环链表352.3.3 双链表362.4 线性表的应用实例39第3 章 队列443.1 队列的定义443.1.1 队列的逻辑结构定义443.1.2 队列的基本运算443.2 循环队列453.2.1 顺序队列453.2.2 循环队列的概念47 3.2.3 循环队列的运算483.3 链队列513.3.1 链队列的定义513.3.2 链队列的基本运算523.4 队列的应用实例57第4 章 堆栈604.1 堆栈的定义604.1.1 堆栈的逻辑结构定义604.1.2 堆栈的基本运算604.2 堆栈的使用614.2.1 顺序栈614.2.2 链栈654.3 堆栈的应用实例69第5 章 串735.1 串的定义735.1.1 串的基本概念735.1.2 串的存储结构745.2 串的主要操作765.3 串的应用实例85第6 章 数组866.1 数组的定义866.1.1 N 维数组的定义866.1.2 数组的存储方式876.1.3 数组元素的寻址886.2 稀疏矩阵的压缩存储896.2.1 三元组顺序表906.2.2 十字链表936.3 稀疏矩阵运算的上机体验966.4 数组的应用实例100第7 章 树与二叉树1047.1 树的定义1047.1.1 树的逻辑结构定义1047.1.2 树的逻辑表示1057.1.3 树的基本术语1067.2 二叉树的定义1067.2.1 二叉树的逻辑结构定义1067.2.2 二叉树的性质1087.3 二叉树的遍历1087.3.1 二叉树的存储结构1087.3.2 二叉链表的生成与输出1107.3.3 遍历二叉树1127.3.4 上机体验119 7.4 树的应用实例120第8 章 图1248.1 图的定义1248.1.1 图的逻辑结构定义1248.1.2 图的基本术语1248.2 图的储存1268.2.1 邻接矩阵存储1268.2.2 邻接表存储1288.3 图的遍历1298.3.1 深度优先搜索遍历1298.3.2 广度优先搜索遍历1318.3.3 上机体验1328.4 图的最小生成树1348.4.1 生成树与最小生成树1348.4.2 普里姆算法1348.4.3 克鲁斯卡尔算法1388.4.4 上机体验1408.5 最短路径1418.5.1 路径的概念1418.5.2 从一个顶点到其余各顶点的最短路径1428.5.3 每对顶点之间的最短路径1458.5.4 上机体验1488.6 图的应用实例149第9 章 排序1509.1 插入排序1509.1.1 排序原理1509.1.2 程序设计1519.1.3 算法分析1539.2 选择排序1539.2.1 排序原理1539.2.2 程序设计1549.2.3 算法分析1559.3 冒泡排序1569.3.1 排序原理1569.3.2 程序设计1579.3.3 算法分析1589.4 排序操作上机体验1599.5 排序方法的选择1629.6 排序的应用实例163第10 章 查找16710.1 顺序查找16710.2 折半查找16710.3 索引查找169