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

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

1、线性存储结构事第十章数组、链表一、数组1.数组的特性(1)数组元素的数据类型相同(2)通过数组名和索引对数组元素进行访问(3)数组(主要指静态数组)在内存中的存储空间连续且固定不变(4)Python中没有数组这种结构，教材中使用列表来模拟数组的操作(5)二维数组在存储时也采用顺序存储,Python中对二维数组采用的是地选的存储方式。2.创建数组一维数组si=0*9#间接创建si=1,2,3,4#直接创建二维数组s2=0foriinrange(4)fbriinrange(4)#间接创建s2=1,24,5,68,9,10J1J2#直接创建3 .浅拷贝PyIhon中创建二维数组不能使用如同一维数组的

2、创建方式，如s2=0*4*4.这样在修改某行元素时会导致4行中同一列的数据会同时被修改。这与Python在创建变量时实际是创建了引用有关。以上这种情况被称之为浅拷贝。4 .列表生成式格式：元素表达式for循环语句if条件约束dl=i*iforiinrange(l()dl=(),1,4,9,16,25,36,49,64,81d2=i*iforiinrange(10)ifi%2=0d2=0,4,16,36,64d3=m+nfornin,ABCforninXYZ1d3=AX,AY,AZ,BX,BY,BZ,CX,CY,CZ,d4=s.lower()forsinABC,EDG,LSP,1d4=,abc,

3、edg,Isp5.在数组中插入数据/删除数据#在数组中插入数据(While循环为例)a=1,3,5,7,9,IT,13,15,17,19,0num=6#待插入数据i=0whileilen(a):#查找变量插入位置ifaii:#插入位置后的元素后移aj=aj-lj=j-1ai=num#数据插入print(a)#在数组中删除数据(for循环为例)a=1,3,5,7,9,11,13,15,17,19num=9#需要删除的元素i=0foriinrange(len(a):ifai=num:breakforjinrange(i+l,len(a):aj-l=ajai=0#末尾清空print(a)【注:】数组

4、由于自身特性，在执行插入和删除过程中都需要移动元素。而向前和向后移动元素时，需要防止元素相互覆盖，这一点需要特别小心。二、链表1 .链表的特性(1)同一链表中每个节点的结构均相同,包括值域的数据类型以及指针域的数量和功能(2)每个链表必定有一个头指针,实现对链表的引用和边界处理。链表访问只能从头指针开始，通过指针链接向后依次访问。(3)链表占用的存储空间不连续且不固定。链表的存储空间由节点数决定，增加或减少节点会改变链表占用空间。(4)PythOn没有直接定义链表结构，教材中用列表来模拟链表的操作。而在第十二章，会演示通过类方式创建链表的方法。2 .创建空链表item=#存储空间head=-l

5、#头指针(-1表示没有后继节点)3 .单向链表单向链表即链表节点的指针域只有一个指向下一个元素的后继指针。后面的操作中我们默认定义单向链表的节点格式为data,next,next存放的是节点在列表中的索引值。3.1 单向链表的元素遍历head=4item=5,2j7,3,9,5,2,-l,l,0,3,lp=head#运行结果l-5-9-3-7-2【注:】两种方式的区别已经用加框出标出。思考两个循环在结束时，遍历指针P所在的位置。#方式1strl=whilepi=-1:strl+=str(itemp0)+-p=itemp1#跳转到下一节点print(strl:-2)#清除最后的“#方式2whil

6、eIitempt!=-1:print(str(itemp0)+-,end=,)p=itemp1#跳转到下一节点print(itemp0)3.2在单向链表中插入节点在链表中执行插入和删除操作时，建议先建立模型，然后根据模型分类讨论链表头插入Ihead1data2Ildta3IheedJdatall；XdaU4InextIrwxtIMxtIdata=3#插入位置判断略#判断结果为遍历指针P指向data3,pre指向datald(date,p)itempre1=len(item)-l链表尾部插入*aau41I2皿I5I川卜：I:IIntIrwpIIWrtdata=6#插入位置判断略#判断结果为遍历指

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

8、ut()#被插入数据，要求插入后链表依然保持升序。p=headwhileitemp0Fdatalnextdata2IHnexthead=0data=1,2,3#值域next=1,2,-1#指针域#删除位置判断略#判断结果为遍历指针p指向datalhead=netp删除中间节head|直data1nextata2nextdata3next#删除位置判断略#判断结果为遍历指针P指向data2,pre指向datalnetpre=netp删除尾节点hood_Jdat1IdU2Idta3Inea|XKtR|rwxt#删除位置判断略#判断结果为遍历指针p指向-1,Pre指向data3netpre=netp

9、-l以上就是链表删除的三种情况，但实际操作过程中，还可能出现第四种情况，即删除位置不存在。不过这种情况在遍历过程中就己经处理，链表本身没有改变。1 .链表的删除与插入类似的，中间和尾部删除的代码可以更用2 .链表的删除过程中也需要保存前向节点位置的pre指针3 .这次的例子中，原链表节点的值域和指针域是分别放在两个存储空间中,对于这种方式构建的链表，也要掌握其操作方式。以下是链表删除的完整过程head=0data=1,2,2,3next=1,2,3,-1num=int(input()#被删除数据p=headwhilep!=-l:ifitemp0=num:ifp=head:#链表头部删除head

10、=nextpelse:#链表中间或尾部删除nextpre=nextpelse:pre=pp=netp#遍历跳转细心的同学可能会发现链表删除代码中，查找和删除是同时进行的。这么做的原因是删除有两种情况：1.删除指定元素，有重复元素也只删除一次4 .删除指定元素，由重复元素全部删除在第二种情况下就必须完整遍历整个链表，尤其当重复元素在链表中连续时(如上例)，pre需要特殊处理。这个细节做题时需要格外注意。4.双向链表双向链表即链表节点的指针域有两个指针，分别指向前驱节点和后继节点。后面的操作中我们默认定义双向链表的节点格式为date,prev,next,PreV为前驱指针，nexl为后继指针。指针

11、域存放的是节点在列表中的索引值。4.1 在双向链表中插入数据在双向链表中插入节点的操作和单向链表类似。唯一的不同点是，双向链表可以通过前向指针返回前向节点，所以不需要通过Pre保存前向节点的位置。完整的操作代码如下head=item=2,-l,l,4,0,246,l,-lnum=int(input()#被插入数据，要求插入后链表依然保持升序p=headwhileitemp0numanditemp2!=-1:注意与单向链表的区别P=itemp2ifp=head:#链表头插入d(num,-l,head)head=Ien(item)-1#注意先后顺序itemp1=Ien(item)-1#注意先后顺序

12、elifitemp0num:#链表中间插入d(num,itempl,p)itemitempl2=len(item)-l#注意先后顺序itemp1=len(item)-l#注意先后顺序else:#链表尾插入d(num,pj-l)itemp2=len(item)-l注意：由于没有Pre保存前向位置，完成尾插时，P不能等于1。所以代码中需要做如下处理：l.p遍历结束时，在最后一个链表节点上。2.当P在最后一个节点时，需要分别判断中间插入和尾部插入两情况。4.2在双向链表中删除数据与单向链表删除类似，双向链表删除也不需要前向节点指针pre,同时，在删除过程中也需要考虑多个删除值存在时，删除一个还是多个的问题。完整的删除代码如下head=0item=1,-1,1,2j0,242,1,3,3j2,-1num=int(input()#被删除数据p=headwhilep!=-1:ifitemp0=num:ifitemp1!=-l:itemitemP12=itemp2ifitemp2!=-1:itemitemP2