数据结构与算法分析

出版时间：2012-2  出版社：西安电子科技大学出版社  作者：荣政 编  页数：296  

内容概要

本书以程序设计能力的培养为目标，系统地介绍了数据结构和算法设计的相关知识，其主要内容包括：线性表、栈、队列、串、数组、树、图、索引和散列等基本数据结构及其应用；分治法、动态规划、贪心算法、回溯法、分支界限法等常用的算法设计方法。书中还通过具体实例的分析和设计，介绍了软件设计规范及程序设计的关键技术，具有较高的使用价值。
本书可作为高等学校电子信息类非计算机专业“数据结构”课程的本科(或大专)教材，也可供自学计算机软件基础知识的读者参考。

书籍目录

第1章　绪论
　1．1软件的基本概念
　　1．1．1软件应用
　　1．1．2软件生存期
　　1．1．3软件技术
　　1．1．4程序设计技术
　1．2数据结构概述
　　1．2．1数据结构的引入
　　1．2．2数据结构的基本概念
　　1．2．3数据结构与程序设计
　1．3算法与算法分析
　 1．3．1算法的概念
　 1．3．2算法分析
　1．4程序设计的关键技术
　 1．4．1程序结构设计
　 1．4．2模块设计
　 1．4．3 良好的编程风格
　 1．4．4排错与测试
　 1．4．5程序性能
　1．5程序设计的步骤及实例
　 1．5．1程序设计的步骤
　 1．5．2程序设计实例
　习题
第2章　线性表
　2．1线性表的基本概念及运算
　2．2顺序表
　 2．2．1顺序表的基本运算
　 2．2．2顺序表的应用实例——学生学籍档案管理．
　2．3链表
　　2．3．1 单链表
　　2．3．2单链表的基本运算
　　2．3．3循环链表
　　2．3．4双向链表
　　2．3．5链表应用实例——多项式的表示及运算
　习题
第3章　栈和队列
　3．1 栈
　　3．1．1栈的顺序存储表示——顺序栈
　　3．1．2栈的链式存储表示——链栈
　　3．1．3栈的应用
　3．2 队列
　 3．2．1队列的存储结构
　 3．2．2队列的应用
　习题
第4章　串和数组
　4．1串及其运算
　4．2串的存储结构
　4．3 串运算的实现
　 4．3．1基本运算的实现
　 4．3．2改进的模式匹配算法
　4．4数组的定义和运算
　4．5数组的顺序存储结构
　4．6矩阵的压缩存储
　 4．6．1特殊矩阵
　 4．6．2稀疏矩阵
　习题
第5章　树
　5．1树的基本概念
　5．2二叉树
　5．3二叉树的存储结构
　 5．3．1顺序存储结构
　 5．3．2链式存储结构
　 5．3_3二叉树的建立
　5．4二叉树的遍历
　 5．4．1二叉树的深度优先遍历
　 5．4．2二叉树的广度优先遍历
　 5．4．3深度优先遍历的非递归算法
　 5．4．4从遍历序列恢复二叉树
　 5．4．5遍历算法的应用
　5．5树和森林
　 5．5．1树的存储结构
　 5．5．2树、森林和二叉树之间的转换
　5．6线索二叉树
　 5．6．1线索二叉树的建立
　　……
第6章　图
第7章　索引结构与散列技术
第8章　缩小规模算法
第9章　搜索算法
第10章　“难”问题求解算法
参考文献
　　

章节摘录

　　第1章 绪 论　　随着计算机科学技术的发展和日趋成熟，软件已经成为社会发展的重要驱动力之一：软件是商业决策的基本引擎，是解决现代科学研究和工程问题的基础，也是提升现代产品和服务品质的关键因素。软件在现代社会中是不可缺少的，它可以应用于各种类型的应用系统中，如办公、娱乐、交通、教育、医药、通信……数不胜数，并成为从基础教育到基因工程的所有领域的推进器。　　所有这一切改变了软件原有的概念，软件无所不在，已经成为人们现实生活中必不可少的实用技术。　　1.1 软件的基本概念　　从一般意义上讲，能够在计算机上运行的程序都可以称为软件。软件更准确的定义是利用计算机本身提供的逻辑功能，合理地组织计算机的工作流程，简化或替代人们使用计算机过程中的各个环节，提供给使用者一个便于操作的工作环境的“程序集”。它包括计算机程序和与之相关的文档资料的总和（文档是指编制程序所使用的技术资料和使用该程序的说明性资料，如使用说明书等，即开发、使用和维护程序所需的一切资料）。　　软件是逻辑的而不是物理的产品，与硬件相比具有以下完全不同的特征：　　（1）软件是由开发或工程化而形成的，而不是由传统意义上的制造产生的。硬件的再制造过程中可能引入质量问题，软件则几乎不可能发生类似问题。软件的成本集中于开发，而硬件的成本除了开发成本外还有生产成本。　　（2）软件不会磨损。软件的故障率随时间的推移而降低，而硬件的故障率随时间的推移而增加。硬件模块磨损后可以用新的备用模块替换，而软件故障则是其中的错误，没有可替换的备件。　　（3）大多数软件是自定义的，而不是通过已有的组件组装而来的。当然，目前基于组件的软件开发已经成为软件未来的主要发展趋势。　　1.1.1 软件应用　　从某种程度上讲，对软件应用给出一个确切的分类是比较困难的。下面给出的一些软件的应用领域，可以看做是一种潜在的应用分类：　　（1）系统软件。系统软件是指一组为其他程序服务的程序，如操作系统、编译器等。　　（2）实时软件。管理、分析和控制现实世界中发生的事件的程序称为实时软件。实时软件包括：①数据接收部件：负责从外部环境获取和格式化信息；②分析部件：负责将信息转换为具体应用所需要的形式；③控制/输出部件：负责对外部事件做出响应；④管理部件：负责协调其他各部件，使得系统能够保持一个可接受的实时响应时间。　　（3）商业软件。商业信息处理是目前最大的软件应用领域。具体的“信息系统”均可归入管理信息系统（MIS）软件。使用这类软件可以访问一个或多个包含商业信息的大型数据库。该领域的应用使已有的数据重新构造，变换成一种能够辅助商业操作或管理决策的形式。除了传统的数据处理应用外，商业软件还包括交互式计算和客户/服务器模式计算（如POS事务处理）。　　（4）工程和科学计算软件。工程和科学计算软件的特征是“数值分析”算法。此类软件应用的涵盖面很广，从天文学到火山学，从汽车压力分析到航天飞机的轨道动力学，从分子生物学到自动化制造等。　　（5）嵌入式软件。智能产品在工业和消费电子市场上都是必不可少的，而嵌入式软件正是驻留在这些智能产品的只读内存中，实现产品的智能应用。嵌入式软件能够执行有限但专职的功能。　　（6）个人软件。仅供个人使用的程序称为个人软件，如文字处理、电子表格、多媒体娱乐、数据库管理、个人金融应用、访问外部网络应用等。　　（7）人工智能软件。利用非数值算法解决复杂的问题，这些问题不能通过计算或直接分析得到答案，这就要使用人工智能软件，如专家系统（基于知识的软件）、模式识别、定理证明、游戏等。　　1.1.2 软件生存期　　软件生存期是指从软件项目的需求定义到完成使命后而废弃的全过程。把整个过程中的活动进一步展开，可以得到软件生存期的六个工作阶段，即制定计划、需求分析和定义、软件设计、程序编制、软件测试及运行/维护。　　1．制定计划　　首先要确定开发软件系统的总目标，给出对其在功能、性能、可靠性以及接口等方面的要求；然后由系统分析员和用户合作，论证该项软件任务的可行性，探讨解决问题的方案，并对可利用的资源（计算机硬件、软件、人力等）、研发的成本、可取得的效益、开发的进度做出评估，制定出完成开发任务的实施计划，连同可行性研究报告，提交管理部门审查。　　2．需求分析和定义　　对开发软件提出的需求进行分析并给出详细的定义。首先由软件人员和用户共同讨论决定哪些需求是可以满足的，并对其加以确切的描述；然后编写出软件需求说明书或系统功能说明书，以及初步的系统用户手册，提交管理机构评审。　　3．软件设计　　在软件设计阶段中，设计人员把已确定的各项需求转换成一个相应的体系结构。结构中的每一个组成部分都是意义明确的模块，每个模块都和某些需求相对应，即概要设计。然后对每个模块要完成的工作进行具体的描述，为源程序的编写打下基础，即详细设计。　　……