数据的组织　　 【核心知识精讲精析】 浙教版（2019）高中信息技术选修1

选择性必修1《数据与数据结构》第一章数据与数据结构1.2数据的组织什么是数据结构根据问题求解的需要，对数据进行有效的整理和组织，并以一定的形式加以存储和表示的过程称为数据结构。瑞士计算机科学家沃斯（N.Wirth）曾指出“算法+数据结构=程序”数据结构的概念

数据元素是数据的基本单位。有些情况下，数据元素也称为元素、结点、顶点、记录等。图1.2.1数据元素及其包含的数据项

图1.2.1所示二维表中，每一行实际内容（也称为一条记录）就是数据元素，而每个元素又由5个数据项（“代码”“名称”“最新价格”“动态市盈”“流通股本”）组成。数据项是具有独立含义的最小数据表示单位。1.数据元素（DataElement）数据结构的概念2.数据类型（DataType）数据类型指的是具有相同性质的计算机数据的集合及在这个数据集合上的一组操作。数据类型可以分为基本数据类型（也称为原子数据类型）和结构数据类型。基本数据类型由计算机编程环境提供，编程者可以在编程时直接用系统提供的标识符进行定义，如Python编程语言中的整型、实型、布尔型等。

结构数据类型是在程序设计时利用基本数据类型构造出的、复合的新类型。意思是我们把一些不同类型的数据组合成一个整体，如一个学生的学号、姓名、班级、年龄和成绩等，虽然各个属性分别属于不同的数据类型，但是它们之间密切相关，各种信息都属于同一个人。这时，可以声明一个结构型的数据类型，由多种数据类型，可以是基本数据类型，也可以是自定义的数据类型，组成一个集合。基本数据类型结构数据类型数据结构的概念3.数据结构（DataStructure）数据结构指的是数据之间的相互关系，即数据的组织形式。它包括了以下三个方面的内容：①数据元素之间的逻辑关系，也称为数据的逻辑结构。②数据元素及其关系在计算机存储器内的表示，也称为数据的存储结构或物理结构。③数据的运算，即对数据施加的操作。如删除、查找、插入数据等常见的数据结构——数组李彤张强胡洁杜刚第1个第2个第3个第4个这批数据序列可用数组“a[1]="李彤"、a[2]="张强"、a[3]="胡洁"、a[4]="杜刚"”来表达。描述数据所处的位置或数据之间的前后顺序关系，通过数组的下标可以精确的访问序列中的某个数据元素。常见的数据结构——链表吴坚知道自己排在首位，王林知道排在自己前面的是吴坚，黄刚知道排在自己前面的是王林，李丰知道排在自己前面的是黄刚。有了这些相邻人员之间的链接关系，即使休息时大家分散在各处，一旦需要集合，大家可以根据链接关系快速地按照原顺序排成队伍。虽然整队前后每个人员的站位地点发生改变，但相互之间排队的顺序关系是不变的。只需要知道相邻人员之间的前后顺序关系，而对每个人员的位置信息并不作要求。常见的数据结构——链表抽象化后的排队链接关系

组织、处理一批数据时，若不关心数据实际所处的具体位置，而只需知道数据之间相互链接的顺序时，可以借鉴上面的方法。在计算机科学中，这种方法的具体实现形式就是链表。常见的数据结构——链表单向链表双向链表基于单向链表的循环链表指针：用了指示一个数据存储地址的变量。数据域单项链表的基础上每个结点增加一个指向前驱结点的连接常见的数据结构——队列有序排队上车的乘客有序排队接客的出租车乘客排队时先到的总是从队伍的头部出去（出队）上车，而后到的乘客则必须在队伍的尾部加入（入队）。同时，为了确保有序，人们总是规定不能从队伍的中间部位插队。常见的数据结构——队列

用计算机程序处理数据时，有时也需要将数据进行“排队”，并遵循现实中排队的规律，对数据进行“先进先出”FIFO（FirstInFirstOut）且中间不能“插队”的组织和操作，计算机科学家由此发明了“队列”这种数据结构。常见的数据结构——栈弹匣的装弹过程（入栈）子弹进出弹匣的过程具有下列特点：①整个装置只有一端开放（最上端），而且进、出只能在这一端进行。②弹匣中的子弹成一纵队排列。③任何子弹进出弹匣的规律是“先进后出、后进先出”，即最先装入弹匣的子弹最后才能被弹出，而最后装入弹匣的子弹则最先被弹出。问题与讨论在文字处理软件Word中输入若干文字，然后删除其中部分文字，再输入若干文字。然后进行“撤消”操作（按Ctrl+Z键，或者单击撤消操作快捷按钮“”）。观察各个操作后的现象，回答下列问题。（1）根据“撤消”操作所产生的结果，说明Word中符号输入及撤消操作中，内部所依托的数据结构是哪种数据结构？为什么？（2）结合自己的经历，谈谈哪些信息系统中也采用了栈这种数据结构。一筒羽毛球十进制转二进制拓展链接线性表是由零个或多个数据元素组成的有限序列，数据元素之间的关系是一对一的关系。线性表是一种基本的、常见的数据结构，可以根据需要向线性表中添加或者删除元素。数组、队列、链表都是线性表的特殊形式。应用实例：现在假设有7个数据元素的线性表，以删除数据元素3为例进行分析。53406821、数组存储：从a[0]开始找到数组元素“3”需要查找_______次，删除“3”后，其后续数组元素需要往前移动___________次，a[6]的值为__________2、单链表存储：从第一个结点的数据元素“5”开始找到数组元素“3”需要查找_______次，删除该结点后，其后续结点需要往前移动___________次，此时链表中数据元素的个数为__________252206应用实例：现在假设有7个数据元素的线性表，以删除数据元素3为例进行分析。53406823、队列存储：从队首查找到数组元素“3”需要查找_______次，删除“3”后，为保持原队列其他数据元素的次序不变，还需要出队___________次，入队_______次，次队列中数据元素的个数为___个。2、栈存储：从栈顶查找需要出栈_____次找到数组元素“3”，删除该元素后，为了保持栈内其他元素的次序不变，还需入栈___________次.255621常见的数据结构——树数据元素前面只有一个元素，后面可以有0个或多个元素相邻，所有元素之间的关系特征像一颗倒放的树。常见的数据结构——树问题与讨论分小组讨论，举出在生活和信息系统中用树组织数据的例子，并用树结构描述数据之间的关系特征。公司和部门各级领导关系学科思维导图等请画出其他结构图？数据结构的作用姓名班级滚铁圈打弹子拍纸板竹蜻蜓跳绳踢毽子陈涛932杨琼351金凯245吴敏1613朱刚强6517……………………1.设计算法解决问题离不开数据结构

数据统计前，需要先收集数据并将数据按照既有的逻辑关系进行结构化组织，可以用一张表格来组织数据并表示数据之间的逻辑关系。数据结构的作用2.不同数据结构会导致处理效率的不同xm(i)bj(i)d1(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……………………（2）用二维数组组织数据程序代码：其中的bjdf(j)表示第j班的总分数据结构的作用2.不同数据结构会导致处理效率的不同二维数组程序实现：一维数组程序实现：不同数据结构会导致处理效率的不同数据合并案例生产厂家总会根据各地产品销量的数据分析来预估市场情况，并为后续调整生产规划、完善营销策略提供依据。

由于数据量巨大，为了充分运用分布式处理的优势，总部会要求各下属地区上报数据时，按各产品销量进行从大到小的排序。总部收到数据后的第一件事是将所有数据合并并按照销量进行降序排序（从大到小），为了完成数据合并和整理工作，总部数据分析员小刚需要设计合适的数据结构和算法。不同数据结构会导致处理效率的不同分析：

小刚可以用一个二维数组存储所有下属地区的产品销量数据，然后直接运用排序算法进行降序排序。如果利用既有数据已是分块有序的特点，设计新的数据结构和算法，则处理效率可以得到相应的提升。

各个地区的数据合并问题可以简化为2个地区的数据合并问题，当2个地区的数据合并完成后，剩余各地区的数据合并就可以按照同样方式完成。因此，接下来着重分析2个地区的数据合并问题。不同数据结构会导致处理效率的不同第一步抽象与建模设第1个地区共有n个产品销量数据，第2个地区共有m个产品销量数据。为了简化描述，突出核心部分的分析，考虑将问题抽象为n个有序整数和m个有序整数的合并问题，具体的问题模型如下：已知一个降序排列的整数数列A：a1，a2，a3，…，an以及一个降序排列的整数数列B：b1，b2，b3，…，bm

，将两个数列合并形成一个新的有序数列C，使新数列仍按降序排列，即c1≥c2≥c3≥…≥ck≥ck+1≥…≥cn+m（其中ck∈A或者ck∈B）。请完成解决该问题的数据结构和算法的设计。不同数据结构会导致处理效率的不同第二步设计、描述算法1.基于数组的算法设计与描述（1）将数组a中所有元素存储到数组c的前n个位置中；1234519161285a191612851234519161285b20151410412345678910c12345678910不同数据结构会导致处理效率的不同第二步设计、描述算法1.基于数组的算法设计与描述（2）变量p赋值为0，将表示数组c中有效元素总个数的变量tot赋值为n；1234519161285a191612851234519161285b201514104c-1-1-1-1-10iptot12345678910不同数据结构会导致处理效率的不同（3）将数组b中元素b(i)逐个插入到数组c中（1≤i≤m）：1916128512345201514104b201514104c-1-1-1-1-10iptot①p值增加1；②如果c(p)＞b(i)，那么使p值增加1；③如果c(p)=–1，那么直接将b(i)存储到c(p)中，同时tot值增加1；④如果c(p)≤b(i)，那么依次将c(tot)，c(tot–1)，…，c(p)向右移动一个位置，然后将b(i)存储到c(p)中，同时tot值增加1。12345678910不同数据结构会导致处理效率的不同（4）将数组b中元素b(i)逐个插入到数组c中（1≤i≤m）：1916128512345201514104b201514104c-1-1-1-10iptot①p值增加1；②如果c(p)＞b(i)，那么使p值增加1；③如果c(p)=–1，那么直接将b(i)存储到c(p)中，同时tot值增加1；④如果c(p)≤b(i)，那么依次将c(tot)，c(tot–1)，…，c(p)向右移动一个位置，然后将b(i)存储到c(p)中，同时tot值增加1。pp②如果c(p)＞b(i)，那么使p值增加1；12345678910不同数据结构会导致处理效率的不同（4）将数组b中元素b(i)逐个插入到数组c中（1≤i≤m）：1916128512345201514104b201514104c-1-1-10itot①p值增加1；②如果c(p)＞b(i)，那么使p值增加1；③如果c(p)=–1，那么直接将b(i)存储到c(p)中，同时tot值增加1；④如果c(p)≤b(i)，那么依次将c(tot)，c(tot–1)，…，c(p)向右移动一个位置，然后将b(i)存储到c(p)中，同时tot值增加1。p12345678910不同数据结构会导致处理效率的不同（4）将数组b中元素b(i)逐个插入到数组c中（1≤i≤m）：1916128512345201514104b201514104c-1-10itot①p值