2章数据结构及应用概念及顺序表.pptVIP

第2章数据结构及应用概念及顺序表 西安交通大学计教中心 思考问题 数据结构要研究什么问题？ 什么是线性数据结构和线性表？ 如何描述线性表？ 线性表在计算机中如何存放？有几种存储形式？它们的特点是什么？ 如何处理线性数据结构中的数据？ …… 数据结构问题的由来 计算机求解问题的过程步骤： 数据结构 数据结构是计算机的专业技术基础课。它研究的主要问题有： ?分析数据（计算机加工的对象）的特征 ?选择适当逻辑存储结构和物理存储结构 ?在存储结构的基础上实现对数据的操作 2.1 数据结构基本概念 1．数据（data） 数据是指能够输入到计算机中，并被计算机识别和处理的符号的集合。 2．数据元素（data element） 数据元素是组成数据的基本单位。数据元素是一个数据整体中相对独立的单位。但它还可以分割成若干个具有不同属性的项（字段），故不是组成数据的最小单位 数据结构（data structure） 是指相互之间存在一种或多种特定关系的数据元素所组成的集合。数据结构包含三个方面的内容，即数据的逻辑结构，数据的存贮结构和对数据所施加的运算。 数据的逻辑结构 它是描述数据间的顺序（逻辑）关系，只是抽象地反映数据元素的结构，而不管它们在计算机中如何存放。一般用下列二元组来描述： DS=（D，R） 其中： D：是数据元素的有限集合； R：是数据元素之间关系的集合。 举例 课题组由1名教师、1~3名研究生、1~6名本科生组成；成员关系是：教师指导研究生、研究生指导1~2名本科生。 定义DS如下： Group=（D，R） 其中： 数据的存储结构 又称物理结构 是指数据结构在计算机中的表示(又称映象),即数据在计算机中的存放。 逻辑结构和存储结构的关系 数据的逻辑结构是从逻辑关系（某种顺序）上观察数据，它是独立于计算机的；可以在理论上、形式上进行研究、推理、运算等各种操作。 数据的存储结构是逻辑结构在计算机中的实现，是依赖于计算机的；离开了机器，则无法进行任何操作。 任何一个算法的设计取决于选定的逻辑结构；而算法的最终实现依赖于采用的存储结构。 数据存储结构分类 顺序存储结构 链式存储结构 索引存储结构 散列存储结构 顺序存储结构 把数据元素按某种顺序存放在一块连续的存储单元中的存储形式。数据结点结构: 链式存储结构 以链表形式将数据元素存放于任意存储单元中，可连续存放，也可以不连续存放，以指针实现链表间的联系。数据结点结构: 索引存储结构 数据按索引形式存放。存储时分为：数据项和索引号；通过索引表记录逻辑号（记录号）和物理号（存储序号）之间的对应关系。 数据结点结构: 散列存储结构 在数据元素与存储位置之间建立一种存储关系F，根据这种关系F，已知元素E，就可以得到它的存储地址，即D=F（E）。 哈希查找中的哈希表就是这样一种存储结构。 特点： 数据元素间无内在联系； 存储形式不定。 数据运算 数据运算是指对存放在物理结构上的数据,按定义的逻辑结构进行的各种操作。 常见操作有： 输入、检索、插入、删除、修改、排序等。 数据结构分类 数据结构基本类型 线性结构 —— 通迅录、成绩单、花名册 树形结构 —— 电子字典、家谱、目录 图状结构 —— 交通线路、通信网络 算法（algorithm） 通俗地讲，算法就是一种解题的方法。更严格地说，算法是由若干条指令组成的有穷序列，它必须满足下述条件（也称为算法的五大特性）： ⑴输入：具有0个或多个输入的外界量（算法开始前的初始量） ⑵输出：至少有一个输出，是算法执行完后的结果。 ⑶有穷性：每条指令的执行次数必须是有限的。 ⑷确定性：每条指令的含义都必须明确，无二义性。 ⑸可行性：每条指令的执行时间都是有限的。 算法分析 1．时间复杂度 一个算法花费的时间与算法中语句的执行次数成正比，哪个算法中语句执行次数多，它花费时间就多。 数据结构中数据元素个数n称为问题的规模，当n不断变化时，语句的执行次数也会变化。一个算法中的时间复杂度一般用语句执行次数的数量级来衡量。 例如： for(i=1; i=n; i++)  for(j =1; j=i; j++) d[i][j]=data[i][j]+1; 算法的评价 算法评价的标准： 时间复杂度 指在计算机上运行该算法所花费的时间。用“O（数量级）”来表示，称为“阶”。常见的时间复杂度有： O（1） O（l