Python数据结构之线性顺序表

本文转载自微信公众号「python与大数据分析」，数据作者一只小小鸟鸟 。结构转载本文请联系python与大数据分析公众号。性顺序表

线性表(linear list)是数据数据结构的一种，一个线性表是结构n个具有相同特性的数据元素的有限序列。本文结合了互联网上的性顺序表一些代码，以及结合百度百科关于线性顺序表的数据定义，实现了全部代码。结构

在稍复杂的性顺序表线性表中，一个数据元素可由多个数据项(item)组成，数据此种情况下常把数据元素称为记录(record)，结构含有大量记录的性顺序表线性表又称文件(file)。

线性表中的数据个数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

代码如下：

# 线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的企商汇数据元素的有限序列。 # 在稍复杂的线性表中，一个数据元素可由多个数据项（item）组成，此种情况下常把数据元素称为记录（record），含有大量记录的线性表又称文件（file）。 # 线性表中的个数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)则返回true，否则返回false # 10）Clear（L）清除所有元素 # 11）Init（L）同第一个，初始化线性表为空 # 12）Traverse（L）遍历输出所有元素 # 13）Find（L，x）查找并返回元素 # 14）Update（L，x）修改元素 # 15）Sort（L）对所有元素重新按给定的条件排序 # 16) strstr(string1,string2)用于字符数组的求string1中出现string2的首地址 class Sequencelist(object):     def __init__(self, datatype=int, maxlength=10):         self.maxlength = maxlength         self.currentnum = 0         self.data = [None] * self.maxlength         self.datatype = datatype     def __setitem__(self, key, value):         if not isinstance(key, int):             raise TypeError         if not isinstance(value, self.datatype):             raise TypeError("数据类型不符合{ 0}".format(self.datatype))         if 0 <= key <= self.currentnum:             self.data[key-1] = value         else:             raise IndexError     def __getitem__(self, key):         if not isinstance(key, int):             raise TypeError         if 1 <= key <= self.currentnum:             return self.data[key-1]         else:             raise IndexError     def __len__(self):         return self.currentnum     def __repr__(self):         return __repr__={ }.format(str(self.data))     def __str__(self):         return __str__={ }.format(str(self.data[:self.currentnum]))     def isempty(self):         return self.currentnum == 0     def isfull(self):         return self.currentnum == self.maxlength     def maxlength(self):         return self.maxlength     def makeempty(self):         self.clear()     def length(self):         return self.__len__()     def count(self):         return self.__len__()     def get(self, key):         return self.__getitem__(key)     def set(self, key,value):         self.__setitem__(key,value)     def prior(self, key):         assert key>1 and key <self.currentnum+1 ,数组越界         return self.data[key-2]     def next(self, key):         assert key>=1 and key <self.currentnum, 数组越界         return self.data[key]     def locate(self, value,start=0):         for i in range(start,self.currentnum):             if self.data[i]==value:                 return i+1         raise ValueError("{ } is not find in list".format(value))     def index(self,value,start=0):         return self.locate(value,start)     def append(self,value):         if self.isfull():             print(list is full)             return         else:             self.data[self.currentnum]=value             self.currentnum+=1     def insert(self, key, value):         if not isinstance(key,self.datatype):             raise TypeError         if key<1:             raise IndexError         if key>=self.currentnum:             self.append(value)         else:             for i in range(self.currentnum,key-1,-1):                 self.data[i]=self.data[i-1]             self.data[key-1]=value             self.currentnum+=1     def delete(self, key):         if not isinstance(key, self.datatype):             raise TypeError         if key < 1 and key>self.currentnum:             raise IndexError         else:             for i in range(key-1,self.currentnum):                 self.data[i]=self.data[i+1]             self.currentnum-=1     def pop(self):         return self.delete(self.currentnum)     def clear(self):         self.__init__()     def init(self):         self.__init__()     def reverse(self):         i,j=0,self.currentnum-1         while i<j:             self.data[i],self.data[j]=self.data[j],self.data[i]             i,j=i+1,j-1             #print(self.data)     def find(self, value,start=0):         return self.locate(self,value,start)     def update(self, key,value):         self.__setitem__(key,value)     def sort(self):         for i in range(0,self.currentnum-1):             for j in range(i+1,self.currentnum):                 if self.data[i]>self.data[j]:                     self.data[i],self.data[j]=self.data[j],self.data[i]     def strstr(string1, string2):         pass if __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))     print(a)     print(a.get(2))     a.insert(2,4)     print(a)     a.delete(2)     print(a)     print(a.length())     a.pop()     print(a)     print(a.length())     a.update(2,4)     print(a)     print(a.index(4))     # print(a.index(5))     # ValueError: 5 is not find in list     print(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.exe C:/python/pyproject/pythonalgorithms/sequencelist.py __str__=[1, 2, 3] __repr__=[1, 2, 3, None, None, None, None, None, None, None] 2 False False 3 3 1 2 2 3 __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] Process finished with exit code 0 

很赞哦!（3685）