是存储在计算机内有结构的数据的集合页.pdf

数据结构概述 在计算机科学中，数据结构是指存储在计算机中的有结构的数据的集合。它是计算机科学中最基本和最重要的概念之一。数据结构主要包括逻辑结构和存储结构两个方面。 一、逻辑结构 逻辑结构是对数据元素之间逻辑关系的描述，它与数据在计算机中存储方式无关。根据数据元素之间的不同特性，可以对数据的逻辑结构进行分类。常见的逻辑结构有： 1. 线性结构：有且只有一个开始节点和终端节点，并且所有节点最多只有一个直接前驱和一个直接后继。线性表就是一个典型的线性结构，它有四个基本特征：每个节点只有一个直接前驱和一个直接后继，除了最后一个元素外其他数据元素都有唯一的“后继”，除了第一个元素外其他数据元素都有唯一的“前驱”。 2. 非线性结构：一个节点元素可能对应多个直接前驱和直接后驱。常见的非线性结构有树和图。 3. 集合结构：就是数学中所学的集合，数据元素之间除了“属于同一个集合”的联系之外，没有其他关系。 4. 树形结构：数据元素之间存在着一对多的关系，数据之间存在层次关系。除了根节点元素外，其余的元素都有唯一一个前驱元素，并且可以有多个后继元素。 5. 图结构：数据元素之间存在多对多的关系，每个数据元素可以有多个前驱元素和多个后继元素。 二、存储结构 存储结构是数据结构在计算机中表示方法。常见的存储结构有： 1. 顺序存储结构：借助数据元素在存储器中的相对位置来表示元素之间的逻辑关系。通常用数组来表示。特点：优点是节省存储空间，因为分配给数据的存储单元全用来存储节点的数据，节点之间的逻辑关系没有占用额外的存储空间。缺点是插入和删除元素需要移动元素，效率较低。 2. 链式存储结构：在数据元素上附加指针域并借助指针来只是数据元素之间的逻辑关系。通常用指针类型来表示。特点：优点是便于修改，在进行插入和删除运算时仅需修改相应数据元素的指针值而不必移动数据元素。缺点是与顺序存储结构相比，链式存储结构的存储空间利用率低，因为除了用于数据元素的存储空间外，还需要额外的空间来存储数据之间的逻辑关系。 3. 索引存储结构：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。索引表由若干索引项组成。特点：优点是可以对节点进行随机访问，在进行插入删除运算时只需要改动存储在索引表中数据元素的存储地址，有较高的数据修改和运算效率。缺点是增加了索引表，减低了存储空间的利用率。 4. 哈希（散列）存储结构：根据元素的关键字通过哈希函数直接计算出数据元素的存储地址。