基于python的数据结构与算法——线性表

线性表

概念

• 将一组（同为某个类型的）数据元素作为整体管理和使用
• 用元素在序列里的位置和顺序，表示数据之间的某种关系
• 线性表是一种组织数据元素的数据结构
• 一个线性表是某类元素的一个集合+记录元素之间的顺序关系
• 实现：list和tuple

操作

• self：被操作的对象
• elem：元素
• op：具体的操作

两种基本的实现模型

• 将表中元素顺序地存放在一大块连续的存储区里——顺序表
• 将表中元素存放在通过链接构造起来的一系列存储块里——链表

顺序表的实现

基本实现方式

元素顺序存放在一片足够大的连续存储区里，首元素存入开始位置，其余元素依次顺序存放

1. tuple：创建不变的顺序表，适用于建立时就确定好元素个数的存储。
2. list：创建变动的表，需区分当前元素个数（num）和总容量（max）

基本操作的实现

一、创建和访问操作

1. 创建空表

• python函数默认值只初始化一次，也就是说这段代码的模块一旦加载进来，参数的默认值就固定不变了
• 想要实现动态默认值用None
• 传入的参数是可变类型时用None

import copy

maxsize = 5  # 全局变量，给定一个空间

# python函数默认值只初始化一次，也就是说这段代码的模块一旦加载进来，参数的默认值就固定不变了
# 想要实现动态默认值用None
# 传入的参数是可变类型时用None
class seqList:
    def __init__(self, A=None):
        # 不传入A，就是None,表示还没有表
        # 传入A，表示已经有个表
        self.maxsize = maxsize

        if A is None:  # 表不存在，就创建一个空表
            self.len = 0
            self.list = []
        elif len(A) > self.maxsize:
            self.len = 0
            self.list = []
            raise Exception("Warning:输入列表过大，返回一个空顺序表，以重新建一个更大的表")
        else:
            self.len = len(A)
            self.list = copy.deepcopy(A)  # deepcopy真正意义上的复制，新开辟一块空间


if __name__ == '__main__':
    s = seqList()
    print(s.list)
    A = [1, 2, 3, 4, 5]
    s = seqList(A)
    print(s.list)
    A = [1, 2, 3, 4, 5, 6]
    s = seqList(A)
    print(s.list)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

2. 简单判断操作
   

    # 判断空
    def is_empty(self):
        return self.len == 0

    # 判断满
    def is_full(self):
        return self.len == maxsize
1
2
3
4
5
6
7

3. 计算表长
   

# 计算表长
    def count_len(self):
        length = 0
        for i in self.list:
            length += 1
        print("表长", length)
        return length
1
2
3
4
5
6
7

4. 访问给定下标 i 的元素
   

    # 访问给定下标i的元素
    def get_i(self, i):
        if (i < 1) or (i > self.len):
            raise Exception("i不合法")
        return self.list[i - 1]
1
2
3
4
5

5. 查找给定元素 d 的位置（首次出现）
   

    # 查找给定元素的第一次出现的位置
    def locate_elem(self, elem):
        for i in range(self.len):  # 下标从0到self.len-1
            if self.list[i] == elem:
                return i + 1  # 返回位序
        return 0
1
2
3
4
5
6

二、变动操作

删除

1.根据位置删

 # 删除位置为i的元素
    def del_by_i(self, i):
        if (i < 1) or (i > self.len):
            raise Exception("位置i不合法")
        temp = self.list[i - 1]
        for index in range(i - 1, self.len - 1):  # 左闭右开
            self.list[index] = self.list[index + 1]  # [len-2]=[len-1]
        self.list[self.len - 1] = -1
        self.len -= 1
        return temp
  
1
2
3
4
5
6
7
8
9
10
11

2. 摧毁表
   
   

插入

• 发现这个代码出错了
  
  

后来查阅资料才知道：

• 由于我没有用append()，所以体验不到列表自动扩容的特性（这是个黑匣子，封装好了，隐形使用）
• 由于python的list是动态扩展的，而我们要实现底层具有固定容量、占用一段连续的内存空间的顺序表，需要在构造函数初始化时加上下面的化，None作为无效元素的标识

self._data = [None] * self._capacity 
1

所以我的构造函数初始化应该这样写：

    def __init__(self, A=None):
        # 不传入A，就是None,表示还没有表
        # 传入A，表示已经有个表
        self.maxsize = maxsize

        if A is None:  # 表不存在，就创建一个空表
            self.len = 0
            self.list = [None] * maxsize
        elif len(A) > self.maxsize:
            self.len = 0
            self.list = [None] * maxsize
            raise Exception("Warning:输入列表过大，返回一个空顺序表，以重新建一个更大的表")
        else:
            self.len = len(A)
            # deepcopy真正意义上的复制，新开辟一块空间
            # 本来传来一个A，然后我重新开辟一个空间，跟她一模一样，但是叫list，两个的地址不一样了
            self.list = copy.deepcopy(A)
            self.list += [None] * (maxsize - self.len)  # 原来的+再扩大（maxsize-self.len)的空间，拼接起来又给了self.list
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

插入才能跑起来：

 # 先判满，满就需要重新开辟
    # 插入
    def insert_elem_by_i(self, i, elem):
        if s.is_full():
            raise Exception("表已满，请扩容")
        elif (i < 1) or (i > self.len + 1):
            raise Exception("插入位置异常")
        else:
            # 中间插
            for index in range(self.len, i - 1, -1):
                self.list[index] = self.list[index - 1]
            self.list[i - 1] = elem
            self.len += 1
            return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14

反转

    def reverse_list(self):
        list = self.list
        i, j = 0, self.len - 1
        while i < j:
            list[i], list[j] = list[j], list[i]
            i, j = i + 1, j - 1

1
2
3
4
5
6
7

注意

python 列表 初始化

总结

完整代码

import copy

maxsize = 5  # 全局变量，给定一个空间


# python函数默认值只初始化一次，也就是说这段代码的模块一旦加载进来，参数的默认值就固定不变了
# 想要实现动态默认值用None
# 传入的参数是可变类型时用None
class seqList:
    def __init__(self, A=None):
        # 不传入A，就是None,表示还没有表
        # 传入A，表示已经有个表
        self.maxsize = maxsize

        if A is None:  # 表不存在，就创建一个空表
            self.len = 0
            self.list = [None] * maxsize
        elif len(A) > self.maxsize:
            self.len = 0
            self.list = [None] * maxsize
            raise Exception("Warning:输入列表过大，返回一个空顺序表，以重新建一个更大的表")
        else:
            self.len = len(A)
            # deepcopy真正意义上的复制，新开辟一块空间
            # 本来传来一个A，然后我重新开辟一个空间，跟她一模一样，但是叫list，两个的地址不一样了
            self.list = copy.deepcopy(A)
            self.list += [None] * (maxsize - self.len)  # 原来的+再扩大（maxsize-self.len)的空间，拼接起来又给了self.list

    # 判断空
    def is_empty(self):
        return self.len == 0

    # 判断满
    def is_full(self):
        return self.len == maxsize

    # 访问给定下标i的元素
    def get_i(self, i):
        if (i < 1) or (i > self.len):
            raise Exception("i不合法")
        return self.list[i - 1]

    # 查找给定元素的第一次出现的位置
    def locate_elem(self, elem):
        for i in range(self.len):  # 下标从0到self.len-1
            if self.list[i] == elem:
                return i + 1  # 返回位序
        return 0

    # 计算表长
    def count_len(self):
        length = 0
        for i in self.list:
            length += 1
        print("表长", length)
        return length

    # 删除位置为i的元素
    def del_by_i(self, i):
        if (i < 1) or (i > self.len):
            raise Exception("位置i不合法")
        temp = self.list[i - 1]
        for index in range(i - 1, self.len - 1):  # 左闭右开
            self.list[index] = self.list[index + 1]  # [len-2]=[len-1]
        self.list[self.len - 1] = -1
        self.len -= 1
        return temp

    # 先判满，满就需要重新开辟
    # 插入
    def insert_elem_by_i(self, i, elem):
        if s.is_full():
            raise Exception("表已满，请扩容")
        elif (i < 1) or (i > self.len + 1):
            raise Exception("插入位置异常")
        else:
            # 中间插
            for index in range(self.len, i - 1, -1):
                self.list[index] = self.list[index - 1]
            self.list[i - 1] = elem
            self.len += 1
            return True

    def reverse_list(self):
        list = self.list
        i, j = 0, self.len - 1
        while i < j:
            list[i], list[j] = list[j], list[i]
            i, j = i + 1, j - 1

    def print_list(self):
        print(self.list[:self.len])  # 左闭右开


if __name__ == '__main__':
    A = [1, 2]
    s = seqList(A)

    s.insert_elem_by_i(2, 12)
    s.print_list()
    s.insert_elem_by_i(2, 24)
    s.print_list()
    s.insert_elem_by_i(5, 55)
    s.print_list()
    # s.reverse_list()
    # s.print_list()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107