数据结构与算法的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

测试效果如下：