数据结构第一课.ppt

教材及参考书(1) ? 教材 、数据结构(C语言版) ，严蔚敏，吴伟民 清华大学出版社，2008 二、数据结构题集，严蔚敏，吴伟民 清华大学出版社，2008 学习方式 ? 听课 （启发式、讨论式） ? 读书 （预习、复习） ? 报告 （综合练习） 考试成绩 平时成绩 （书面作业、上机练习、综合练习） 期中考试 期末考试 内容安排(1) 第一章：绪论 第二章：线性表 第三章：栈和队列 第四章：串 第五章：数组和广义表 第六章：数和二叉树 第七章：图 第九章：查找 第十章：内部排序 第十一章：外部排序 从三方面看本课程的地位 一、从计算机专业九大主科目看 1、算法与数据结构 2、计算机体系结构 3、人工智能与机器人 4、数据库与信息检索 5、人—机通信 6、数值与符号计算 7、操作系统 8、程序设计语言 9、软件方法与工程 二、从毕业生应聘考试和工作需要来看 当今的计算机科学家必须学习和具备彻底理解隐藏在高效程序设计后面的一般原理的能力，因为在日常生活中并不会用到这些在进行程序设计时才需要的能力。 三、从考研来看 在不同的编程环境中，存储结构可有不同的描述方法， 当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。 例如： 以三个带有次序关系的整数表示一个长整数时，可利用C语言中提供的整数数组类型，定义长整数为： typedef int Long_int[3] 若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。 若所需存储量依赖于特定的输入，则通常按最坏情况考虑。 例 计算f=1！+2！+3！+…+n！，用C语言描述。 void factorsum（int n） {int i，j； int f，w； f=0； for （i=1，i〈=n；i++） {w=1； for （j=1; j〈=i；j++） w=w*j； f=f+w； } return； } 此算法所用到的运算有乘法、加法、赋值和比较，其基本运算为乘法操作。在上述算法的执行过程中，对外循环变量i的每次取值，内循环变量j循环i次。因为内循环每执行一次，内循环体语句w=w*j只作一次乘法操作，即当内循环变量j循环i次时，内循环体的语句w=w*j作i次乘法。所以，整个算法所作的乘法操作总数是： f（n）=1+2+3+…+n =n（n+1）/2。 1、一张100元人民币换成5元, 1 元,0.5元共100张。 2、x与y中内容交换，不允许 使用辅助空间。 x=x+y; y=x-y; x=x-y; 本章练习 1.1, 1.2, 1.8, 1.10, 1.16 如何估算 算法的时间复杂度？ 算法 = 控制结构 + 原操作 （固有数据类型的操作） 算法的执行时间 = 原操作(i)的执行次数×原操作(i)的执行时间 算法的执行时间 与 原操作执行次数之和 成正比 从算法中选取一种对于所研究的问题来说是 基本操作 的原操作，以该基本操作 在算法中重复执行的次数 作为算法运行时间的衡量准则。 例 一 两 个 矩 阵 相 乘 void mult(int a[], int b[], int c[] ) { // 以二维数组存储矩阵元素，c 为 a 和 b 的乘积 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]; } //for } //mult 基本操作: 乘法操作 时间复杂度: O(n3) 例 二 选 择 排 序 void select_sort(int a[], int n) { // 将 a 中整数序列重新排列成自小至大有序的整数序列。