1 顺序表的定义
- 线性表 是具有相同数据类型的n个数据元素的有限序列。
- 顺序表 使用组地址连续的存储单元、依次存储线性表中的数据元素,从而使得逻辑上相邻的两个元素在物理位置上也相邻。顺序表是线性表的顺序存储。
假设线性表L存储的起始位置为LOC(A),sizeof(ElemType)是每个数据元素所占用存储空间的大小,则表L所对应的顺序存储如下图所示:
线性表的顺序存储结构
python实现
class SeqList(object): def __init__(self,size=50): # 初始化线性表 # 定义线性表的最大长度为50 self.max=size self.num=0 self.data=[None]*self.max def is_empty(self): # 判断线性表是否为空 return self.num is 0 def if_full(self): # 判断线性表是否为满 return self.num is self.max def __getitem__(self, index): # 获取线性表中某一位置的值 if not isinstance(index,int): raise TypeError if 0 <= index < self.max: return self.data[index] else: raise IndexError def __setitem__(self, index, value): # 修改线性表中某一位置的值 if not isinstance(index,int): raise TypeError if 0<=index<self.max: self.data[index]=value else: raise IndexError def locate_item(self,value): # 按值查找第一个等于该值的索引 for i in range(self.num): if self.data[i]==value: return i return -1 def count(self): # 返回线性表中元素的个数 return self.num def append_last(self,value): # 在表尾插入一个元素 if self.num>self.max: print("list is full") else: self.data[self.num]=value self.num+=1 def insert(self,index,value): # 在表中任意位置插入一个元素 if self.num>=self.max: print("list is full") if not isinstance(index,int): raise TypeError if index<0 or index>self.num: raise IndexError for i in range(self.num,index,-1): self.data[i]=self.data[i-1] self.data[index]=value self.num += 1 # def insert_by_loc(self,i,value): # 在线性表的第i个位置插入值value 表头 表中 表尾 都可以 # if i < 1 or i > self.num+1: # print("i is not right") # if self.num >= self.max: # print("list is full!") # for j in range(self.num+1,i,-1): # self.data[j]=self.data[j-1] # self.data[i-1]=value # self.num += 1 def remove(self,index): # 删除表中某一位置的值 if isinstance(index,int): raise TypeError if index < 0 or index >= self.num: raise IndexError for i in range(index,self.num): self.data[i]=self.data[i+1] self.num -= 1 def print_list(self): # 删除线性表 for i in range(0,self.num): print(self.data[i]) def destroy(self): # 销毁线性表 self.__init__() if __name__ == '__main__': seqlist=SeqList() print(seqlist.is_empty()) seqlist.append_last(18) print(seqlist.__getitem__(0))
买了王道的数据结构与算法,准备用python进行代码实现里面的实例,准备春招