！！#数据结构概述.PDFVIP

随着计算机技术的高速发展 其应用早已不局限于科学计算 而是更多地用于控制 管理等 非数值计算的领域 计算机处理的对象也由最初的数值发展到诸如图 文 声 像等复杂的非数 值数据 这给程序设计带来了一些新问题 为了编写一个 好的 程序 必须分析待处理对象 的特性及各处理对象之间存在的关系 这正是学习 数据结构 课程的基本目的 本章是全书的基础 主要介绍以下几方面的内容 本课程的研究内容和发展史 基本概念和术语 算法和算法分析技术 算法描述工具 数据结构概述 一般说来 使用计算机解决问题大致需要以下几个步骤 先从具体问题中抽象出适当的数 学模型 然后设计一个能够解此模型的算法 最后编写计算机程序 通过编译和测试 得到问题 的计算机解答 现实世界中的问题基本可以分为数值计算问题和非数值计算问题 对于前者 其 数学模型通常可以表示为一个或多个数学方程 而对于后者 往往很难用数学方程来描述对象 之间的关系 只能采用数据结构的方法进行描述 几个非数值计算问题 例 学校的学生信息管理系统 学生信息管理系统是学校存储和管理学生信息的最基本途径 其中记录了学生的姓名 学 号 性别 出生日期 民族等基本信息 对于学生的这些信息 最方便的管理方法就是把它们组 织成一个表 如表 所示 表学生基本信息情况表 学号 姓名 性别 出生日期 民族 专业 赵光 男 汉 计算机应用 钱伟 男 回 计算机应用 孙丽 女 汉 软件工程 李勇 男 汉 软件工程 表 中行之间存在先后顺序关系 这种关系称为线性关系 这是一种线性的数据结构 也 是一种重要的数据结构 对这种结构我们经常做的操作有查找 插入和删除等 第章绪论 例 典型的文件系统的组织结构 典型的文件系统的组织结构是一个层次结构 顶层结点代表整个系统 用根目录 表示 它的下一层代表根的各个子目录 如 等 它们的下一层结点表示其更下一级的子目录 如 目录下的 子目录等 如此类推 直到底层 如果用图表示 可以 表示成如图 所示的树状结构 这种结构具有明显的层次性 它也是某些非数值计算问题的数 学模型 是一种重要的数据结构 对这种结构经常做的操作有遍历 查找等 图文件系统的组织结构图 例 城市间的交通网络 图 示意了我国一些主要城市之间的铁路交通路线情况 我们看到 从一个城市到另一个 城市往往有多条线路可达 图 中城市之间的关系既不是线性的也不是树型的 而是呈现一种 网状关系 这种关系称为图结构或网状结构 它也是许多非数值计算问题的数学模型 而且也是 一种重要的数据结构 对这种结构经常做的操作有遍历 判断连通性等 图城市之间的交通网络示意图 上面 个例子说明 描述现实世界中许多问题的数学模型往往不是数学方程 而是诸如表 树