DS1-概论.ppt

;本课程的教学目的： 以掌握基本理论、基本方法、基本技能为目的。 ;本课程讲述的主要内容 本课程将分别讲述数据结构的基本概念、 线性表、栈和队列、串和数组、树形结构、图 结构、查找、排序和文件等内容。 ;课程要求;1. 熟悉各名词、术语的含义，掌握基本概念。;1.1 什么是数据结构;概括地说：;1.2 基本概念和术语;数据结构的理解;数据结构：;例如，在2行3列的二维数组{a1, a2, a3, a4, a5, a6} 中六个元素之间 存在两个关系:;再例，在一维数组 {a1, a2, a3, a4, a5, a6} 的数据元素之间存在如下的次序关系:;解释1： 什么叫数据的逻辑结构？;线性结构 :元素之间为一对一的线性关系，第一个元素无直接前驱，最后一个元素无直接后继，其余元素都有一个直接前驱和直接后继。;全校学生档案管理的组织方式;A;数据的逻辑结构可以用二元组表示， 即S=(D, R);（2） S=(D, R) D={di | 1≤i≤5} R={di , dj, ij};解释2：什么叫数据的物理结构？;(1)顺序存储（向量存储） 所有元素存放在一片连续的存贮单元中，逻辑上相邻的元素存放到计算机内存仍然相邻。;(2) 链式存储 所有元素存放在可以不连续的存贮单元中，但元素之间的关系可以通过地址确定，逻辑上相邻的元素存放到计算机内存后不一定是相邻的。;(3)索引存储 存放元素的同时，还建立附加的索引表。索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址），其中的关键字是能唯一标识一个结点的那些数据项。;(4)散列存储 根据结点的值确定结点的存储地址。通过构造散列函数，用函数的值来确定元素存放的地址。;解释3：什么是数据的运算？;在不同的编程环境中，;三、抽象数据类型 (Abstract Data Type 简称ADT);基本操作：;ADT 有两个重要特征:;1.4 算法与算法分析;程序设计实质＝好算法＋好结构;算法的五个特性： 有穷性： 每一条指令的执行次数必须是有限的。 确定性： 每条指令的含义都必须是确定的。 可行性： 算法是能行的，即算法中描述的操作都是可以通过已经???现的基本运算执行有限次来实现的。 输入： 具有0个或多个输入。 输出： 至少产生1个输出。;例：分析以下程序段的时间复杂度。;数学符号（O）的定义：若T(n)和f(n)是定义在正整数集合上的两个函数，当存在两个正的常数 c和n0 ，使得对所有的 n ? n0，都有T(n) ? c·f(n)成立，  则 T(n) = O （f(n）) ;例：分析以下程序段的时间复杂度。 for (i=1; i=n; ++i) /* n+1 */ for (j=1; j=n; ++j) /* n(n+1) */ c [i][j]=0; /* n2 */ -------------------------------------------------------- T(n)=2n2+2n+1 当n充分大时， T(n)与n2是同阶的。 该算法时间复杂度为：T(n)=O(n2);例1：分析以下程序段的时间复杂度。 for (i=1; i=n; ++i) for (j=1; j=n; ++j) { c [i][j]=0; for (k=1;k=n;++k) c[i][j]=c[i][j]+a[i][k]*b[j][k]; } ;时间复杂度T(n)按数量级递增顺序为： ;练习：分析以下程序段的时间复杂度。