1、选择性必修1数据与数据结构第一章 数据与数据结构 1.2 数据的组织情境导入QWERTY键盘 打印机刚发明时，键盘左上角的字母顺序是“ABCDEF”。这个排列顺序让打字员打起来飞快，但是相邻字母频繁敲击长杆和字锤可能会卡在一起。为了解决卡键这个难题，打印机发明者肖尔斯请他的妹夫一位数学家来帮忙。这位数学家建议肖尔斯把键盘上那些英文字母中最常用的字母分开，以避免故障的发生。肖尔斯采纳了这个建议，将字母重新排列，形成了我们现在看到的“QWERTY”的布局。打字员使用这个键盘的时候，打字速度明显下降，也因此很少发生卡键的情况了。至今很多人质疑“QWERTY”键盘布局的字频统计的科学性，这里我们可以使
2、用Python语言赋值我们展开字频统计研究，下面是老师的一个程序样例，但数据样本比较小，分析结果存在一定局限。情境导入QWERTY键盘运行程序样例，得到字频统计瑞士计算机科学家沃斯（N.Wirth）曾指出“算法+数据结构=程序”数据结构的概念 数据元素是数据的基本单位。有些情况下，数据元素也称为元素、结点、顶点、记录等。图1.2.1 数据元素及其包含的数据项 图1.2.1所示二维表中，每一行实际内容（也称为一条记录）就是数据元素，而每个元素又由5个数据项（“代码”“名称”“最新价格”“动态市盈”“流通股本”）组成。1.数据元素（Data Element）数据结构的概念2.数据类型（Data T
3、ype）数据类型指的是具有相同性质的计算机数据的集合及在这个数据集合上的一组操作。数据类型可以分为基本数据类型（也称为原子数据类型）和结构数据类型。基本数据类型由计算机编程环境提供，编程者可以在编程时直接用系统提供的标识符进行定义，如Python编程语言中的整型、实型、布尔型等。结构数据类型是在程序设计时利用基本数据类型构造出的、复合的新类型，这种新类型由用户根据实际需要定义，能较好地描述数据元素数据项组成以及数据元素之间的逻辑关系，方便用户根据数据之间逻辑关系的特点进行数据处理，如很多编程语言中提供的记录类型、集合等。基本数据类型结构数据类型数据结构的概念3.数据结构（Data Struct
4、ure）数据结构指的是数据之间的相互关系，即数据的组织形式。它包括了以下三个方面的内容：数据元素之间的逻辑关系，也称为数据的逻辑结构。数据元素及其关系在计算机存储器内的表示，也称为数据的存储结构或物理结构。数据的运算，即对数据施加的操作。常见的数据结构数组李彤 张强 胡洁 杜刚第1个 第2个 第3个 第4个这批数据序列可用数组“a(1)=李彤、a(2)=张强、a(3)=胡洁、a(4)=杜刚”来表达。常见的数据结构链表 吴坚知道自己排在首位，王林知道排在自己前面的是吴坚，黄刚知道排在自己前面的是王林，李丰知道排在自己前面的是黄刚。有了这些相邻人员之间的链接关系，即使休息时大家分散在各处，一旦需要
5、集合，大家可以根据链接关系快速地按照原顺序排成队伍。虽然整队前后每个人员的站位地点发生改变，但相互之间排队的顺序关系是不变的。常见的数据结构链表游戏体验“排排队”1.准备2组1-6的数字2.一组1-6随机贴在6位志愿者的胸前，一组1-6随机贴在志愿者的背后（每位自愿者两个数组不同）3.确定一位同学站在队首，然后每位志愿者根据胸前数字与排定同学背后数字配对完成排队。常见的数据结构链表抽象化后的排队链接关系 组织、处理一批数据时，若不关心数据实际所处的具体位置，而只需知道数据之间相互链接的顺序时，可以借鉴上面的方法。在计算机科学中，这种方法的具体实现形式就是链表。常见的数据结构链表单向链表双向链表
6、基于单向链表的循环链表问题与讨论高铁站信息显示 车站或者机场为了方便旅客了解最新出乘信息，会在电子屏上滚动显示最近的班次信息（如图1.2.9所示）。该系统内部程序控制滚动显示可以采用怎样的数据结构？主要算法又是怎样的？常见的数据结构队列有序排队上车的乘客有序排队接客的出租车 乘客排队时先到的总是从队伍的头部出去（出队）上车，而后到的乘客则必须在队伍的尾部加入（入队）。同时，为了确保有序，人们总是规定不能从队伍的中间部位插队。常见的数据结构队列 用计算机程序处理数据时，有时也需要将数据进行“排队”，并遵循现实中排队的规律，对数据进行“先进先出”FIFO（First In First Out）且中
7、间不能“插队”的组织和操作，计算机科学家由此发明了“队列”这种数据结构。常见的数据结构栈弹匣的装弹过程（入栈）子弹进出弹匣的过程具有下列特点：整个装置只有一端开放（最上端），而且进、出只能在这一端进行。弹匣中的子弹成一纵队排列。任何子弹进出弹匣的规律是“先进后出、后进先出”，即最先装入弹匣的子弹最后才能被弹出，而最后装入弹匣的子弹则最先被弹出。问题与讨论在文字处理软件Word中输入若干文字，然后删除其中部分文字，再输入若干文字。然后进行“撤消”操作（按Ctrl+Z键，或者单击撤消操作快捷按钮“”）。观察各个操作后的现象，回答下列问题。（1）根据“撤消”操作所产生的结果，说明Word中符号输入及
8、撤消操作中，内部所依托的数据结构是哪种数据结构？为什么？（2）结合自己的经历，谈谈哪些信息系统中也采用了栈这种数据结构。常见的数据结构树常见的数据结构树问题与讨论 分小组讨论，举出在生活和信息系统中用树组织数据的例子，并用树结构描述数据之间的关系特征。数据结构的作用姓名班级滚铁圈打弹子拍纸板竹蜻蜓跳绳踢毽子陈 涛932杨 琼351金 凯245吴 敏1613朱刚强65171.设计算法解决问题离不开数据结构 数据统计前，需要先收集数据并将数据按照既有的逻辑关系进行结构化组织，可以用一张表格来组织数据并表示数据之间的逻辑关系。数据结构的作用2.不同数据结构会导致处理效率的不同xm(i)bj(i)d1
9、(i)d2(i)d3(i)d4(i)d5(i)d6(i)sum(i)陈 涛9302000杨 琼3000051金 凯2045000吴 敏1610300朱刚强6501070其中的bjdf(j)表示第j班的总分（1）用一维数组组织数据程序代码：数据结构的作用2.不同数据结构会导致处理效率的不同xm(i)a(i,1)a(i,2)a(i,3)a(i,4)a(i,5)a(i,6)a(i,7)a(i,8)陈 涛9302000杨 琼3000051金 凯2045000吴 敏1610300朱刚强6501070（1）用二维数组组织数据程序代码：其中的bjdf(j)表示第j班的总分数据结构的作用2.不同数据结构会导致
10、处理效率的不同二维数组程序实现：一维数组程序实现：不同数据结构会导致处理效率的不同数据合并案例 生产厂家总会根据各地产品销量的数据分析来预估市场情况，并为后续调整生产规划、完善营销策略提供依据。由于数据量巨大，为了充分运用分布式处理的优势，总部会要求各下属地区上报数据时，按各产品销量进行从大到小的排序。总部收到数据后的第一件事是将所有数据合并并按照销量进行降序排序（从大到小），为了完成数据合并和整理工作，总部数据分析员小刚需要设计合适的数据结构和算法。不同数据结构会导致处理效率的不同分析 小刚可以用一个二维数组存储所有下属地区的产品销量数据，然后直接运用排序算法进行降序排序。如果利用既有数据已
11、是分块有序的特点，设计新的数据结构和算法，则处理效率可以得到相应的提升。各个地区的数据合并问题可以简化为2个地区的数据合并问题，当2个地区的数据合并完成后，剩余各地区的数据合并就可以按照同样方式完成。因此，接下来着重分析2个地区的数据合并问题。不同数据结构会导致处理效率的不同第一步 抽象与建模设第1个地区共有n个产品销量数据，第2个地区共有m个产品销量数据。为了简化描述，突出核心部分的分析，考虑将问题抽象为n个有序整数和m个有序整数的合并问题，具体的问题模型如下：已知一个降序排列的整数数列A：a1，a2，a3，an以及一个降序排列的整数数列B：b1，b2，b 3，bm，将两个数列合并形成一个新
12、的有序数列C，使新数列仍按降序排列，即c1c2c3ckck+1cn+m（其中ck A或者ck B）。请完成解决该问题的数据结构和算法的设计。不同数据结构会导致处理效率的不同第二步 设计、描述算法1.基于数组的算法设计与描述（1）将数组a中所有元素存储到数组c的前n个位置中；1234519 16 1285a 19 16 12851234519 16 1285b 20 15 14 10412345678910c12345678910不同数据结构会导致处理效率的不同第二步 设计、描述算法1.基于数组的算法设计与描述（2）将数组c右边的m个元素赋值为1（c(n+1)直到c(n+m)）；1234519
13、16 1285a19 16 12851234519 16 1285b 20 15 14 104c-1-1-1-1-112345678910不同数据结构会导致处理效率的不同第二步 设计、描述算法1.基于数组的算法设计与描述（3）变量p赋值为0，将表示数组c中有效元素总个数的变量tot赋值为n；1234519 16 1285a19 16 12851234519 16 1285b 20 15 14 104c-1-1-1-1-10iptot12345678910不同数据结构会导致处理效率的不同（4）将数组b中元素b(i)逐个插入到数组c中（1im）：19 16 12851234520 15 14 10
14、4b 20 15 14 104c-1-1-1-1-10iptotp值增加1；如果c(p)b(i)，那么使p值增加1；如果c(p)=1，那么直接将b(i)存储到c(p)中，同时tot值增加1；如果c(p)b(i)，那么依次将c(tot)，c(tot1)，c(p)向右移动一个位置，然后将b(i)存储到c(p)中，同时tot值增加1。12345678910不同数据结构会导致处理效率的不同（4）将数组b中元素b(i)逐个插入到数组c中（1im）：19 16 12851234520 15 14 104b2015 14 104c-1-1-1-10iptotp值增加1；如果c(p)b(i)，那么使p值增加1
15、；如果c(p)=1，那么直接将b(i)存储到c(p)中，同时tot值增加1；如果c(p)b(i)，那么依次将c(tot)，c(tot1)，c(p)向右移动一个位置，然后将b(i)存储到c(p)中，同时tot值增加1。pp如果c(p)b(i)，那么使p值增加1；12345678910不同数据结构会导致处理效率的不同（4）将数组b中元素b(i)逐个插入到数组c中（1im）：19 1612851234520 15 14 104b201514 104c-1-1-10itotp值增加1；如果c(p)b(i)，那么使p值增加1；如果c(p)=1，那么直接将b(i)存储到c(p)中，同时tot值增加1；如果
16、c(p)b(i)，那么依次将c(tot)，c(tot1)，c(p)向右移动一个位置，然后将b(i)存储到c(p)中，同时tot值增加1。p12345678910不同数据结构会导致处理效率的不同（4）将数组b中元素b(i)逐个插入到数组c中（1im）：19 1612851234520 15 14 104b2015 14104c-1-10itotp值增加1；如果c(p)b(i)，那么使p值增加1；如果c(p)=1，那么直接将b(i)存储到c(p)中，同时tot值增加1；如果c(p)b(i)，那么依次将c(tot)，c(tot1)，c(p)向右移动一个位置，然后将b(i)存储到c(p)中，同时tot
17、值增加1。pp12345678910不同数据结构会导致处理效率的不同（4）将数组b中元素b(i)逐个插入到数组c中（1im）：19 1612851234520 15 14 104b2015 14104c-10itotp值增加1；如果c(p)b(i)，那么使p值增加1；如果c(p)=1，那么直接将b(i)存储到c(p)中，同时tot值增加1；如果c(p)b(i)，那么依次将c(tot)，c(tot1)，c(p)向右移动一个位置，然后将b(i)存储到c(p)中，同时tot值增加1。ppp不同数据结构会导致处理效率的不同第二步 设计、描述算法2.基于链表的算法设计与描述19161285链表链表a:head_a指针p1指针p201514105链表链表b:head_b指针q1指针q课堂小结学习评价对自己和同伴的表现进行客观的评价，并思考后续完善的方向。（5=优秀，4=超出一般水平，3=满意，2=有待改进，1=不太理想）评分项自我评价同学互评能理解数据结构的概念及其作用5 4 3 2 15 4 3 2 1了解常见数据结构的特点及其操作特征5 4 3 2 15 4 3 2 1能针对简单的具体问题明确数据需求、确定问题模型，并抽象出数据结构5 4 3 2 15 4 3 2 1能对数据结构的合理性进行简单评估5 4 3 2 15 4 3 2 1课堂作业
