数据结构研究的内容

《数据结构研究的内容》由会员分享，可在线阅读，更多相关《数据结构研究的内容（39页珍藏版）》请在金锄头文库上搜索。

1、第一讲： 数据结构及其研究的内容 Data Structure Curriculum & Its Research Field,山东师范大学传播学院 李大锦 Communication school of SDNU Li Da-Jin,一、数据结构课程的产生与发展,计算机处理的数据 最初是为了纯粹的数值计算 随着计算机的发展，人们逐步探求用计算机来 处理和加工非数值问题：字符、图像、声音、表格等。 处理非数值数据为程序设计提出了新的课题： 数据的表示？+数据的组织存储？+数据对象的有效运算？数据结构,1、“数据结构”作为一门独立的课程在国外是从 1968年才开始设立的。 2、1968年美国唐欧

2、克努特教授开创了数据结构 的最初体系。 3、 “数据结构”在计算机科学中是一门综合性的专业基础课。 4、数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。,二、数据结构课程的研究内容,计算机处理问题： 问题的数学模型编程求解 数据结构+算法=程序设计 算法：处理问题的策略 数据结构：问题的数学模型,结构静力问题 线性方程组模型 人口增长问题 微分方程模型 更多的非数值计算问题无法用严格的数学方程来表示,1、图书馆的书目检索问题： 每本书有一条记录，记录包括:书号、书名、作者、出版社、出版年月。书目的检索按记录中的任意数据项作为关键字进行查询。 记录在数据库中按顺序排列，对象之间

3、是简单的线性关系这类数学模型称之为：线性的数据结构 算法：查找 模型：线性结构,2、人机对弈问题,将每一种可能的棋盘格局存储在计算机里，对弈过程就是根据当前棋局搜索最优的棋局对策。棋盘格局之间的关系是一颗倒立的树结构 算法：搜索最优棋盘格局 模型：树,3、煤气管道敷设问题,这是一个称之为图的结构 算法：如何规划总投资最少？ 模型：图（网）,概括的说: 数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科,三、相关的概念,1、数据：数据是客观事物的符号的表示，在计算机中指能够输入到计算机并被计算机程序处理的符号的总合。是计算机加工的“原料”。

4、如整数、实数、字符、图像、声音等。,2、数据元素：是数据结构中讨论的数据的基本单位，在计算机里通常作为一个整体进行考虑。是数据结构中讨论的基本单位。数据元素有时包含若干数据项。 如描述一个职工的纪录： 数据元素 编号 姓名 性别 年龄 职务 职称 数据项,3、数据对象：是性质相同的数据元素的集合，是数据的一个子集。 4、数据结构：是相互存在着某种逻辑关系的数据元素的集合。 带结构的数据元素的集合 指的是数据元素之间存在的关系,线性结构,树结构,图结构,集合,数据结构的定义,数据结构可以用一个二元组来定义： Data_srtuct=(D,S) D是数据元素的有限集，S是D上的关系。 例：复数的表

5、示 ： Complex=(C,R) C是两个实数的集合c1，c2，R是两个实数的关系。C2是虚部。,例：课题小组的管理程序:每个课题小组由一位老师、1至3名研究生和1至6名本科生组成。小组成员的关系是：教师指导研究生，研究生指导1-2名本科生。 Group=(P,R) 其中：P=T,G1,G2Gn,S11,S12Snm 1n3 1m2 R=R1,R2 R1= 1in 1n3 R2= 1in 1jm 1n3 1m2,数据结构包括“逻辑结构” 和“物理结构”两个层面。 逻辑结构：是对数据元素之间的逻辑关系的描述。 物理结构 ：是逻辑结构在计算机中的表示和实现（映像），故又称“存储结构”，存储结构中

6、的每一个数据元素叫做节点，节点中的数据项称为数据域。,如前面所述的职工档案管理程序，可如下定义数据元素： typedef struct int NO； char name10; int age; bool sex; char position20; char pos_rank20; char department20; RecordType ;,数据在计算机中表示方式： 顺序映像（顺序存储结构）：以相 对的存储位置表示后继 关系。如前述的职工档案管理程序，所有职工的纪录组成一张表，这张表就使一个顺序存储结构。计算机在为这张表分配存储空间时分配一个连续的存储空间。 非顺序映像（链式存储结构）：,

7、链式存储结构里相邻节点间的具体存储位置不是一个顺序关系，查询节点需要借助于指针。 在不同的编程环境中， 存储结构可有不同的描 述方法。当用高级程序 设计语言进行编程时， 通常可用高级编程语言 中提供的数据类型描述 之。,5、数据类型： 在程序设计时，我们必须先对变量进行声明，不同的数据类型他的取值范围不同，施加其上的操作也不同： 如：整型 （int） 取值范围：-32768 32767 可行的操作：+，-，*，/，% 对于浮点型来说，不可以进行% 操作。,数据类型 是一个值的集合和定义在此集合上的一组操作的总称。 尽管同一个数据类型在不同的CPU上处理的方法不同，对程序原来说他们是相同的，程序

8、员可以不考虑具体机器的实现方法。也就是说这些数据类型仅仅取决于它的逻辑特性，与在计算机内的实现无关。在数学抽象的角度上看可以称之为抽象数据类型。,抽象数据类型： （Abstract Data Type ：ADT） 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。 抽象数据类型可以用一个三元组来表示：（D，S，P） D是数据对象，S是D上的关系集，P是D的基本的操作集 。,ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名 如：定义复数的抽象数据类型,ADT Complex 数据对象： De1,e2e1,e2Re

9、alSet 数据关系： R1 | e1是复数的实数部分, e2 是复 数的虚数部分 基本操作： AssignComplex( &Z, v1, v2 ) 操作结果：构造复数 Z,其实部和虚部，分别被 以参数 v1 和 v2 的值。 DestroyComplex( &Z)操作结果：复数Z被销毁 GetReal( Z, &realPart ) 操作结果：用 realpart返回复数Z的实部值。 GetImag( Z, &ImagPart ) 操作结果：用 imgpart返回复数Z的虚部值。 Add( z1,z2, &sum ) 用sum返回两个复数z1, z2 的和值。 ADT Complex,6、

10、抽象数据类型的表示与实现 课后自己阅读。,四、算法和算法分析 算法是为了解决某类问题而规定的一个有限长的操作序列， 算法的特征： 1有穷性 2确定性 3可行性 4有输入 5有输出,有穷性：在执行有穷步骤之后一定能结束。 确定性：对于每种情况下所应执行的操作， 在算法中都有确切的规定 。 可行性：算法中的所有操作都可以通过已经 实现的基本操作运算有限次实现之 。 有输入输出：每个算法都要有算法需要加工 的数据，经加工后获得一定的结果。,1、算法设计的要求： 正确性、可读性、健壮性、效率与低存储量要求。 2、算法分析： 算法的效率：指算法的时间效率。 衡量算法效率的方法： 1、事后统计法： 2、事

11、前分析法：,一个算法所需要的时间取决于多个方面： 1、算法采用的策略 2、问题的规模 3、采用的语言 4、机器的运算速度 5、编译程序产生的机器代码的质量,一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。 如： int s; for(int i=0;in;i+) s+=i; 问题的规模是n,程序的运算工作量和n成线性的增长关系 ，或者说它可以看作是n的函数f(n)。,随着规模的增大，算法执行所需要的时间的增长率和f(n)的增长率是相同的。用时间复杂度来表示算法的时间效率， T (n) = O(f(n) 称T (n) 为算法的(渐近)时间

12、复杂度,如何估算时间复杂度？ 算法 = 控制结构 + 原操作 （固有数据类型的操作） 算法的执行时间 = 原操作的执行次数原操作的执行时间,算法的实行时间和原操作的执行次数是成正比的。从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。,如上例中，时间复杂度为O(n) 例： （a） +x;s+=x; （b）for (i=1;i=n;+i) +x;s+=x; （c）for (j=1;j=n;+j) for (k=1;k=n;k+)+x;s+=x; 基本操作： +x;s+=x; a的执行次数：1 时间复杂度O(1) b的实行次数：n 时间复杂度O(n) c的执行次数：n2 时间复杂度O(n2),例：两矩阵相乘 #define n 100 void MatrixMultiply(int Ann,int Bnn,int Cnn) int i,j,k for (i=1;i=n;+i) n+1 for (j=1;j=n;+j) n*(n+1) Cij=0; n2 for (k=1;k=n,k+) n2(n+1) Cij=Cij+aik*bkj; n3 最后的时间复杂度为O(n3)。,算法的空间效率： 是指除输入和程序之外的辅助变量所占额外空间。,thanks!,