第2章 程序设计基础知识 课件 2022—2023学年苏科版初中信息技术九年级全一册

第二章 程序设计基本知识 第1节 程序基本常识 1 一、算法的特征 二、算法的空间复杂度 三、算法的时间复杂度 目录 2 01 算法特征 3 01 算法的复杂度 4 01 时间复杂度计算规则 5 【课堂练习】 6 01 课堂练习 7 01 课堂练习 8 第二章 程序设计基本知识 第2节 C++语言基础 9 一、程序的基本构成 二、变量及数据类型 三、类 目录 四、程序的基本结构 五、函数 六、递归函数 10 02 程序的基本构成 11 02 变量及数据类型 12 02 类 13 02 程序的基本结构 14 02 函数 15 02 递归函数 16 【课堂练习】 17 02 课堂练习 18 02 课堂练习 19 02 课堂练习 20 02 课堂练习 21 02 课堂练习 22 【不定项选择题】 23 02 课堂练习 24 第二章 程序设计基本知识 第3节 排序算法 25 一、内排序和外排序的定义 二、衡量效率的方法 三、排序稳定性 目录 四、常用排序算法复杂度 26 03 内排序和外排序的定义 由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为两大类：内排序与外排序。 1.内排序：待排序记录存放在计算机内存中进行的排序过程。插入排序、快速排序、选择排序、归并排序、基数排序等目前竞赛研究的算法基本上都是内排序方法。 2.外排序：待排序记录的数量很大，以致于内存不能一次容纳全部记录，所以在排序过程中需要对外存进行访问的排序过程。 27 03 衡量效率的方法 1.内排序：比较次数，也就是时间复杂度。 2.外排序：IO次数，也就是读写外存的次数。 28 03 排序稳定性 排序前后相同元素的相对位置不变，则称排序算法是稳定的，否则排序算法是不稳定的。如原序列ri=rj且ri位于rj之前，排序后ri仍在rj之前，则称该排序是稳定的。 29 03 常用排序算法复杂度 30 【课堂练习】 31 03 课堂练习 32 03 课堂练习 33 03 课堂练习 34 【不定项选择题】 35 03 课堂练习 36 03 课堂练习 37 第二章 程序设计基本知识 第4节 基础算法 38 04 基础算法 39 04 基础算法 40 04 基础算法 41 【课堂练习】 42 04 课堂练习 43 04 课堂练习 44 04 课堂练习 45 04 课堂练习 46 04 课堂练习 47 04 课堂练习 48 04 课堂练习 49 【不定项选择题】 50 04 课堂练习 51 04 课堂练习 52 第二章 程序设计基本知识 第5节 字符数组与字符串 53 一、C风格字符串 二、C++引入的string类 三、相关函数总结 目录 54 05 C风格字符串 55 05 C++引入的string类 56 05 字符数组相关函数总结 57 05 字符串（stl容器）相关函数总结 58 【课堂练习】 59 05 课堂练习 60 第二章 程序设计基本知识 第6节 链表 61 一、顺序表 二、链表 目录 62 06 顺序表 63 06 单向链表/线性链表 64 06 双向链表 双向链表的链结点 65 06 循环链表 66 【课堂练习】 67 06 课堂练习 68 06 课堂练习 69 06 课堂练习 70 【不定项选择题】 71 06 课堂练习 72 第二章 程序设计基本知识 第7节 栈和队列 73 一、栈 二、队列 目录 74 07 栈 75 07 进栈（PUSH）、退栈（POP）算法 76 07 例题1 77 07 例题2 78 07 队列 79 07 队列 80 07 课堂练习 81 【课堂练习】 82 07 课堂练习 83 07 课堂练习 84 07 课堂练习 85 07 课堂练习 86 【不定项选择题】 87 07 课堂练习 88 第二章 程序设计基本知识 第8节 树 89 一、树的定义 二、树的相关概念 三、树的性质 目录 四、二叉树 90 08 树的定义 91 08 树的度 92 08 树的前驱和后继 93 08 树中结点的层次 94 08 森林 95 08 树的性质 96 08 二叉树 97 08 例题 98 07 例题 99 08 例题 100 08 课堂练习 101 08 二叉树的性质 102 08 二叉树的性质 103 08 二叉树的性质 104 08 二叉树的性质 105 08 二叉树的性质 106 08 课堂练习 107 【课堂练习】 108 08 课堂练习 109 08 课堂练习 110 08 课堂练习 111 08 课堂练习 112 08 课堂练习 113 08 课堂练习 114 08 课堂练习 115 08 课堂练习 116 【不定项选择题】 117 08 课堂练习 118 08 课