10.线性存储结构_数组、链表 知识点梳理- 2023届浙教版（2019）高考信息技术专题复习（选修）

*线性存储结构* 第十章 数组、链表 一、数组 1.数组的特性 (1)数组元素的数据类型相同 (2)通过数组名和索引对数组元素进行访问 (3)数组（主要指静态数组）在内存中的存储空间连续且固定不变 (4)Python中没有数组这种结构，教材中使用列表来模拟数组的操作 (5)二维数组在存储时也采用顺序存储，Python中对二维数组采用的是行优先的存储方式。 2.创建数组 一维数组 s1 = [0]*9          #间接创建 s1 = [1,2,3,4]      #直接创建 二维数组 s2 = [[0 for i in range(4)]for i in range(4)]    #间接创建 s2 = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]         #直接创建 3.浅拷贝 Python中创建二维数组不能使用如同一维数组的创建方式，如s2=[[0]*4]*4。这样在修改某行元素时会导致4行中同一列的数据会同时被修改。这与Python在创建变量时实际是创建了引用有关。以上这种情况被称之为浅拷贝。 4.列表生成式 格式：<元素表达式> <for 循环语句> <if 条件约束> d1 = [i*i for i in range(10)] d1= [0, 1, 4, 9, 16, 25, 36, 49, 64, 81] d2 = [i*i for i in range(10) if i%2==0] d2= [0, 4, 16, 36, 64] d3 = [m+n for m in 'ABC' for n in 'XYZ'] d3= ['AX', 'AY', 'AZ', 'BX', 'BY', 'BZ', 'CX', 'CY', 'CZ'] d4 = [s.lower() for s in ["ABC",'EDG','LSP']] d4= ['abc', 'edg', 'lsp'] 5.在数组中插入数据/删除数据 #在数组中插入数据(while循环为例) a = [1,3,5,7,9,11,13,15,17,19,0]   num = 6         #待插入数据 i = 0 while i<len(a): #查找变量插入位置     if a[i]<num:         i = i + 1     else:         break j = len(a)-1   #从最后一位开始移动 while j > i:   #插入位置后的元素后移     a[j] = a[j-1]       j = j - 1 a[i] = num #数据插入 print(a) #在数组中删除数据(for循环为例) a = [1,3,5,7,9,11,13,15,17,19] num = 9   #需要删除的元素 i = 0 for i in range(len(a)):     if a[i] == num:         break for j in range(i+1,len(a)): a[j-1] = a[j] a[i] = 0       #末尾清空 print(a) 【注:】数组由于自身特性，在执行插入和删除过程中都需要移动元素。而向前和向后移动元素时，需要防止元素相互覆盖，这一点需要特别小心。 二、链表 1.链表的特性 (1)同一链表中每个节点的结构均相同，包括值域的数据类型以及指针域的数量和功能 (2)每个链表必定有一个头指针，实现对链表的引用和边界处理。链表访问只能从头指针开始，通过指针链接向后依次访问。 (3)链表占用的存储空间不连续且不固定。链表的存储空间由节点数决定，增加或减少节点会改变链表占用空间。 (4)Python没有直接定义链表结构，教材中用列表来模拟链表的操作。而在第十二章，会演示通过类方式创建链表的方法。 2.创建空链表 item=[] #存储空间 head=-1 #头指针（-1表示没有后继节点） 3.单向链表 单向链表即链表节点的指针域只有一个指向下一个元素的后继指针。后面的操作中我们默认定义单向链表的节点格式为[data,next]，next存放的是节点在列表中的索引值。 3.1单向链表的元素遍历 head = 4 item=[[5,2],[7,3],[9,5],[2,-1],[1,0],[3,1]] p = head #运行结果 1->5->9->3->7->2 【注:】两种方式的区别已经用加框出标出。思考两个循环在结束时，遍历指针p所在的位置。 #方式1 str1 = '' while p != -1:     str1 += str(item[p