本章要点：5.1数据结构基础5.2常用的数据结构5.3Python序列数据概述5.4序列数据的基本操作5.5列表5.6元组5.7集合5.8字典（映射）5.9算法基础5.10常用的查找和排序算法5.11应用举例第5章组合数据和数据结构
5.1数据结构基础著名的计算机科学家尼克劳斯?沃思（NikiklausWirth）指出：程序=算法+数据结构算法是执行特定任务的方法数据结构是一种存储数据的方式，有助于求解特定的问题组成数据元素的项称之为数据项，数据项是数据的最小标识单位，又称为字段（Field）或者域（Field）例如，学生信息由学号、姓名、性别、出生年月、专业等组成数据（Data）是能够被计算机处理的对象集合。数据由数据元素（DateElement）组成，数据元素包含数据项（DataItem）在学生档案管理系统中，每位学生信息是数据的基本单位，称之为数据元素，也称为元素（Element）、节点（Node）或者记录（Record）
数据结构数据的运算结构数据的运算结构反映在数据的逻辑结构上定义的操作算法，例如检索、插入、删除、更新和排序等数据结构通常由三个部分组成：数据的逻辑结构，数据的存储结构和数据的运算结构数据的逻辑结构数据的逻辑结构反映数据元素之间的逻辑关系。数据的逻辑结构主要包括线性结构（一对一的关系）、树形结构（一对多的关系）、图形结构（多对多的关系）、集合等数据的物理结构数据的物理结构反映数据的逻辑结构在计算机存储空间的存放形式，即数据结构在计算机中的表示。其具体的实现方法包括顺序、链接、索引、散列等多种形式。一种数据结构可以由一种或者多种物理存储结构实现010302
数据的逻辑结构（1）线性表、队列、栈等数据结构属于线性结构反映数据元素之间的逻辑关系，与他们在计算机中的存储位置无关数据结构可以表示为DS=(D,R)，其中DS表示数据结构，D表示数据集合，R表示关系（Relation）集合三口之家的成员的数据逻辑结构可以表示如下：DS=(D,R)D={父亲,母亲,孩子}R={(父亲,母亲),(父亲,孩子),(母亲,孩子)}数据的逻辑结构可以分为线性结构和非线性结构线性结构中的元素节点具有线性关系。如果从数据结构的语言来描述，线性结构具有以下特点。（1）线性结构是非空集。（2）线性结构有且仅有一个开始节点和一个终端节点。（3）线性结构所有节点都最多只有一个直接前趋节点和一个直接后继节点
数据的逻辑结构（2）常用的数据逻辑结构包括如下几种方式，如图所示。（1）集合：数据结构中的元素之间除了“同属一个集合”的相互关系外，别无其他关系。（2）线性结构：数据结构中的元素存在一对一的相互关系。（3）树形结构：数据结构中的元素存在一对多的相互关系。（4）图形结构：数据结构中的元素存在多对多的相互关系非线性结构中的各元素节点之间具有多个对应关系。如果从数据结构的语言来描述，非线性结构具有以下特点。（1）非线性结构是非空集。（2）非线性结构的一个节点可能有多个直接前趋节点和多个直接后继节点。在实际应用中，数组、广义表、树结构和图结构等数据结构属于非线性结构
数据的物理结构数据的物理结构是指逻辑结构在计算机存储空间的存放形式。数据的物理结构是数据结构在计算机中的实现方式，它包括数据元素的机内表示和关系的机内表示实现逻辑数据结构的常用方法包括顺序、链接、索引、散列等。一种逻辑数据结构可以表示成一种或者多种物理存储结构数据元素之间的关系在计算机内部的存储结构通常有两种方式：顺序存储结构和链式存储结构顺序映像借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系非顺序映像借助指示元素存储位置的指针来表示数据元素之间的逻辑关系
常用算法基于数据结构的常用算法包括以下几种。（1）检索：在数据结构中查找满足给定条件的节点。（2）插入：在数据结构中增加新的节点。（3）删除：从数据结构中删除指定节点。（4）更新：改变指定节点的一个或者多个字段的值。（5）排序：按某种指定的顺序重新排列节点（从而可以提高其他算法的操作效率）数据的算法基于数据的逻辑结构，但具体实现要在物理存储结构上进行
5.2常用的数据结构5.2.1线性表5.2.2队列5.2.3栈5.2.4树5.2.5图5.2.6堆5.2.7散列表
线性表线性表（LinearList）是最基本的一种数据结构，是具有相同特性的数据元素的有限序列，通常记做(a1,a2,…,an）。其中a1无前趋，an无后继，其他每个元素都有一个前趋和后继线性表的物理存储结构主要有两种：顺序存储结构和链式存储结构，前者称为顺序表，后者称为线性链表顺序存储结构使用一组地址连续的存储单元依次存储线性表的数据元素顺序表的优点是查找和访问元素速度快，