计算机软件技术基础

计算机软件技术基础教师：曾晓东电话_mail:zengxiaodong@263.net计算机软件技术基础数据结构概述第2章数据结构概述一、什么是数据结构二、有关数据结构的基本概念和术语三、算法四、算法描述语言和算法分析计算机软件技术基础数据结构概述第2章数据结构概述 一、什么是数据结构 程序=算法+数据结构例：表达式解释6+5*4=？字符串匹配串“ABCAC”出现在另一个串“ABCABCACAC”的第几个位置上排序一个序列，如何最快地对其进行排序压缩编码AAAABBBCDDE?图的最短路径地理研究中的交通网络计算机软件技术基础数据结构概述第2章数据结构概述一、什么是数据结构1、数值型与非数值型数据（1）学生表格计算机软件技术基础数据结构概述一、什么是数据结构(2)选课表(3)UNIX的文件系统计算机软件技术基础数据结构概述一、什么是数据结构2、数据结构

简单来说，就是相互之间存在一种或多种特定关系的数据元素的集合。 如线性关系、层次关系、网状关系等。计算机软件技术基础数据结构概述第2章数据结构概述

二、有关数据结构的基本概念和术语1、数据(data)：计算机程序所处理的一切数值性的和非数值性的信息。2、数据元素(dataelement)：是数据集合中的一个个体，是数据的基本单位。如数据集合N={1，2，3，4，5}中整数1至5均为数据元素。数据元素不一定是单个的数字或字符，也可能是若干个数据项的组合，如学生信息。

学生（学号，姓名，性别，成绩）数据项(dataitem)是数据不可再分的最小单位。数据元素有时也称结点、节点或记录。计算机软件技术基础数据结构概述二、有关数据结构的基本概念和术语3、数据对象(dataobject)：是具有相同性质的数据元素的集合。如大写字母字符的数据对象是集合：C={‘A’，’B’，...，’Z’}。4、数据结构(datastructure)：研究数据元素之间抽象化的相互关系和这种相互关系在计算机系统中的存储方式，并对每种数据结构定义相关的运算算法，确保经过运算后仍然是原来的数据结构类型。5、数据的逻辑结构(logicalstructure):表示数据元素之间抽象化的相互关系，又可简称为数据结构。它研究数据元素及其关系的数学特性。 集合、线性、树型、网状6、数据的物理结构(physicalstructure):表示数据的逻辑结构在计算机系统中的存储方式，又可简称为存储结构。它是逻辑结构在计算机中的映象，也就是具体实现。

顺序存储、链式存储、索引存储、散列存储计算机软件技术基础数据结构概述第2章数据结构概述三、算法1、算法：为解决某个计算任务而安排的有限操作过程的描述。2、算法的特性有穷性确定性数据输出数据输入能行性计算机软件技术基础数据结构概述三、算法3、好的算法的特性正确性可读性健壮性高效率和低存储空间要求简洁性计算机软件技术基础数据结构概述第2章数据结构概述四、算法描述语言和算法分析1.算法描述语言本门课程基本采用ANSIC描述算法。注释部分用//或/*...*/表示。有些地方为方便起见，可能省略变量定义等有关内容。请大家复习C语言的相关内容，特别是指针和结构两部分的内容计算机软件技术基础数据结构概述四、算法描述语言和算法分析2、算法的复杂性分析一个可执行的算法不一定是一个好算法，算法的分析是一个复杂的问题，通常用计算机执行时在时间和空间两方面的消耗多少作为评价该算法优劣的标准。这两个标准分别称为时间复杂度和空间复杂度。一般时间复杂度考虑的较多。度量一个程序的执行时间通常有两种方法：

事后统计和事前分析估算这里我们介绍第二种方法。计算机软件技术基础数据结构概述四、算法描述语言和算法分析2.1时间复杂度频度：指一条语句重复执行的次数，记作：F(n)时间复杂度：T(n)=O(F(n))下面举例说明如何求时间复杂度？计算机软件技术基础数据结构概述四、算法描述语言和算法分析

1.

for(i=0;i<n;i++)

2.for(j=0;j<n;j++){

3.b[i][j]=0;

4.for(k=0;k<n;k++)

5.b[i][j]=b[i][j]+a[i][k]*a[k][j];

6.}

我们以执行次数最多的语句（第5句）进行计算：语句频度为：F(n)=n3

时间复杂度：T(n)=O(F(n))=O(n3)计算机软件技术基础数据结构概述四、算法描述语言和算法分析思考下列程序段的时间复杂度

1)、x=x+1;2)、for(j=0;j<n;j++)x=x+1;3)、for(j=0;j<n;j++)

for(k=0;k<n;k++)

x=x+1;4)、for(j=2;j<=n;j++)

for(k=2;k<=j-1;k++)

x=x+1;T(n)=O(1)T(n)=O(n)T(n)=O(n2)T(n)=O(n2)计算方法：对于外层循环中的j，从2到n循环，计算出j每取一个值时，内层循环执行的次数0、1、2、...、n-2，然后累加起来，得到一个n的多项式(n-1)(n-2)/2，取出次数最高的项即可。计算机软件技术基础数据结构概述四、算法描述语言和算法分析常见的时间复杂度1）O(1)：常量型

2）O(n)、O(n2)、...、O(nk)：多项式型

3）O(log2n)、O(2log2n)：对数型

4）O(2n)、O(en)：指数型计算机软件技术基础数据结构概述四、算法描述语言和算法分析2、空间复杂度空间复杂度