首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >线性表之顺序存储结构

线性表之顺序存储结构

作者头像
哒呵呵
发布2018-08-06 15:01:07
3480
发布2018-08-06 15:01:07
举报
文章被收录于专栏:鸿的学习笔记鸿的学习笔记

"""

线性表

定义是零个或多个数据元素的有限序列

线性表的长度是线性表元素的个数n(n>=0),当n=0时,就是空表

线性表的抽象数据类型

ADT 线性表(List)

Data:

线性表的数据对象集合为{a1,a2,...an},每个元素的数据类型均为DataType。

Operation

InitList(List):初始化操作,建立一个空的线性表L

ListEmpty(List):若线性表为空,返回True,否则就是False

ClearList(List):将线性表清空

GetElem(L,i,e):将线性表L中的第i个位置元素值返回e

LocateElem(L,e):确定与给定值e相等的元素,查找成功,则返回True,否则False

ListInsert(L,i,e):在线性表L中的第i个位置插入新元素e

ListLength(L):返回线性表L的元素个数

"""

"""

顺序存储结构:用一段地址连续的存储单元依次存储线性表的数据元素

"""

class SqList():

def __init__(self):

self.list = []

self.length = 0

def ListEmpty(self):

return self.length == 0

def ClearList(self):

self.list = []

def GetElem(self, i, e):

if (self.length == 0) or (i < 1) or (i > self.length):

return False

e = self.data[i - 1]

return e

def LocateElem(self, e):

for elem in self.list:

if elem == e:

return True

return False

def ListInsert(self, i, e):

if (self.length == 0) or (i < 1) or (i > self.length):

return False

for j in range(self.length, i-1, -1):

self.list[j+1] = self.list[j]

data[i-1] = e

self.length += 1

return True

def ListLength(self):

return self.length

def ListDelete(self, i, e):

if (self.length == 0) or (i < 1) or (i > self.length):

return False

for j in range(i, self.length):

self.list[j-1] = self.list[j]

self.length -= 1

return False

"""

然后这是复杂度的计算

最好的情况,插入和删除最后一个位置,时间复杂度为O(1),最坏的情况呢,显然是O(n)

"""

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2017-09-03,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 鸿的学习笔记 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档