数据结构第01周.ppt

《数据结构第01周.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、数据结构（绪论）学习内容1数据结构的定义2数据的逻辑结构3数据的存储结构4算法描述以及分析数据结构的基本概念和术语计算机的处理对象：早期：主要用于数值计算，处理的对象为数字，字符。后来：处理逐渐扩大到非数值计算领域,处理的对象为文字，图象和声音等。数据（data)是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的集合。数据元素（dataelement）是数据的基本单位，在程序中作为一个整体而加以考虑和处理。数据元素又为元素、结点、顶点或记录。数据项（dataitem）是数据不可分割的最小单位。

2、通常作为数据元素的分量，数据项又称为字段或域。练习题：请在以下的学生成绩表中指出数据、数据元素和数据项学号姓名数学分析普通物理高等代数平均成绩880001丁一90859590880002马二80859085880003张三95919995880004李四70848680880005王五91849289…..……………数据学号姓名数学分析普通物理高等代数平均成绩880001丁一90859590880002马二80859085880003张三95919995880004李四70848680880005王五91849289…..……………数

3、据元素880002马二80859085数据项90数据结构的定义数据的逻辑结构数据结构数据的存储结构数据的运算数据结构指的是数据以及相互之间的关系，包括逻辑结构、存储结构和数据的运算。数据元素之间的相互关系称为数据的逻辑结构，其可以看作是从具体问题抽象出来的数学模型。根据数据元素间关系的基本特性，有四种基本数据逻辑结构（集合）——数据元素间除“同属于一个集合”外，无其它关系线性结构——一个对一个，如线性表、栈、队列树形结构——一个对多个，如树图状结构——多个对多个，如图数据的逻辑结构登录号：书名：作者名：分类号：：：图书信息按书名按作者

4、名按分类号索引表例1：图书馆的书目检索系统自动化问题什么是线形关系？线性结构的特点：（1）存在唯一的一个被称做“第一个”的记录（2）存在唯一的一个被称做“最后一个”的记录（3）除第一个记录之外，表中的每个记录只有一个与它相邻的而且处在它前面的记录（4）除最后一个记录之外，表中的每个记录只有一个与它相邻的而且处在它后面的记录。线性结构例2计算机和人对奕问题树……..……..…...…...…...…...某大学专业设置问题。如图所示，一所大学可以下设多个学院，一个学院又办有多个专业，显然这种关系用“树”型结构来表示更形象。树型结构通常用

5、来表示结点的分层组织，结点之间是一对多的关系。XX大学机械工程学院计算机科学学院电气工程学院文理学院机械制造计算机应用网络工程自动控制材料工程商务英语通讯工程应用数学树型结构的另外一个例子例3：田径赛的时间安排问题参赛选手比赛项目表丁一跳高跳远100米张三标枪100米跳远李四跳高铅球王五铅球100米标枪假设某校的田径选拔赛共设五个项目的比赛，即跳高、跳远、标枪、铅球、100米短跑，规定每个选手至多参加三个项目的比赛。现有四名选手报名比赛，选手所选择的项目如右图所示。现在要求设计一个竞赛日程安排表，使得在尽可以短的时间内安排完比赛。例3

6、田径赛的时间安排问题图丁一跳高跳远100米张三标枪100米跳远李四跳高铅球王五铅球100米标枪跳高跳远铅球标枪100米跳高标枪跳远铅球100米安排竞赛项目的数据结构模型参赛选手比赛项目表顺序存储结构链式存储结构数据的逻辑结构在计算机中的映像称为数据的物理结构，又称为存储结构。数据的存储（物理）结构存储结构顺序存储：用一组连续的存储单元依次存放一个线性表的各个数据元素。数据元素的逻辑结构与物理结构存在着一一对应的关系。类比假设一个班有30个同学，学号为1-30，现在有30个房间，房间号也为1-30。按找学号的顺序依次给每个同学分配房间，

7、那么知道某个同学的学号，也就知道了这个同学的房间号。线性表的第k个数据元素的存储地址为：Loc(ak)=Loc(a1)+(k-1)*C其中：Loc(a1)是线性表的第一个数据元素的储存地址C为每个元素占据的存储单元的数目。链式存储结构特点：用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai，除存储本身信息外，还需存储其后面元素的地址信息每个数据元素均有两个部分：数据域：元素本身信息指针域：指示后面元素的存储位置1536元素21400元素11346元素3∧元素41345h存储地址

8、存储内容指针1345元素114001346元素4∧…….……..…….1400元素21536…….……..…….1536元素31346链式存储h数据的逻辑结构数据的存储结构数据的运算：检索、排序、插入、删除、修改等线性结