文档介绍：1 第一章绪论 1--1 什么是数据结构 1. 例子例一. 学生成绩表( 线性表) 学号姓名语文数学物理化学 001 张三 76 80 90 87 002 李四 65 74 80 60 003 王五 59 70 76 60 例二对奕问题( 树结构) 例三多叉路口交通灯的管理问题( 图的结构)CD BE A 2. 数据结构: 带有结构的数据元素集合及其运算称为数据结构. 结构: 数据元素间的关系。 1—2 基本概念和术语 1. 数据: 对客观对象的抽象。 2. 数据元素: 数据的基本单位。 3. 数据对象: 有相同性质的数据元素的集合。 4. 数据结构: 1) 结构: 数据间的关系。 2) 基本结构( 四类) AB BA EA AC AD BC BD DA DB EB EC DC ED 2 a) 集合 b) 线性结构 c) 树形结构 d) 图状结构( 网状结构) 3) 数据结构的形式定义: (D,S) : 其中 D 为数据元素有限集 S为D 上关系的有限集。 5. 逻辑结构:( 逻辑关系) 6. 物理结构:( 存储结构) 在计算机中的表示 7. 数据元素间的关系在计算机中的两种表示方法 1) 顺序映象-?顺序存储结构 2) 非顺序映象-?链式存储结构 8. 数据类型: 一个值的集合和定义在这个值集上的一组操作的总称。 9. 抽象数据类型(ADT): 一个数学模型以及定义在该模型上的一组操作可用(D,S,P) 表示, 其中 D 为数据对象 S为D 上的关系集 P 为对 D 的基本操作。 1—3 ADT 描述的一些说明及实现(P10) 1—4 算法算法的描述和算法分析一、算法是解决某一特定问题的有限运算序列, 其特性有: 1. 有穷性 2. 确定性 3. 能行性 4. 输入 5. 输出二、描述算法的约定 1. 每一个算法以函数形式给出(类的概念)。 2. 有关结点的类型定义, 全局变量的说明等均在算法之前说明。的函数可直接调用 4. NULL 空指针? define 预定义。如求 10! #define M 10 int p(int x) { int i, s; for (i =1,s=1; i <=10; i ++) s=s* i; return(s);} 三、算法分析 1. 时间、空间复杂性( 时间消耗、空间占用量) 2. 渐近时间复杂度: T(n)=O(f(n)) 第二章线性表线性表的特点: (1) 存在唯一的一个被称作”第一个”的数据元素。(2) 存在唯一的一个被称作”最后一个”的数据元素。 3 (3) 除第一个外, 集合中的每一个数据元素均只有一个前驱。(4) 除最后一个外, 集合中的每一个数据元素一均只有一个后继。 2—1 线性表的类型定义一、线性表 1. 线性表: 具有上述四个特点的 n 个数据元素的有限序列 2. 数据项?记录?文件 3. 线性表的长度注: 线性表是一个相当灵活的数据结构, 它的长度可根据需要增长或缩短其运算有: 存取,插入,删除,查找,合并,分拆,排序,求表的长度。二、抽象数据类型 ADT List { 数据对象:D={a i|a i? ElementSet ,i =1,2, … n, n>=0} 数据关系: R1={<a i-1 ,a i>|a i-1 ,a i? D,i =2,3, ….n} 基本操作:(略)} 三、例子分别表示集合A和B 的线性表LA和 LB, 现需求A ? B,即在LA 中插入LB中在LA 中没有的元素( 算法 ) 四、算法已知两个数据元素已按不减有序排列的线性表LA和 LB, 现要它们归并为一个新的线性表 LC, 且 LC 的数据元素也是按不减有序排列。如 LA=(3,5,8,11) 、 LB=(2,6,8,9,11,15,20) 则 LC=(2,3,5,6,8,8,9,11,11,15,20) ( 算法 ) 2—2 线性表的顺序表示和实现一、线性表的顺序表示 1) 、线性表的顺序表示就是用一组地址连续的存储单元依次存储线性表的数据元素。 2) 、对于线性表 a 1 ,a 2,…a i…,a n 如果每个元素占用 s 个存储单元,则a i+1 的位置为: LOC(a i+1 )=LOC(a i )+s LOC(a i+1 )=LOC(a 1 )+( i -1)* s( 存储结构示意图 P22) 二、线性表的实现 1 、动态分配顺序存储结构#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct { ElemType *elem ; int length ; int listsize ;}SqList ;2 、基本操作 1 )构造一个空表( 算法