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

代码如下：

 
 
 
    
  
  
  
  1. # 线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。 
    2. 
  
  
  
  2. # 在稍复杂的线性表中，一个数据元素可由多个数据项（item）组成，此种情况下常把数据元素称为记录（record），含有大量记录的线性表又称文件（file）。 
    3. 
  
  
  
  3. # 线性表中的个数n定义为线性表的长度，n=0时称为空表。在非空表中每个数据元素都有一个确定的位置，如用ai表示数据元素，则i称为数据元素ai在线性表中的位序。 
    4. 
  
  
  
  4. # 线性表的相邻元素之间存在着序偶关系。如用（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]  。 
    5. 
  
  
  
  5. # 1）MakeEmpty(L) 这是一个将L变为空表的方法 
    6. 
  
  
  
  6. # 2）Length（L） 返回表L的长度，即表中元素个数 
    7. 
  
  
  
  7. # 3）Get（L，i） 这是一个函数，函数值为L中位置i处的元素（1≤i≤n） 
    8. 
  
  
  
  8. # 4）Prior（L，i） 取i的前驱元素 
    9. 
  
  
  
  9. # 5）Next（L，i） 取i的后继元素 
    10. 
  
  
  
  10. # 6）Locate（L，x） 这是一个函数，函数值为元素x在L中的位置 
    11. 
  
  
  
  11. # 7）Insert（L，i，x）在表L的位置i处插入元素x，将原占据位置i的元素及后面的元素都向后推一个位置 
    12. 
  
  
  
  12. # 8）Delete（L，p） 从表L中删除位置p处的元素 
    13. 
  
  
  
  13. # 9）IsEmpty(L) 如果表L为空表(长度为0)则返回true，否则返回false 
    14. 
  
  
  
  14. # 10）Clear（L）清除所有元素 
    15. 
  
  
  
  15. # 11）Init（L）同第一个，初始化线性表为空 
    16. 
  
  
  
  16. # 12）Traverse（L）遍历输出所有元素 
    17. 
  
  
  
  17. # 13）Find（L，x）查找并返回元素 
    18. 
  
  
  
  18. # 14）Update（L，x）修改元素 
    19. 
  
  
  
  19. # 15）Sort（L）对所有元素重新按给定的条件排序 
    20. 
  
  
  
  20. # 16) strstr(string1,string2)用于字符数组的求string1中出现string2的首地址 
    21. 
  
  
  
  21. class Sequencelist(object): 
    22. 
  
  
  
  22.     def __init__(self, datatype=int, maxlength=10): 
    23. 
  
  
  
  23.         self.maxlength = maxlength 
    24. 
  
  
  
  24.         self.currentnum = 0 
    25. 
  
  
  
  25.         self.data = [None] * self.maxlength 
    26. 
  
  
  
  26.         self.datatype = datatype 
    27. 
  
  
  
  27.  
    28. 
  
  
  
  28.     def __setitem__(self, key, value): 
    29. 
  
  
  
  29.         if not isinstance(key, int): 
    30. 
  
  
  
  30.             raise TypeError 
    31. 
  
  
  
  31.         if not isinstance(value, self.datatype): 
    32. 
  
  
  
  32.             raise TypeError("数据类型不符合{0}".format(self.datatype)) 
    33. 
  
  
  
  33.         if 0 <= key <= self.currentnum: 
    34. 
  
  
  
  34.             self.data[key-1] = value 
    35. 
  
  
  
  35.         else: 
    36. 
  
  
  
  36.             raise IndexError 
    37. 
  
  
  
  37.  
    38. 
  
  
  
  38.     def __getitem__(self, key): 
    39. 
  
  
  
  39.         if not isinstance(key, int): 
    40. 
  
  
  
  40.             raise TypeError 
    41. 
  
  
  
  41.         if 1 <= key <= self.currentnum: 
    42. 
  
  
  
  42.             return self.data[key-1] 
    43. 
  
  
  
  43.         else: 
    44. 
  
  
  
  44.             raise IndexError 
    45. 
  
  
  
  45.  
    46. 
  
  
  
  46.     def __len__(self): 
    47. 
  
  
  
  47.         return self.currentnum 
    48. 
  
  
  
  48.  
    49. 
  
  
  
  49.     def __repr__(self): 
    50. 
  
  
  
  50.         return '__repr__={}'.format(str(self.data)) 
    51. 
  
  
  
  51.  
    52. 
  
  
  
  52.     def __str__(self): 
    53. 
  
  
  
  53.         return '__str__={}'.format(str(self.data[:self.currentnum])) 
    54. 
  
  
  
  54.  
    55. 
  
  
  
  55.     def isempty(self): 
    56. 
  
  
  
  56.         return self.currentnum == 0 
    57. 
  
  
  
  57.  
    58. 
  
  
  
  58.     def isfull(self): 
    59. 
  
  
  
  59.         return self.currentnum == self.maxlength 
    60. 
  
  
  
  60.  
    61. 
  
  
  
  61.     def maxlength(self): 
    62. 
  
  
  
  62.         return self.maxlength 
    63. 
  
  
  
  63.  
    64. 
  
  
  
  64.     def makeempty(self): 
    65. 
  
  
  
  65.         self.clear() 
    66. 
  
  
  
  66.  
    67. 
  
  
  
  67.     def length(self): 
    68. 
  
  
  
  68.         return self.__len__() 
    69. 
  
  
  
  69.  
    70. 
  
  
  
  70.     def count(self): 
    71. 
  
  
  
  71.         return self.__len__() 
    72. 
  
  
  
  72.  
    73. 
  
  
  
  73.     def get(self, key): 
    74. 
  
  
  
  74.         return self.__getitem__(key) 
    75. 
  
  
  
  75.  
    76. 
  
  
  
  76.     def set(self, key,value): 
    77. 
  
  
  
  77.         self.__setitem__(key,value) 
    78. 
  
  
  
  78.  
    79. 
  
  
  
  79.     def prior(self, key): 
    80. 
  
  
  
  80.         assert key>1 and key 
  
  
  
  81.         return self.data[key-2] 
    82. 
  
  
  
  82.  
    83. 
  
  
  
  83.     def next(self, key): 
    84. 
  
  
  
  84.         assert key>=1 and key 
  
  
  
  85.         return self.data[key] 
    86. 
  
  
  
  86.  
    87. 
  
  
  
  87.     def locate(self, value,start=0): 
    88. 
  
  
  
  88.         for i in range(start,self.currentnum): 
    89. 
  
  
  
  89.             if self.data[i]==value: 
    90. 
  
  
  
  90.                 return i+1 
    91. 
  
  
  
  91.         raise ValueError("{} is not find in list".format(value)) 
    92. 
  
  
  
  92.  
    93. 
  
  
  
  93.     def index(self,value,start=0): 
    94. 
  
  
  
  94.         return self.locate(value,start) 
    95. 
  
  
  
  95.  
    96. 
  
  
  
  96.     def append(self,value): 
    97. 
  
  
  
  97.         if self.isfull(): 
    98. 
  
  
  
  98.             print('list is full') 
    99. 
  
  
  
  99.             return 
    100. 
  
  
  
  100.         else: 
    101. 
  
  
  
  101.             self.data[self.currentnum]=value 
    102. 
  
  
  
  102.             self.currentnum+=1 
    103. 
  
  
  
  103.  
    104. 
  
  
  
  104.     def insert(self, key, value): 
    105. 
  
  
  
  105.         if not isinstance(key,self.datatype): 
    106. 
  
  
  
  106.             raise TypeError 
    107. 
  
  
  
  107.         if key<1: 
    108. 
  
  
  
  108.             raise IndexError 
    109. 
  
  
  
  109.         if key>=self.currentnum: 
    110. 
  
  
  
  110.             self.append(value) 
    111. 
  
  
  
  111.         else: 
    112. 
  
  
  
  112.             for i in range(self.currentnum,key-1,-1): 
    113. 
  
  
  
  113.                 self.data[i]=self.data[i-1] 
    114. 
  
  
  
  114.             self.data[key-1]=value 
    115. 
  
  
  
  115.             self.currentnum+=1 
    116. 
  
  
  
  116.  
    117. 
  
  
  
  117.     def delete(self, key): 
    118. 
  
  
  
  118.         if not isinstance(key, self.datatype): 
    119. 
  
  
  
  119.             raise TypeError 
    120. 
  
  
  
  120.         if key < 1 and key>self.currentnum: 
    121. 
  
  
  
  121.             raise IndexError 
    122. 
  
  
  
  122.         else: 
    123. 
  
  
  
  123.             for i in range(key-1,self.currentnum): 
    124. 
  
  
  
  124.                 self.data[i]=self.data[i+1] 
    125. 
  
  
  
  125.             self.currentnum-=1 
    126. 
  
  
  
  126.  
    127. 
  
  
  
  127.     def pop(self): 
    128. 
  
  
  
  128.         return self.delete(self.currentnum) 
    129. 
  
  
  
  129.  
    130. 
  
  
  
  130.     def clear(self): 
    131. 
  
  
  
  131.         self.__init__() 
    132. 
  
  
  
  132.  
    133. 
  
  
  
  133.     def init(self): 
    134. 
  
  
  
  134.         self.__init__() 
    135. 
  
  
  
  135.  
    136. 
  
  
  
  136.     def reverse(self): 
    137. 
  
  
  
  137.         i,j=0,self.currentnum-1 
    138. 
  
  
  
  138.         while i
  
  
  
  139.             self.data[i],self.data[j]=self.data[j],self.data[i] 
    140. 
  
  
  
  140.             i,j=i+1,j-1 
    141. 
  
  
  
  141.             #print(self.data) 
    142. 
  
  
  
  142.  
    143. 
  
  
  
  143.     def find(self, value,start=0): 
    144. 
  
  
  
  144.         return self.locate(self,value,start) 
    145. 
  
  
  
  145.  
    146. 
  
  
  
  146.     def update(self, key,value): 
    147. 
  
  
  
  147.         self.__setitem__(key,value) 
    148. 
  
  
  
  148.  
    149. 
  
  
  
  149.     def sort(self): 
    150. 
  
  
  
  150.         for i in range(0,self.currentnum-1): 
    151. 
  
  
  
  151.             for j in range(i+1,self.currentnum): 
    152. 
  
  
  
  152.                 if self.data[i]>self.data[j]: 
    153. 
  
  
  
  153.                     self.data[i],self.data[j]=self.data[j],self.data[i] 
    154. 
  
  
  
  154.  
    155. 
  
  
  
  155.     def strstr(string1, string2): 
    156. 
  
  
  
  156.         pass 
    157. 
  
  
  
  157.  
    158. 
  
  
  
  158.  
    159. 
  
  
  
  159. if __name__ == '__main__': 
    160. 
  
  
  
  160.     a=Sequencelist() 
    161. 
  
  
  
  161.     a.append(1) 
    162. 
  
  
  
  162.     a.append(2) 
    163. 
  
  
  
  163.     a.append(3) 
    164. 
  
  
  
  164.     print(a) 
    165. 
  
  
  
  165.     print(repr(a)) 
    166. 
  
  
  
  166.     b=a.locate(2) 
    167. 
  
  
  
  167.     print(b) 
    168. 
  
  
  
  168.     print(a.isempty()) 
    169. 
  
  
  
  169.     print(a.isfull()) 
    170. 
  
  
  
  170.     print(len(a)) 
    171. 
  
  
  
  171.     print(a.length()) 
    172. 
  
  
  
  172.     #print(a.prior(1)) 
    173. 
  
  
  
  173.     # AssertionError: 数组越界 
    174. 
  
  
  
  174.     print(a.prior(2)) 
    175. 
  
  
  
  175.     print(a.prior(3)) 
    176. 
  
  
  
  176.     print(a.next(1)) 
    177. 
  
  
  
  177.     print(a.next(2)) 
    178. 
  
  
  
  178.     print(a) 
    179. 
  
  
  
  179.     print(a.get(2)) 
    180. 
  
  
  
  180.     a.insert(2,4) 
    181. 
  
  
  
  181.     print(a) 
    182. 
  
  
  
  182.     a.delete(2) 
    183. 
  
  
  
  183.     print(a) 
    184. 
  
  
  
  184.     print(a.length()) 
    185. 
  
  
  
  185.     a.pop() 
    186. 
  
  
  
  186.     print(a) 
    187. 
  
  
  
  187.     print(a.length()) 
    188. 
  
  
  
  188.     a.update(2,4) 
    189. 
  
  
  
  189.     print(a) 
    190. 
  
  
  
  190.     print(a.index(4)) 
    191. 
  
  
  
  191.     # print(a.index(5)) 
    192. 
  
  
  
  192.     # ValueError: 5 is not find in list 
    193. 
  
  
  
  193.     print(a) 
    194. 
  
  
  
  194.     a.reverse() 
    195. 
  
  
  
  195.     print(a) 
    196. 
  
  
  
  196.     a.append(3) 
    197. 
  
  
  
  197.     a.append(5) 
    198. 
  
  
  
  198.     # a.append(2) 
    199. 
  
  
  
  199.     print(a) 
    200. 
  
  
  
  200.     a.sort() 
    201. 
  
  
  
  201.     print(a) 
    202.

结果如下：

 
 
 
    
  
  
  
  1. C:\python\pyproject\pythonalgorithms\venv\Scripts\python.exe C:/python/pyproject/pythonalgorithms/sequencelist.py 
    2. 
  
  
  
  2. __str__=[1, 2, 3] 
    3. 
  
  
  
  3. __repr__=[1, 2, 3, None, None, None, None, None, None, None] 
    4. 
  
  
  
  4. 2 
    5. 
  
  
  
  5. False 
    6. 
  
  
  
  6. False 
    7. 
  
  
  
  7. 3 
    8. 
  
  
  
  8. 3 
    9. 
  
  
  
  9. 1 
    10. 
  
  
  
  10. 2 
    11. 
  
  
  
  11. 2 
    12. 
  
  
  
  12. 3 
    13. 
  
  
  
  13. __str__=[1, 2, 3] 
    14. 
  
  
  
  14. 2 
    15. 
  
  
  
  15. __str__=[1, 4, 2, 3] 
    16. 
  
  
  
  16. __str__=[1, 2, 3] 
    17. 
  
  
  
  17. 3 
    18. 
  
  
  
  18. __str__=[1, 2] 
    19. 
  
  
  
  19. 2 
    20. 
  
  
  
  20. __str__=[1, 4] 
    21. 
  
  
  
  21. 2 
    22. 
  
  
  
  22. __str__=[1, 4] 
    23. 
  
  
  
  23. __str__=[4, 1] 
    24. 
  
  
  
  24. __str__=[4, 1, 3, 5] 
    25. 
  
  
  
  25. __str__=[1, 3, 4, 5] 
    26. 
  
  
  
  26.  
    27. 
  
  
  
  27. Process finished with exit code 0 
    28.

网页题目：Python数据结构之线性顺序表
分享路径：http://www.shufengxianlan.com/qtweb/news2/411652.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

定制网站知识

各行业网站

wap网站建设　　 　成都免费做网站公司　　 　一带一路　　 　成都商城网站建设　　 　成都众诚伟业　　 　遂宁做网站　　 　重庆移动网站建设　　 　成都微信开发　　 　德信企业管理　　 　IDC机房托管　　 　腾讯云香港空间　　 　重庆水土三线托管　　 　网站免费收录　　 　成都广告招牌　　 　四川中建建业　　 　成都微信小程序开发　　 　成都服装定制　　 　成都网站建设公司　　 　达州网站建设　　 　青羊总部基地