chap1第一章 绪论.ppt

数 据 结 构 湖南文理学院 曲孝海 第一章 绪论（2学时） 数 据 结 构 数据结构是计算机专业重要的专业基础课，它的前期课程主要有程序设计语言，学好这门课，可以加深对程序设计的理解，有助于进一步提高程序设计能力，并为计算机专业后续课程，如数据库操作系统编译原理，软件工程等课程奠定良好的基础。 教材： 数据结构 （ C语言版） 严蔚敏 吴伟民 清华大学出版社 数据结构题集 （ C语言版） 严蔚敏 吴伟民 清华大学出版社 1．1 本课程的研究对象 2·数据元素　　是数据(集合)中的一个个体，在计算机中通常作为一个整体进行考虑和处理，是数据结构中讨论的基本单位。　　有两类数据元素：一类是不可分割的原子型数据元素，如：整数5，字符 N 等；另一类是由多个款项构成的数据元素，其中每个款项被称为一个数据项。例如描述一个学生的信息的数据元素可由下列6个数据项组成。其中的出身日期又可以由三个数据项：年、月和日组成，则称出身日期为组合项，而其它不可分割的数据项为原子项。·数据对象　　是具有相同特性的数据元素的集合，如：整数、实数等。它是数据的一个子集。 学生成绩表格 1．2 数据结构的有关概念 四个基本结构 集合 线性结构 树形结构 网状结构 1．3 数据结构的分类及表示 1．4 算法与算法分析 本课程的教学目标 教学安排 基础知识题 第一章 习题 第一章 习题 第一章 习题 1．5 类C语言 1．5 类C语言 1．5 类C语言 1．5 类C语言 1．5 类 C 语言 1．5 类 C 语言 * C的数据类型 * C的数据类型 * C的数据类型 * C的数据类型 * C的数据类型 * C的数据类型 * C的数据类型 * C的数据类型 *类C语言简要说明 类C语言简要说明 类C语言简要说明 类C语言简要说明 类C语言简要说明 类C语言简要说明 类C语言简要说明 类C语言简要说明 O（n3） 称为矩阵相乘算法时间复杂度； O（n3）表示矩阵相乘算法执行时间与n3成正比 即O（n3）与n3 同一数量级； 例 6 n 阶矩 阵相乘的算法 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 ] += a[ i ][ k ] * b[ k ] [ j ] } 乘法 加法 执行次数均为 n3 矩阵相乘的基本运算：乘法 加法； 有如下情况，算法基本操作执行次数与问题的输入数据有关，这时可考虑 （1） 算法平均时间复杂度 （2） 算法在最坏情况下的时间复杂度 一般来说，设算法中原操作的执行次数是问题规模n的某个函数f(n)，算法的时间复杂度记作： T(n) = O(f(n))  它表示随问题规模n的增大，算法执行时间的增长率与f(n) 的增长率相同。 例7 起泡排序算法 void bubble_sort (int a[ ], int n ) { //用方法，将a 中n个整数的序列排列成自小至大有序的整数序列 For (i = n-1,change=TRUE; i 1change; - -i ) { change= FALSE; For (j = 1; j= i; ++j ) If (a [j] a[ j+ 1]) { a [j] a[ j+ 1]; change=TRUE;} }}// bubble_sort 当a中初始序列自大至小排列时，比较次数,交换次数均为 n(n-1)/2； 起泡排序算法的基本操作：比较，交换序列中相邻两个整数 当a中初始序列自小至大有序时，比较次数为n-1,交换次数为 0； 假设出现各种排列的概率相等，则起泡排序平均时间复杂度为 Targ ( n ) =O (n2) 比较交换序列中 相邻两个整数 算法在最坏