数据结构与算法的Python实现(二)——线性表之顺序表

在编程中,我们常使用一组有顺序的数据来表示某个有意义的数据,这种一组元素的序列的抽象,就是线性表,简称表,是很多复杂数据结构的实现基础,在Python中,list和tuple就可以看作是线性表的实现。

一、线性表的性质和ADT

(一)几个基本概念

1.线性表是一组有穷元素(元素可以是任何类型的数据)拍成的序列,元素的位置称作下标,下标从0开始计数;

2.表中元素的个数称作表的长度,不含任何元素的表称为空表,空表的长度为0;

3.非空表的第一个元素为首元素,最后一个元素为尾元素,除首元素外,每一个元素的上一个元素称为前驱元素,除尾元素外,每一个元素的后一个元素称为后继元素;

(二)表抽象数据类型

1.表的操作

考虑到需求,我们对表可能有如下操作:

•创建一个空表,或者根据提供的元素序列初始化一个新表;

•判断是否为空表、输出表的长度(元素个数)、检查是否存在某个元素;

•在表中插入一个元素、删除特定位置的元素或按照内容删除元素;

•对整个表进行的操作,比如两个表的合并、一个表按照某种运算生成一个新表等;

•遍历

2.表抽象数据类型的伪代码描述

根据以上操作,我们可以设计表抽象数据类型伪代码如下:

ADT List: #表抽象数据类型

List(self) #创建一个新表

is_empty(self) #判断self是否为空表

len(self) #获得self的长度

prepend(self,elem) #在self的首元素前插入元素elem

append(self,elem) #在self的尾元素后插入元素elem

insert(self,elem,i) #在self的位置i处插入元素elem,其他元素保持相对位置不变

del_first(self) #删除self的首元素

del_last(self) #删除self的尾元素

del(self,i) #删除self的第i个元素

search(self,elem) #查找elem在self中出现的位置,不存在则返回-1

forall(self,op) #对self中的每个元素执行操作op

3.经典的线性表实现模型

•将表中的元素顺序存放在一片足够大的连续存储位置里,称作顺序表,元素在存储区内的物理顺序就是该表的元素的逻辑顺序,本文后面讲讨论顺序表;

•将表中的元素通过链接的形式保持顺序,存储在一系列存储区内,称作链表,在下一篇文章中讨论。

二、顺序表的实现

(一)顺序表的布局方案

先考虑一种简单情况:如果表中的每一个元素占用的存储空间相同,那么可以直接在内存中顺序存储,假设第0个元素的存储位置为l_0,每个元素占用的空间为c=size(e),那么第i个元素的存储位置就是l_i=l_0 + c * i,此时实现对某个位置元素的访问,可以直接通过计算出的位置访问,时间复杂度为O(1)。

那么当元素长度不一样的时候怎么解决呢?我们可以按照刚才的方式,在顺序表中存放元素的存储位置,而元素另行存储,这个顺序表就称作是这组数据的索引,这就是最简单的索引结构了。索引顺序表的每个元素为地址,占用空间一样,直接访问索引再依据索引中存放的地址找到实际元素,时间复杂度依然为O(1)。

新的问题来了,表的操作要求表的长度是可以变化的,增删操作均会引起表长度的变化,那么如何给表分配空间呢?Python中的tuple类型就是一种不可变的数据类型,在建立时根据元素个数分配存储区域,但需要变化长度的时候,就不能用这种分配方式了。

解决这种方式有一种方法是分配一大片区域,在表的开始位置记录这个表的容量和现有元素个数,表中除了构造时的元素外,其他空间留出空位供新元素使用。至于如果需要的空间超出了表的容量了怎么办呢?这个我们后面再讨论,现在我们先依照上面的思路,考虑各种操作的实现。

(二)顺序表基本操作的实现

1.创建空表

分配一块内存区域,记录表的容量,同时将表的元素个数设置为0,例如max=8,num=0;

2.判断表空表满

很简单,num=0时为表空,num=max时为表满;O(1)

3.访问下标为i的元素

首先检查下标i是否合法,即i在0到num-1之间(能取到边界值),合法则计算实际位置,由实际位置返回元素值;O(1)

4.遍历访问元素

用一个整数标志记录遍历到达的位置,每个元素的位置同理计算得出,前后位置可以减一加一实现,注意遍历时不可超出边界;O(n)

5.查找某值在表中第一次出现的位置

基于下标线性检索,依次比较元素和该值是否相同,相同则返回索引,若检索完不存在相同,则返回-1;O(n)

6.查找某值在表中k位置后第一次出现的位置

原理与上一条相同,只不过索引从k开始而已。O(n)

7.尾端插入新元素

先不考虑分配更多空间的情况,表满时插入返回错误提示,不满时,直接在该位置插入,并修改num的值;O(1)

8.新元素插入到位置k

这是插入的一般情况,尾端时k=num。先检查k是否合法,如果合法,将表中k位置和之后的元素都向后移动,以保证表的顺序,然后在k位置插入该元素,更新num值;O(n)

9.删除尾元素

直接num减一就行,在逻辑上已经删除了尾元素;O(1)

10.删除位置k的元素

将位置k之后的元素依次前移,num减一;O(n)

11.基于条件的删除

遍历,删除;O(n*n)

(三)补充说明

1.顺序表的实现方式

2.表满之后的操作

插入时如果表满,可以申请一片更大的空间,然后将表的元素全部复制过去,然后改变表对象的链接指向新区域,插入新元素,这样就可以实现表的动态扩容。

3.扩容的大小

可以是线性扩容,例如每次增加10个元素存储空间,考虑到每次扩容需要复制,此时插入一个元素的平均时间复杂度为O(n),显然不太理想,另一种一种方法加倍扩容,每次扩容后容量翻倍,此时插入操作的复杂度为O(1),虽然效率提高了,但造成了空间的浪费。(时间复杂度的具体计算在此不做讨论)

(四)Python中的list类型

Python中的list就是个可变的顺序表类型,实现了以上各种操作,感兴趣可以去看具体实现的代码,其中表容量操作由解释器完成,避免了认为设置容量引发的错误。最后列举几个操作的使用:

1.访问

list[i]

2.获取元素个数

len(list)

3.返回最大值,最小值

max(list)

min(list)

4.将元组转化为列表

list(seq)

5.尾部插入新元素

list.append(elem)

6.统计某个元素出现的次数

list.count(elem)

7.尾部一次性追加元素序列

list.extend(seq)

8.找出第一个值为elem的元素的索引

list.index(elem)

9.在i位置插入elem

list.insert(i,elem)

10.弹出第i个元素,并返回该元素的值,默认为最后一个元素

list.pop(i)

11.移除第一个值为elem的元素

list.remove(elem)

12.将list反向

list.reverse()

13.清空列表

list.clear()

14.复制列表

list.copy()

15.对列表进行排序

list.sort(cmp=None,key=None,reverse=False)

cmp为排序方法,key为用来比较的元素,reverse为True时降序,默认False为升序,具体使用很灵活,可以参考相关文档。

思考:设计一个列表(以后我们会知道这种列表叫做栈),可以实现

push(x):将x插入队尾

pop():弹出最后一个元素,并返回该值

top():返回第一个元素

getMin():返回列表中的最小值

并且要求每个操作的时间复杂度都为O(1),难点在于getMin()的时间复杂度。

以下是上篇思考题我的实现,欢迎提建议:

import datetime

class Student:

_idnumber = 0 #用于计数和生成累加学号

@classmethod #类方法,用于生成学号

def _generate_id(cls):

cls._idnumber += 1

return "{:04}{:05}".format(year,cls._idnumber)

def __init__(self,name,sex,birthday): #验证输入后初始化

if not sex in ("男","女"):

raise StudentValueError(sex)

if not isinstance(name,str):

raise StudentValueError(name)

try:

birth = datetime.date(*birthday)

except:

raise StudentValueError(birthday)

self._name = name

self._sex = sex

self._birthday = birth

self._studentid = Student._generate_id()

def print(self): #打印全部属性

print(",".join((self._studentid,self._name,self._sex,str(self._birthday))))

def setName(self,newname): #设置姓名属性,其他属性同理

if not isinstance(newname,str):

raise StudentValueError(name)

self._name = newname

def getAge(self): #计算年龄

try:

birthday = self._birthday.replace(year = today.year) #如果生日是2月29且今年不是闰年则会异常

except ValueError:

birthday = self._birthday.replace(year = today.year,day = today.day - 1) #解决方法是把日减一

if birthday > today: #没到今年生日则减一,到了则不减

return today.year - self._birthday.year - 1

else:

return today.year - self._birthday.year

class StudentValueError(ValueError): #用于抛出异常的类

pass

测试效果如下:

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180616G131FK00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券