高等数据结构与算法幻灯片.pptVIP

教材： 数据结构(C语言版) 严蔚敏 清华大学出版社 参考书： 数据结构——使用C语言 朱战立 西安交通大学出版社 数据结构与算法 齐德昱 清华大学出版社 数据结构与算法——C++版(第2版) Adam Drozdek 清华大学出版社 课程与考试安排： 第8、11、12章不作要求 有**号的小节不作要求 期末成绩和平时成绩各占60％和40％ 第一章 绪言 1.1.1 什么是数据结构 程序设计=数据模型+算法 程序设计：为计算机处理问题编制的一组指令集 数据模型：现实问题的抽象 算法：处理问题的策略 数值计算问题——数学模型是一组线性或非线性的代数方程组或微分方程组 非数字计算问题(包括管理、控制、数据处理等)——数学模型是数据结构 例1 书目自动检索系统 登录号： 书名： 作者名： 分类号： 出版单位： 出版时间： 价格： 书目卡片 书目文件 按书名 按作者名 按分类号 索引表 线性表 例2 人机对奕问题 树 …….. …….. …... …... …... …... 多叉路口交通灯管理问题 C E D A B AB AC AD BA BC BD DA DB DC EA EB EC ED 图 数据结构定义: 是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科 1.1.2 为什么要学数据结构 程序设计的需要 计算机专业基础课 编译程序、操作系统、数据库系统和大型应用程序 1.1.3 学什么 掌握各种类型的数据结构 掌握查找和排序操作 学会用算法去处理问题 学会用C语言去实现算法 1.1.4 怎么学 重视实践环节，包括编程和上机 1.2 基本概念和术语 数据(data)——所有能输入到计算机中去的描述客观事物的符号，数据是信息的载体 数据元素(data element)——数据的基本单位，数据中的一个“个体” 数据项(data item)——数据的最小单位，数据元素是数据项的组合，有组合项和原子项之分 数据对象(data object)——性质相同的数据元素的集合，如整数、所有书目信息等 数据结构(data structure)——数据元素和数据元素关系的集合，数据元素相同而关系不同的数据结构是不同的数据结构 根据数据元素间关系的基本特性，有四种基本数据结构 （集合）——数据元素间除“同属于一个集合”外，无其它关系 线性结构——一个对一个，如线性表、栈、队列 树形结构——一个对多个，如树 图状结构——多个对多个，如图 数据结构的形式定义为： 数据结构是一个二元组　　　Data_Structures = ( D,S ) 　　其中：D是数据元素的有限集，　　　　　S是D上关系的有限集。 数据的逻辑结构—只抽象反映数据元素的逻辑关系 数据的存储（物理）结构—数据的逻辑结构在计算机存储器中的实现 数据的逻辑结构与存储结构密切相关 算法设计 逻辑结构 算法实现 存储结构 存储结构分为： 顺序存储结构——借助元素在存储器中的相对位置来表示 数据元素间的逻辑关系 链式存储结构——借助指示元素存储地址的指针表示数据 元素间的逻辑关系 数据元素的实现 数值321 可用位串 101000001 表示，字母A可用位串 001000001 表示 关系的实现 元素n …….. 元素i …….. 元素2 元素1 Lo Lo+m Lo+(i-1)*m Lo+（n-1)*m 存储地址 存储内容 Loc(元素i)=Lo+（i-1)*m 顺序存储 1536 元素2 1400 元素1 1346 元素3 ∧ 元素4 1345 h 存储地址 存储内容 指针 1345 元素1 1400 1346 元素4 ∧ ……. …….. ……. 1400 元素2 1536 ……. …….. ……. 1536 元素3 1346 链式存储 h 不同的编程环境中，数据存储结构可有不同的描述方法： 以上用的是计算机的编码及内存来描述 还可用高级程序语言提供的数据类型来描述 关系 顺序存储结构 int Long_int[3];[ 链式存储结构 int *Long_int[3]; 数据元素 Long_int[0]=4234; 1.3 抽象数据类型 数据类型(data type)——一个值的集合和定义在此集合上的一组操作的总称 抽象数据类型(abstract data type,ADT)——一个数学模型以及定义在此数学模型上的一组操作 抽象不同语言不