软件技术基础.ppt

《软件技术基础.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构软件工程操作系统软件技术基础数据结构数据结构与算法的基本概念常用数据结构线性结构——线性表、栈、队列、链表非线性结构——树、二叉树、图线性表的查找内排序软件工程程序、软件、软件工具、软件工程的概念软件生存期及开发模型结构化方法——结构化分析、结构化设计、设计工具面向对象——概念、与结构化方法的区别软件集成与软件复用软件测试操作系统功能与类型进程及处理机管理：进程、进程通信、进程控制、调度、死锁存储器管理、设备管理、文件管理的任务及基本概念8.1数据结构概述在计算机系统软件和应用软件中都要用到各种数据结构，因此，要进行高质量的程序设计和软

2、件开发，仅掌握几种计算机语言而缺乏数据结构方面的知识是不够的，难以应付各种复杂的问题。要设计出合适的数据结构，才能有效地解决问题。在计算机系统中，数据就是计算机可以保存和处理的信息。在计算机发展初期计算机主要用于数值运算，数据就是数值。随着计算机硬件技术与软技术件的不断发展，扩大了计算机的应用范围。因此，数据范畴不仅包含了数值，还具有更为广泛的含义，如文字、字母、字符、声音、程序、图形、图像等。何谓数据结构？一、数据结构的基本概念数据+结构数据是描述客观事物并能为计算机加工处理的符号的集合。结构是指事物间的相互关系和约束。数据结构（DataSt

3、ructure）是指数据元素的组织形式和相互关系。数据结构：讨论数据在计算机中的组织形式与相互关系的学科算法：问题求解（程序设计）的步骤与方法数据：十进制、二进制常数字母、字符程序段、图形图象、语音数据元素：数据的基本单位（数据结点），往往对应客观世界的一个有意义的独立实体，可大可小数组：A(4)＝(123，234，456，789)字符串：z1="abcdhg"数据库表文件：每一条记录二、数据结构的内容1.数据元素之间的逻辑结构2.数据的存储结构3.数据的操作相关算法（提高效率）以上称为数据结构的三个层次，后继所有结构的讨论，都是从这三方面进行

4、的。如“学生表”、“职工表”就是一个数据结构，从逻辑结构来说，是一种线性表结构数据结构实际上就是研究以下问题：l数据元素间的逻辑关系是什么？l适宜采用什么样的存储结构？l有哪些基本运算？怎样实现？实际上也就是数据结构的三个层次：数据的逻辑结构数据的存储结构数据操作相关算法集合。数据结构一般包括以下三方面的内容：（1）数据的逻辑结构数据的逻辑结构从逻辑上抽象地反映数据元素间的结构关系，它与数据在计算机中的存储表示方式无关。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的逻辑结构有两大类：线性结构——线性结构的逻辑特征是：……非线

5、性结构——非线性结构的逻辑特征是：……线性结构——linearity的逻辑特征：有并且仅有一个开始数据元素和一个终点数据元素，所有数据元素都最多只有一个直接前趋和一个直接后继。例如：线性表就是一个典型的线性结构。数据元素之间为1对1的关系07020106100803040509堆栈、队列、数组、串等都是线性结构。有且仅有一个无直接前驱而仅有一个直接后继的起始元素有且仅有一个无直接后继而仅有一个直接前驱的终点元素其余的内部元素各有一个直接前驱和一个直接后继线性结构是一种最简单最常用的数据结构线性表是一种最简单和常用的线性结构非线性结构——非线性结

6、构的逻辑特征是：一个结点可以有多个前趋结点和后继结点。该结构中一个数据元素可能有多个直接前趋和直接后继。非线性结构中最一般的结构是图结构。在图结构中，任何数据元素的直接前趋和直接后继的个数都不作限制。如树形结构、图等在非线性结构中还有一类较特殊的结构，称为——“树结构”。树的逻辑特征是：①有且仅有一个称为根的元素无直接前趋；②其他元素有且仅有一个直接前趋，而每个元素都可能有多个直接后继；③所有数据元素(除根元素)都存在一条从根元素到该元素的路径。（2）数据的物理结构数据的物理结构是讨论数据元素之间的关系在计算机中的表示，也称为存储结构。数据的存

7、储结构可用以下四种基本存储方法体现：(A)顺序存储方法——把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点之间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储结构称为顺序存储结构。——即数据的逻辑顺序与存储单元的物理顺序（地址）一致顺序存储方法主要应用于线性数据结构，如线性表、数组等。非线性的数据结构也可以通过某种线性化的方法来实现顺序存储。(B)链式存储方法——对那些不能在物理位置上相邻的（不连续）数据，则可以采用链式存储结构。链式存储结构可以用一组任意的存储单元来存储数据元素。链接存储结构的特点是把存放数据元素的节点分为两部分，

8、一部分存放数据元素（称为数据域）；另一部分存放指示存储地址的指针（称为指针域），指针域指出了其后继或前趋数据元素的存储地址（即数据元素之间的关系），从