常用数据结构及其运算1.pptVIP

第2章 常用数据结构及其运算 2.1 概述 2.1.1 数据和数据结构 2.1.2 算法的描述和评价 2.2 线性表 2.2.1 线性表的定义及操作 2.2.2 线性表的顺序存储结构 2.2.3 线性表的链式存储结构 2.2.4 循环链表和双向链表 2.3 栈和队列 2.3.1 栈 2.3.2 队列 2.4 数组 习题 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。 2．数据元素（data element） 数据元素是数据集合中的一个个体，它是数据的基本单位。 数据元素可以是一个数或字符串，也可以是若干数据项的组合(数据的最小单位)。在这种情况下，通常把数据元素称为记录。如P22表2-1所示的学生学籍登记表，在这个表中每一个学生的学籍信息为一个数据元素，每一个元素由学号、姓名、性别、民族、籍贯、专业六个数据项组成。 4.数据类型 数据类型是指程序语言中允许的变量类型。 程序中出现的每一个变量必须与一个且仅与一个 数据类型相联系。各种语言都规定了它允许的数 据类型。 数据类型分为基本数据类型和结构数据类型。 5.数据结构 数据结构就是研究数据及数据元素之间关系的一门学科。它包括三个方面的内容：数据的逻辑结构、数据的存储结构、数据的运算。 a.数据的逻辑结构独立于计算机，是数据本身所固有的。 b.存储结构是逻辑结构在计算机存储器中的映像，必须依赖于计算机。 c.运算是指所施加的一组操作总称。 (1) 数据的逻辑结构(数据结构) ? 数据的逻辑结构就是数据元素之间的逻辑关系。可以用一个二元组，给出其形式定义为 S =(D，R) 其中，D是数据元素的有限集合，R是数据元素之间的关系集合。 例：在计算机科学中，复数可取如下定义：复数是一种数据结构 Complex=(D,R) 其中：D是含两个实数的集合{c1,c2}；R={P}，而P是定义在集合C上的一种关系{c1,c2}，其中有序偶c1,c2表示c1是复数的实部，c2是复数的虚部。 (2)数据的存储结构 数据的逻辑结构是从逻辑上来描述数据元素之间的关系的，是独立于计算机的。然而讨论数据结构的目的是为了在计算机中实现对它的处理。因此还需要研究数据元素和数据元素之间的关系如何在计算机中表示，这就是数据的存储结构。 计算机的存储器是由很多存储单元组成的，每个存储单元有惟一的地址。数据的存储结构要讨论的就是数据结构在计算机存储器上的存储映像方法。 从存储结构划分数据结构 数据结构从存储结构划分为： a.顺序存储结构 所有元素存放在一片连续的存储单元中，逻辑上相邻的元素存放到计算机内存仍然相邻。 b. 链式存储结构 所有元素存放在可以不连续的存储单元中，但元素之间的关系可以通过地址确定，逻辑上相邻的元素存放到计算机内存后不一定是相邻的。 c. 索引存储结构。 使用该方式存放元素的同时，还建立附加的索引表，索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址），其中的关键字是能唯一标识一个结点的那些数据项。 d. 散列存储结构。 通过构造散列函数，用函数的值来确定元素存放的地址。 三、 算法的描述和评价 2. 算法的描述 3. 算法的评价—衡量算法优劣的标准 正确性(Correctness ) 算法应满足具体问题的需求。 可读性(Readability) 算法应该好读。以有利于阅读者对程序的理解，便于调试和修改。 健状性(Robustness) 算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 效率与存储量需求 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。 在算法是“正确性”（ + 易读性 + 健壮性）的前提下，评价算法主要有两个指标： (1) 时间复杂度（性）：依据算法编制成程序后，在计算机上运行时所消耗的时间。 (2