第5章数据结构基础5.1引言5.2线性结构5.3树形结构5.45.4图形结构图形结构5.5内部排序5.6检索（查找）5.1引言5.1.15.1.1什么是数据结构什么是数据结构5.1.25.1.2数据的逻辑结构数据的逻辑结构5.1.35.1.3数据的存储结构数据的存储结构5.1.45.1.4数据的运算数据的运算应用举例——学籍档案管理学生信息表：学生信息表：每个学生的信息占一行，结构类型每个学生的信息占一行，结构类型表中依据学号的大小存在着一种前后关系，表中依据学号的大小存在着一种前后关系，即线性结构即线性结构操作通常是插入、删除、更新某个学生的信操作通常是插入、删除、更新某个学生的信息，和按条件检索某个学生的信息等息，和按条件检索某个学生的信息等其它应用举例计算机和人对奕问题计算机和人对奕问题对弈的规则和策略对弈的规则和策略----------算法算法棋盘及棋盘的格局棋盘及棋盘的格局----------模型、树模型、树多叉路口交通灯的管理问题多叉路口交通灯的管理问题路口、通路、交通灯颜色路口、通路、交通灯颜色------------图图5.1.1什么是数据结构研究数据之间的相互关系研究数据之间的相互关系逻辑结构逻辑结构存储结构（物理结构）存储结构（物理结构）数据的运算数据的运算数据类型数据类型原子类型原子类型->->不可分解不可分解结构类型结构类型->->原子类型构造而成原子类型构造而成5.1.2数据的逻辑结构5.1.3数据的存储结构数据的逻辑结构在计算机存储器中的实数据的逻辑结构在计算机存储器中的实现，也称现，也称物理结构物理结构顺序映射方式顺序映射方式链接映射方式链接映射方式索引映射方式索引映射方式散列映射方式散列映射方式1、顺序存储用一组连续地址依次存储类型相同、有序用一组连续地址依次存储类型相同、有序的数据元素的集合的数据元素的集合可以采用索引的方式访问其中的元素可以采用索引的方式访问其中的元素一维数组描述一维数组描述数组名称为数组名称为bb用用b[0]b[0]表示第一个元素表示第一个元素用用b[1]b[1]表示第二个元素表示第二个元素…………[][]内的数是元素的索引下标内的数是元素的索引下标可以是常量也可以是变量可以是常量也可以是变量也可以用循环结构访问数组元素也可以用循环结构访问数组元素b+b+b+b+b+插入删除2、链式存储链表是一个链式存储的线性表链表是一个链式存储的线性表链表将物理上不连续的结点连接起来链表将物理上不连续的结点连接起来链表中的每个元素习惯上被称为链表中的每个元素习惯上被称为结点，结点，结点包结点包含两部分：含两部分：数据数据指针指针((指针即是存储下一个相同类型元素的地址指针即是存储下一个相同类型元素的地址))链表包括单链表、双链表、循环链表链表包括单链表、双链表、循环链表…………，在此只讨论单链表，在此只讨论单链表单链表即每个即每个节点节点仅有一个指向后继节点的链仅有一个指向后继节点的链通常使用一个指针变量指向第一个元素，称通常使用一个指针变量指向第一个元素，称为链表的为链表的头指针头指针通过头指针可以顺序访问其后的所有节点通过头指针可以顺序访问其后的所有节点链表的最后一个元素包含一个链表的最后一个元素包含一个空指针空指针，标识，标识链表的结束链表的结束链表的操作对链表的操作很多：对链表的操作很多：插入节点插入节点删除节点删除节点查找列表查找列表检索列表检索列表遍历列表遍历列表…………注意：注意：（（11）当向表尾插入、向表头插入、）当向表尾插入、向表头插入、向空表插入节点时，要做特殊处理向空表插入节点时，要做特殊处理（（22）删除第一个节点、只有一个节）删除第一个节点、只有一个节点时，要做特殊处理点时，要做特殊处理注意：注意：（（11）当向表尾插入、向表头插入、）当向表尾插入、向表头插入、向空表插入节点时，要做特殊处理向空表插入节点时，要做特殊处理（（22）删除第一个节点、只有一个节）删除第一个节点、只有一个节点时，要做特殊处理点时，要做特殊处理5.1.4数据的运算5.2线性结构5.2.1...
