数据结构：线性表（Python实现基本操作）_python线性表语法

简介

线性表：n 个数据元素的有限序列。是一种常见的线性结构。

线性结构特点：

• 第一个元素无前驱
• 最后一个元素无后继
• 除第一个元素和最后一个元素外，所有的元素都有前驱和后继

顺序结构

顺序表

        线性表的顺序存储结构
特点：

• 逻辑上相邻的元素物理位置上相邻
• 随机访问

        只要确定好了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的储存结构。通常用数组表示顺序表。

        Python实现基本操作：

List = [0,1,2,3,4,5]
# 按址查找（地址）
List.index(2)
print(List.index(2))
# 插入(地址， 值)
List.insert(2, 3)
print(List)
# 删除(地址)
List.pop(2)
print(List)
# 判空
ListEmpty = True if not List else False
print(ListEmpty)
# 求长
len(List)
print(len(List))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

输出：

2
[0, 1, 3, 2, 3, 4, 5]
[0, 1, 2, 3, 4, 5]
False
6
1
2
3
4
5

插入与删除：

链式结构

单链表

线性表的链式存储结构之一
特点：

• 逻辑相邻的元素物理位置不一定相邻

下面是单链表的简单结构：

        链表中的数据是以结点来表示的，每个结点包含两个域，一个数据域（元素域）和一个指针域。这个指针指向链表中的下一个结点，而最后一个结点的指针域则指向一个空值。每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。
基本构成：

• 结点：每个节点有两个部分，左边部分称为值域，用来存放数据；右边部分称为指针域，用来存放指向下一个元素的指针。
• head（头结点）：head节点永远指向第一个节点
• tail（尾节点）：tail永远指向最后一个节点
• null：链表中最后一个节点的指针域为None值

Python实现单链表操作（参考：python实现单链表的基本操作）

class Node(object):
    def __init__(self, item):
        # 元素
        self.element = item
        # 指针
        self.next = None


# 创建单链表类
class SingleLinkList(object):
    def __init__(self):
        self.header = None
        self.length = 0

    # 1、判断是否为空
    def is_empty(self):
        if self.header == None:
            return True
        else:
            return False

    # 2、头部插入
    def add(self, node):
        # 如果为空
        if self.is_empty():
            self.header = node
        else:
            node.next = self.header
            self.header = node
            # currentNode = self.header
        self.length += 1

    # 3、尾部插入
    def append(self, node):
        current_Node = self.header
        if self.is_empty():
            self.add(node)
        else:
            # 找到最后一个结点
            while (current_Node.next != None):
                current_Node = current_Node.next
            current_Node.next = node
            self.length += 1

    # 4、指定位置插入
    def insert(self, node, index):
        current_Node = self.header
        
        if index > self.length + 1 or index <= 0:
            while (index > self.length + 1 or index <= 0):
                print("你要插入的位置不对，请重选位置:")
                index = eval(input())

        if index == 1:
            self.add(node)
        elif index == 2:
            node.next = self.header.next
            self.header.next = node
            self.length += 1
        else:
            for i in range(1, index - 1):
                current_Node = current_Node.next
            node.next = current_Node.next
            current_Node.next = node
            self.length += 1

    # 5、遍历
    def travel(self):
        current_Node = self.header
        if self.length == 0:
            print("目前链表没有数据！")
        else:
            print("目前链表里面的元素有:", end=" ")
            for i in range(self.length):
                print("%s " % current_Node.element, end=" ")
                current_Node = current_Node.next
            print("\n")

    # 6、排序不用交换节点的位置，只需要交换节点上的数据值
    def list_sort(self):
        for i in range(0, self.length - 1):
            current_Node = self.header
            for j in range(0, self.length - i - 1):
                if current_Node.element > current_Node.next.element:
                    temp = current_Node.element
                    current_Node.element = current_Node.next.element
                    current_Node.next.element = temp

                current_Node = current_Node.next

    # 7、按索引删除
    def delete(self, index):
        if index <= 0 or index > self.length:
            while (index <= 0 or index > self.length):
                print("你输入的下标不对，请重新输入需要删除的值的下标：")
                index = eval(input())
                #   return
        else:
            if index == 1:
                self.header = self.header.next
                currentNode = self.header
            elif index == 2:
                current_Node = self.header
                current_Node.next = current_Node.next.next
            else:
                current_Node = self.header
                for i in range(1, index - 1):
                    current_Node = current_Node.next
                current_Node.next = current_Node.next.next
        self.length -= 1

    # 8、查找是否包含,并返回下标
    def isContain(self, num):
        contain = 0
        current_Node = self.header
        for i in range(self.length):
            if current_Node.element == num:
                print("%d在链表中%d处\n" % (num, i + 1))  # i+1是在正常人认为的位置处，程序员一般是从0开始算起
                contain = 1
            current_Node = current_Node.next
        if contain == 0:
            print("%d不在链表中\n" % num)

    # 9、根据下标找节点
    def searchNodeByIndex(self, index):
        current_Node = self.header
        if index <= 0 or index > self.length:
            while (index <= 0 or index > self.length):
                print("你输入的下标不对，请重新输入:")
                index = eval(input())
                #   return 0
        if index > 0 or index <= self.length:
            for i in range(index - 1):
                current_Node = current_Node.next
            return current_Node

    # 10、根据下标修改节点的值
    def Alert(self, index, num):  # index定义为下标
        current_Node = self.header
        if index <= 0 or index > self.length:
            print("你输入的下标不对，请重新输入!\n")
        else:
            for i in range(index - 1):
                current_Node = current_Node.next
            current_Node.element = num
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145

循环链表

特点：

• 最后一个结点的指针指向头结点

双向循环链表

特点：

• 一个结点包含指向后继(next)和指向前驱(prior)两个指针，两个方向又分别构成循环链表。