数据结构1章线性表1.ppt

《数据结构（Java版）》 《数据结构（Java版）》 第1章 绪论 第2章 线性表 第3章 排序 第4章 栈与队列 第5章 数组和广义表 第6章 树和二叉树 第7章 查找 第8章 图 第9章 综合应用设计 第1章 绪论 软件设计是计算机学科各个领域的核心。软件设计时要考虑的首要问题是数据的表示、组织和处理方法。数据结构设计和算法设计是软件系统设计的核心。 “数据结构十算法=程序”。 1.1 数据结构的基本概念 1.2 算法与算法分析 1.3 Java语言简介 1.1 数据结构的基本概念 1.1.1 抽象数据类型与数据结构 1.1.2 数据的逻辑结构 1.1.3 数据的存储结构 1.1.4 数据的操作 1.1.1 抽象数据类型与数据结构 数据、数据元素、数据项 描述客观事物的数字、字符以及所有能输入到计算机中并能为计算机接受的各种符号集合统称为数据（data）。数据是计算机程序的处理对象。 表示一个事物的一组数据称作一个数据元素（data element），数据元素是数据的基本单位；构成数据元素的数据称作该数据元素的数据项（data item），数据项是数据元素的不可分割的最小单位。 数据类型 类型是一组值的集合。数据类型（data type）是指一个类型和定义在这个类型上的操作集合。数据类型定义了数据元素的性质、取值范围以及对数据元素所能进行的各种操作。 表1.1 学生信息表 class Student { String number; String name; String sex; int age; } 抽象数据类型 抽象数据类型（Abstract Data Type，缩写为ADT）是指一个逻辑概念上的类型和这个类型上的操作集合。没有定义具体数据类型的数据元素称作抽象数据元素。 数据结构 对一个数据元素集合来说，如果在数据元素之间存在一种或多种特定的关系，则称为数据结构（data structure）。因此，“结构”就是指数据元素之间存在的关系。 1.1.2 数据的逻辑结构 线性结构：数据元素只有一个前驱数据元素和一个后继数据元素。 树结构：每个数据元素只有一个前驱数据元素，可有零个或若干个后继数据元素。 图结构：每个数据元素可有零个或若干个前驱数据元素，零个或若干个后继数据元素。 1.1.3 数据的存储结构 数据元素在计算机中的存储表示方式称为数据的存储结构，也称为物理结构。 顺序存储结构 顺序存储结构是把数据元素存储在一块连续地址空间的内存中，其特点是逻辑上相邻的数据元素在物理上也相邻，数据间的逻辑关系表现在数据元素的存储位置关系上。 链式存储结构 指针是指向物理存储单元地址的变量。由数据元素域和指针域组成的一个整体称为一个结点（node）。链式存储结构是使用指针把相互直接关联的结点（即直接前驱结点或直接后继结点）链接起来，其特点是逻辑上相邻的数据元素在物理上（即内存存储位置上）不一定相邻，数据间的逻辑关系表现在结点的链接关系上。 图1.2 两种存储结构 1.1.4 数据的操作 对一种数据类型的数据元素进行的某种处理称作数据的操作。 访问数据元素。 统计数据元素个数。 更新数据元素值。 插入数据元素，在数据结构中增加新的结点。 删除数据元素，将指定数据元素从数据结构中删除。 查找——在数据结构中查找满足一定条件的数据元素。插入、删除、更新操作都包括一个查找操作，以确定需要插入、删除、更新数据元素的确切位置。 排序——在线性结构中数据元素数目不变的情况下，将数据元素按某种指定的顺序重新排列。 1.2 算法与算法分析 1.2.1 算法 1.2.2 算法设计 1.2.3 算法分析 1.2.1 算法 算法定义 有穷性——算法必须在执行有穷步之后结束。 确定性——算法的每一个步骤必须是确切地定义的。 输入——算法有零个或多个输入。 输出——算法有一个或多个输出，即与输入有某种特定关系的量。 可行性——算法中有待执行的操作和操作必须是相当基本的，即是说，它们原则上都是能够精确地进行的，而且用笔和纸做有穷次就可以完成。 算法的描述 算法可用文字、高级程序设计语言或类同于高级程序设计语言的伪码描述。此时算法是由语义明确的操作步骤组成的有限序列，它精确地指出怎样从给定的输入信息得到要求的输出信息。 【例1.3】 学生信息表的顺序查找算法。 图1.5 学生信息表的顺序查找过程 算法与数据结构 算法是建立在数据的逻辑结构与存储结构上的。 对于同样的逻辑结构和存储结构，根据问题的不同要求，采用不同的算法。 同样的数据结构，不同的存储结构，则采用的算法必然不同。例如，存储结构不同的线性表其排序算法必然不同。 算法与程序 算法用抽象的语言描述解决特定问题的每一步的操作