软件技术基础

《软件技术基础/高等学校电子信息类专业系列教材》在总结教学团队丰富教学经验的基础上，结合作者多年的科研实践，从掌握基础知识及应用的角度出发，阐述了程序设计语言、数据结构及算法、操作系统、计算机网络、数据库系统和软件工程的基本原理及Z新技术。《软件技术基础/高等学校电子信息类专业系列教材》结合理工科专业的课程梯度，辅以大量应用案例，内容丰富、语言简明、实用性强，可作为高等院校“计算机软件技术”相关课程的教材。

 系统全面 涵盖“计算机软件技术”课程中的经典内容。考虑到《软件技术基础/高等学校电子信息类专业系列教材》中的案例均以C语言描述，为方便读者的理解，第2章回顾了C语言中较复杂的数组、结构、指针、递归算法等相关知识。

 技术前沿 针对信息技术领域的Z新进展，介绍了大数据、云计算、物流网等信息技术的主要原理及具体应用，启迪创新思想，为未来的进一步学习与研究奠定基础。

　　《软件技术基础/高等学校电子信息类专业系列教材》是计算机基础教材。全书系统、通俗地介绍了新计算机软件技术的基础知识和应用，内容包括软件技术概论、C语言回顾、数据结构、遍历、查找和排序、操作系统、数据库系统、计算机网络、软件工程及网络新技术等。讲解由浅人深，循序渐进，通俗易懂。该书将原理、方法与实例相结合，图文并茂。书中的案例都在Dev-C++环境下测试通过。
　　《软件技术基础/高等学校电子信息类专业系列教材》既可作为高等院校非计算机专业本科生的教材，又可作为从事工程应用领域计算机软件开发工作的科研技术人员的参考书。

　　瞿亮，湖南大学电气与信息工程学院教授，中国人工智能学会智能检测与运动控制技术专业委员会委员，教育部学位评审专家，湖南省科技评审专家，北京市自然科学基金评议专家，长沙市政府工业科技特派员。有高校、科研所及公司工作经验，长期从事智能信息处理、智能控制、计算机仿真等领域的教学和研究工作。主持或参加了国家自然科学基金、国家“863计划”、湖南省科技计划及企业研发项目20余项，主编教材4部。

第1章 软件技术概论
1．1 软件的定义及分类
1．2 软件技术及其发展
1．3 章节内容及学习方法

第2章 C语言回顾
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．4 递归
2．4．1 递归的定义
2．4．2 应用递归的问题类型
2．4．3 递归与回溯
2．4．4 递归与非递归程序的转换

第3章 数据结构
3．1 数据的逻辑结构与存储结构
3．1．1 基本概念
3．1．2 数据的逻辑结构
3．1．3 数据的存储结构
3．2 线性表
3．2．1 线性表的顺序存储和操作
3．2．2 线性表的链式存储和操作
3．2．3 小结
3．2．4 栈
3．2．5 队列
3．2．6 栈和队列的应用
3．3 树
3．3．1 常用术语
3．3．2 二叉树
3．3．3 森林、树与二叉树的转换
3．3．4 树的应用举例
3．4 图
3．4．1 常用术语
3．4．2 图的存储结构
3．4．3 图的应用举例

第4章 遍历、查找和排序
4．1 算法
4．1．1 算法的定义及描述
4．1．2 算法设计的要求
4．1．3 算法的效率度量
4．2 遍历
4．2．1 二叉树的遍历
4．2．2 图的遍历
4．3 查找
4．3．1 查找的基本概念
4．3．2 顺序查找
4．3．3 二分查找
4．3．4 分块查找
4．3．5 哈希查找
4．4 排序
4．4．1 排序的基本概念
4．4．2 插入排序
4．4．3 交换排序
4．4．4 选择排序
4．4．5 归并排序
4．4．6 多关键字排序
4．4．7 小结
……
第5章 操作系统
第6章 数据库系统
第7章 计算机网络
第8章 软件工程
第9章 网络新技术
参考文献

第3章

CHAPTER 3

数 据 结 构

数据结构是研究非数值计算程序设计中计算机的操作对象以及它们之间关系和运算的科学。数据结构与数学、计算机硬件和计算机软件等有着密切的关系，数据结构与算法密不可分，是操作系统、编译原理、数据库、情报检索、人工智能等学科的重要基础。

3.1数据的逻辑结构与存储结构

3.1.1基本概念

数据是信息的载体，是描述客观事物的数、字符以及所有能被输入到计算机中并被计算机程序识别和处理的符号的集合，包括数值性数据和非数值性数据。

1. 数据元素、数据项和数据对象

数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可以由若干个数据项组成。数据项是在数据处理时不能再分割的最小单位。数据对象是性质相同的数据元素的集合。数据对象亦称数据元素类。数据元素是数据对象的一个实例。

例如，学生张强的学籍信息集合是数据元素，学生学籍信息表中的每一项，如学号、姓名、性别等各自为一个数据项。特征相同且具有共同数据项的众多学生数据可形成一个学生数据对象student。例如：

student = { 张强，李兵，…… }

任何问题中，数据元素之间都不是孤立的，它们之间存在着某种关系，数据元素之间的关系称为结构。

2. 数据结构

数据结构是互相之间存在关系的数据元素的集合。数据结构将数据按某种逻辑关系组织起来，按一定的存储表示方式把它们存储在计算机存储器中，并在这些数据上定义一个运算的集合。数据结构与数据类型和数据对象不同，它不仅要描述数据类型的数据对象，还要描述数据对象各元素之间的相互关系。

数据结构通常包括逻辑结构和存储结构。逻辑结构用于描述数据之间的逻辑关系，存储结构描述数据如何在计算机内存储。

通常，用计算机解决一个具体问题时，可分为以下步骤。

(1) 从具体问题抽象出一个适当的数学模型。

(2) 设计一个解此数学模型的算法。

(3) 编出程序，进行测试、调试直至得到最终解答。

寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。数值问题可以用诸如方程等描述。而非数值计算问题的数学模型则是用诸如表、树和图之类的数据结构描述。

3. 数据操作

数据操作亦称为数据运算。数据运算是数据结构的一个重要方面，对任何一种数据结构的研究都离不开对该结构上的数据运算及其实现算法的研究。最常用的数据操作有5种： 插入、删除、修改、查找、排序。例如针对线性表常见的基本操作如下。

(1) 线性表初始化。构造一个空的线性表。

(2) 求线性表的长度。返回线性表中所含元素的个数。

(3) 取表元。返回线性表L中的第i个元素的值或地址。

(4) 按值查找。在线性表L中查找值为x的数据元素，其结果返回在L中首次出现的值为x的元素的地址； 若未找到，返回一个特殊值表示查找失败。

(5) 插入操作。在线性表L的第i个位置插入一个值为x的新元素。

(6) 删除操作。删除线性表L中序号为i的数据元素。

基本运算并不是它的全部运算。数据结构的操作定义在逻辑结构层次上，而操作的具体实现建立在存储结构基础上。每个操作的算法只有在存储结构确立之后才能实现。

图31描述了数据结构的3个研究内容。

数据结构

逻辑结构线性结构线性表

线

队

非线性结构树

图

存储结构顺序存储

链式存储

数据运算： 检索、排序、插入、删除、修改等

　　伴随着信息化时代的到来，计算机技术得到高速发展。随着互联网和手机等智能终端设备的广泛应用，计算机软件与日常工作和生活紧密地结合在一起，改变了人们的生活和工作方式。这种发展趋势还将进一步扩大和深入，对绝大多数非计算机专业的人士来说，掌握必要的软件技术基础知识是了解和提高软件开发与应用水平的重要途径。
　　软件技术包含的内容非常丰富，涉及程序设计语言、数据结构及算法、操作系统、计算机网络、数据库系统和软件工程等知识。软件技术发展迅猛，新技术不断涌现，如何在一本教材中让非计算机专业的学生理解和掌握最新的软件技术基础知识和技能是软件技术教学的难点及重点。作者在高校长期从事计算机软件技术基础课程的教学和研究工作，熟悉该课程的教学需求和学生体会。本书是根据高等院校非计算机专业对计算机软件技术的知识要求，结合作者多年的教学和实践经验集体编写而成的。
　　本书共分为9章。第1章介绍软件的概念及分类，软件技术的发展历史，并对教材各章内容、学习目的及学习方法做了介绍；第2章为方便读者更好地理解书中案例程序，对c语言中相对复杂的数组、结构及指针的运用等知识进行简单回顾；第3章介绍数据结构的概念、数据的逻辑结构与存储结构，线性表、堆栈、队列、树和图结构的基本术语与相关运算；第4章结合数据结构讲述了算法的概念和分析方法以及各种结构数据的遍历、查找与排序方法；第5章介绍操作系统的工作原理、主要功能、与硬件的关系及典型操作系统Linux的使用方法；第6章介绍数据库的基础知识、数据模型、关系数据库、结构化查询语言SQL等；第7章从使用者的角度介绍了计算机网络的基本概念、拓扑结构与通信协议、无线网络、IPv6及网络安全等常识；第8章介绍软件工程的起源和主要思想，常用系统开发模型及开发步骤和工具等；第9章介绍大数据、云计算、物联网等近年来兴起的网络新技术。
　　本书由瞿亮主编，梁桥康、王绍源、唐璐、王亚副主编，第1、2、3、6、8章由瞿亮编写，第4章由王绍源编写，第5章由唐璐编写，第7章由梁桥康编写，第9章由王亚编写。
　　本书内容翔实，图文并茂，在编写过程中注重由浅人深，循序渐进，书中的实例源于工程，所有案例都在Dev-C++环境下测试通过。本书既可作为高等院校非计算机专业本科生的教材，又可作为从事工程应用领域计算机软件开发工作的科研技术人员的参考书。
　　由于作者水平有限，编写时间仓促，书中难免存在不足和疏漏之处，恳请各位专家和广大读者指正。另外，在编写中参考了许多同类书籍，在此向相关作者一并表示最诚挚的感谢。