计算机软件技术基础教程课件-6第六章-数据结构概述

第2部分数据结构

目录第1章绪论第3章结构化开发方法第4章面向对象的系统分析和设计第2章软件工程概述第6章数据结构概述第5章并发程序开发技术第7章线性表第8章栈和队列第10章树第11章图第9章数组第15章互联网软件开发实践第12章排序第14章数据库基本概念与应用程序设计第13章查找第1部分软件技术基础第2部分数据结构第3部分软件技术实践第六章数据结构概述6.1数据结构的引入

从提出一个实际问题到计算机解出答案，需要经历下列步骤：分析阶段、设计阶段、编码阶段和测试维护阶段等。其中分析阶段就是从实际问题中提取操作对象以及操作对象之间的关系。下面我们来看几个例子。6.1数据结构的引入

[例6.1]

计算机管理图书目录问题书名作者登录号分类号出版日期定价Java语言李晓等9700001873.8792-991977/3/2643.5UNIX系统张昊9600012973.874-1261996/9/1923.5··················6.1数据结构的引入

[例6.2]

计算机和人对弈问题6.1数据结构的引入

[例6.3]

多叉路口交通灯管理问题6.2数据结构的基本概念6.2.1引论什么是数据计算机处理的对象是数据，那么什么是数据呢？数据是客观事物在计算机中的表示，是信息的载体，具有可识别性、可加工处理性和可存储性等特征，是计算机程序加工处理的对象。可识别性是指计算机能够识别数据，为此必须对客观事物进行编码；可存储性是指数据能够存储在计算机的存储设备上；可加工处理性是指计算机能够以程序设计人员设计的算法，对数据进行加工处理，以得到预期的结果。6.2数据结构的基本概念6.2.2名词定义数据(Data)是描述客观事物的数、字符以及所有能输入到计算机中并被计算机程序处理的符号的集合。数据元素(DataElement)是数据的基本单位，即数据这个集合中的一个个体（客体）。数据对象(DataObject)具有相同特性的数据元素的集合，是数据的一个子集。数据结构(DataStructure)是指数据之间的相互关系，即数据的组织形式。6.2数据结构的基本概念6.2.3数据结构研究的内容(1)研究数据元素之间固有的客观联系，即数据的逻辑结构（LogicalStructure）。(2)研究数据在计算机内部的存储方法，即为数据的存储结构（StorageStructure），又称物理结构。(3)研究如何在数据的各种结构（逻辑的和物理的）上施加有效的操作或处理（算法）。6.2数据结构的基本概念6.2.3数据结构研究的内容直接前趋与直接后继学号姓名性别课名成绩95001王丽女物理8195002刘建东男物理76···············95031陈立平男物理92学生成绩表6.2数据结构的基本概念6.2.3数据结构研究的内容综上所述，我们可以将数据结构定义为：按某种逻辑关系组织起来的一批数据，应用计算机语言，可按一定的存储表示方式把它们存储在计算机的存储器中，并在该数据上定义了一个运算的集合。6.2数据结构的基本概念6.2.4数据的逻辑结构分类通常我们将数据的逻辑结构简称为数据结构。数据的逻辑结构有以下两大类：1)线性结构线性结构的逻辑特征是有且仅有一个开始结点和一个终端结点，且所有结点都最多只有一个直接前趋和一个直接后继。线性表就是一种典型的线性结构。本书第7章到第8章介绍的都是线性结构。2)非线性结构非线性结构的逻辑特征是一个结点可能有多个直接前趋和直接后继。第9章到第11章介绍的都是非线性结构。6.2数据结构的基本概念6.2.5存储方法1.顺序存储方法2.链接存储方法3.索引存储方法4.散列存储方法6.3关于算法的描述及算法分析6.3.1算法的概念算法是由若干条指令组成的有限序列，它必须满足以下性质：1.输入性2.输出性3.有穷性4.确定性5.可行性6.3关于算法的描述及算法分析6.3.2算法分析衡量一个算法的好坏，除其“正确性”外，还应考虑：(1)执行算法所消耗的时间；(2)执行算法所耗费的存储空间，其中主要应考虑辅存量的大小；(3)其他诸如：算法是否易读，是否易于调试、测试等。6.3关于算法的描述及算法分析6.3.2算法分析求两个n阶方阵的乘积C=A×B，下面是算法描述：＃definen自然数MATRIXMLT(A,B,C)FloatA[][n],B[][n],C[][n];{inti,j,k;(1) for(i=0;i<n;i++)n+1(2) for(j=0；j<n;j++)n(n+1)(3) {C[i][j]=0;n2(4) for(k=0;k<n;k++)n2(n+1)(5) C[i][j]=C[i][j]+A[i][k]*B[k][j];}}n36.3关于算法的描述及算法