数据结构1章线性表.ppt

《数据结构1章线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构（Java版）》《数据结构（Java版）》第1章绪论第2章线性表第3章排序第4章栈与队列第5章数组和广义表第6章树和二叉树第7章查找第8章图第9章综合应用设计第1章绪论软件设计是计算机学科各个领域的核心。软件设计时要考虑的首要问题是数据的表示、组织和处理方法。数据结构设计和算法设计是软件系统设计的核心。“数据结构十算法=程序”。1.1数据结构的基本概念1.2算法与算法分析1.3Java语言简介1.1数据结构的基本概念1.1.1抽象数据类型与数据结构1.1.2数据的逻辑结构1.1.3数据的存储结构1.1.4数据的操作《数据结构（Java版）》叶核亚1.1.1抽象数据类型与数据

2、结构数据、数据元素、数据项描述客观事物的数字、字符以及所有能输入到计算机中并能为计算机接受的各种符号集合统称为数据（data）。数据是计算机程序的处理对象。表示一个事物的一组数据称作一个数据元素（dataelement），数据元素是数据的基本单位；构成数据元素的数据称作该数据元素的数据项（dataitem），数据项是数据元素的不可分割的最小单位。数据类型类型是一组值的集合。数据类型（datatype）是指一个类型和定义在这个类型上的操作集合。数据类型定义了数据元素的性质、取值范围以及对数据元素所能进行的各种操作。《数据结构（Java版）》叶核亚表1.1学生信息表classStuden

3、t{Stringnumber;Stringname;Stringsex;intage;}学号姓名性别年龄20020001王红男1820020002张明男1920020003吴宁女18《数据结构（Java版）》叶核亚抽象数据类型抽象数据类型（AbstractDataType，缩写为ADT）是指一个逻辑概念上的类型和这个类型上的操作集合。没有定义具体数据类型的数据元素称作抽象数据元素。数据结构对一个数据元素集合来说，如果在数据元素之间存在一种或多种特定的关系，则称为数据结构（datastructure）。因此，“结构”就是指数据元素之间存在的关系。《数据结构（Java版）》叶核亚1.1.

4、2数据的逻辑结构线性结构：数据元素只有一个前驱数据元素和一个后继数据元素。树结构：每个数据元素只有一个前驱数据元素，可有零个或若干个后继数据元素。图结构：每个数据元素可有零个或若干个前驱数据元素，零个或若干个后继数据元素。图1.1三种基本的数据结构《数据结构（Java版）》叶核亚1.1.3数据的存储结构数据元素在计算机中的存储表示方式称为数据的存储结构，也称为物理结构。顺序存储结构顺序存储结构是把数据元素存储在一块连续地址空间的内存中，其特点是逻辑上相邻的数据元素在物理上也相邻，数据间的逻辑关系表现在数据元素的存储位置关系上。链式存储结构指针是指向物理存储单元地址的变量。由数据元素域

5、和指针域组成的一个整体称为一个结点（node）。链式存储结构是使用指针把相互直接关联的结点（即直接前驱结点或直接后继结点）链接起来，其特点是逻辑上相邻的数据元素在物理上（即内存存储位置上）不一定相邻，数据间的逻辑关系表现在结点的链接关系上。《数据结构（Java版）》叶核亚图1.2两种存储结构《数据结构（Java版）》叶核亚1.1.4数据的操作对一种数据类型的数据元素进行的某种处理称作数据的操作。访问数据元素。统计数据元素个数。更新数据元素值。插入数据元素，在数据结构中增加新的结点。删除数据元素，将指定数据元素从数据结构中删除。查找——在数据结构中查找满足一定条件的数据元素。插入、删除

6、、更新操作都包括一个查找操作，以确定需要插入、删除、更新数据元素的确切位置。排序——在线性结构中数据元素数目不变的情况下，将数据元素按某种指定的顺序重新排列。《数据结构（Java版）》叶核亚1.2算法与算法分析1.2.1算法1.2.2算法设计1.2.3算法分析《数据结构（Java版）》叶核亚1.2.1算法算法定义有穷性——算法必须在执行有穷步之后结束。确定性——算法的每一个步骤必须是确切地定义的。输入——算法有零个或多个输入。输出——算法有一个或多个输出，即与输入有某种特定关系的量。可行性——算法中有待执行的操作和操作必须是相当基本的，即是说，它们原则上都是能够精确地进行的，而且用笔

7、和纸做有穷次就可以完成。算法的描述算法可用文字、高级程序设计语言或类同于高级程序设计语言的伪码描述。此时算法是由语义明确的操作步骤组成的有限序列，它精确地指出怎样从给定的输入信息得到要求的输出信息。《数据结构（Java版）》叶核亚【例1.3】学生信息表的顺序查找算法。图1.5学生信息表的顺序查找过程《数据结构（Java版）》叶核亚算法与数据结构算法是建立在数据的逻辑结构与存储结构上的。对于同样的逻辑结构和存储结构，根据问题的不同要求，采用不同的算法。同样的