Python数据结构之顺序表的实现代码示例

240 阅读 0 评论 159 点赞

我是靠谱客的博主文静水壶，这篇文章主要介绍Python数据结构之顺序表的实现代码示例，现在分享给大家，希望可以做个参考。

顺序表即线性表的顺序存储结构。它是通过一组地址连续的存储单元对线性表中的数据进行存储的，相邻的两个元素在物理位置上也是相邻的。比如，第1个元素是存储在线性表的起始位置LOC(1)，那么第i个元素即是存储在LOC(1)+(i-1)*sizeof(ElemType)位置上，其中sizeof(ElemType)表示每一个元素所占的空间。

追加直接往列表后面添加元素，插入是将插入位置后的元素全部往后面移动一个位置，然后再将这个元素放到指定的位置，将长度加1删除是将该位置后面的元素往前移动，覆盖该元素，然后再将长度减1　

实现代码：

复制代码

#!/usr/bin/python
# -*- coding: utf-8 -*-

class SeqList(object):
  def __init__(self,maxsize):
    self.maxsize = maxsize
    self.data = range(maxsize)
    self.last = len(self.data) -1
  def __getitem__(self, key):
    if self.is_empty():
      print 'seqlist is empty'
      return
    elif key<0 or key>self.last:
      print 'the given key is Error'
      return
    else:
      return self.data[key]
  def __setitem__(self, key, value):
    if self.is_empty():
      print 'seqlist is empty'
      return
    elif key<0 or key>self.last:
      print 'the given key is Error'
      return
    else:
      self.data[key] = value
  def __len__(self):
    length = self.last + 1
    return length
  def getlength(self):
    return self.last+1
  def clear(self):
    self.data = []
  def is_empty(self):
    if self.last == -1:
      return True
    else:
      return False
  def is_full(self):
    if self.last == self.maxsize-1:
      return True
    else:
      return False
  def getelem(self,index):
    if self.is_empty():
      print 'seqlist is empty'
      return
    elif index<0 or index>self.last:
      print 'position is error'
    else:
      return self.data[index]
  def getindex(self,elem):
    if self.is_empty():
      print 'seqlst is empty'
      return
    else:
      for i in range(self.last):
        if self.data[i]==elem:
          return i
  def append(self,elem):
    if self.is_empty():
      print 'seqlist is empty'
      return
    else:
      self.last +=1
      self.data = self.data + [elem]
  def insert(self,index,elem):
    if self.is_empty():
      print 'seqlist is empty'
      return
    elif index<0 or index> self.last+1:
      print 'postion is error'
      return
    elif index == self.last+1:
      self.last+=1
      self.data = self.data + [elem]
    else:
      self.data += [elem]
      if index ==0:
        for i in self.data[self.last::-1]:
          self.data[i+1] = self.data[i]
      else:
        for i in self.data[self.last:index-1:-1]:
          self.data[i+1] = self.data[i]
      self.data[index] = elem
      self.last+=1
      #print self.data

def delete(self,index):
    if self.is_empty():
      print 'seqlist is empty'
      return
    elif index<0 or index> self.last+1:
      print 'postion is error'
      return
    elif index == self.last+1:
      self.last -= 1
      self.data =self.data[:-1]
    else:
      for i in self.data[:-1]:
        if i >= index:
          self.data[i] = self.data[i+1]
        else:
          pass
      self.data = self.data[:-1]
      self.last -= 1
sl = SeqList(5)
print sl.data
sl.append(5)
print sl.data
sl.insert(6,10)
print sl.data
sl.delete(5)
print sl.data

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#!/usr/bin/python
# -*- coding: utf-8 -*-

class SeqList(object):
  def __init__(self,maxsize):
    self.maxsize = maxsize
    self.data = range(maxsize)
    self.last = len(self.data) -1
  def __getitem__(self, key):
    if self.is_empty():
      print 'seqlist is empty'
      return
    elif key<0 or key>self.last:
      print 'the given key is Error'
      return
    else:
      return self.data[key]
  def __setitem__(self, key, value):
    if self.is_empty():
      print 'seqlist is empty'
      return
    elif key<0 or key>self.last:
      print 'the given key is Error'
      return
    else:
      self.data[key] = value
  def __len__(self):
    length = self.last + 1
    return length
  def getlength(self):
    return self.last+1
  def clear(self):
    self.data = []
  def is_empty(self):
    if self.last == -1:
      return True
    else:
      return False
  def is_full(self):
    if self.last == self.maxsize-1:
      return True
    else:
      return False
  def getelem(self,index):
    if self.is_empty():
      print 'seqlist is empty'
      return
    elif index<0 or index>self.last:
      print 'position is error'
    else:
      return self.data[index]
  def getindex(self,elem):
    if self.is_empty():
      print 'seqlst is empty'
      return
    else:
      for i in range(self.last):
        if self.data[i]==elem:
          return i
  def append(self,elem):
    if self.is_empty():
      print 'seqlist is empty'
      return
    else:
      self.last +=1
      self.data = self.data + [elem]
  def insert(self,index,elem):
    if self.is_empty():
      print 'seqlist is empty'
      return
    elif index<0 or index> self.last+1:
      print 'postion is error'
      return
    elif index == self.last+1:
      self.last+=1
      self.data = self.data + [elem]
    else:
      self.data += [elem]
      if index ==0:
        for i in self.data[self.last::-1]:
          self.data[i+1] = self.data[i]
      else:
        for i in self.data[self.last:index-1:-1]:
          self.data[i+1] = self.data[i]
      self.data[index] = elem
      self.last+=1
      #print self.data

  def delete(self,index):
    if self.is_empty():
      print 'seqlist is empty'
      return
    elif index<0 or index> self.last+1:
      print 'postion is error'
      return
    elif index == self.last+1:
      self.last -= 1
      self.data =self.data[:-1]
    else:
      for i in self.data[:-1]:
        if i >= index:
          self.data[i] = self.data[i+1]
        else:
          pass
      self.data = self.data[:-1]
      self.last -= 1
sl = SeqList(5)
print sl.data
sl.append(5)
print sl.data
sl.insert(6,10)
print sl.data
sl.delete(5)
print sl.data