数据结构-第一章 绪论9.pptVIP

数据结构重要性 课程主要内容和任务 课程教学目标 发展历史1：初期数值计算问题 发展历史2：非数值计算问题 例1：学生信息检索系统（线性结构) 图 1 学生信息查询系统中的数据结构-1 例2:教学计划编排问题 第2节 数据结构中的一些基本概念 2.2 数据结构 数据的逻辑结构 数据的存储结构 2.3 数据的操作 例 数据结构三方面的关系 2.4数据类型 一维数组a[n] 二维数组b[m][n] 三维 2.6算法 + 数据结构 = 程序 例 2)文字描述 3)程序设计语言描述 3.3 算法评价 算法正确性 算法的复杂度 3.4 时间复杂度（time complexity） 3.6 算法性能选择 数据的存储结构可采用顺序存储或链式存储的方法。 顺序存储方法 顺序存储方法是把逻辑上相邻的元素存储在物理位置相邻的存储单元中，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。 链式存储方法 链式存储方法对逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过附设的指针字段来表示，由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计语言中的指针类型来实现。 除了通常采用的顺序存储方法和链式存储方法外，有时为了查找的方便还采用索引存储方法和散列存储方法。 数据的存储结构 数据的操作是定义于数据逻辑结构上的一组运算，每种数据结构都有一个运算的集合。例如对数据进行查找、插入、删除、合并、拆分、排序、统计、计算、转换、输入、输出、传送等的操作过程。 （1）逻辑结构　　表中的每一行是一个数据元素（或记录、结点），它由学号、姓名、各科成绩及平均成绩等数据项组成。表中数据元素之间的逻辑关系是：对表中任一个结点，与它相邻且在它前面的结点（亦称为直接前趋（Immediate Predecessor））最多只有一个；与表中任一结点相邻且在其后的结点（亦称为直接后继（Immediate Successor））也最多只有一个。表中只有第一个结点没有直接前趋，故称为开始结点；也只有最后一个结点没有直接后继。故称之为终端结点。例如，表中马二所在结点的直接前趋结点和直接后继结点分别是丁一和张三所在的结点，上述结点间的关系构成了这张学生成绩表的逻辑结构。 （2）存储结构　　该表的存储结构是指用计算机语言如何表示结点之间的这种关系，即表中的结点是顺序邻接地存储在一片连续的单元之中，还是用指针将这些结点链接在一起？（3）数据的运算　　在上面的学生成绩表中，可能要经常查看某一学生的成绩；当学生退学时要删除相应的结点；进来新学生时要增加结点。究竟如何进行查找、删除、插入，这就是数据的运算问题。??? 搞清楚了上述三个问题，也就弄清了学生成绩表这个数据结构。 数据的逻辑结构、数据的存储结构及数据的运算这三方面是一个整体。孤立地去理解一个方面，而不注意它们之间的联系是不可取的。??? 存储结构是数据结构不可缺少的一个方面：同一逻辑结构的不同存储结构可冠以不同的数据结构名称来标识。 【例】线性表是一种逻辑结构，若采用顺序方法的存储表示，可称其为顺序表；若采用链式存储方法，则可称其为链表；若采用散列存储方法，则可称为散列表。 数据的运算也是数据结构不可分割的一个方面。在给定了数据的逻辑结构和存储结构之后，按定义的运算集合及其运算的性质不同，也可能导致完全不同的数据结构。??? 【例】若对线性表上的插入、删除运算限制在表的一端进行，则该线性表称之为栈；若对插入限制在表的一端进行，而删除限制在表的另一端进行，则该线性表称之为队列。更进一步，若线性表采用顺序表或链表作为存储结构，则对插入和删除运算做了上述限制之后，可分别得到顺序栈或链栈，顺序队列或链队列。 在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。 不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。 所谓数据类型是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。【例】 C语言的整数类型就定义了一个整数可取值的范围（其最大值INT-MAX依赖于具体机器）以及对整数可施加的加、减、乘、除和取模等操作。 ??? 按值是否可分解，可将数据类型划分为两类：①原子类型：其值不可分解。通常是由语言直接提供。? 【例】C语言的整型、字符型等标准类型及指针等简单的导出类型；②结构类型：其值可分解为若干个成分（或称为分量）。是用户借助于