文章目录
  1. 1. 线性表的顺序存储
    1. 1.1. test

线性表的顺序存储

用一段地址连续地存储单元依次存储线性表的数据元素。
优点:

  1. 无需增加额外的操作。
  2. 快速存取任一元素。

缺点:

  1. 插入和删除需要移动大量的元素。
  2. 长度较大时,无法确定存储空间。
  3. 有碎片。

结构和操作比较简单,不在赘述。Google后,发现Python实现的各种版本都有,有些漏洞百出。虽然原理简单,实现起来还是要花点时间,正好加深Python的学习。过程不在重复,注释和test部分写的很详细,不说了上码。
Python实现

# -*- coding: utf-8 -*- 
# author:minenet
# date: 2016-8-30 04:15:47
class SqList(object):

'''''
线性表顺序存储表,线性表第一个元素的下标为1,数组的下标为0
'''''
def __init__(self, maxSize):
self.maxSize = maxSize # 存储空间初始分配量
self.data = range(maxSize) #数组存储元素的最大长度
self.last = -1

def __getitem__(self, key):
'''''索引器 get,实现SqList[key]获得value'''
if self.isEmpty():
print 'SeqList is empty!'
return
elif key < 1 or key > self.last +1: #key不在线性表内
print 'the given key is Error'
return
else:
return self.data[key-1]

def __setitem__(self, key, value):
'''''索引器 set,实现SqList[key]的赋值'''
if self.isEmpty():
print 'SeqList is empty!'
return
if key < 1 or key > self.last + 1: #key不在线性表内
print 'the given key is Error'
return
else:
self.data[key-1] = value

def __len__(self):
'''''长度,实现len(SqList)'''
length = self.last + 1
return length

def getLength(self):
'''''顺序表长度'''
return self.last + 1

def clear(self):
'''''清空顺序表'''
self.last = -1

def isEmpty(self):
'''''顺序表是否为空'''
if self.last == -1:
return True
else:
return False

def isFull(self):
'''''判断顺序表是否满了'''
if self.last == self.maxSize - 1:
return True
else:
return False

def getElem(self, index):
'''''根据索引获取元素'''
if self.isEmpty():
print 'SeqList is empty!'
elif index < 1 or index > self.last + 1:
print 'Position is error'
else:
return self.data[index-1]

def getIndex(self, elem):
'''''根据元素获取索引'''
if self.isEmpty():
print 'SeqList is empty!'
return
else:
for i in range(self.last + 1):
if self.data[i] == elem:
return i + 1

def append(self, elem):
'''''向顺序表尾插入一个元素'''
if self.isFull():
print 'SeqList is full'
else:
self.last += 1
self.data[self.last] = elem

def insert(self, index, elem):
'''''
初始条件:顺序线性表已存在, 1 <= index <= self.last + 1
操作结果:在index前面插入新元素,并长度加1
'''
if self.isFull():
print 'SeqList is full'
return
elif index < 1 or index > self.last + 1:
print 'Position is error'
return
else:
for i in range(self.last, index-2, -1): #index-1位置后面的全部元素往后移动1位
self.data[i + 1] = self.data[i]
self.data[index-1] = elem #插入
self.last += 1 #长度加1

def delete(self, index):
'''''删除元素'''
if self.isEmpty():
print "SeqList is empty"
return
elif index < 1 or index > self.last + 1:
print 'Position is error'
return
else:
for i in range(index, self.last+1): #index后面的元素全部往前移动一位。
self.data[i-1] = self.data[i]
self.last -= 1

test

s = SqList(5) # data = [0, 1, 2, 3, 4]   s = None
s.append(5) # data = [5, 1, 2, 3, 4] s = [5]
s.insert(1, 6) # data = [6, 5, 2, 3, 4] s = [6, 5]
s.insert(1, 7) # data = [7, 6, 5, 3, 4] s = [7, 6, 5]

s.insert(2,11) # data = [7, 11, 6, 5, 4] s = [7, 11, 6, 5]

s.delete(3) # data = [7, 11, 5, 5, 4] s = [7, 11, 5]

s.getIndex(7) # 1
s.getElem(2) # 11
s.getLength() # 3
s[2] = 99 # data = [7, 99, 5, 5, 4] s = [7, 99, 5]
s.clear() # data = [7, 99, 5, 5, 4] s = None
len(s) # 0

插入和删除的时间的复杂度O(n)。

文章目录
  1. 1. 线性表的顺序存储
    1. 1.1. test