电子教案7-3算法的数据结构设计

大学计算机,第7章：算法与数据结构基础,算法的数据结构设计,7.3,7.3算法的数据结构设计,对任意一个程序，首要任务是正确高效地组织和处理数据。计算机科学中，数据结构（DataStructure）指的是程序中数据的组织形式，连同组织这些数据的技术。数据结构可描述为Group=（D，R）D为有限个数据元素的集合R为有限个数据元素间关系的集合。在任何问题中，数据元素之间都不是孤立的，而是存在着一定的关系，这种关系称为结构(Structure)。,7.3算法的数据结构设计,数据结构主要包括三个方面：数据的逻辑结构数据的存储结构数据的运算。,7.3.1数据的逻辑结构,数据的逻辑结构是指数据元素之间的逻辑关系与数据的在计算机内部是如何存储无关数据的逻辑结构独立于计算机数据的逻辑结构是面向应用问题的，是从用户角度看到的数据的结构,7.3.1数据的逻辑结构,根据数据元素之间关系的不同特性，数据结构可分为线性数据结构和非线性数据结构。线性结构包括：数组、链表、队列和栈等。非线性结构包括：树和图型结构。非线性结构的逻辑特征是一个结点可能有多个直接前趋和直接后继。,7.3.1数据的逻辑结构,线性结构主要特征为各个数据之间有明确的、唯一的“先后”顺序，除第一个结点和最后一个结点外，其他所有结点都有且只有一个直接前趋和一个直接后继结点。在现实生活中具有线性结构的实例非常多，例如在日常生活中的排队购物，队列中的每个人都有一个明确先后次序关系。,7.3.1数据的逻辑结构,线性结构包括：数组、链表、队列和栈等。数组：位置连续的大小相等的存储单元。数组存储的数据类型都是相同的。链表：一组数据项，每一项都有一个指针指向它的下一项，最后一项指向特殊的结尾符号。链表的数据项在物理空间上不是连续的，但逻辑上是连续的。链表易于插入和删除操作。队列：一种特殊的链表或数组。处理队列元素的原则是先进先出。栈：一种特殊的链表或数组。处理栈元素的原则是先进后出。,7.3.1数据的逻辑结构,非线性结构包括：树和图型结构。树：一种层级结构。它主要特征是结点之间存在着一种层次的关系，每一个结点对应着下一层的多个结点，也就是说，数据元素之间的关系是“一对多”的关系。例如：,7.3.1数据的逻辑结构,图：一种由点及连接点的边组成的结构。任何两个结点之间都可能存在着联系，数据元素之间存在着多对多的关系。典型的图型结构就是城市交通。如果城市中有单行线路，则从城市中的一个地点A出发，可以到达N个不同的地方，从城市的M个不同的地方出发又可以到达地点A。城市交通就是一个典型的“多对多”的图型结构。,例:数据结构B(D,R)D=1,2,3,4R=(1,2),(1,3),(1,4),(2,3),(3,4),(2,4),例:数据结构C(D,R)D=1,2,3R=,7.3.1数据的逻辑结构,7.3.1数据的逻辑结构,每一种数据结构都有相应的数据组织和数据操作。例如，栈可以将数据组成一个线性序列，提供且仅提供Push（放到栈顶）pop（弹出栈顶）is-empty（检测是否为空栈）这样的数据结构有利于隐藏数据与操作的细节，让程序员只用考虑诸如入栈、出栈这样的问题，而不是实现这些操作的具体代码、存储细节。,7.3.2数据的存储结构,数据必须在计算机内存储，数据的存储结构(storagestructure)是研究数据元素和数据元素之间的关系如何在计算机中表示，是逻辑数据的存储映像，它是面向计算机的。,7.3.2数据的存储结构,1.顺序存储结构（SequentialStorageStructure）把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。,7.3.2数据的存储结构,顺序存储结构例：线性表,7.3.2数据的存储结构,2.链式存储结构（LinkedStorageStructure）链式存储结构把逻辑上相邻的两个元素存放在物理上不一定相邻的存储单元中，结点间的逻辑关系是由附加的指针字段表示的。,7.3.2数据的存储结构,2.链式存储结构（LinkedStorageStructure）通常我们把链表画成用箭头相链接的结点的序列，结点之间的箭头表示链域中的指针。,7.3.2数据的存储结构,2.链式存储结构（LinkedStorageStructure）链接存储结构特点：比顺序存储结构多用空间(存储密度小)每个节点都由数据域和指针域组成逻辑上相邻的节点物理上不必相邻。插入、删除灵活不必移动节点，只要改变节点中的指针非随机存取。,7.3.2数据的存储结构,3.索引存储结构（IndexStorageStructure）在存储结点信息的同时，建立附加的索引表。索引表中的每一项称为索引项。4.散列存储结构根据结点的关键字值计算出该结点的存储地址。即在数据元素与其在存储器上的存储位置之间建立一个映像关系F，根据关键字值和映像关系F就可以得到它的存储地址，即D=F(E)，E是要存放的数据元素的关键字值，D是该数据元素的存储位置。哈希表是散列存储结构中最常用的一种方法。,7.3.3数据的运算,数据的运算是定义在数据逻辑结构上的操作，也就是删除、检索和排序等与问题相关的处理。数据结构通常具有下列一些基