1、主要学习内容1线性表的概念和性性表的概念和性质线性表的性表的顺序序实现23线性表的性表的链式式实现4线性表性表应用及其下算法用及其下算法设计线性表概念及性质v线性表性表简称表，称表，是是由由n（n0）个数据元素构成的有限序列。）个数据元素构成的有限序列。n称为线性表的表长，当n=0，表长为0，表中没有元素，称为空线性表，简称空表；当n0，非空表，记为：L=(a0,a1,a2,ai,an-1)；每个元素有一个固定的位序号，如元素a0的位序号是0，ai的位序号是i；例如，A=(5,3,2,9)包含4个整数，这4个元素的位序依次为0、1、2、3。线性表v线性表性表中元素之中元素之间的次序非常的次序非
2、常重要重要。v举例：例：一个一个单词是是字符构成的字符构成的线性表性表；一一篇文章是篇文章是单词构成的构成的线性表性表；一一个菜个菜谱是由操作指令构成的是由操作指令构成的线性表性表；一一个文件是磁个文件是磁盘上的数据上的数据块构成的构成的线性表性表。线性表vL=(a0,a1,a2,ai,an-1)，除除了了首首元元素素a0，每每个个元元素素都都有有一一个个直直接接前前驱，除了尾元素，除了尾元素an-1，每个元素都有一个直接后，每个元素都有一个直接后继；v元元素素之之间的的关关系系为一一对一一的的线性性关关系系，线性性表表的的逻辑结构构是是线性性结构。构。v如如果果线性性表表中中的的元元素素值随
3、随着着位位序序的的增增大大递增增或或递减减，则该线性性表表称称为有序表；有序表；v如如果果元元素素值的的大大小小和和位位序序之之间没没有有特特定定关关系系，则该线性性表表称称为无无序表。序表。线性表v有有穷性：性：线性表中的元素个数是有限的；性表中的元素个数是有限的；v同同构构性性：一一般般来来说，线性性表表中中所所有有元元素素具具有有相相同同的的性性质，即即具具有有相同的相同的类型；如果数据元素性型；如果数据元素性质不同，通常不具有不同，通常不具有实际应用意用意义；v不不同同类型型元元素素构构成成的的线性性表表，如如一一个个整整数数线性性表表和和一一个个书目目单，虽然然作作用用和和应用用场合
4、合不不同同，但但其其元元素素之之间的的逻辑关关系系和和基基本本操操作作是相同的。是相同的。线性表特点T类型型元素构成的元素构成的线性表是由性表是由T类型型元素构成的有限序列元素构成的有限序列，并且具有以下基本操作：，并且具有以下基本操作：（1）创建一个空建一个空线性表（性表（init）；）；（2）判断）判断线性表是否性表是否为空（空（empty）；）；（3）求出）求出线性表的性表的长度（度（len）；）；（4）将）将线性表清空（性表清空（clear）；）；（5）在指定位置插入一个元素（）在指定位置插入一个元素（insert）；）；（6）删除指定位置的元素（除指定位置的元素（remove）；）；
5、（7）获取指定位置的元素（取指定位置的元素（retrieve）；）；（8）用指定元素替）用指定元素替换线性表的指定位置性表的指定位置处的元素（的元素（replace）；）；（9）判断指定元素）判断指定元素item在在线性表中是否存在（性表中是否存在（contains）；）；（10）对线性表中每个元素性表中每个元素进行遍行遍历（traverse）。）。线性表的抽象数据类型ADT1）动态性：线性表是动态的结构，可以进行元素的插入或删除，长度可以变化。2）基于位序进行插入、删除、读写等操作。vPython列表（列表（list）表元素可不同构实现ADT中的全部方法vPython元元组（tuple）表不
6、可以改变，不能修改、添加、删除元素，只能按位序访问vPython字符串（字符串（str）表中元素限定为单个字符字符串操作Python内置线性结构 线性表抽象类fromabcimportABCMeta,abstractmethodclassAbstractList(metaclass=ABCMeta):抽象表类，metaclass=ABCMeta表示AbstractList类为ABCMeta的子类abstractmethoddef_init_(self):初始化线性表abstractmethoddefempty(self):判断表是否为空abstractmethoddef_len_(self):
7、返回表中元素的个数abstractmethoddefclear(self):清空表abstractmethoddefinsert(self,i,item):在表中i号位置插入元素item“abstractmethoddefremove(self,i):删除i号位置的元素abstractmethoddefretrieve(self,i):获取i号位置的元素abstractmethoddefreplace(self,i,item):用item替换表中i号位置的元素abstractmethoddefcontains(self,item):判断表中是否包含元素itemabstractmethoddef
8、traverse(self):输出表中的所有元素v按操作方法不同按操作方法不同普通线性表、列表，是Python列表的抽象概念栈队列双端队列优先队列v按数据元素按数据元素类型不同型不同字符串线性结构分类v顺序存序存储v链式存式存储线性表的存储线性表的顺序存储v所所有有元元素素按按照照逻辑顺序序依依次次存存储在在一一块连续的的存存储空空间中中，简称称顺序表。序表。v具具有有前前驱、后后继关关系系的的两两个个元元素素其其内内存存映映像像也也相相邻，即即元元素素之之间物理位置的相物理位置的相邻直接反映其直接反映其逻辑关系的前后。关系的前后。顺序存储元素内置的顺序表an-1n-1aiia11a00数据元
9、素数据元素逻辑地址逻辑地址an-1Location(a0)+(n-1)*caiLocation(a0)+i*ca1Location(a0)+ca0Location(a0)数据元素数据元素存储地址存储地址c 是是一个一个元素的大小。元素的大小。an-1Location(a0)+(n-1)*caiLocation(a0)+i*ca1Location(a0)+ca0Location(a0)数据元素数据元素存存储地址地址c 是一个指针（引用）的大小是一个指针（引用）的大小，指向元素对象。指向元素对象。元素外置的顺序表v不不管管是是元元素素内内置置的的顺序序表表和和外外置置的的顺序序表表，根根据据元元素
10、素位位序序号号可可以以直直接接定定位位到到元元素素的的地地址址，对元元素素的的存存取取操操作作可可以以在在O(1)时间内内完完成。成。v称称顺序表具有随机存取（序表具有随机存取（Random Access）或直接存取的特性。）或直接存取的特性。v示意示意图：顺序表特点及简化表示012i-1a0a1a2aian-1entryv如如线性表性表A=(5,3,2,9)v在在Python语言中直接将其表示言中直接将其表示为一个一个list，如，如alst=5,3,2,9v未封装未封装实现。顺序表存储1：用Python列表直接表示Python列表的存储64位机，每个指针8个字节Python列表的空间递增机
11、制倍增策略和增量策略相结合倍增策略：将原来数组的容量乘以一个大于1的常数；增量策略是给数组容量增加一个数值。在空间较小时，采用倍增机制；在列表空间较大时，采用增量策略，依次增加9,10,11,12,14,16,18个空间。从空表开始生成长度为1000（10000）的表，需要27（46）次空间追加操作。列表长度0,总占用字节数56列表长度1,总占用字节数88,表元素容器大小4,增加大小:4列表长度5,总占用字节数120,表元素容器大小8,增加大小:4列表长度9,总占用字节数184,表元素容器大小16,增加大小:8列表长度17,总占用字节数256,表元素容器大小25,增加大小:9列表长度26,总占
12、用字节数336,表元素容器大小35,增加大小:10列表长度36,总占用字节数424,表元素容器大小46,增加大小:11列表长度47,总占用字节数520,表元素容器大小58,增加大小:12列表长度59,总占用字节数632,表元素容器大小72,增加大小:14列表长度73,总占用字节数760,表元素容器大小88,增加大小:16列表长度89,总占用字节数904,表元素容器大小106,增加大小:18列表长度107,总占用字节数1064,表元素容器大小126,增加大小:20列表长度127,总占用字节数1240,表元素容器大小148,增加大小:22列表长度149,总占用字节数1440,表元素容器大小173,
13、增加大小:25列表长度174,总占用字节数1664,表元素容器大小201,增加大小:28列表长度202,总占用字节数1920,表元素容器大小233,增加大小:32列表长度234,总占用字节数2208,表元素容器大小269,增加大小:36列表长度270,总占用字节数2528,表元素容器大小309,增加大小:40列表长度310,总占用字节数2888,表元素容器大小354,增加大小:45列表长度355,总占用字节数3296,表元素容器大小405,增加大小:51列表长度406,总占用字节数3752,表元素容器大小462,增加大小:57列表长度463,总占用字节数4264,表元素容器大小526,增加大小
14、:64扩容总次数:21import syslst=empty_size=b=sys.getsizeof(lst)count=0print(列表长度%4d,总占用字节数%4d%(0,b)for k in range(500):lst.append(None)a=len(lst)old_b=b b=sys.getsizeof(lst)if b!=old_b:print(列表长度%4d,总占用字节数%4d,表元素容器大小%4d,增加大小:%4d%(a,b,(b-empty_size)/8,(b-old_b)/8)count+=1print(扩容总次数:,count)整个算法O(n)resize所花时
15、间可以忽略；每个append操作的摊销时间复杂度仍为O(1)。顺序表存储2：用python的list封装实现利用底层C数组实现顺序表v定定义一一个个自自定定义类DynamicArrayList来来模模拟一个一个顺序表；序表；v利利用用ctypes模模块提提供供的的底底层C数数组实现线性性表表的的顺序序存存储，需需import ctypes ；v底底层C数数组对应于于内内存存中中的的一一块容容量量确确定定的的连续内内存存空空间，线性性表表元元素素依依次次直直接接存存放放在在该数数组中中，即即元元素素内内置置方方式式顺序存序存储。顺序表存储3：利用底层C数组实现顺序表importctypesfro
16、mAbstractListimportAbstractListclassDynamicArrayList(AbstractList):def_init_(self):defempty(self):def_len_(self):defclear(self):definsert(self,i,item):defremove(self,i):defretrieve(self,i):defreplace(self,i,item):defcontains(self,item):defappend(self,item):deftraverse(self):def_str_(self):def_make_a
17、rray(self,c):def_resize(self,c):初始化def _init_(self,cap=0):初始化一个空表 super()._init_()self._cur_len=0#线性表元素个数计数 self._capacity=cap#默认数组容量 self._entry=self._make_array(self._capacity)#存放所有表元素的数组def _make_array(self,c):#私有方法 返回一个容量为c的数组 return(c*ctypes.py_object)()O(1)判空、求长度、清空def empty(self):return self.
18、_cur_len=0def _len_(self):返回线性表中元素个数 return self._cur_lendef clear(self):del self._entry self._capacity=0 self._cur_len=0 O(1)插入 insert(self,i,item)if self._cur_len=self._capacity:#如果线性表的空间已用完 if self._capacity=0:cap=4 else:cap=2*self._capacity self._resize(cap)#给线性表扩容1倍空间 O(n)for j in range(self._c
19、ur_len,i,-1):#线性表尾部至i号位置所有元素后移 self._entryj=self._entryj-1 self._entryi=item#将新元素item放在i号位置 self._cur_len+=1#表长增1def insert(self,i,item):将元素item插入到表的i号位置 if not 0=i=self._cur_len:raise IndexError(插入位置不合法)数组空间扩容def _resize(self,c):#保护方法 将数组空间扩容至c.temp=self._make_array(c)#生成新的更大的数组temp for k in range(
20、self._cur_len):#将原线性表元素复制到新数组temp中 tempk=self._entryk self._entry=temp#启用新数组temp存放线性表元素 self._capacity=c#当前线性表的容量为c按位置删除 def remove(self,i)def remove(self,i):if not 0=i self._cur_len:raise IndexError(删除位置不合法)O(n)item=self._entryi for j in range(i,self._cur_len-1):#将找到位置之后的元素后移。self._entryj=self._ent
21、ryj+1 self._cur_len-=1#表长减1 return item#返回被删除元素按值查找def contains(self,item):for i in range(self._cur_len):if self._entryi=item:return True return FalseO(n)按位置读写def retrieve(self,i):if not 0=i self._cur_len:raise IndexError(读取位置不合法)return self._entryidef replace(self,i,item):if not 0=i self._cur_len:r
22、aise IndexError(写入位置不合法)self._entryi=itemO(1)随机存取vPython语言言的的列列表表和和C语言言的的数数组都都可可以以用用来来实现线性性表表的的顺序序存存储，并且其基本操作的，并且其基本操作的实现和和时间性能也大体一致。性能也大体一致。v在在具具体体存存储和和使使用用时，Python语言言的的列列表表更更加加方方便便灵灵活活，C语言言的数的数组空空间更加更加紧凑。凑。vPython列列表表的的本本质就就相相当当于于一一个个指指针数数组，凡凡是是用用列列表表实现的的各各个数据个数据结构都可以用构都可以用C语言数言数组或或array模模块中的数中的数组
23、来来实现。说明线性表的链式实现v线性性表表的的链式式实现不不需需要要使使用用连续内内存存空空间，表表中中的的数数据据元元素素可可以存以存储在任意可用空在任意可用空间中。中。v链式式结构通构通过显式的指式的指针域来表明元素的前域来表明元素的前驱、后、后继关系。关系。v链式式结构构中中，元元素素在在内内存存中中的的映映像像称称为结点点，结点点包包含含两两大大部部分分：元元素素值和和指指针域域，其其中中指指针域域用用于于记录其其后后继结点点或或前前驱结点点的的地址。地址。v线性性表表的的链式式实现结构构简称称为链表表，根根据据结点点中中指指针域域的的数数目目及及尾部尾部结点指点指针的定的定义，可以分
24、，可以分为单链表、双向表、双向链表、循表、循环链表等。表等。v最常最常见的的链表形式是表形式是单链表。表。链表概述v单链表表的的每每个个结点点包包含含2个个域域，其其中中entry域域存存储元元素素，next域域存存储后后继结点的指点的指针。v在在Python语言言中中，entry域域存存储的的是是元元素素的的指指针，而而在在其其他他语言言如如C+中，中，entry域存域存储的即是元素的即是元素值。单链表的结点结点类class Node:def _init_(self,data,link=None):self.entry=data self.next=linkv L=(a0,a1,a2,ai,
25、an-1)Python语言中单链表的存储C、Java等语言中单链表的存储单链表单链表示意图用首结点指针head代表整个线性表带头结点的单链表a0aian-1headai-1ai+1首结点尾结点头结点用头结点指针head代表整个线性表python的对象名即指针单链表类fromAbstractListimportAbstractListfromNodeimportNodeclassLinkedList(AbstractList):def_init_(self):defempty(self):def_len_(self):defclear(self):definsert(self,i,item):d
26、efremove(self,i):defretrieve(self,i):defreplace(self,i,item):defcontains(self,item):deftraverse(self):defget_head(self):初始化、判空def _init_(self):super()._init_()self._head=Node(None)def empty(self):return self._head.next=NoneheadO(1)求长度def _len_(self):def _len_(self):p=self._head.nextcount=0while p!=N
27、one:p=p.nextcount+=1return countO(n)a0aian-1headai-1ai+1ppp顺序访问列表清空def clear(self):def clear(self):p=self._head.next self._head.next=None while p:q=p p=p.next del qa0a1aian-1headai-1ai+1首结点尾结点头结点O(n)读取i号元素 def retrieve(self,i):def retrieve(self,i):if i 0:raise IndexError(i is too small)p=self._head.
28、next count=0 while p and count i:p=p.next count+=1 if p:return p.entry else:raise IndexError(i is too big)O(n)顺序存取a0a1aian-1headai-1ai+1pppcount=0count=i p=self._head.next count=0 while p and count i:p=p.next count+=1将元素item插入到表的i号位置a0a1aian-1headai-1ai+1previousitemnew_nodeprevious.next=new_nodepre
29、vious=self._headcount=-1whilepreviousandcounti-1:previous=previous.nextcount+=1def insert(self,i,item):if i 0:raise IndexError(i is too small)previous=self._head count=-1 while previous and count i-1:previous=previous.next count+=1 if previous is None:raise IndexError(i is too big)new_node=Node(item
30、)new_node.next=previous.next previous.next=new_nodeO(n)p=self._head.next count=0 while p and count i:p=p.next count+=1previous为空，说明i-1结点不存在；不能在i号位置插入；否则指向i-1号结点new_node=Node(item)new_node.next=previous.next删除i号位置的元素a0a1aian-1headai-1ai+1previouscurrentprevious.next=current.nextdef remove(self,i):if
31、i 0:raise IndexError(i is too small)previous=self._head j=-1 while previous and j i-1:previous=previous.next j+=1 if previous is None:raise IndexError(k is too big,no element has position i-1)current=previous.next if current is None:raise IndexError(k is too big,no element has position i)previous.ne
32、xt=current.next item=current.entry del current return itemitem=current.entrydel currentprevious为空，说明i-1结点不存在；current为空，说明i号结点不存在；这两种情况都不能删除i号位置结点，否则previous指向i-1号结点，current指向i号结点。O(n)previous=self._headj=-1while previous and j i-1:previous=previous.next j+=1if previous is None:raise IndexError(k is
33、too big,no element has position i-1)current=previous.nextif current is None:raise IndexError(k is too big,no element has position i)v使算法得到使算法得到简化化对首结点的操作与对其它结点的操作统一空表与非空表的处理一致表头结点的作用v对单链表表任任意意结点点的的访问都都必必须从从头结点点或或首首结点点开开始始顺序序地地向向后操作后操作，效率，效率较低低。v一一种种可可选的的改改进方方法法是是在在链表表类定定义中中添添加加current指指针指指示示最最近近访问的的
34、结点点，同同时增增设current_position记录该结点点的的位位序序号号，这样当当重重复复访问current结点点或或访问比比current_position位位序序号号大大的的结点点时，不不必必再再从从head开开始始定定位位，而而可可以以直直接接从从current结点点开开始始，结点点访问的效率可以得到提高的效率可以得到提高。v这种种方方法法只只在在按按从从前前往往后后的的次次序序对表表结点点进行行访问时才才能能提提高高效效率。率。小结循环链表a0a1aian-1headai-1ai+1head循环链表类的实现class CircularLinkedList:def _init_(
35、self):self._head=Node(None)self._head.next=self._head def empty(self):return self._head.next=self._head def _len_(self):p=self._head.next count=0 while p!=self._head:count+=1 p=p.next return count与单链表结点结构一致，结点类定义可以直接共用；与普通单链表类的各个基本操作的实现方法基本一致；主要差别：单链表各算法中用于判别活动指针p是否已走到表尾的条件是p为None；而循环链表中是p是否再次回到head
36、。插入算法def insert(self,i,item):if i 0:raise IndexError(i is too small)previous=self._head count=-1 while previous and count i-1:previous=previous.next count+=1 if previous is None:raise IndexError(i is too big)new_node=Node(item,previous.next)previous.next=new_nodedef insert(self,i,item):if i 0:raise
37、IndexError(i is too small)previous=self._head count=-1 while previous.next!=self._head and count i-1:previous=previous.next count+=1 if count=i-1:new_node=Node(item,previous.next)previous.next=new_node else:raise IndexError(i is too big)带头结点单链表下的插入算法带头结点单向循环链表下的插入算法v循循环链表中表中可以可以仅设尾指尾指针代表整个代表整个链表表，而不
38、，而不设头指指针。设尾指针的循环链表a0a1aian-1ai-1ai+1tailtail根据情况考虑是否设头结点1）从任一）从任一结点出点出发都可都可访问到表中所有到表中所有结点；点；2）在在用用头指指针表表示示的的单循循环链表表中中，首首结点点定定位位操操作作的的时间性性能能是是O(1)，尾，尾结点定位操作的点定位操作的时间性能是性能是O(n)；3）在在用用尾尾指指针表表示示的的单循循环链表表中中，首首结点点和和尾尾结点点的的定定位位都都只只需需O(1)时间性能。性能。循环链表的特点删除算法(自行完成）v每个每个结点有两个指点有两个指针，分，分别指向指向后后继结点点和和前前驱结点点实现方法3
39、：双向链表entry nextpriorclass DuNode:def _init_(self,entry,prior=None,next=None):self.entry=entry self.prior=prior self.next=next双向非循环链表a0a1an-1a2headhead双向循环链表heada0aian-1ai-1ai+1head双向循环链表类class DuLinkedList:def _init_(self):self._head=DuNode(None)self._head.next=self._head self._head.prior=self._head
40、插入操作heada0aian-1ai-1ai+1itempreviousfollowingnew_node插入方法def insert(self,i,item):if i 0:raise IndexError(i is too small)previous=self._head count=-1 while previous.next!=self._head and count i-1:previous=previous.next count+=1 if count=i-1:new_node=Node(item,previous.next)previous.next=new_node else
41、:raise IndexError(i is too big)def insert(self,i,item):if i 0:raise IndexError(插入位置不合法，i值小于0)previous=self._head count=-1 while previous.next!=self._head and count i-1:previous=previous.next count+=1 following=previous.next if count=i-1:new_node=DuNode(item,previous,following)previous.next=new_node
42、following.prior=new_node else:raise IndexError(插入位置不合法，i值太大)带头结点单向循环链表下的插入算法带头结点双向循环链表下的插入算法v“插入插入”和和“删除除”时需要同需要同时修改前修改前驱和后和后继两个方向上的指两个方向上的指针。v对指指向向双双链表表结点点的的任任意意current指指针，如如其其前前驱结点点和和后后继结点点存在，存在，则：current=current.next.prior=current.prior.next，v在在插插入入和和删除除操操作作时，不不必必定定位位插插入入或或删除除位位置置的的前前驱结点点，而而可以直接定
43、位当前位置可以直接定位当前位置结点。点。v可可不不设头指指针或或和和尾尾指指针，而而设一一个个current指指针指指示示最最近近访问结点点，同同时设current_position记录该结点点的的位位序序号号。当当需需定定位位i号号结点点时，活活动指指针总是是从从current开开始始，根根据据current_position与与i的的大大小关系，确定移小关系，确定移动方向和次数。（此方向和次数。（此时一般不再一般不再设头结点）点）双向链表特点删除算法（自行完成）有序表有序表类class OrderedList(LinkedList):def add(self,item):p=self._h
44、ead while p.next and p.next.entry=item:p=p.next newnode=Node(item,p.next)p.next=newnode def insert(self,position,item):if positionlen(self):raise Exception(插入位置不合法)if position0:previous=self.retrieve(position-1)if itemprevious:raise Exception(插入位置不正确)if positionnextvalue:raise Exception(插入位置不正确)supe
45、r().insert(position,item)def replace(self,position,item):passv是是/否否带头结点点v单向向/双向双向v是是/否否循循环链表种类8种各种链表实现的比较类别特点和适用场合不加头结点单链表0号位置的插入、删除等操作需要额外处理；适合递归处理。加了头结点的单链表0号位置的操作与其他位置的操作一致，使算法得到简化，广泛使用。单向循环链表可以方便地从尾结点走到头结点，方便循环往复地操作。双向链表存储密度更低，需要频繁进行两个方向的行进时适用。根据重要操作的方便性和效率进行选择v优点：点：1动态管理存储空间，不需事先申请空间2不需要担心溢出3插入
46、删除只引起指针的变化，效率更高。v缺点：缺点：1顺序存取，非随机存取，根据位序读写效率为O(n)2由于涉及到指针操作，程序设计的复杂性增大3链域也占空间，使存储密度降低，必定小于1。链表结构优缺点v1元素个体元素个体较大大v2不能事先确定表不能事先确定表长v3经常需要做插入、常需要做插入、删除和元素的重排。除和元素的重排。适用场合v优点点1程序设计简单；2元素的物理位置反映逻辑关系，可实现随机存取，根据位序的读写时间效率为O(1)；3存储密度为1。v缺点缺点1须事先确定初始表长2插入删除会带来元素的移动3多次插入后初始空间耗尽，造成溢出或需要空间扩容顺序表优缺点（不局限仅在python中实现）
47、v1经常需要根据位序常需要根据位序进行行读写写v2很少在非尾部位置插入和很少在非尾部位置插入和删除除v3元素个体元素个体较小小v4表表长能事先确定能事先确定适用场合顺序表与链表基本操作时间复杂度序号方法顺序表下时间复杂度单链表下时间复杂度1initO()O()2emptyO()O()3lenO()O()4clearO()O()5appendO()O()6insertO()O()7removeO()O()8retrieveO()O()9replaceO()O()10containsO()O()顺序表与链表的比较类别优点缺点适用场合顺序表1程序设计简单；2元素的物理位置反映逻辑关系，可实现随机存取
48、，根据位序的读写时间效率为O(1)3存储密度为1。1须事先确定初始表长2插入删除会带来元素的移动3多次插入后初始空间耗尽，造成溢出或需要空间扩容1元素个体较小2表长能事先确定3很少在非尾部位置插入和删除4经常需要根据位序进行读写链表1动态管理存储空间，不需事先申请空间2不需要担心溢出3插入删除只引起指针的变化，效率更高。1不能做到随机存取，根据位序读写效率为O(n)2由于涉及到指针操作，程序设计的复杂性增大3链域也占空间，使存储密度降低，必定小于1。1元素个体较大2不能事先确定表长3经常需要做插入、删除和元素的重排。序列sequence栈线性表list顺序表Python 列表底层数组实现的顺序
49、表集合运算链表单链表循环链表约瑟夫环双向链表队列抽象数据类型层数据结构层实现层应用层数学概念层概念层算法层程序设计层自顶向下的数据结构层次线性表应用v用用无无序序线性性表表表表示示集集合合，假假设集集合合A=7,2,1，B=3,6,7,2,5，求求C=AB=7,2。集合运算def intersect(la,lb):m=len(la)n=len(lb)lc=DynamicArrayList()for i in range(m):x=la.retrieve(i)if lb.contains(x):lc.append(x)return lcO(m*n)v用有序用有序线性表表示集合性表表示集合，求，求
50、C=AB。集合运算将A和B和交集结果C组织为有序表，上例中的A和B表示为：A=（1，2，7）B=（2，3，5，6，7)则：C=AB=2，7求交集的算法：用双游标法，即设两个变量分别指示A和B的当前位置，设为 i和j，初始分别为0。将Ai与Bj进行比较，AiBj，说明Ai不在C中，i+1Ai=Bj，加入到c中，i+1，j+1否则，说明Bj不在C中，j+1通过一次比较，可以加入或排除一个元素。元素总数最多为m+n，因此比较次数最多为m+n-1，算法的时间复杂度可以达到O(m+n)。A=（1，3，5,7,9）B=（2，4，6，8，10，12,13)有序表表示集合求交集def intersect(la
