单片机程序设计基础

　　内容简介本书是《单片机应用程序设计技术》（修订版）一书的姐妹篇。《单片机应用程序设计技术》的内容以程序设计的经验和技巧为主，而本书内容则以程序设计的基本算法为主，目的在于全面提高单片机程序设计者的软件素质。基本内容包括：单片机常用的线性数据结构和相关算法、排序和查找算法、树和图在单片机中的实现、常用的数据处理算法及常用编码方法等。从单片机系统的实际硬件环境出发，语言通俗易懂，使读者轻松地将单片机程序设计基本算法学到手。为加强学习效果和增加实用价值，本书配套了上机学习光盘，在光盘中还提供了最新修订的子程序库和相关调试工具软件，以及众多单片机资料。本书可作为电子技术人员自学单片机程序设计基本算法的教材，也可供高等院校电子技术类专业本科生和研究生参考。前言嵌入式系统的应用越来越广，我国从事嵌入式系统开发的人员也越来越多，而单片机是嵌入式系统的核心单元。从我国主要的几种电子杂志上可以看出，有关单片机应用的文章也越来越多。在开发一种嵌入式系统产品（含单片机产品）时，有关单片机部分的工作主要是做两方面的设计：硬件设计和软件设计。在硬件设计方面，世界上几家主要的半导体公司（如INTEL，PHILIPS，MOTOROLA等）竞相推出各种高性能、低功耗、低成本的单片机和外围芯片，使我们在进行硬件设计时可以很快地得到最先进的芯片。在这种情况下，硬件设计的外部条件越来越好，集成度越来越高，在实现相同功能的情况下线路越来越简化。在软件设计方面，虽然开发工具和程序设计语言也在不断提高，但技术人员本身的软件素质对软件设计水平无疑起决定作用。软件设计水平在嵌入式系统产品开发的过程中占有重要地位，直接影响到产品的水平和竞争能力。不容置疑，在我国各大专院校、科研院所和大中型企业中，有一批专家，他们的软、硬件水平均非常高；但另一方面，我国目前绝大多数从事电子产品开发的技术人员身在基层，基本上不是计算机专业毕业的，有的没有上过大学，他们未接受过系统的软件基础理论教育，软件设计水平不太高。在软件开发过程中，他们只是不自觉地采用了一些规律性的设计方法，或者模仿别人的程序设计方法，而有更多成熟的基本方法没有被掌握，致使开发出来的软件水平不高，使产品的功能和可靠性受到一定的制约。作者已经出版了《单片机应用程序设计技术》（修订版）一书。该书内容以程序设计的经验和技巧为主，而本书内容则以程序设计的基本算法为主，目的在于全面提高单片机程序设计者的软件素质。软件设计是一门科学，有其自身的规律，也有很多成熟的理论和算法。对于广大电子技术人员来说，不大可能再脱产进大学系统学习基础理论，只能一边干一边学。要学习就要选教材，而目前能选到的教材大都是专为大学生编写的，如《数据结构》、《计算方法》、《线性代数》及《代数与编码》等。这些教材起点较高，偏重理论证明，不考虑单片机的特点，对于广大电子产品开发人员来说不是十分适合，学起来会感到比较抽象和吃力。出于提高我国广大电子产品开发人员软件素质的愿望，我决定编写一本适合自学软件理论基础和基本算法的书。该书起点不高，只要有中学数学基础，并已从事了一段时间电子产品的开发，就可以看懂。学完本书后，对单片机程序设计的主要基础理论和常用成熟算法能初步掌握，在进行软件设计时，可以减少很多盲目性，并为更系统、更深入地学习计算机理论打下良好基础。在内容上，我们选择最基本和最成熟的理论和算法予以介绍。主要范围为数据结构、计算方法、线性代数及代数与编码，但不可能介绍全部内容，只是选取与单片机应用系统开发联系最紧密的内容加以重新整理、编排，打破大学教科书的传统教材格式，基本取消推导证明过程，尽量结合单片机的特点，使广大读者能够比较顺利地理解和接受。在单片机中应用最多的是线性数据结构，故本书第1章首先介绍常用的线性数据结构及部分基础算法；第2章和第3章集中介绍线性数据结构的排序算法和查找算法；第4章介绍几种常用的特殊算法，为进一步介绍非线性数据结构作准备；对于常用的非线性数据结构及其有关算法分别在第5，6章进行介绍；带单片机的电子仪器设备一般都具有较强的数据处理能力，为此在第7章中介绍常用线性方程组的解法；第8章介绍插值算法；第9章介绍数理统计中常用的计算方法；第10章介绍常用编码方法，这对优化设计很有帮助；第11章介绍两个实例，作为全书的一个总结；附录A介绍浮点数据处理的基本原理，这对不熟悉浮点数的读者会有一定帮助；附录B为本书上机学习光盘文件说明。为了更好地掌握本书内容，建议上机实际运行一下书中的程序，效果一定要好得多。为配合学习，我们将书中的程序添加上主程序和各种支撑子程序以及数据样品，形成可执行、可调试的运行程序，并进行了较严格的测试，然后汇总成一张配套的上机学习光盘，附在本书中。在该光盘中还包含了经过长期考验和优化的最新版本的子程序库，实用价值较高。本书1997年出版了第一版，受到读者好评；但也存在一些缺陷，本次修订工作就显得十分必要。修订工作如下：（1）对过时或不合适的字句进行修改，对插图中少量的瑕疵进行了弥补。（2）对汇编语言程序中的常量和变量在定义时分别用EQU和DATA进行区分，使程序更准确、更规范。（3）对上机学习光盘中的程序进行了全面整理，更方便上机学习。（4）为配合C51的推广，增加了大量与汇编语言程序对应的C算法程序。（5）增加了少量新内容。在本书修订过程中，得到北京航空航天大学出版社的大力支持，在此表示衷心感谢！由于水平有限，书中错误及不足之处敬请广大读者予以指正，不胜感谢！作者于江西省抚州市2003年3月

暂缺《单片机程序设计基础》作者简介

     目录
   第一章 单片机中常用的线性数据结构
    §1.1数据结构的基本概念
    1.1.1逻辑结构
    1.1.2存储结构
    1.1.3算法
    §1.2简单变量
    1.2.1系统变量
    1.2.2临时变量
    1.2.3计数器
    1.2.4指针
    §1.3表格
    1.3.1固定表格
    1.3.2动态表格
    1.3.3线性表的插入算法
    1.3.4线性表的删除算法
    §1.4数组和数据块
    1.4.1一维数组
    1.4.2多维数组
    1.4.3数据块操作
    §1.5数据缓冲区
    1.5.1输入缓冲区
    1.5.2输出缓冲区
    §1.6队列
    1.6.1队列的基本概念
    1.6.2队列的存储结构
    1.6.3人队的算法
    1.6.4出队的算法
    1.6.5队列的应用实例
    §1.7用户堆栈
    1.7.1用户堆栈的基本概念
    1.7.2用户堆栈的存储结构
    1.7.3人栈的算法
    1.7.4出栈的算法
   第二章 线性表的排序算法
    §2.1插入排序
    §2.2选择排序
    §2.3冒泡排序
    §2.4归并排序
    §2.5快速排序
    §2.6排序方法比较
   第三章 线性表的查找算法
    §3.1顺序查找
    §3.2折半查找
    §3.3分块查找
    §3.4串的匹配
    §3.5查找算法应用实例
   第四章 几种常用特殊算法
    §4.1递归算法
    4.1.1递归算法的特点
    4.1.2递归算法举例
    §4.2递推算法
    4.2.1递推算法的适用性
    4.2.2递推算法举例
    §4.3回溯算法
    4.3.1回溯算法的特点
    4.3.2回溯算法举例
   第五章 树及其在单片机中的算法实现
    §5.1树的基本概念
    5.1.1树的定义
    5.1.2树的基本概念
    §5.2二叉树
    5.2.1二叉树的定义及其性质
    5.2.2完全二叉树及其特点
    5.2.3二叉树的顺序存储
    5.2.4二叉树按编号的遍历算法
    5.2.5二叉树的前根遍历算法
    5.2.6二叉树的中根遍历算法
    5.2.7二叉树的后根遍历算法
    §5.3普通树
    5.3.1普通树的存储方法
    5.3.2普通树的前根遍历算法
    5.3.3普通树的后根遍历算法
   第六章 图及其在单片机中的算法实现
    §6.1图的基本概念
    6.1.1图的定义
    6.1.2图的基本概念
    §6.2图的存储结构
    6.2.1邻接矩阵
    6.2.2邻接表
    §6.3图的遍历算法
    6.3.1图的深度优先搜索遍历算法
    6.3.2图的广度优先搜索遍历算法
    §6.4图的生成树和最短路径问题
    6.4.1图的生成树
    6.4.2图的最短路径问题
    §6.5网络的最小生成树和最短路径问题
    6.5.1网络的最小生成树
    6.5.2网络的最短路径问题
   第七章 常用线性方程组求解算法
    §7.1引言
    §7.2主元消去法
    7.2.1无回代过程的主元消去法
    7.2.2有回代过程的主元消去法
    §7.3三元线性方程组的行列式法
    7.3.1行列式法概述
    7.3.2三元线性方程组的行列式法
   第八章 常用插值算法
    §8.1引言
    §8.2线性插值算法
    §8.3抛物线插值算法
    8.3.1算法概述
    8.3.2逐次线性插值算法
    §8.4插值算法应用实例
    8.4.1线性插值算法应用实例
    8.4.2抛物线拟合算法应用实例
   第九章 常用数理统计分析
    §9.1引言
    §9.2均值和标准离差的估算
    9.2.1计算X（估算均值μ）
    9.2.2计算S（估算标准离差σ）