第10～11章 数据与数据组织 数组与链表-浙江高中信息技术知识点

37 第十章 数据与数据组织 1. 数据是对客观事物的性质、状态以及相互关系等进行描述的物理符号表示或 这些符号表示的组合 2. 数据的表现形式不仅有数字和数值，还有文字、图形、图像、音频、视频等。 3. 数字指的是由阿拉伯数字“0,1,2,3,4,5,6,7,8,9”或其他含义相同的符号表 示。 4. 数字本身没有意义，没有量的含义，数字只有在具体的情景中才具有实际的 意义 5. 数值指的是由数字符号组成的、具有量的意义的、可以进行算术运算的数据。 6. 数据是人类与客观世界进行对话的接口，数据对于人类有着极其重要的价值 与意义 7. 数据促进了人类社会的发展、大数据推动人类进入一个崭新的时代 8. 对数据进行加工与分析前，需要对数据进行预处理并将数据组织成一定的形 式，程序=算法+数据结构。 9. 数据元素：数据元素是数据的基本单位，数据元素也称为元素、节点、订点、 记录等。有时一个数据元素可以由若干个数据项组成，数据项是具有独立含义的 最小数据表示单位 10. 数据类型：数据类型是指具有相同性质的计算机数据的集合及在这个数据集 合上的一组操作，数据类型可分为基本数据类型和结构数据类型。 11. 数据结构指的是数据之间的相互关系，即数据的组织形式。他包括数据元素 之间的逻辑关系（也称为数据的逻辑结构）、数据元素及其关系在计算机存储器 内的表示（也称为数据的存储结构或物理结构）、数据的运算（对数据施加的操 作） 12. 常见的数据结构有；数组、链表、队列、栈、树 13. 遍历指的是根据数据之间的逻辑结构，遵循一定的顺序依次对所有的数据元 素做一次且仅做一次访问 14. 指针是用来指示一个数据存储地址（内存或寄存器）的变量。 15. 线性表是由 0个或多个数据元素组成的有限的序列，数据元素之间的关系是 一对一的关系，既除了第一个和最后一个数据元素外，中间任何一个数据元素的 前面和后面都只有一个数据元素与它相邻，数组、队列、栈、链表都是线性表的 特殊形式。 16. 数据结构的作用：1.设计算法解决问题离不开数据结构，2.不同的数据结构 会导致处理的效率的不同 38 第十一章 数组与链表 1. 数组在内存中的存储方式为顺序存储，数组作为常用的数据结构，有特定的 数据组织、存储结构及操作特性。 2. 计算机中数据的存储结构主要分为顺序存储结构和非顺序存储结构。常见的 顺序存储结构是数组，常见的非顺序存储结构是链表 3. 数字是由相同类型的变量构成的一个序列。数组使用一个标识符命名，并用 编号区分数组内的各个变量，这个特殊的标识符号称为数组名，编号称为下表或 索引。由数组名和下标组成数组的各个变量称为数组的分量，也称为数组元素。 （数组的下标一般从 0开始） 4. 数组在内存中的存储结构简单，创建数组时系统会分配一块连续的存储空间， 每个数组元素按照下标顺序依次存储。如下图 5. 一维数组适合用来表示具有线性特征的数据序列，因此只需要一个下标来表 示数据元素在该序列中的位置。如果要表示二维空间内既有纵向联系和又有横向 联系的一批数据，那么采用二维数组会变得更形象、方便由于二维数组中的数组 有行有列两个维度的位置信息，因此需要两个下标。二维数组下标详见下图： 6. 用二维数组表示的数据在内存中的存储方式也才用顺序存储，有行优先存储 和列优先存储。一般默认采用行优先。 7. 数组的特性：1.数组元素的数据类型相同，2.通过数组名的下标对数组元素 的值进行访问，3.数据存储空间不变 8. 动态数组就是在声明时没有确定数据规模的数组，可以在任何时候改变数据 39 规模。 9. 对数组的常见操作有：数组的创建、数组元素的访问、数组元素的插入和删 除等。 10. Python 没有数组这种数据结构，所以采用列表来实现。 11. 数组的和创建实质是在系统内存中划分一块连续区域，同来保存数组所含的 所有数据元素 12. 数组元素的访问指的是寻址到特定的数组元素，并根据存储地址对该数据元 素进行读取、修改等操作。因为数组元素从 0开始数，所以：例如 s[5] 访问的 是 s数组的第六个元素 13. Python 列表常用函数与方法: 14. 链表指的是将需要处理的数据对象以节点的形式，通过指针串联在一起的一 种数据结构。链表中的每一个节点一般由“数据区域”和“指针区域”两部分构 成（如下图）。数据区域用于保存实际需要处理的数据元素，指针区域用来保存 该节点相邻节点的存储地址，通过该地址指向（指针）来实现从当前节点按顺序 走到相邻的节点。某个节点前面的相邻节点称为该节点的前驱节点，后面的相邻 节点称为该节点的后继节点。 15. 每个链表都拥有一个表头---head(也称为头指针)，头指针的作用之一是链 表的入口，只有通过头指针才能进入链表；作用之二是为循环链表设立一个边界， 便于数据处理时的边界判断和处理。 16. 链表可以根据每个节点中指针的数量分为两类: 只有一个指针的单向链表 和有两个指针的双向链表（即每个节点有两个指针区域，一个指向前驱节点，一 个指向后继节点）。将第一个节点和最后一个节点使用指针链接，就会形成循环 链表 17. 单向链表中各个节点在内存中可以非顺序存储，每个节点使用指针指向后继 节点的存储地址。进入链表只能通过头指针 head，其他节点则需要经过所有在 40 它之前的节点才可以访问，尾节点的指针指向 null,表示指向为空（一般情况下， 尾指针为-1。当尾指针指向 head 时，即为循环链表） 18. 链表的特性：1.同一链表中每个节点的结构均相同，2.每个链表必定有一个 头指针，以实现对链表的引用和边界处理，3.链表占用的空间不固定。 19. 链表的操作有：链表的创建、链表节点的访问、链表节点的插入与删除 （一）二维数组单向链表代码实现 给定一个链表 a[]，其第一个元素代表的下标为 head。a[i] 代表的元素是一个 长度为 2 的数组，其中 a[i][0] 表示它的数据 data（数据都是整数），a[i][1] 表示它的下一个元素 next，如果 next 为 −1 代表其是链表的最后一个元素。 假设有如下代码： a = [['A',2],['D',-1],['B',3],['C',1]] head = 0 #删除第一个元素 head = a[head][1] #遍历链表 h = head while h != -1: print(a[h][0]) h = a[h][1] #删除中间元素,根据内容 B h = head pre = head while h != -1: if a[h][0] == 'B': break else: pre = h h = a[h][1] a[pre][1] = a[h][1] #在头部插入元素 head = 0 a.append(['E',head]) head = len(a)-1 #插入中间元素根据值 #首先找到 B h = head while h != -1: if a[h][0] == 'B': break else: h = a[h][1] #然后插入 E a.append(['E',a[h][1]]) a[h][1] = len(a)-1 链表相对于数组而言，更便于删除和 添加，数组相对于链表而言，更便于 查找和修改 41 （二）双向链表代码实现 给定一个链表 a[]，其第一个元素代表的下标为 head。a[i] 代表的元素是一个 长度为 3的数组，其中 a[i][0]表示当前节点的前一个节点 pre， a[i][1] 表示 它的数据 data（数据都是整数），a[i][2] 表示它的下一个节点 next，如果 next 为 −1 代表其是链表的最后一个元素。 假设有如下代码： a = [[-1,'A',2],[3,'D',-1],[0,'B',3],[2,'C',1]] head = 0 pre=next1=head #遍历链表(从前往后） while next1!=-1: print(a[next1][1]) next1=a[next1][2] #遍历链表(从后往前） while a[next1][2]!=-1: #先找到最后一个节点 next1=a[next1][2] pre=next1 while pre!=-1: #从最后一个节点向前遍历 print(a[pre][1]) pre = a[pre][0] #删除中间元素,根据内容 B while next1!=-1: if a[next1][1]=="B": break else: pre=next1 next1=a[next1][2] a[a[next1][2]][0]=a[next1][0] a[pre][2]=a[next1][2] #在头部插入元素 a.append([-1,'E',head]) head = len(a)-1 pre=next1=head #插入中间元素根据值 while next1!=-1: if a[next1][1]=="B": break else: next1=a[next1][2] a.append([next1,'E',a[next1][2]]) a[a[next1][2]][0]=len(a)-1 a[next1][2] = len(a)-1 #删除第一个元素 head = a[head][2] pre=next1=head 42 （三）一维数组单向链表代码实现 给定一个链表值数组 a[]，给定一个链表指针数组 ls[] 给定一个头指针 head a=['A','D','B','C'] ls=[2,-1,3,1] head=0 #遍历链表(从前往后） p=head while p!=-1: print(a[p]) p=ls[p] #删除第一个元素 head=ls[head] p=head #删除中间元素,根据内容 B p=q=head while p!=-1 and a[p]!="B": q=p p=ls[p] ls[q]=ls[p] #在头部插入元素 a.append("E") ls.append(head) head=len(ls)-1 #插入中间元素根据值 p=head while p!=-1 and a[p]!="B": p=ls[p] a.append("E") ls.append(ls[p]) ls[p]=len(ls)-1 43 （四） 旋转链表 有一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。 def xz(head): #旋转 q=p=head while a[p][1]!=-1: q=p p=a[p][1] pre=a[q][1] a[q][1]=a[p][1] a[p][1]=head return pre a = [['A',2],['D',-1],['B',3],['C',1]] head=0 for i in range(2): #旋转两次 head=xz(head) p=head while p!=-1: print(a[p][0]) p=a[p][1] 44 （五）翻转链表 给你单链表的头节点 head 和链表 a，请你反转链表，并返回反转后的链表。 原来：a->b->c->d 输出为：d->c->b->a # 翻转链表 def reverseList(head): pre = -1 p = head while p!=-1: next_temp = a[p][1] a[p][1] = pre pre = p p = next_temp return pre a = [['A', 2], ['D', -1], ['B', 3], ['C', 1]] head = 0 head=reverseList(head) p=head while p!=-1: print(a[p][0]) p=a[p][1] 浙江高中技术培优算法（陶小波） 45 （六）数组排序 1（链表实现） 原理： 第一步：先创建一个只有一个元素的链表。 第二步：依次生成节点，再将节点放置到链表中指定位置。 第三步：输出链表节点。 import random # 插入排序（链表实现）[891, 201, 404, 616, 437] ls = [] # 链表 ls[0][0]是值，ls[0][1]是指针 v = [random.randint(1, 1000) for i in range(5)] # 待排序的数 ls.append([v.pop(0), -1]) # 将第一个节点放入 head = 0 p = q = 0 while len(v) != 0: p = q = head while p != -1 and ls[p][0] > v[0]: q = p p = ls[p][1] if p!=head: #不放在链表头上 ls.append([v.pop(0), ls[q][1]]) ls[q][1] = len(ls) - 1 else: #放在链表头上 ls.append([v.pop(0), head]) head=len(ls)-1 p = head while p != -1: print(ls[p][0]) p = ls[p][1] 浙江高中技术培优算法（陶小波） 46 （七）数组排序 2（链表实现） ls = [] # 链表 ls[0][0]是值，ls[0][1]是指针 v = [891, 201, 404, 616, 437] # 待排序的数 ls.append([v.pop(v.index(max(v))), -1]) # 将第一个节点放入 head = 0 p = q = 0 while len(v) != 0: p = q = head #ls[p][1]!=-1 and ls[ls[p][1]][0]>v[0] while ls[p][1]!=-1 and ls[ls[p][1]][0]>v[0]: #问题 1，初始值就是-1 q = p p = ls[p][1] if ls[p][1]!=head : #404 要走这里 ls.append([v.pop(0), ls[p][1]]) ls[p][1]= len(ls) - 1 else: #放在链表头上 ls.append([v.pop(0), head]) head = len(ls) - 1 p = head while p != -1: print(ls[p][0]) p = ls[p][1] 浙江高中技术培优算法（陶小波） 47 （八）链表求和 用链表 1->2->3+1->2->3 得到结果为 2->4->6 def reverseList(a,head): pre = -1 p = head while p!=-1: next_temp = a[p][1] a[p][1] = pre pre = p p = next_temp return pre #求和 lsa=[[1,1],[2,2],[3,-1]] lsb=[[1,1],[2,2],[3,-1]] heada=headb=0 heada=reverseList(lsa,heada) headb=reverseList(lsb,headb) p1,p2=heada,headb q1=p1 while p1!=-1 and p2!=-1: q1=p1 lsa[lsa[p1][1]][0]+=((lsa[p1][0]+lsb[p2][0])//10) lsa[p1][0]=((lsa[p1][0]+lsb[p2][0])%10) p1=lsa[p1][1] p2=lsa[p2][1] heada=reverseList(lsa,heada) p=heada while p!=-1: print(lsa[p][0],end="") p=lsa[p][1]