- 顺序表
- Python顺序表中基本操作的实现
- 单链表
- python单链表基本操作的实现
- 顺序表与单链表的对比
顺序表
线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，这种表示也称作线性表的顺序存储结构或顺序映像。通常，称这种存储结构的线性表为顺序表（SequentialList其特点是,逻辑上相邻的数据元素，其物理次序也是相邻的。假设线性表的每个元素需占用个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储起始位置。则线性表中第个数据元素的存储位置和第个数据元素的存储位置LOC之间满足下列关系：
一般来说，线性表的第个数据元素的存储位置为：
a=[1,2,3,4,4,5]id(a[1])-id(a[0])
id(a[2])-id(a[1])
id(a[0])+32*3==id(a[3])
True
Python顺序表中基本操作的实现
Python的list和tuple采用了顺序表的实现技术,具有顺序表的所有性质
- 初始化
顺序表的初始化操作就是构造一个空的顺序表。
alist=[]
- 取值
取值操作是根据指定的位置序号i，获取顺序表中第i个数据元素的值。由于顺序存储结构具有随机存取的特点，可以直接通过数组下标定位得到,elem[i-1]单元存储第i个数据元素。
a[2]
- 查找
查找操作是根据指定的元素值e，查找顺序表中第1个与e相等的元素。若查找成功，则返回该元素在表中的位置序号;若查找失败，则返回0。
a.index(4)
- 插入
线性表的插入操作是指在表的第个位置插人一个新的数据元素,使长度为的线性表
变成长度为的线性表
一般情况下，在第个位置插入一个元素时，需从最后一个元素即第个元素开始，依次向后移动一个位置，直至第个元素（共个元素)。
顺序表插入算法的平均时间复杂度为
Python中有多种方法向表中插入某一元素
a
[1,2,3,4,4,5]
#在列表尾部添加一个对象#官方：sameass[len(s):len(s)]=[x]a.append(0)a
id(a[2])-id(a[1])0
#在列表尾部添加一个序列#官方：sameass[len(s):len(s)]=ta.extend([9])a
id(a[2])-id(a[1])2
#在指定位置插入元素a.insert(2,8)a
id(a[2])-id(a[1])4
a.pop(2)
- 删除
线性表的删除操作是指将表的第个元素删去，将长度为的线性表
变成长度为的线性表
一般情况下,删除第个元素时需将第个至第个元素（共个元素)依次向前移动一个位置
#从a中删除a[i]等于x的第一项a.remove(4)a
id(a[2])-id(a[1])7
#返回i处的元素值，并将其从a中删除a.pop(-1)a
id(a[2])-id(a[1])9
list其他操作
id(a[0])+32*3==id(a[3])0
id(a[0])+32*3==id(a[3])1
max(b)
id(a[0])+32*3==id(a[3])3
id(a[0])+32*3==id(a[3])4
False
id(a[0])+32*3==id(a[3])6
True
id(a[0])+32*3==id(a[3])8
id(a[0])+32*3==id(a[3])9
True0
True1
#清空b.clear()b
True3
list内置操作的时间复杂度
单链表
线性表链式存储结构的特点是：用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的因此，为了表示每个数据元素与其直接后继数据元素之间的逻辑关系，对数据元素来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置这两部分信息组成数据元素的存储映像，称为结点(node)。它包括两个域：其中存储数据元素信息的域称为数据域;存储直接后继存储位置的域称为指针域。指针域中存储的信息称作指针或链。个结点（的存储映像)链结成一个链表，即为线性表
示意图
python单链表基本操作的实现
单个节点实现
classLNode(object):def__init__(self,elem,next=None):self.elem=elemself.next=next
单链表的实现
- 单链表的初始化
classSingleLinkList(object):def__init__(self):self.__head=None#头结点的指针域置空
- 判断链表是否为空
defis_empty(self):returnself.__head==None
- 链表长度
deflength(self):#p初始时指向头节点p=self.__headcount=0#尾节点指向None，当未到达尾部时whilep!=None:count+=1#将cur后移一个节点p=p.nextreturncount
- 取值
和顺序表不同，链表中逻辑相邻的结点并没有存储在物理相邻的单元中，这样，根据给定的结点位置序号i'在链表中获取该结点的值不能像顺序表那样随机访问，而只能从链表的首元结点出发，顺着链域next逐个结点向下访问。
defget_elem(self,i):#p为扫描指针p=self.__headwhilep!=Noneand0<i<self.length():i-=1p=p.nextreturnp.elem
- 查找
链表中按值查找的过程和顺序表类似，从链表的首元结点出发，依次将结点值和给定值e进行比较，返回查找结果。
defloc_elem(self,elem):p=self.__headwhilep!=None:ifp.elem==elem:returnTrueelse:p=p.nextreturnFalse
- 插入
假设要在单链表的两个数据元素a和b之间插入一个数据元素x,已知p为其单链表存储结构中指向结点a的指针
步骤：
- 查找结点并由指针指向该结点。
- 生成一个新结点*s。
- 将新结点*s的数据域置为e。
- 将新结点*s的指针域指向结点a
- 将结点p的指针域指向新结点s。
时间复杂度为
definsert(self,pos,elem):node=LNode(elem)count=0#p用来指向指定位置pos的前一个位置pos-1，初始从头节点开始移动到指定位置p=self.__headwhilecount<(pos-1):count+=1p=p.next#先将新节点node的next指向插入位置的节点node.next=p.next#将插入位置的前一个节点的next指向新节点p.next=node
- 删除
要删除单链表中指定位置的元素，同插人元素一样，首先应该找到该位置的前驱结点。如图所示，在单链表中删除元素b时，应该首先找到其前驱结点a。为了在单链表中实现元素a、b和c之间逻辑关系的变化,仅需修改结点a中的指针域即可。假设p为指向结点a的指针，则修改指针的语句为
#按值删除defremove_1(self,elem):cur=self.__headpre=Nonewhilecur!=None:ifcur.elem==elem:#先判断此结点是否是头节点#头节点ifcur==self.__head:self.__head=cur.nextelse:pre.next=cur.nextbreakelse:pre=curcur=cur.next#按位置删除defremove_2(self,i):p=self.__headcount=0whilep!=None:ifcount!=i-1:p=p.nextcount+=1else:p.next=p.next.nextbreak
- 创建单链表
(1)创建一个只有头结点的空链表。
(2)根据待创建链表包括的元素个数,循环次执行以下操作:
- 生成一个新结点*p;
- 输入元素值赋给新结点*p的数据域;
- 将新结点*p插人到头结点之后。
- 尾插法
(1)创建一个只有头结点的空链表。
(2)尾指针r初始化，指向头结点。
(3)根据创建链表包括的元素个数,循环次执行以下操作:
- 生成一个新结点*p;
- 输入元素值赋给新结点*p的数据域;
- 将新结点p插入到尾结点r之后;
- 尾指针r指向新的尾结点*p。。
#头插法defadd(self,elem):#先创建一个保存item值的节点node=LNode(elem)#将新节点的链接域next指向头节点，即__head指向的位置node.next=self.__head#将链表的头_head指向新节点self.__head=node
#尾插法defappend(self,elem):node=LNode(elem)#先判断链表是否为空，若是空链表，则将_head指向新节点ifself.is_empty():self.__head=node#若不为空，则找到尾部，将尾节点的next指向新节点else:p=self.__headwhilep.next!=None:p=p.nextp.next=node
顺序表与单链表的对比