(
课件网) 选择性必修1《数据与数据结构》 第一章 数据与数据结构 1.2 数据的组织 情境导入———QWERTY键盘 打印机刚发明时，键盘左上角的字母顺序是“ABCDEF”。这个排列顺序让打字员打起来飞快，但是相邻字母频繁敲击长杆和字锤可能会卡在一起。为了解决卡键这个难题，打印机发明者肖尔斯请他的妹夫———一位数学家来帮忙。 这位数学家建议肖尔斯把键盘上那些英文字母中最常用的字母分开，以避免故障的发生。肖尔斯采纳了这个建议，将字母重新排列，形成了我们现在看到的“QWERTY”的布局。打字员使用这个键盘的时候，打字速度明显下降，也因此很少发生卡键的情况了。 至今很多人质疑“QWERTY”键盘布局的字频统计的科学性，这里我们可以使用Python语言赋值我们展开字频统计研究，下面是老师的一个程序样例，但数据样本比较小，分析结果存在一定局限。 情境导入———QWERTY键盘 运行程序样例，得到字频统计 瑞士计算机科学家沃斯（N.Wirth）曾指出“算法+数据结构=程序” 数据结构的概念 数据元素是数据的基本单位。有些情况下，数据元素也称为元素、结点、顶点、记录等。 图1.2.1 数据元素及其包含的数据项 图1.2.1所示二维表中，每一行实际内容（也称为一条记录）就是数据元素，而每个元素又由5个数据项（“代码”“名称”“最新价格”“动态市盈”“流通股本”）组成。 1. 数据元素（Data Element） 数据结构的概念 2. 数据类型（Data Type） 数据类型指的是具有相同性质的计算机数据的集合及在这个数据集合上的一组操作。 数据类型可以分为基本数据类型（也称为原子数据类型）和结构数据类型。 基本数据类型由计算机编程环境提供，编程者可以在编程时直接用系统提供的标识符进行定义，如Python编程语言中的整型、实型、布尔型等。 结构数据类型是在程序设计时利用基本数据类型构造出的、复合的新类型，这种新类型由用户根据实际需要定义，能较好地描述数据元素数据项组成以及数据元素之间的逻辑关系，方便用户根据数据之间逻辑关系的特点进行数据处理，如很多编程语言中提供的记录类型、集合等。 基本数据类型 结构数据类型 数据结构的概念 3. 数据结构（Data Structure） 数据结构指的是数据之间的相互关系，即数据的组织形式。 它包括了以下三个方面的内容： ①数据元素之间的逻辑关系，也称为数据的逻辑结构。 ②数据元素及其关系在计算机存储器内的表示，也称为数据的存储结构或物理结构。 ③数据的运算，即对数据施加的操作。 常见的数据结构———数组 李彤 张强 胡洁 杜刚 第1个 第2个 第3个 第4个 这批数据序列可用数组 “a(1)="李彤"、a(2)="张强"、a(3)="胡洁"、a(4)="杜刚"”来表达。 常见的数据结构———链表 吴坚知道自己排在首位，王林知道排在自己前面的是吴坚，黄刚知道排在自己前面的是王林，李丰知道排在自己前面的是黄刚。有了这些相邻人员之间的链接关系，即使休息时大家分散在各处，一旦需要集合，大家可以根据链接关系快速地按照原顺序排成队伍。虽然整队前后每个人员的站位地点发生改变，但相互之间排队的顺序关系是不变的。 常见的数据结构———链表 游戏体验“排排队” 1.准备2组1-6的数字 2.一组1-6随机贴在6位志愿者的胸前，一组1-6随机贴在志愿者的背后（每位自愿者两个数组不同） 3.确定一位同学站在队首，然后每位志愿者根据胸前数字与排定同学背后数字配对完成排队。 常见的数据结构———链表 抽象化后的排队链接关系 组织、处理一批数据时，若不关心数据实际所处的具体位置，而只需知道数据之间相互链接的顺序时，可以借鉴上面的方法。在计算机科学中，这种方法的具体实现形式就是链表。 常见的数据结构———链表 单向 ... ...
