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

摘要：文章首发于公众号一件风衣在编程中，我们常使用一组有顺序的数据来表示某个有意义的数据，这种一组元素的序列的抽象，就是线性表，简称表，是很多复杂数据结构的实现基础，在中，和就可以看作是线性表的实现。

文章首发于公众号一件风衣（ID：yijianfengyi）

在编程中，我们常使用一组有顺序的数据来表示某个有意义的数据，这种一组元素的序列的抽象，就是线性表，简称表，是很多复杂数据结构的实现基础，在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
        year = datetime.date.today().year
        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):  #计算年龄
        today = datetime.date.today()
        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

测试效果如下：