电通班学习-数据结构

第一章 绪论一、 数据结构为什么要学习数据结构举例：1）2）3）本馆中最短路径的问题打印文件排队叫号系统只要有数据的地方，就涉及到数据怎样组织、排列的问题，即数据结构。同样的数据可以有不同的结构。进一步研究：在某种结构上怎样进行数据处理一、 数据结构为什么要学习数据结构研究内容：数据的不同结构和组织方法在某种结构上进行数据处理的不同算法算法的分析和比较

最佳方案二、数据结构课程的发展及其地位数据结构（DataStructure）是计算机软件和计算机应用等相关专业的一门课程，它所研究的对象是非数值计算中计算机操作的对象，以及对象之间的关系和操作等。二、数据结构课程的发展及其地位计算机发展的初期，由于其价格昂贵，运算速度慢，容量有限，人们使用计算机主要是用于处理数值问题。其特点是计算量大，数据量小，程序设计者主要精力集中在程序设计的技巧上，无须重视数据结构。二、数据结构课程的发展及其地位随着计算机技术的发展，“非数值问题”越来越显得重要。计算机大量应用于非数值计算领域，像工业领域、商业企业和

机构的管理等领域。据统计，处理非数值问题占用了90%以上的机器时间。二、数据结构课程的发展及其地位这些问题所涉及的数据量大，数据结构复杂，数据之间的关系一般无法用数学方程式加以描述。解决此类问题的关键已不再是分析数学和计算方法，为了对其进行有效处理，必须研究数据自身的结构。因而对于数据结构的设计显得尤为重要。二、数据结构课程的发展及其地位20世纪60年代，

计算机界首先使用了数据结构这一名称。1968年

著名的计算机

唐·欧·

教授创立了数据结构的最初体系，他在《计算机程序设计技巧》第一卷《基本算法》一书中，全面、系统的阐述了数据的逻辑结构和

结构，为数据结构奠定了基础。二、数据结构课程的发展及其地位

人们普遍认为程序设计实质上是对实际问题选择一种好的数据结构，加上设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。二、数据结构课程的发展及其地位从70年代中期到80年代初期，人们对于数据结构的研究逐渐产生了浓厚的，各种版本的数据结构著作相继出现。二、数据结构课程的发展及其地位地位：是三种学科：数学、计算机硬件、

的边缘学科，与上述三种学科都有密切关系。是一门计算机科学专业的 课程不仅是一般程序设计的基础，而且是设计程序编译系统、计算机操作系统、数据库系统和其他系统程序和大型应用程序的基础因此学习数据结构具有十分重要的意义。1.1

常用术语、数据（Data）：能被计算机输入、处理和输出的一切信息。数据元素（DataElement）：数据整体中相对独立的单位数据记录：组织数据的基本单位。用于把相互有关系的多个数据项组成一条记录。数据处理：其基础是数据结构1.1

常用术语数据结构：虽然至今没有一个关于数据结构的标准定义，但普遍认为数据结构应当包含以下面的内容：逻辑结构：数据间关系。逻辑结构是从逻辑关系上描述数据，与具体

无关，与计算机无关。因此逻辑结构可以看作是从具体问题抽象出来的数学模型。物理结构：逻辑结构在计算机中的

方式。数据的运算：是指对数据施加的操作。每种逻辑结构都有一个运算的集合。常用的数据运算有：查找、排序、 、删除、更新等操作。常用术语数据结构：综上所述， 可以将数据结构定义为：按某种逻辑关系组织起来的一批数据，按一定的方式到计算机的 器中，并在这些数据之上定义一个运算的集合，就称之为一个数据结构。B=（K，R）数据结构的表示方法：二元组——集合形式图示法常用术语数据类型：1)

简单类型2)

结构类型抽象数据类型——类包括数据以及数据上的操作。数据对象——数据类型的具体化（常量和变量）算法：在某数据结构上解决特定问题的方法。有5个特性。1.2

算法描述举例1.3

算法评价正确性稳健性可读性时间复杂度空间复杂度1.3

算法评价使用绝对运行时间来衡量算法的优劣是不科学的，因为这样的统计依赖于计算机的软、硬件环境等多种综合因素，不单纯反映算法的优劣，容易掩盖算法自身的特性。因此，通常是在不实际运行该算法的前提下，估算当问题的规模扩大时，该算法的时间代价和空间代价。1.3

算法评价时间复杂度算法运行时间＝一次简单操作的时间×简单操作次数通常把算法中包含简单操作的次数叫做该算法的时间复杂度，用它来衡量一个算法的运行时间性能。当问题的规模为n时，算法的时间复杂度通常是一个n的函数f(n)【例】交换i和j的内容。Temp=i；i=j；j=temp；以上三条单个语句的频度均为1，该算法段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作f(n)=Ο(1)。如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是Ο(1)。【例】循环语句当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。x=0；for

（k=1；k<=n

；k++）x=x+1；for

（i=1；i<=n

；i++）for

（j=1；j<=n

；j++）y=y+1；该算法段的时间复杂度为f(n)=O(n2)int

fact(int

n){if

(n==0)

or

(n==1)return

1;else return

(n*fact(n-1));}以n=3为例,调用过程如下：fact(3)-fact(2)-fact(1)-fact(2)-fact(3)递

归

回

溯【例】递归算n法！——递归算法如下：【例】递归算法

——

n！分析：

f(n)=f(n-1)+O(1)其中O(1)为一次乘法操作.迭代求解过程如下：f(n)=f(n-1)+O(1)=f(n-2)+O(1)+O(1)=f(n-3)+O(1)+O(1)+O(1)……=f(1)+……+O(1)+O(1)+O(1)=n*O(1)=O(n)算法时间复杂度的计算量级表示时间复杂度的主要运算规则如下：（1）加

则：

O

(f(n))+O

(g(n))

=O

(max

(f(n),g(n)

)（2）

乘

则：

O(f(n))

*

O(

g(n))

=O

(

f(n)

*

g(n)

)算法的时间复杂度还与输入的初始状态有关。这类算法的时间复杂度的分析比较复杂，一般分最好情况（处理最少的情况),

情况(处理最多的情况)和平均情况分别进行讨论。【例】在数组a[n]中查找给定值为key的算法：for（int

i=0;i<n;i++）if

(a[i]==key)

return

i;return

-1；此算法的时间复杂度不仅与问题规模n有关，还与数组a的各元素取值及key的取值有关：最好情况：a[0]==key，只需比较1次，f(n)=O(1)。情况：若a[n-1]==key或a中没有与key相等的元素,则需要比较n次，f(n)=O(n)。∑(pi

×(i+1))i=0n-11n(1+2+……+n)=

½(n+1)=3.平均情况：∑（a[i]==key的概率×比较次数）通常假定查找不同元素的概率p是相同的,则算法的平均复杂度为：若对于查找不同元素的概率p不相同时，其算法复杂度就只能做近似分析。算法的空间复杂度算法所占用的

空间包括：算法本身所占空间输入/输出数据所占空间辅助变量所占空间其中，前两个空间是计算机运行时所必须的，因此通常把算法执行时所需的辅助空间作为分析算法空间复杂度的依据。算法的空间复杂度对于同一个问题，采用不同的算法，所需的辅助

空间往往是不一样的。常见的空间复杂度也表示为O(1)、O(n)、O(n2)、O(n3)等。如果所需辅助空间相对于输入数据量（规模为n）来说是个常数，即不随问题规模大小而改变，则称这种算法为“就地”进行，空间复杂度为O(1)算法的复杂度在一个算法的实现中，时间复杂度和空间复杂度往往是相互的。若要减少算法的执行时间，就要以牺牲空间为代价；反之，若要节省空间，就可能要增加算法的执行时间。二者很难兼顾。实际应用中，要根据具体情况有所侧重。30数据类型空类型void整字符型型int

单字符型char实

型双精度型double逻辑型bool宽字符型w_char单精度型float结构struct联合union枚举enum数

组type[

]指

针type*类class非基本数据类型数据类型基本数据类型对象的概念每个对象都有各自的

状态和行为特点。对象（Object）由属性（Attribute）和行为（Action）两部分组成。属性是行为是对象静态特征的一个数据项。对象动态特征的一个操作。对象是属性和行为的封装体。类的概念类（Class）是具有相同属性和行为的一组对象集合的再抽象。从语言角度来说，类是一种用户自定义数据类型，而对象是具有这种类型的变量。例：下面是一年12个月的数据结构的二元组表示方法。B=（K，