《数据结构（C#）》-第1章 绪论

1.1引言 1.2数据结构的发展简史1.3什么是数据结构 1.4基本概念和术语 1.5算法和算法的描述 第1章绪论1.1引言

处理对象的转变导致系统程序和应用程序的规模越来越大,结构也相当复杂,单凭程序设计人员的经验和技巧已难以设计出效率高、可靠性强的程序,数据的表示方法和组织形式已成为影响数据处理效率的关键。因此,就要求人们对计算机程序所加工的对象进行系统的研究,即研究数据的特性以及数据之间存在的关系———数据结构(DataStructure)。1.2数据结构的发展简史

“数据结构”在计算机科学中是一门综合性的专业基础课。数据结构的研究不仅涉及到计算机硬件(特别是编码理论、存储装置和存取方法等)的研究范围,而且和计算机软件的研究有着更密切的关系,无论是编译程序还是操作系统,都涉及到数据元素在存储器中的分配问题。1.3什么是数据结构用计算机解决一个具体问题时,大致需要经过下列几个步骤:首先要从具体问题中抽象出一个适当的数学模型,然后设计一个解此数学模型的算法(Algorithm),最后编写程序、进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题,从中提取操作的对象,并找出这些操作对象之间含有的关系,然后用数学的语言加以描述。数据结构是研究程序设计中计算机操作的对象以及它们之间的关系和运算的一门学科。1、数据2、数据元素及数据项3、数据对象4、数据结构1.4基本概念和术语数据

数据（data）是描述和量化客观事物和信息等的符号，在计算机领域是指所有能输入计算机并能被计算机系统和程序识别、存储、加工和处理的符号的总称。包括数字、字符、图像和声音等。

学号姓名性别出生日期籍贯入学成绩所在班级00201

张平男82/06/01武汉56104计算机2

00102王磊男83/12/21襄樊51204计算机1数据元素、数据项数据元素是数据的基本单位，在计算机程序中通常把数据元素作为一个整体来存储和处理。数据元素可由一个或若干个数据项组成，数据项是数据的不可分割的最小单位。数据结构：数据结构是由某一数据对象及该对象中所有数据成员之间的关系组成。数据对象：是性质相同的数据元素的集合。

如上例：一个班级的成绩表可以看作一个数据对象。举例：

某单位领导结构如下图所示总经理项目经理部门经理大堂经理

总经理、项目经理、部门经理、大堂经理的集合构成了一个数据对象，其中的每个成员是该数据对象中的一个数据元素。成员与成员之间不是相互独立的，而是存在着一种关系——领导与被领导的关系。数据结构就是这样，不仅要考虑数据对象，还要考虑对象中所有数据成员之间的关系。数据结构一般包括以下三方面内容

1、数据的逻辑结构

2、数据的存储结构

3、数据的运算

数据的逻辑结构主要体现的是数据与数据之间的关系。在研究数据的逻辑结构时，可忽略数据自身情况，所以书中所举的例子中数据都使用的是简单的数值或字符。通常所说的数据结构是指数据的逻辑结构。数据的逻辑结构：数据的存储结构

数据的存储结构：数据元素及其关系在计算机存储器内的表示。数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。对机器语言而言，存储结构是具体的。一般，只在高级语言的层次上讨论存储结构。（1）顺序存储方法

该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。

由此得到的存储表示称为顺序存储结构（SequentialStorageStructure），通常借助程序语言的数组描述。

（2）链接存储方法

该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。由此得到的存储表示称为链式存储结构,通常借助于程序语言的指针类型描述。（3）索引存储方法

该方法通常在储存结点信息的同时，还建立附加的索引表。

索引表由若干索引项组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引。索引项的一般形式是：

(关键字、地址)

关键字是能唯一标识一个结点的那些数据项。稠密索引中索引项的地址指示结点所在的存储位置；稀疏索引中索引项的地址指示一组结点的起始存储位置。（4）散列存储方法

该方法的基本思想是：根据结点的关键字直接计算出该结点的存储地址。

数据的运算即对数据施加的操作。数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。算法：是对求解某个问题的步骤的一种描述方法或操作序列。

注：数据结构的优劣与算法直接有关。数据结构的性能实际是由实现其各个服务的算法来体现的。对数据结构的分析实质上是对实现其各个服务的算法的性能的分析。1.5算法和算法的描述算法的基本特征：

1）输入：0个或多个输入；

2）输出：1个或多个输出；

3）有穷性：算法必须在有限步内结束；

4）确定性：组成算法的操作必须清晰无二义性。

5）可行性：组成算法的操作必须能够在计算机上实现。算法和算法的描述评价算法标准

算法的正确性，易读性，可维护性，健壮性，高效率等。算法时间复杂度T（n）

本课程采用以求解问题的基本操作的执行次数作为算法时间的度量算法的空间复杂度S(n)

一个算法所需要辅助存储空间的多少为空间复杂度O（n3）

称为矩阵相乘算法时间复杂度；O（n3）表示矩阵相乘算法执行时间与n3成正比,即O（n3）与n3同一数量级；

n阶矩阵相乘的算法For(i=1;i<=n;i++)

For(j=1;j<=n;j++){c[i][j]=0;

For(k=1;k<=n;k++)

c[i][j]+=a[i][k]*b[k][j]}

乘法加法执行次数均为n3

例算法和算法的描述有些算法，基本操作执行次数与问题的输入数据有关，这时可考虑

（1）算法平均时间复杂度

（2）算法在最坏情况下的时间复杂度算法的时间复杂度一般来说，设算法中基本操作的执行次数是问题规模n的某个函数f(n)，算法的时间复杂度记作：

T(n)=O(f(n))

它表示随问题规模n的增大，算法执行时间的增长率与f(n)的增长率相同。算法和算法的描述算法的时间复杂度为O(N3)

100元买100支笔,其中钢笔3元/支,圆珠笔2元/支,铅笔0.5元/支.写算法输出各种组合方案解法1#defineN100voidscheme(){inti,j,k,count,money;for(i=0;i<=N;i++)

for(j=0;j<=N;j++)for(k=0;k<=N;k++){count=i+j+k;money=3*i+2*j+0.5*k;

if(count==N&&money==N)printf(“%d,%d,%d\n%”,i,j,k);

}

}例算法和算法的描述2算法空间复杂度

在本课程中，用执行算法所需的辅助空间的大小作为算法所需空间的度量。

设执行算法所需的辅助空间是问题规模n的某个函数g(n),则算法空间复杂度记作：S（n）=O(g(n))表示算法辅助空间的增长率与g(n)的增长率相同算法和算法的描述计算解法1先计算x的幂,存于power[]中,再分别乘以相应的系数

#defineN100floatevaluate(floatcoef[],floatx,intn){floatpower[N],f;inti;for(power[0]=1,i=1;i<=n;i++)power[i]=x*power[i-1];

for(f=0,i=0;i<=N;i++)f=f+coef[i]*power[i];return(f);}算法和算法的描述例问题规模为n,算法时间复杂度:O(n)空间复杂度：O(N)解法2#defineN