Python数据结构之线性序列表

本文转载自微信公众号《python与大数据分析》，作者是一只小鸟。转载本文请联系python与大数据分析公众号。线性列表是一种数据结构，线性列表是由n个具有相同特征的数据元素组成的有限序列。本文结合网上的一些代码和百度百科对线性序列表的定义，实现了所有的代码。在稍微复杂一点的线性表中，一个数据元素可以由多个数据项（item）组成。在这种情况下，数据元素通常称为记录，包含大量记录的线性表也称为文件。线性表中的数n定义为线性表的长度，n=0称为空表。非空表中的每个数据元素都有一个确定的位置。如果用ai表示一个数据元，则i称为线性表中数据元ai的比特序列。线性列表的相邻元素之间存在顺序偶数关系。如果用(a1,...,ai-1,ai,ai+1,...,an)表示一个序列表，则表中ai-1在ai前面，ai在ai前面+1，而ai-1称为ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1,2,...,n-1时，ai只有一个直接后继；当i=2,3,...,n时，ai有一个且只有一个直接前驱[1]。需要改变的是，无论是线性列表中的参数还是最大数量，都需要在列表的序号上加1。代码如下：#线性表（linearlist）是一种数据结构，线性表是n个和n个性质相同的数据元素的有限序列。#在稍微复杂一点的线性表中，一个数据元素可以由多个数据项（item）组成。在这种情况下，数据元素通常称为记录，具有大量记录的线性表也称为文件。#线性表中的数n定义为线性表的长度，当n=0时，称为空表。非空表中的每个数据元素都有一个确定的位置。如果用ai表示一个数据元，则i称为线性表中数据元ai的比特序列。#线性表的相邻元素之间存在序偶关系。如果用(a1,...,ai-1,ai,ai+1,...,an)表示顺序表，则表中ai-1在ai前面，ai在ai+前面1，而ai-1称为ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1,2,...,n-1时，ai只有一个直接后继，当i=2,3,...,n时，ai只有一个直接前继[1]。#1)MakeEmpty(L)这是一个将L变成空列表的方法#2)Length(L)返回列表L的长度，即表中元素的个数#3)Get(L,i)这是一个函数，函数值是L中位置i的元素(1≤i≤n)#4)Prior(L,i)取i的前驱元素#5)Next(L,i)取i的后继元素#6)Locate(L,x)这是一个函数，其值为元素x在L中的位置#7)Insert(L,i,x)在表L的位置i插入元素x，并插入原来的元素占据位置i并且所有后续元素都被推回一个位置#8)Delete(L,p)从列表L中删除位置p处的元素#9)IsEmpty(L)如果列表L是一个空列表（长度0),否则返回false#10)Clear(L)清除所有元素#11)Init(L)同第一个，将线性表初始化为空#12)Traverse(L)遍历并输出所有元素#13)Find(L,x)查找并返回元素#14)Update(L,x)修改元素nt#15)Sort(L)根据给定的条件对所有元素重新排序#16)strstr(string1,string2)用于查找字符数组中string1出现的位置string2的首地址classSequencelist(object):def__init__(self,datatype=int,maxlength=10):self.maxlength=maxlengthself.currentnum=0self.data=[None]*self.maxlengthself.datatype=datatypedef__setitem__(self,key,value):ifnotisinstance(key,int):raiseTypeErrorifnotisinstance(value,self.datatype):raiseTypeError("数据类型不符合{0}".format(self.datatype))if0<=key<=self.currentnum:self.数据[key-1]=valueelse:raiseIndexErrordef__getitem__(self,key):ifnotisinstance(key,int):raiseTypeErrorif1<=key<=self.currentnum:returnsself.data[key-1]else:raiseIndexErrordef__len__(self):returnsself.currentnumdef__repr__(self):return'__repr__={}'.format(str(self.data))def__str__(self):return'__str__={}'.format(str(self.data[:self.currentnum]))defisempty(self):returnsself.currentnum==0defisfull(self):returnsself.currentnum==self.maxlengthdefmaxlength(self):returnsself.maxlengthdefmakeempty(self):self.clear()deflength(self):returnsself.__len__()defcount(self):returnsself.__len__()defget(self,key):returnsself.__getitem__(key)defset(self,key,value):self.__setitem__(key,value)defprior(self,key):assertkey>1andkey=1andkey=self.currentnum:self.append(value)else:foriinrange(self.currentnum,key-1,-1):self.data[i]=self.data[i-1]self.data[key-1]=valueself.currentnum+=1defdelete(self,key):ifnotisinstance(key,self.datatype):raiseTypeErrorifkey<1andkey>self.currentnum:raiseIndexErrorelse:foriinrange(key-1,self.currentnum):self.data[i]=self.data[i+1]self.currentnum-=1defpop(self):returnsself.delete(self.currentnum)defclear(self):self.__init__()definit(self):self.__init__()defreverse(self):i,j=0,self.currentnum-1whileiself.data[j]:self.data[i],self.data[j]=self.data[j],self.data[i]defstrstr(string1,string2):passif__name__=='__main__':a=Sequencelist()a.append(1)a.append(2)a.append(3)print(a)print(repr(a))b=a.locate(2)print(b)print(a.isempty())print(a.isfull())print(len(a))print(a.length())#print(a.prior(1))#AssertionError:数组越界print(a.prior(2))print(a.prior(3))print(a.next(1))print(a.next(2))打印(a)打印(a.get(2))a.insert(2,4)打印(a)a.delete(2)打印(a)打印(a.length())a.pop()打印(a)print(a.length())a.update(2,4)print(a)print(a.index(4))#print(a.index(5))#ValueError:5isnotfindinlistprint(a)a。reverse()print(a)a.append(3)a.append(5)#a.append(2)print(a)a.sort()print(a)结果如下：C:\python\pyproject\pythonalgorithms\venv\Scripts\python.exeC:/python/pyproject/pythonalgorithms/sequencelist.py__str__=[1,2,3]__repr__=[1,2,3,None,None,None,None,None,None,None]2FalseFalse331223__str__=[1,2,3]2__str__=[1,4,2,3]__str__=[1,2,3]3__str__=[1,2]2__str__=[1,4]2__str__=[1,4]__str__=[4,1]__str__=[4,1,3,5]__str__=[1,3,4,5]Processfinishedwithexitcode0