第5章 数据结构基础VIP免费

第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...