当前课程知识点:程序设计基础 > 第四章 筛法与查找 > 程设论道 > 程设论道一:数组与编码思维
我们这章引入了一个非常重要的概念
就是这个数组
我在清华大学给大家上课的时候呢
数组这个概念其实就
前面大家看看都还好
就是写的作业 大部分同学都能得到满分 这种程度
从数组开始将慢慢的往下下滑
说明数组的理解有难度
所以我们应该讨论一下数组这个概念
其实数组的基本概念还是挺简单的
就是把一些有关联的数放在一起嘛
组织在一起,集中存放
关键是你放在一起,其实是体现了
设计者认为这些数据有关联
他把他认为有关联这个意思 清楚的通过数组
这样一种定义方式 表达出来了
放在一起 其实这在计算机里头 是一个最初步的数据结构
把数据用一种办法组织在一起
有一种方式
而且主要特点就是说
组织在一起后我就能通过它的下标去访问
而且我们以后还要学其他的数据结构的话
就会知道数组这种下标访问是一种非常快速的方式
其实数组是一种天然的线性结构
其他的线性结构的表示方法
可能就是 找一下前面一项 找一下后面一项
就顶天了 是吧
数组这个 随便访问
对我们叫随机访问 术语叫随机访问
那是因为每个元素访问的地址
实际上是有规律的
就像你刚刚说的 它是一个线性的结构
它前后单元是一个连着一个
没有间隔的 这么一个连续的空间
所以呢你就知道首地址 知道下标
你就可以知道那个元素在哪里
正是因为这个原因,你马上可以算出它在什么位置
所以你可以快速的访问任意的东西
我们后面章节里面讲到链表 就不具备这种特性
但是最重要的还是数组的一些性质
大概我觉得同学们在实际的做题的时候
遇到的更多的是 诶我这道题要不要用数组
什么时候要用数组
那为什么我们做一道题的时候要把数组引入进来
那其实更多的情况下是说 我这个题里头
本来我想用枚举法 但里面的东西都是散在那的
可能没有什么规律
就比如说每句话 我们正常写一个循环嘛
for循环最后那个递进条件
要么加个1,要么加个2
或者乘个2,乘个3
这种形成的数都是很有规律的
这就是我们那个 在他讲的那一章 后面讨论里头提到的
有条件 你枚举 没条件 你创造条件枚举
所以当时就是说 所谓创造条件
我们说后面会讲
在 第四章里头
数组就是一个创造条件
让那些看上去你没法去枚举的东西
对那我怎么枚举啊 他没顺序啊
像东南西北 你说谁在前谁在后
这个东西里头是人规定的
但事实上它本身是没有顺序的
那这时候你怎么枚举呢?
诶我们就 把它放在数组里头去
我们就借用数组天然的空间顺序
就可以 你放在数据里头 就有个顺序了
像您刚才说的那个东南西北那个
其实生活中有很多这样的例子
这个 咱们之前提到过的这个
ASCII码的这个表
还有那个密码表
密码本
我们很多那个速查手册
凡是需要有一个好查的那个东西
形成一个顺序的那个东西
然后给他编个号
这样就方便多了
其实你看那个 如果
抓这个中药的时候 你去中药库
那么大的柜子 里头一大堆格子
它其实也是 编着号
而且它也是空间上有顺序的
然后每个里头放了好几种不同的药材
他从来没有说 把那些药材 散堆着
然后乱捣一气
这样每一个格子都有固定的内容
然后找起来非常方便
其实 也可是说是 人家在没有发明计算机之前
其实这样一个 通过空间的有序
去对一些不好处理的东西 去进行有序化
其实人类早就在运用这样的思想
我们无非是把实体的空间 搬到计算机内存的空间里头去了
还是一格格对着的
所以实际上就是
让数据变得更有序
其实是一直以来的一种追求
对而且用了数组就是
就是感觉一下子我们能处理的东西就多了
原来我们说要处理东西怎么办的
你得要用个变量
那我要10个东西,就要10个变量,100个东西,就要100个变量
我写不过来了我都
所以我在那里讲 比方说这个计算器 是个超级计算器
诶强在什么地方呢 强在我可以用公式
但毕竟公式里的变量是有限的
你得一个个去写
那一旦多了怎么办呢
没办法处理
那么我觉得就是
数组 就像你刚刚说的
它其实是提供了一个 一次性的 批处理
因为你那个定义很方便啊 int[a] ...
而且我觉得这个东西也很天然
就是符合我们第一章说的那个计算机的优势
咱们计算机里面 冯诺依曼的架构嘛
关键核心的部件就是那个内存
但内存就是长那个样
就是一个连续存放的
数组就是对应上的
而且就是 这个批量定义的这个变量啊
它还有一个独特的优势
就是我们回想一下 在循环里头
它是一个变量的值
在那个地方通过循环去改变
在变化它
但是呢 我们那时候讲变量的时候是说
变量的名字你也必须符合一定的要求
其实潜台词是变量名是不能改的
但是有的时候我们处理一个问题 或者一个算法
我们需要有一种名字能够变的变量
对 我们要遍历这些变量
那这时候 你看数组 就是天然的
a[i]
对不对 加入我们认为方括号
也是一个名称的一部分的话
那你想想 a[i]
它就是一个变量名啊
可是它变量名字还老换
今天是a[0],明天就变成a[1]了
但是它长起来又是一样的
就是在代码里头写上去 看上去 都是a[i]
但是它一会儿代表a[0],一会儿代表a[28]
这个里头,就给我们提供了一个极大的
设计程序的 算法的 方便的 这个途径
同时又便利
当然我们同学们在理解这个的时候
如果这一点理解的不深刻
恐怕就会觉得数组 就会比较难
对吧 所以我觉的 我们
这一点应该告诉他们
对于他们理解这个是有一个很大的帮助
对 而且 就是说 有了数组之后 确实很多事情
我们的能力就增强了嘛
我能同时操作那么多变量对吧
包括就说函数好了
我们以前的那个函数 可能也就是
这几个参数了
我们现在用数组这个工具
我们一下子 成百上千个参数传给它 都可以
其实对同学们来说 这个不是个好事是吧
每次我们引入一个新的知识,和前面的知识都有关联
然后每个每个一配合,就能出出新的题来
当然反过来说 就能解决更多生活中的问题了
其实就是说我们这个
说到学习这个课程一个新的知识啊
每次都引入进来
我觉得学咱们的程序设计啊
有的时候是有一种螺旋上升的那种感觉
就是每次接触一个概念,可能只学到了其中一部分
比方说我们的数组这一章
或者说查找和筛法这一章
我们只是介绍了一维的数组
那我们下一章 后面的
还会去讲二维的数组
对吧 那现在数组是静态的定义的,后面我们还会讲动态的定义的
动态的来分配
但是呢 这些跟数组有关系的
可是呢我们每次都会讲一部分
然后呢 在不断地带着大家
把这个对于数组啊 对于相关的概念
一步一步去深入 每个台阶都比较小
那么其实学生在学的时候呢
也得注意的一个方法 就是说
可能是 每一次 都要把 对应的那个
相对简单的东西 把它掌握好
然后后面可能反复的出现 或者反复的运用它
所以我们讲的都是一些 真的有这样的需要
其实是很重要的 很常用的东西
不常用的一些东西 比如语法啊细节啊
其实也不会给大家介绍
我们会放到那个wiki里头 让助教放进去
所以如果说
他们真的想去查的话,就去看在线平台上的内容
所以我们还是多讨论讨论 向大家介绍介绍
一般语法书上没有的东西
多交流交流这方面 我觉得对大家学习和今后的发展 会更有利
其实编程啊 一个是你对这个语言本身的语法啊这种 运用和理解
但是最核心的问题
还是说 你的解题的思路
对吧 那个算法
那是一个最根本的东西
就想说我们 可能每个字你都认识
但是不见得认识字的人都能写小说啊
对不对 我们现在其实是要用
计算机的语言去表达一种观念
表达一种思想
当然更多的时候我们表现出来是一种
去解决一部分的问题
那所有的这些技术
都是要去运用它才能完成的
嗯好 讲得好!
-1.1 基础知识
-1.2 买菜问题
-1.3 数学运算
-1.4 补充说明
-1.5 总结
--1.5 总结
-程设论道
--程设论道
-师生问答
-第一章 编程初步--语法自测
-2.1 关于超级计算器的几点思考
-2.2 电子秤模拟 — 背景介绍及需求分析
-2.3 电子秤模拟 — 代码实现
-2.4 变量定义与变量类型
-2.5 猜数游戏与数据表示
-2.6 关于变量的讨论
--公告
-2.7 变量体现的计算思维
-程设论道
--程设论道
-师生问答
--师生问答
-第二章 变量与代数思维--语法自测
-3.1 谁做的好事——语义表示
-3.2 谁做的好事——真假检查
-3.3 谁做的好事——循环枚举
-3.4 谁是嫌疑犯——多重循环枚举
-3.5 谁是嫌疑犯——破案线索表示
-3.6 谁是嫌疑犯——用二进制枚举
-程设论道
--程设论道一
--程设论道二
--程设论道三
-师生问答
-第三章 逻辑推理与枚举解题--语法自测
-4.1 插花游戏
-4.2 筛法
-4.3 线性查找
-4.4 折半查找
--4.4.1 提问
-4.5 排序问题
-4.6 总结
--4.6.1 总结
-程设论道
--程设论道二:筛法
-师生问答
-第四章 筛法与查找--语法自测
-5.1 阶乘
-5.2 排序
-5.3 矩阵填充
-5.4 分书与八皇后
-5.5 青蛙过河
-程设论道
--程设论道一
--程设论道二
-师生问答
--师生问答一
--师生问答二
-第五章 分治思想与递归--语法自测
-6.1 兔子数列问题
-6.2 分鱼问题
-6.3 橱窗的插花问题
-6.4 最长公共子序列问题
-程设论道
--程设论道一
--程设论道二
-师生问答
--师生问答
-第六章 递推与动态规划--语法自测
-7.1 统计记录总数
-7.2 统计活跃用户数
-7.3 统计在线时长
--7.3.2 结构
-7.4 总结
--7.4.1 总结
-程设论道
--程设论道
-师生问答
--师生问答
-第七章 文本数据处理--语法自测
-8.1 将数据组织成链表
-8.2 提高链表访问效率 —— 哈希链表
-8.3 以二进制文件存储链表
-程设论道
--程设论道一
--程设论道二
-师生问答
--师生问答
-第八章 非文本数据处理--语法自测
-9.1 自动售卖程序
-9.2 配制水果信息
-9.3 指定界面语言
-程设论道
--程设论道
-师生问答
--师生问答
-第九章 可配置的程序设计--语法自测