当前课程知识点:程序设计基础 >  第四章 筛法与查找 >  程设论道 >  程设论道一:数组与编码思维

返回《程序设计基础》慕课在线视频课程列表

程设论道一:数组与编码思维在线视频

程设论道一:数组与编码思维

下一节:程设论道二:筛法

返回《程序设计基础》慕课在线视频列表

程设论道一:数组与编码思维课程教案、知识点、字幕

我们这章引入了一个非常重要的概念

就是这个数组

我在清华大学给大家上课的时候呢

数组这个概念其实就

前面大家看看都还好

就是写的作业 大部分同学都能得到满分 这种程度

从数组开始将慢慢的往下下滑

说明数组的理解有难度

所以我们应该讨论一下数组这个概念

其实数组的基本概念还是挺简单的

就是把一些有关联的数放在一起嘛

组织在一起,集中存放

关键是你放在一起,其实是体现了

设计者认为这些数据有关联

他把他认为有关联这个意思 清楚的通过数组

这样一种定义方式 表达出来了

放在一起 其实这在计算机里头 是一个最初步的数据结构

把数据用一种办法组织在一起

有一种方式

而且主要特点就是说

组织在一起后我就能通过它的下标去访问

而且我们以后还要学其他的数据结构的话

就会知道数组这种下标访问是一种非常快速的方式

其实数组是一种天然的线性结构

其他的线性结构的表示方法

可能就是 找一下前面一项 找一下后面一项

就顶天了 是吧

数组这个 随便访问

对我们叫随机访问 术语叫随机访问

那是因为每个元素访问的地址

实际上是有规律的

就像你刚刚说的 它是一个线性的结构

它前后单元是一个连着一个

没有间隔的 这么一个连续的空间

所以呢你就知道首地址 知道下标

你就可以知道那个元素在哪里

正是因为这个原因,你马上可以算出它在什么位置

所以你可以快速的访问任意的东西

我们后面章节里面讲到链表 就不具备这种特性

但是最重要的还是数组的一些性质

大概我觉得同学们在实际的做题的时候

遇到的更多的是 诶我这道题要不要用数组

什么时候要用数组

那为什么我们做一道题的时候要把数组引入进来

那其实更多的情况下是说 我这个题里头

本来我想用枚举法 但里面的东西都是散在那的

可能没有什么规律

就比如说每句话 我们正常写一个循环嘛

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.1.1 什么是程序?什么是语言?

--1.1.2 什么是程序设计?

--1.1.3 计算机发展史

-1.2 买菜问题

--1.2.1 问题描述

--1.2.2 程序的基本结构

-1.3 数学运算

--1.3.1 数学运算符

--1.3.2 数学函数

-1.4 补充说明

--1.4.1 编程环境的下载与安装

--1.4.2 程序基本结构中的含义

--1.4.3 格式与风格

-1.5 总结

--1.5 总结

-程设论道

--程设论道

-师生问答

--师生问答一:怎样学好程序设计

--师生问答二:语言选择

--师生问答三:关于函数

-第一章 编程初步--语法自测

第二章 变量与代数思维

-2.1 关于超级计算器的几点思考

--2.1.1 关于超级计算器的几点思考

-2.2 电子秤模拟 — 背景介绍及需求分析

--2.2.1 电子秤模拟 — 背景介绍及需求分析

-2.3 电子秤模拟 — 代码实现

--2.3.1 电子秤模拟 — 代码实现

-2.4 变量定义与变量类型

--2.4.1 变量定义与变量类型

-2.5 猜数游戏与数据表示

--2.5.1 猜数游戏与数据表示

-2.6 关于变量的讨论

--2.6.1 变量的初始值

--2.6.2 变量类型

--2.6.3 变量内存单元地址

--2.6.4 存“变量地址”的变量——指针

--2.6.5 指针的 读/写 操作

--2.6.6 指针的 加/减 操作

--公告

-2.7 变量体现的计算思维

--2.7.1 变量体现的计算思维

-程设论道

--程设论道

-师生问答

--师生问答

-第二章 变量与代数思维--语法自测

第三章 逻辑推理与枚举解题

-3.1 谁做的好事——语义表示

--3.1.1 谁做的好事——语义表示

-3.2 谁做的好事——真假检查

--3.2.1 谁做的好事——真假检查

-3.3 谁做的好事——循环枚举

--3.3.1 谁做的好事——循环枚举

-3.4 谁是嫌疑犯——多重循环枚举

--3.4.1 谁是嫌疑犯——多重循环枚举

-3.5 谁是嫌疑犯——破案线索表示

--3.5.1 谁是嫌疑犯——破案线索表示

-3.6 谁是嫌疑犯——用二进制枚举

--3.6.1 谁是嫌疑犯——用二进制枚举

-程设论道

--程设论道一

--程设论道二

--程设论道三

-师生问答

--师生问答一:字符与ASCII码表

--师生问答二:其他循环语句、运算符优先级与变量作用域

-第三章 逻辑推理与枚举解题--语法自测

第四章 筛法与查找

-4.1 插花游戏

--4.1.1 问题提出(求素数)

--4.1.2 函数初探

--4.1.3 运行演示

-4.2 筛法

--4.2.1 筛法思路

--4.2.2 数组的定义

--4.2.3 代码翻译

--4.2.4 运行演示

--4.2.5 小朋友数人数

--4.2.6 运行演示

--4.2.7 韩信点兵

-4.3 线性查找

--4.3.1 扑克查找问题

--4.3.2 扑克查找问题代码翻译

--4.3.3 最小值问题

--4.3.4 最小值问题代码翻译

-4.4 折半查找

--4.4.1 提问

--4.4.2 折半查找思路

--4.4.3 折半查找代码翻译

--4.4.4 折半查找运行演示

-4.5 排序问题

--4.5.1 插入排序

--4.5.2 选择排序

--4.5.3 函数写法

--4.5.4 运行演示

-4.6 总结

--4.6.1 总结

-程设论道

--程设论道一:数组与编码思维

--程设论道二:筛法

-师生问答

--师生问答一:函数与面向过程编程

--师生问答二:数组的下标越界

-第四章 筛法与查找--语法自测

第五章 分治思想与递归

-5.1 阶乘

--5.1.1 阶乘问题

--5.1.2 递归解法

--5.1.3 递归小结

-5.2 排序

--5.2.1 归并排序——总体思路

--5.2.2 归并排序——思路分解

--5.2.3 归并排序——代码解说

--5.2.4 快速排序——总体思路

--5.2.5 快速排序——代码解说

--5.2.6 排序总结

-5.3 矩阵填充

--5.3.1 矩阵填充问题

--5.3.2 代码解说

-5.4 分书与八皇后

--5.4.1 问题描述

--5.4.2 问题分析——共性

--5.4.3 问题分析——区别

--5.4.4 解题准备——二维数组

--5.4.5 解题准备——递归设计

--5.4.6 代码解说——分书问题

--5.4.7 代码解说——八皇后问题

-5.5 青蛙过河

--5.5.1 问题描述

--5.5.2 问题分析——简单情况

--5.5.3 问题分析——复杂情况

--5.5.4 问题分析——一般情况

-程设论道

--程设论道一

--程设论道二

-师生问答

--师生问答一

--师生问答二

-第五章 分治思想与递归--语法自测

第六章 递推与动态规划

-6.1 兔子数列问题

--6.1.1 问题描述

--6.1.2 按大小兔子分别递推

--6.1.3 按总数递推

--6.1.4 不用数组递推

-6.2 分鱼问题

--6.2.1 问题描述

--6.2.2 从A到E递推

--6.2.3 从E到A递推

-6.3 橱窗的插花问题

--6.3.1 问题描述

--6.3.2 题意理解与分析

--6.3.3 用枚举思想解题

--6.3.4 采用递推的优化算法

--6.3.5.1 采用动态规划算法—优化分析

--6.3.5.2 采用动态规划算法—递推代码

--6.3.5.3 采用动态规划算法—计算过程

--6.3.5.4 采用动态规划算法—输出方案

--6.3.6 动态规划总结

-6.4 最长公共子序列问题

--6.4.1 问题描述与理解

--6.4.2 问题分析

--6.4.3.1 动态规划解题(1)

--6.4.3.2 动态规划解题(2)

--6.4.3.3 动态规划代码

-程设论道

--程设论道一

--程设论道二

-师生问答

--师生问答

-第六章 递推与动态规划--语法自测

第七章 文本数据处理

-7.1 统计记录总数

--7.1.1 问题分析

--7.1.2 读文件操作

-7.2 统计活跃用户数

--7.2.1 问题分析

--7.2.2 字符串

--7.2.3 程序翻译与演示

-7.3 统计在线时长

--7.3.1 问题分析

--7.3.2 结构

--7.3.3 程序翻译与演示

--7.3.4 写文件操作

-7.4 总结

--7.4.1 总结

-程设论道

--程设论道

-师生问答

--师生问答

-第七章 文本数据处理--语法自测

第八章 非文本数据处理

-8.1 将数据组织成链表

--8.1.1 链表的基本概念

--8.1.2 代码讲解

--8.1.3 链表遍历与释放

-8.2 提高链表访问效率 —— 哈希链表

--8.2.1 简单的哈希算法

--8.2.2 算法实现

-8.3 以二进制文件存储链表

--8.3.1 二进制文件的操作方法

--8.3.2 代码讲解

-程设论道

--程设论道一

--程设论道二

-师生问答

--师生问答

-第八章 非文本数据处理--语法自测

第九章 可配置的程序设计

-9.1 自动售卖程序

--9.1.1 提出问题与初步设计

--9.1.2 细化实现订单处理

--9.1.3 使程序更健壮

-9.2 配制水果信息

--9.2.1 提出问题与设计文件格式

--9.2.2 实现订单处理功能

-9.3 指定界面语言

--9.3.1 提出问题与命令行参数

--9.3.2 实现程序功能

-程设论道

--程设论道

-师生问答

--师生问答

-第九章 可配置的程序设计--语法自测

程设论道一:数组与编码思维笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。