[TOC]

线性表概述

定义：线性表是由若干个具有相同特性的数据元素组成的有限序列

栈、队列、双端队列和列表都是有序的数据集合，其元素的顺序取决于添加顺序或移除顺序。一旦某个元素被添加进来，它与前后元素的相对位置将保持不变。这样的数据集合经常被称为线性数据结构。

形式：{a[1],a[2],…,a[i],…,a[n]}

概念：直接先驱元素、直接后继元素、表头、表尾

逻辑结构：

image-20230831220058393

类型：有序线性表和无序线性表

特性：

  • 元素个数一定是有限的
  • 所有元素具有相同的性质
  • 除表头元素以外，其他所有元素都有唯一的（直接）先驱元素，除表尾元素以外，其他所有元素都有唯一的（直接）后继元素

抽象数据类型：

image-20230831220510668

顺序表

顺序表概念

顺序表是指采用顺序存储的方式来存储数据元素的线性表

将结点依次存放在一组地址连续的存储空间中

image-20230831235017246

顺序表的操作

顺序表基本操作的SequenceList类

image-20230831235351295

链表

链表是指采用链式结构来存储数据元素的线性表

  • 链表的特点：

  • 链表实现了存储空间的动态管理。

  • 链表在执行插入与删除操作时，不必移动其余元素，只需修改指针即可。

存储密度：衡量存储空间的使用效率

顺序表的存储密度为1，链表存储密度小于1

链表的基本知识

  • 链表的构成

链表是由一系列结点通过指针链接而形成的，每个结点可分为数据域和指针域两个部分，数据域可用于存储数据元素，指针域可用于存储下一结点的地址

image-20230901190218873

  • 链表的类型

单向链表、双向链表及循环链表

  • 单向链表：每个结点只包含一个指针域，它用来指向其直接后继结点

image-20230901190351310

  • 双向链表：每个结点包含两个指针域，其中一个用于指向先驱结点，可称之为先驱指针；另一个用于指向后继结点，可称之为后继指针

image-20230901190403247

  • 循环链表：循环链表最后一个结点的指针域指向第一个节点，循环链表有循环单链表和循环双链表之分，特点就是从表中任一结点出发，均可找到表中其他结点

image-20230901190611280

image-20230901190627720

  • 带头结点和不带头结点的区别

    插入和删除第一个结点，不带头结点需要特殊考虑，带头结点不需要。

  • 链表的基本操作

image-20230901190708691

代码实现

单链表

image-20230902023207029

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
class Node:
    def __init__(self,data):
        self.data = data
        self.next = None

class SingleLinkedList:
    def __init__(self):
        self.head = None

    def is_empty(self):
        return self.head is None

    def append(self,data):
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

    def prepend(self,data):
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
        else:
            new_node.next = self.head
            self.head = new_node

    # 只删除第一个data
    def delete(self,data):
        if self.is_empty():
            return

        if self.head.data == data:
            self.head = self.head.next
        else:
            current = self.head
            while current.next:
                if current.next.data == data:
                    current.next = current.next.next
                    break
                current = current.next

    def display(self):
        current = self.head
        while current:
            print(current.data,end=" ")
            current = current.next

    def search(self,data):
        if self.is_empty():
            return None

        if self.head.data == data:
            return self.head
        else:
            current = self.head
            while current:
                if current.data == data:
                    return current
                current = current.next

循环单链表

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
class Node:

    def __init__(self,data):
        self.data = data
        self.next = None

class CircularSingleLinkedList:

    def __init__(self):
        self.head = None

    def is_empty(self):
        return self.head is None

    def append(self,data):
        new_node = Node(data)

        if self.is_empty():
            self.head = new_node
            new_node.next = self.head
        else:
            new_node.next = self.head
            current = self.head
            while current.next != self.head:
                current = current.next
            current.next = new_node

    def prepend(self,data):
        new_node = Node(data)
        if self.is_empty():
            new_node.next = self.head
            self.head = new_node
        else:
            new_node.next = self.head
            self.head = new_node

    def insert(self,data):
        new_node = Node(data)
        if self.is_empty():
            print(f"链表为空，找不到{data}插入")
            return False
        else:
            current = self.head
            while True:
                if current.data == data:
                    new_node.next = current.next
                    current.next = new_node
                    break
                if current.next == self.head:
                    print(f"链表中不存在{data},插入错误")
                    break
                else:
                    current = current.next


    # 只删除第一个data
    def delete(self,data):
        if self.is_empty():
            return

        if self.head.data == data:
            self.head = self.head.next
        else:
            current = self.head
            while current.next:
                if current.next.data == data:
                    current.next = current.next.next
                    break
                current = current.next

    def display(self):
        if self.is_empty():
            print("链表为空")
        else:
            current = self.head
            while True:
                print(current.data,end=" ")
                current = current.next
                if current == self.head:
                    break

    def search(self,data):
        if self.is_empty():
            return None

        if self.head.data == data:
            return self.head
        else:
            current = self.head
            while current:
                if current.data == data:
                    return current
                current = current.next

双链表

image-20230902022919407

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
class Node:
    def __init__(self,data):
        self.data = data
        self.next = None
        self.prev = None

class DoubleLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def is_empty(self):
        return self.head is None

    def append(self,data):
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node

    def prepend(self,data):
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node

    def delete(self,data):
        current = self.head
        while current != None:
            if current.data == data:
                if current == self.head:
                    current.next.prev = None
                    self.head = current.next
                elif current == self.tail:
                    current.prev.next = None
                    self.tail = current.prev
                else:
                    current.prev.next = current.next
                    current.next.prev = current.prev
                break
            current = current.next

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" ")
            current = current.next

    def search(self,data):
        current = self.head
        while current:
            if current.data == data:
                return current
            current = current.next
        return False

循环双链表

image-20230902023522179

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
class Node:
    def __init__(self,data):
        self.data = data
        self.prev = None
        self.next = None

class CircularDoubleLinkedList:
    def __init__(self):
        self.head = None

    def is_empty(self):
        return self.head is None

    def append(self,data):
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
            new_node.next = self.head
            new_node.prev = self.head
        else:
            new_node.next = self.head
            self.head.prev.next = new_node
            new_node.prev = self.head.prev
            self.head.prev = new_node

    def prepend(self,data):
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
            new_node.next = self.head
            new_node.prev = self.head
        else:
            new_node.next = self.head
            new_node.prev = self.head.prev
            self.head.prev.next = new_node
            self.head.prev = new_node
            self.head = new_node

    def display(self):
        current = self.head
        while True:
            print(current.data,end=" ")
            current = current.next

            if current == self.head:
                break

    def delete(self,data):
        if self.is_empty():
            print("链表为空，无数据可删除")
            return False
        else:
            current = self.head
            while True:
                if current.data == data:
                    if current == self.head:
                        current.next.prev = self.head.prev
                        self.head.prev.next = current.next
                        self.head = current.next
                    else:
                        current.prev.next = current.next
                        current.next.prev = current.prev
                    return True
                current = current.next
                if current == self.head:
                    return False

    def search(self,data):
        current = self.head
        while current:
            if current.data == data:
                return current
            current = current.next
        return False

案例应用

image-20230902222830320

请结合单链表中的有关操作，输出队形变换后，两支小分队中的总人数和每一位同学的姓名。