线性存储结构第十章数组、链表.docx

《线性存储结构第十章数组、链表.docx》由会员分享，可在线阅读，更多相关《线性存储结构第十章数组、链表.docx（6页珍藏版）》请在第一文库网上搜索。

1、*线性存储结构*第十章数组、链表一、数组L数组的特性数组元素的数据类型相同(2)通过数组名和索引对数组元素进行访问数组(主要指静态数组)在内存中的存储空间连续且固定不变(4)Python中没有数组这种结构，教材中使用列表来模拟数组的操作二维数组在存储时也采用顺序存储,Python中对二维数组采用的是任优先的存储方式。2 .创建数组一维数组si = 0*9#间接创建si = 1,2,3,4# 直接仓 IJ建二维数组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 .浅拷贝Pyth

2、on中创建二维数组不能使用如同一维数组的创建方式，如s2=0*4*40这样在修改 某行元素时会导致4行中同一列的数据会同时被修改。这与Python在创建变量时实际是创 建了引用有关。以上这种情况被称之为浅拷贝。4 .列表生成式格式： 元素表达式for循环语句if条件约束dl = i*i for i in range(10)dl= 0, 1, 4, 9, 16, 25, 36, 49, 64, 81d2 =i*i for i in range(10) if i%2=0d2= 0, 4, 16, 36, 64d3 = m+n for m in ABC for n in XYZd3= AX, AY,

3、 AZ, BX, BY, BZ, CX, CY, CZd4 = s.lower() for s in ABC,EDG,LSPd4= abc, edg, lsp5 .在数组中插入数据/删除数据#在数组中插入数据(WhiIe循环为例)a = 1,3,5,7,9,11,13,15,17,19,0num = 6#待插入数据i = 0while ilen(a): #查找变量插入位置 if ai i:#插入位置后的元素后移aj = aj-l J=J-Iai = num#数据插入print(a)#在数组中删除数据(for循环为例)a = 1,3,5,7,9,11,13,15,17,19num = 9#需要删

4、除的元素i = 0for i in range(len(a):if ai = num: breakfor j in range(i+ljlen(a): aj-l = ajai = 0#末尾清空print(a)【注:】数组由于自身特性，在执行插入和删除过程中都需要移动元素。而向前和向后移动 元素时，需要防止元素相互覆盖，这一点需要特别小心。二、链表1 .链表的特性同一链表中每个节点的结构均相同,包括值域的数据类型以及指针域的数量和功能(2)每个链表必定有一个头指针,实现对链表的引用和边界处理。链表访问只能从头指针开 始，通过指针链接向后依次访问。链表占用的存储空间不连续且不固定。链表的存储空间由

5、节点数决定，增加或减少节点 会改变链表占用空间。(4)PythOn没有直接定义链表结构，教材中用列表来模拟链表的操作。而在第十二章，会演 示通过类方式创建链表的方法。2 .创建空链表item= #存储空间head=-l#头指针(-1表示没有后继节点)3 .单向链表单向链表即链表节点的指针域只有一个指向下一个元素的后继指针。后面的操作中我们默 认定义单向链表的节点格式为data,next, next存放的是节点在列表中的索引值。3.1 单向链表的元素遍历head = 4item=5,2j7,3j9,5 J2,-1J1,0 J3,lP = head#运行结果5-9-3-7-2【注：】两种方式的区别

6、已经用加 框出标出。思考两个循环在结束 时，遍历指针P所在的位置。#方式1Strl =while p != -1:strl += str(itemp 0)+,-p = itemp 1#跳转到下一节点print(strl :-2)#清除最后的#方式2while itnrnpt != -1:print (str (itemp 0 ) + ,-,end=,)p = itemp 1#跳转到下一节点print(itemp0)3.2在单向链表中插入节点在链表中执行插入和删除操作时，建议先建立模型，然后根据模型分类讨论链表头插入data1 1| head dsts2 jd3ts3 Idata4 nextne

7、xtnexthead = 0item=2,lj4,2j5,-l date = 1#插入位置判断略 d(date,head)head = len(item)-1链表中间插入,j data2 head M data1：川 data3 川 data4data = 3#插入位置判断略#判断结果为遍历指针P指向data3,pre指向 datald(date,p)itempre1 = len(item)-1链表尾部插入da：a4 I head I1 datal data2 Idata3 卜 | : |next Inext 卜7nextdata = 6#插入位置判断略#判断结果为遍历指针p指向-1,Pre指

8、向data3 d(date,p)data,-litempre1 = len(item)-l以上就是链表插入节点的三种情况。在上述核心代码中我们发现几个有意思现象：1 .插入过程中不仅需要插入位置后向节点的位置P，也需要保存插入位置前向节点位置Pre2 .当使列表模拟链表时，由于指针域存储的是节点在列表中的索引值位置。插入新节点时不 能影响到原链表指针，插入必须使用append追加,并统一保持正索引方式构建指针。3 .虽然中间插入和尾部插入属于两种不同情况，但插入代码完全一致，可以直接复用。以下是完整的链表插入过程head = 0item = 2,1 J4,2J5,-1num = int(inp

9、ut()#被插入数据，要求插入后链表依然保持升序。p = headwhile itemp 0 num and itemp 2 ! = -l: 注意与单向链表的区别P = itemp2if p=head:#链表头插入d(numj-ljhead) head = len(item)-l#注意先后顺序itemp 1=Ien(item)-1#注意先后顺序elif itemp 0 num:#链表中间插入d(num,itempl,p)itemitemp 1 2 = len(item)-l#注意先后顺序itemp 1 = len(item)-l#注意先后顺序else:#链表尾插入d(num,p,-l)itemp2 = len(item)-l注意：由于没有Pre保存前向位置，完成尾插时，p不能等于-1。所以代码中需要做如下处理： Lp遍历结束时，在最后一个链表节点上。2.当P在最后一个节点时，需要分别判断中间插入和尾部插入两情况。4.2在双向链表中删除数据与单向链表删除类似，双向链表删除也不需要前向节点指针pre,同时，在删除过程中也需 要考虑多个删除值存在时，删除一个还是多个的问题。完整的删除代码如下head = 0item = 1,-1,1,2,0,2J2,