数据结构第一章_绪论

《数据结构第一章_绪论》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构北京联合大学信息学院2数据结构的兴起和发展内容提要1数据结构的研究对象2数据结构的基本概念3算法及算法分析43数据结构的创始人——克努思1938年出生，25岁毕业于加州理工学院数学系，博士毕业后留校任教，28岁任副教授。30岁时，加盟斯坦福大学计算机系，任教授。从31岁起，开始出版他的历史性经典巨著：TheArtofComputerProgramming他计划共写7卷，然而出版三卷之后，已震惊世界，使他获得计算机科学界的最高荣誉图灵奖，此时，他年仅36岁。41.1数据结构的兴起和发展程序设计的实质是什么?数据表示：将数据存储在计算机中数据处理：处

2、理数据，求解问题数据结构问题起源于程序设计数据结构随着程序设计的发展而发展1.无结构阶段2.结构化阶段：数据结构＋算法＝程序3.面向对象阶段：（数据结构＋算法）＝程序数据结构的发展并未终结1.2数据结构的研究对象计算机求解问题:问题→抽象出问题的模型→求模型的解问题——数值问题、非数值问题数值问题→数学方程非数值问题→数据结构例1学籍管理问题——表结构学号姓名性别出生日期政治面貌0001王军男1983/09/02团员0002李明男1982/12/25党员0003汤晓影女1984/03/26团员……………完成什么功能?各表项之间是什么关系？例2人机对弈问题

3、——树结构如何实现对弈?各格局之间是什么关系？…………..……..………...……例3教学计划编排问题——图结构C4,C5,C6数据库原理C7C2,C4计算机原理C6C3,C4数据结构C5C1,C2程序设计C4C1离散数学C3无计算机导论C2无高等数学C1先修课课程名称编号C1C2C3C4C6C5C7如何表示课程之间的先修关系？数据结构是研究非数值问题中计算机的操作对象以及它们之间的关系和操作的学科。1.3数据结构的基本概念数据：所有能输入到计算机中并能被计算机程序识别和处理的符号集合。数值数据：整数、实数等非数值数据：图形、图象、声音、文字等数据元素：

4、数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据项：构成数据元素的不可分割的最小单位。数据对象：具有相同性质的数据元素的集合。1.3数据结构的基本概念数据、数据元素、数据项之间的关系包含关系：数据是由数据元素组成，数据元素是由数据项组成。数据元素是讨论数据结构时涉及的最小数据单位，其中的数据项一般不予考虑。1.3数据结构的基本概念数据结构：相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。逻辑结构：指数据元素之间逻辑关系的整体。关联方式或邻接关系数据的逻辑结构是从具体问题抽象出来的数据模型学籍管理问题

5、中，表项之间的逻辑关系指的是什么？人机对弈问题中，格局之间的逻辑关系指的是什么？教学计划编排问题中，课程之间的逻辑关系指的是什么？1.3数据结构的基本概念数据结构：相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。逻辑结构：指数据元素之间逻辑关系的整体。存储结构：又称为物理结构，是数据及其逻辑结构在计算机中的表示。内存存储结构实质上是内存分配，在具体实现时，依赖于计算机语言。1.3数据结构的基本概念数据结构从逻辑上分为四类：⑴集合：数据元素之间就是“属于同一个集合”；1.3数据结构的基本概念⑵线性结构：数据元素之间存在

6、着一对一的线性关系；1.3数据结构的基本概念树结构：数据元素之间存在着一对多的层次关系；1.3数据结构的基本概念图结构：数据元素之间存在着多对多的任意关系。1.3数据结构的基本概念通常有两种存储结构：1.顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。…batcateat…起始地址例：（bat,cat,eat）1.3数据结构的基本概念2.链接存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示。0200020803000325…………bat0200cat0325eat∧例：（ba

7、t,cat,eat）1.3数据结构的基本概念数据的逻辑结构属于用户视图，是面向问题的，反映了数据内部的构成方式；数据的存储结构属于具体实现的视图，是面向计算机的。一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构，其数据处理的效率往往是不同的。1.3数据结构的基本概念数据的逻辑结构数据的存储结构顺序存储链式存储集合线性结构树结构图结构非数值问题数据表示数据的操作：插入、删除、修改、检索、排序等1.4算法及算法分析1.算法（Algorithm）:是对特定问题求解步骤的一种描述，是指令的有限序列。2.算法的五大特性：⑴输入：一个算法有零个或多个

8、输入。⑵输出：一个算法有一个或多个输出。⑶有穷性：一个算法必须总是在执行有穷步之