Title image
p1nk's blog
Home Tags AboutMe Search
DS coding


x

线性表

线性表插入一个值

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
#include <iostream>
using namespace std;

const int MaxSize = 100; // 定义最大容量

typedef int ElemType; // 定义元素类型为 int

struct sqList {
    ElemType data[MaxSize]; // 存储元素的数组
    int length; // 表示顺序表的当前长度
};

bool ListInsert(sqList &L, int i, ElemType e) {
    // 检查位置 i 是否有效
    if (i < 1 || i > L.length + 1)
        return false;

    // 检查顺序表是否已满
    if (L.length >= MaxSize)
        return false;

    // 将第 i 个位置及之后的元素后移
    for (int j = L.length; j >= i; j--)
        L.data[j] = L.data[j - 1];

    // 在位置 i 处放入新元素 e
    L.data[i - 1] = e;
    L.length++; // 顺序表长度加 1
    return true;
}


int main() {
    // 创建并初始化顺序表
    sqList myList;
    myList.length = 5; // 假设顺序表已有 5 个元素
    for (int i = 0; i < myList.length; i++) {
        myList.data[i] = i + 1; // 初始化元素为 1, 2, 3, 4, 5
    }

    // 插入新元素
    int insertPos = 7; // 指定插入位置
    int newValue = 99; // 指定插入的新值

    if (ListInsert(myList, insertPos, newValue)) {
        cout << "Insertion successful!" << endl;
        cout << "New list: ";
        for (int i = 0; i < myList.length; i++) {
            cout << myList.data[i] << " ";
        }
        cout << endl;
    } else {
        cout << "Insertion failed!" << endl;
    }

    return 0;
}

并且插入的位置是相对位置。值得细看的代码。

简单了来说就说，用L.length作为下标用来表示一个空的位置，然后把前一个移到这个上面。

最后L.data[i - 1] = e;这个实现了为什么说，我们

1
2
3
// 插入新元素
int insertPos = 3; // 指定插入位置
int newValue = 99; // 指定插入的新值

这里是多少就是插入的相对位置。

线性表删除一个值

有了前面的基础，这个理解起来就easy太多了

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
#include <iostream>
using namespace std;

const int MaxSize = 100; // 定义最大容量

typedef int ElemType; // 定义元素类型为 int

struct sqList {
    ElemType data[MaxSize]; // 存储元素的数组
    int length; // 表示顺序表的当前长度
};

// 删除顺序表中的元素
bool ListDelete(sqList &L, int i, ElemType &e) {
    // 检查位置 i 是否有效
    if (i < 1 || i > L.length)
        return false;

    // 将被删除的元素赋值给 e
    e = L.data[i - 1];

    // 将第 i 个位置后的元素前移
    for (int j = i; j < L.length; j++) {
        L.data[j - 1] = L.data[j];
    }

    // 顺序表长度减 1
    L.length--;
    return true;
}

int main() {
    // 创建并初始化顺序表
    sqList myList;
    myList.length = 5; // 假设顺序表已有 5 个元素
    for (int i = 0; i < myList.length; i++) {
        myList.data[i] = i + 1; // 初始化元素为 1, 2, 3, 4, 5
    }

    // 删除操作
    int deletePos = 4; // 指定删除位置
    int deletedValue; // 用于接收被删除的值

    if (ListDelete(myList, deletePos, deletedValue)) {
        cout << "Deletion successful! Deleted element: " << deletedValue << endl;
        cout << "New list: ";
        for (int i = 0; i < myList.length; i++) {
            cout << myList.data[i] << " ";
        }
        cout << endl;
    } else {
        cout << "Deletion failed!" << endl;
    }

    return 0;
}

这个其实也不是删除了，只是把数值朝前移了，其实原来的下表的数字还存在，只不过我们剪短了线性表的长度，所以删除了。

单链表：

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
#include <iostream>
#include <cstdlib>  // For malloc and free

typedef int ElemType;  // 假设元素类型为int

// 定义单链表节点类型
struct iNode {
    ElemType data;    // 数据域
    iNode *next;      // 指针域
};

typedef iNode* LinkList; // 链表类型定义

// 带头结点的单链表的初始化
bool InitList(LinkList &L) {
    L = new iNode();  // 使用new代替malloc
    if (!L) return false;  // 检查内存分配是否成功
    L->next = nullptr;  // 明确使用nullptr代替NULL
    return true;
}

// 在链表的末尾添加一个新节点
void AppendNode(LinkList &L, ElemType value) {
    iNode *newNode = new iNode();  // 使用new创建节点
    newNode->data = value;
    newNode->next = nullptr;

    iNode *current = L;
    while (current->next != nullptr) {
        current = current->next;
    }
    current->next = newNode;
}

// 打印链表中的所有元素
void PrintList(LinkList L) {
    iNode *current = L->next;  // 跳过头结点
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

// 删除链表，释放内存
void DeleteList(LinkList &L) {
    iNode *current = L;
    while (current != nullptr) {
        iNode *next = current->next;
        delete current;  // 使用delete代替free
        current = next;
    }
    L = nullptr;
}

int main() {
    LinkList myList;
    if (InitList(myList)) {
        AppendNode(myList, 10);
        AppendNode(myList, 20);
        AppendNode(myList, 30);
        AppendNode(myList, 40);

        std::cout << "Elements in the linked list: ";
        PrintList(myList); // 输出: Elements in the linked list: 10 20 30 40

        DeleteList(myList); // 释放链表占用的内存
    } else {
        std::cout << "Failed to initialize the list." << std::endl;
    }

    return 0;
}

计算单链表长度

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
#include <iostream>
#include <cstdlib>  // For dynamic memory management

typedef int ElemType;  // 假设元素类型为int

// 定义单链表节点类型
struct iNode {
    ElemType data;    // 数据域
    iNode *next;      // 指针域
};

typedef iNode* LinkList; // 链表类型定义

// 带头结点的单链表的初始化
bool InitList(LinkList &L) {
    L = new iNode();  // 使用new代替malloc
    if (!L) return false;  // 检查内存分配是否成功
    L->next = nullptr;  // 明确使用nullptr代替NULL
    return true;
}

// 在链表的末尾添加一个新节点
void AppendNode(LinkList &L, ElemType value) {
    iNode *newNode = new iNode();  // 使用new创建节点
    newNode->data = value;
    newNode->next = nullptr;

    iNode *current = L;
    while (current->next != nullptr) {
        current = current->next;
    }
    current->next = newNode;
}

// 打印链表中的所有元素
void PrintList(LinkList L) {
    iNode *current = L->next;  // 跳过头结点
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

// 计算链表长度
int Length(LinkList L) {
    int len = 0;
    iNode *p = L->next;  // 从第一个数据节点开始，跳过头结点
    while (p != nullptr) {
        len++;
        p = p->next;
    }
    return len;
}

// 删除链表，释放内存
void DeleteList(LinkList &L) {
    iNode *current = L;
    while (current != nullptr) {
        iNode *next = current->next;
        delete current;  // 使用delete代替free
        current = next;
    }
    L = nullptr;
}

int main() {
    LinkList myList;
    if (InitList(myList)) {
        AppendNode(myList, 10);
        AppendNode(myList, 20);
        AppendNode(myList, 30);
        AppendNode(myList, 40);

        std::cout << "Elements in the linked list: ";
        PrintList(myList); // 输出: Elements in the linked list: 10 20 30 40

        std::cout << "Length of the linked list: " << Length(myList) << std::endl; // 输出链表的长度

        DeleteList(myList); // 释放链表占用的内存
    } else {
        std::cout << "Failed to initialize the list." << std::endl;
    }

    return 0;
}

有关链表的一些内容

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
#include <iostream>
#include <cstdlib>  // For dynamic memory management

typedef int ElemType;  // 假设元素类型为int

// 定义单链表节点类型
struct iNode {
    ElemType data;    // 数据域
    iNode *next;      // 指针域
};

typedef iNode* LinkList; // 链表类型定义

// 带头结点的单链表的初始化
bool InitList(LinkList &L) {
    L = new iNode();  // 使用new代替malloc
    if (!L) return false;  // 检查内存分配是否成功
    L->next = nullptr;  // 明确使用nullptr代替NULL
    return true;
}

// 在链表的末尾添加一个新节点
void AppendNode(LinkList &L, ElemType value) {
    iNode *newNode = new iNode();  // 使用new创建节点
    newNode->data = value;
    newNode->next = nullptr;

    iNode *current = L;
    while (current->next != nullptr) {
        current = current->next;
    }
    current->next = newNode;
}

// 打印链表中的所有元素
void PrintList(LinkList L) {
    iNode *current = L->next;  // 跳过头结点
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

// 计算链表长度
int Length(LinkList L) {
    int len = 0;
    iNode *p = L->next;  // 从第一个数据节点开始，跳过头结点
    while (p != nullptr) {
        len++;
        p = p->next;
    }
    return len;
}

// 删除链表，释放内存
void DeleteList(LinkList &L) {
    iNode *current = L;
    while (current != nullptr) {
        iNode *next = current->next;
        delete current;  // 使用delete代替free
        current = next;
    }
    L = nullptr;
}

// 获取链表中的第 i 个元素的指针
iNode *GetElem(LinkList L, int i) {
    iNode *p = L; // 从头结点开始
    int j = 0;
    while (p != nullptr && j < i) {
        p = p->next;
        j++;
    }
    // 返回第i个结点的指针或nullptr
    return p;
}

int main() {
    LinkList myList;
    if (InitList(myList)) {
        AppendNode(myList, 10);
        AppendNode(myList, 20);
        AppendNode(myList, 30);
        AppendNode(myList, 40);

        std::cout << "Elements in the linked list: ";
        PrintList(myList); // 输出: Elements in the linked list: 10 20 30 40

        std::cout << "Length of the linked list: " << Length(myList) << std::endl; // 输出链表的长度

        iNode *elem = GetElem(myList, 2);
        if (elem != nullptr) {
            std::cout << "Element at position 2: " << elem->data << std::endl;
        }

        DeleteList(myList); // 释放链表占用的内存
    } else {
        std::cout << "Failed to initialize the list." << std::endl;
    }

    return 0;
}

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
146
147
148
149
150
151
152
153
154
155
#include <iostream>
#include <cstdlib>  // For dynamic memory management

typedef int ElemType;  // Assuming element type is int

// Define the node structure for a singly linked list
struct iNode {
    ElemType data;    // Data field
    iNode *next;      // Pointer field
};

typedef iNode* LinkList; // Definition for the linked list type

// Initialize the singly linked list with a head node
bool InitList(LinkList &L) {
    L = new iNode();  // Allocate memory for the head node using new
    if (!L) return false;  // Check if memory allocation was successful
    L->next = nullptr;  // Set the next pointer of head to nullptr
    return true;
}

// Append a new node at the end of the linked list
void AppendNode(LinkList &L, ElemType value) {
    iNode *newNode = new iNode();  // Create a new node using new
    newNode->data = value;
    newNode->next = nullptr;

    iNode *current = L;
    while (current->next != nullptr) {
        current = current->next;
    }
    current->next = newNode;
}

// Print all elements in the linked list
void PrintList(LinkList L) {
    iNode *current = L->next;  // Skip the head node
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

// Compute the length of the linked list
int Length(LinkList L) {
    int len = 0;
    iNode *p = L->next;  // Start from the first data node, skipping the head node
    while (p != nullptr) {
        len++;
        p = p->next;
    }
    return len;
}

// Free the linked list and release memory
void DeleteList(LinkList &L) {
    iNode *current = L;
    while (current != nullptr) {
        iNode *next = current->next;
        delete current;  // Use delete instead of free
        current = next;
    }
    L = nullptr;
}

// Function to insert an element at the i-th position in the linked list
bool ListInsert(LinkList &L, int i, ElemType e) {
    iNode *p = L; // Start from the head node
    int j = 0; // Index to track the position

    // Find the (i-1)-th node
    while (p != nullptr && j < i - 1) {
        p = p->next;
        j++;
    }

    // Check if the position is valid
    if (p == nullptr) {
        return false;
    }

    // Create a new node
    iNode *s = new iNode();
    if (!s) return false; // Check if memory allocation was successful
    s->data = e;
    s->next = p->next;
    p->next = s;

    return true;
}

// Get the pointer to the i-th element in the linked list
iNode *GetElem(LinkList L, int i) {
    iNode *p = L; // Start from the head node
    int j = 0;
    while (p != nullptr && j < i) {
        p = p->next;
        j++;
    }
    // Return the pointer to the i-th node or nullptr
    return p;
}

// Locate a node by its value in the linked list
iNode *LocateElem(LinkList L, ElemType e) {
    iNode *p = L->next;  // Start from the first data node
    while (p != nullptr && p->data != e) {
        p = p->next;
    }
    // Return the pointer to the node if found, otherwise return nullptr
    return p;
}

int main() {
    LinkList myList;
    if (InitList(myList)) {
        AppendNode(myList, 10);
        AppendNode(myList, 20);
        AppendNode(myList, 30);
        AppendNode(myList, 40);

        std::cout << "Elements in the linked list: ";
        PrintList(myList);

        std::cout << "Length of the linked list: " << Length(myList) << std::endl;

        bool insertResult = ListInsert(myList, 2, 25); // Insert 25 at position 2
        if (insertResult) {
            std::cout << "After insertion: ";
            PrintList(myList); // Should print: 10 25 20 30 40
        } else {
            std::cout << "Insertion failed." << std::endl;
        }

        iNode *elem = GetElem(myList, 1);
        if (elem != nullptr) {
            std::cout << "Element at position 2: " << elem->data << std::endl;
        }

        iNode *searchResult = LocateElem(myList, 30);
        if (searchResult != nullptr) {
            std::cout << "Found element: " << searchResult->data << std::endl;
        } else {
            std::cout << "Element not found." << std::endl;
        }

        DeleteList(myList); // Release the list's memory
    } else {
        std::cout << "Failed to initialize the list." << std::endl;
    }

    return 0;
}

删除链表中的结点

简短点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool ListDelete(LinkList &L, int i, ElemType &e) {
    LNode *p = L;
    int j = 0;
    while (p != nullptr && j < i - 1) {
        p = p->next;
        j++;
    }
    if (p == nullptr || p->next == nullptr) {
        return false; // i值不合法
    }
    LNode *q = p->next;
    e = q->data;
    p->next = q->next;
    delete q;
    return true;
}

理解：首先就是要找到被删除结点的指针，然后指针的next指向被删除结点的指针的next就可以了，然后用e来接收一下被删除的值。

头插法：

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
#include <iostream>
#include <cstdlib> // For dynamic memory allocation

struct LNode {
    int data;
    LNode *next;
};

typedef LNode* LinkList;

// Function to initialize the linked list with a dummy head node
LinkList InitList() {
    LinkList L = (LNode*)malloc(sizeof(LNode)); // Allocate memory for the head node
    if (L == nullptr) {
        std::cerr << "Memory allocation failed." << std::endl;
        exit(EXIT_FAILURE);
    }
    L->next = nullptr; // Initially, the list is empty
    return L;
}

// Function to insert elements into the list using head insertion
LinkList HeadInsert(LinkList &L) {
    int x;
    std::cout << "Enter numbers to insert into the linked list (9999 to end): ";
    std::cin >> x; // Read the first element
    while (x != 9999) {
        LNode *s = (LNode*)malloc(sizeof(LNode)); // Allocate memory for a new node
        if (s == nullptr) {
            std::cerr << "Memory allocation failed." << std::endl;
            continue; // If allocation fails, skip to the next iteration
        }
        s->data = x; // Set the node's data
       LinkList HeadInsert(LinkList &L) {
    int x;
    std::cout << "Enter numbers to insert into the linked list (9999 to end): ";
    std::cin >> x; // Read the first element
    while (x != 9999) {
        LNode *s = (LNode*)malloc(sizeof(LNode)); // Allocate memory for a new node
        if (s == nullptr) {
            std::cerr << "Memory allocation failed." << std::endl;
            continue; // If allocation fails, skip to the next iteration
        }
        s->data = x; // Set the node's data
        s->next = L->next; // Insert the new node at the beginning
        L->next = s;
        std::cin >> x; // Read the next element
    }
    return L;
} // Insert the new node at the beginning
        L->next = s;
        std::cin >> x; // Read the next element
    }
    return L;
}

// Function to print the list elements
void PrintList(LinkList L) {
    LNode *current = L->next; // Start from the first actual element
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

int main() {
    LinkList myList = InitList(); // Initialize the linked list
    myList = HeadInsert(myList); // Perform head insertion of elements
    std::cout << "The elements in the linked list are: ";
    PrintList(myList); // Print the elements in the linked list
    return 0;
}


卧槽，我一直以为头插法是，接着插，没想到是每一次都是从头节点开始，后面仔细一想，如果是接着插，那不就是和尾插法一样了么

看一下chatgpt的可视化理解
image-20240503181308980

尾插法：

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
#include <iostream>
#include <cstdlib> // 用于动态内存分配

struct LNode {
    int data;
    LNode *next;
};

typedef LNode* LinkList;

// 初始化链表，创建头结点
LinkList InitList() {
    LinkList L = (LNode*)malloc(sizeof(LNode));
    if (L == nullptr) {
        std::cerr << "Memory allocation failed." << std::endl;
        exit(EXIT_FAILURE);
    }
    L->next = nullptr;
    return L;
}

// 尾插法创建链表
LinkList TailInsert(LinkList &L) {
    int x;
    std::cout << "Enter numbers to insert into the linked list (9999 to end): ";
    std::cin >> x;
    LNode *r = L; // r 是表尾指针
    while (x != 9999) {
        LNode *s = (LNode*)malloc(sizeof(LNode)); // 为新节点分配内存
        if (s == nullptr) {
            std::cerr << "Memory allocation failed." << std::endl;
            continue;
        }
        s->data = x; // 设置新节点数据
        r->next = s; // 将新节点插入到链表尾部
        r = s; // 更新尾指针到新的尾节点
        std::cin >> x;
    }
    r->next = nullptr; // 确保链表的最后一个节点的 next 指针为 nullptr
    return L;
}

// 打印链表
void PrintList(LinkList L) {
    LNode *current = L->next; // 从头结点之后的第一个实际节点开始
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

int main() {
    LinkList myList = InitList(); // 初始化链表
    myList = TailInsert(myList); // 使用尾插法添加元素
    std::cout << "The elements in the linked list are: ";
    PrintList(myList); // 打印链表
    return 0;
}

双链表：

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
#include <iostream>
#include <cstdlib> // 包含对 free 的支持

using namespace std;

typedef int ElemType;

// 定义双链表节点类型
typedef struct DNode {
    ElemType data;  // 数据域
    DNode *prior, *next;  // 前驱和后继指针
} DNode, *DLinkList;

// 初始化双链表
DLinkList InitDList() {
    DLinkList L = new DNode;  // 创建头节点
    L->prior = L->next = L;  // 头节点的前驱和后继指向自己，形成一个循环
    return L;
}

// 在双链表中p节点后插入新元素e
bool InsertAfter(DNode* p, ElemType e) {
    if (p == nullptr) return false;  // 检查p是否为nullptr

    DNode* s = new DNode;  // 创建新节点s
    s->data = e;  // 设置新节点s的数据
    s->next = p->next;      // 步骤1: 将s的next指针指向p的next
    if (p->next != nullptr) {  // 如果p不是最后一个节点
        p->next->prior = s;  // 步骤2: 设置p的下一个节点的prior为s
    }
    s->prior = p;            // 步骤3: 设置s的prior为p
    p->next = s;             // 步骤4: 设置p的next为s
    return true;
}

// 删除双链表中p的下一个节点
bool DeleteAfter(DNode* p) {
    if (p == nullptr || p->next == nullptr) return false;  // 检查p及其下一个节点是否存在

    DNode* q = p->next;  // q是要删除的节点
    if (q->next != nullptr) {  // 如果q不是最后一个节点
        q->next->prior = p;  // 步骤2: 设置q的下一个节点的prior为p
    }
    p->next = q->next;  // 步骤1: 设置p的next为q的next

    delete q;  // 步骤3: 释放q节点的内存
    return true;
}

// 打印双链表
void PrintDList(DLinkList L) {
    DNode* node = L->next;
    while (node != L) {  // 循环直到再次到达头节点
        cout << node->data << " ";
        node = node->next;
    }
    cout << endl;
}

// 主函数
int main() {
    DLinkList myList = InitDList();  // 初始化双链表
    InsertAfter(myList, 10);  // 在头节点后插入10
    InsertAfter(myList, 20);  // 在头节点后插入20
    InsertAfter(myList, 30);  // 在头节点后插入30

    cout << "The elements in the double linked list are: ";
    PrintDList(myList);

    DeleteAfter(myList->next);  // 删除第二个元素（值20的元素）

    cout << "After deletion: ";
    PrintDList(myList);

    return 0;
}

栈：

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
#include <iostream>
using namespace std;

typedef int ElemType;  // 栈元素类型定义为整型，可以根据需要修改

const int MaxSize = 100;  // 定义栈的最大容量

// 定义栈的结构
struct SqStack {
    ElemType data[MaxSize];  // 栈的数组存储
    int top;  // 栈顶指针
};

// 初始化栈
void InitStack(SqStack& s) {
    s.top = -1;  // 初始化栈顶指针
}

// 判断栈是否为空
bool StackEmpty(SqStack s) {
    return s.top == -1;  // 如果栈顶指针为-1，则栈为空
}

// 入栈操作
bool Push(SqStack& s, ElemType x) {
    if (s.top == MaxSize - 1) return false;  // 栈满，不能入栈
    s.data[++s.top] = x;  // 先将栈顶指针加1，然后入栈
    return true;
}

// 出栈操作
bool Pop(SqStack& s, ElemType &x) {
    if (s.top == -1) return false;  // 栈空，不能出栈
    x = s.data[s.top--];  // 先出栈，然后栈顶指针减1
    return true;
}

// 读取栈顶元素
bool GetTop(SqStack s, ElemType &x) {
    if (s.top == -1) return false;  // 栈空，不能读取栈顶元素
    x = s.data[s.top];  // 读取栈顶元素
    return true;
}

// 主函数示例
int main() {
    SqStack s;
    InitStack(s);  // 初始化栈

    // 进栈操作
    Push(s, 10);
    Push(s, 20);
    Push(s, 30);

    // 读取栈顶元素
    ElemType top;
    if (GetTop(s, top)) {
        cout << "Top element is: " << top << endl;
    }

    // 出栈操作
    ElemType popped;
    while (Pop(s, popped)) {
        cout << "Popped element: " << popped << endl;
    }

    return 0;
}

队列：

一些栈的操作

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
#include <iostream>
using namespace std;

const int MaxSize = 50;

typedef int ElemType;

struct SqQueue {
    ElemType data[MaxSize];
    int front, rear;
};

// 初始化队列
void InitQueue(SqQueue& Q) {
    Q.front = Q.rear = 0;
}

// 判断队列是否为空
bool IsEmpty(const SqQueue& Q) {
    return Q.front == Q.rear;
}

// 入队操作
bool EnQueue(SqQueue& Q, ElemType x) {
    if ((Q.rear + 1) % MaxSize == Q.front) {
        // 队满条件，避免假溢出
        return false;
    }
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1) % MaxSize;  // 循环队列
    return true;
}

// 出队操作
bool DeQueue(SqQueue& Q, ElemType& x) {
    if (IsEmpty(Q)) {
        return false;
    }
    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MaxSize;  // 循环队列
    return true;
}

// 查看队头元素
bool GetFront(const SqQueue& Q, ElemType& x) {
    if (IsEmpty(Q)) {
        return false;
    }
    x = Q.data[Q.front];
    return true;
}

int main() {
    SqQueue q;
    InitQueue(q);
    EnQueue(q, 1);
    EnQueue(q, 2);
    EnQueue(q, 3);

    ElemType x;
    while (DeQueue(q, x)) {
        cout << "Dequeued: " << x << endl;
    }

    return 0;
}

队列假溢出原理：

示例

考虑一个简单的非循环队列，最大大小为5，初始时 front 和 rear 都是0。如果连续入队5个元素然后出队3个，此时 front 是3，rear 是5，数组的前两个位置是空的。但如果使用 rear == MaxSize 作为队满的判断，虽然还有两个位置空着，新的入队操作却不能执行，因为 rear 无法增加。

一些疑惑：

在循环队列中，通常会有一个位置被故意留空来区分队列为空和队列为满的情况。这是因为在循环队列的实现中，front 指针和 rear 指针的行为特别关键，它们都在同一个固定大小的数组中循环移动。如果我们不留出一个空位，那么在某些情况下，front 和 rear 将会指向相同的位置，这将使得队列为空的状态和队列为满的状态无法区分。

解释队列为什么只能存储 MaxSize - 1 个元素

在循环队列中，以下是如何区分空队和满队的常用方法：

  • 队空条件：当 front == rear 时，队列为空。
  • 队满条件：当 (rear + 1) % MaxSize == front 时，队列为满。

如果没有留出一个空位，那么当队列实际已满时，rear 指针加一后正好绕回到 front 指针的位置（即 (rear + 1) % MaxSize == front），这时两者相等。但这种情况也恰好是队列为空时的情况（front == rear）。因此，为了避免这种歧义，我们通常保持队列中始终有一个位置不被使用。

举例说明

假设 MaxSize 设为 50，那么实际的存储索引是从 0 到 49。在循环队列中：

  • 当 front = 0 且 rear = 0 时，队列为空。
  • 为了确保队满和队空能够区分，我们让 rear 在队列即将满时停在 front - 1 的位置。即如果 front = 0，那么队满时 rear 应在 49，这时如果尝试再加入一个元素，rear 将移动到 0 位置（(49 + 1) % 50 = 0），恰好等于 front，满足队满的条件 (rear + 1) % MaxSize == front。

这种设计有效地使用数组的空间，并且确保了队列的操作可以高效且正确地判断队列的状态。在实际应用中，这意味着虽然你有一个大小为 50 的数组，实际上只能使用 49 个位置来存储队列中的元素。

栈的应用：

括号匹配 easy

表达式转换：

例子：转换表达式 A+B*(C-D)

中缀表达式：A + B * (C - D)

  • 在人类的日常书写和思考中，我们习惯于这种格式。操作符（如+、*）位于操作数（如A、B）之间，可能需要括号来指明运算顺序。

目标：将其转换为后缀表达式，即操作符跟随其操作数。

转换步骤

  1. 加括号：根据运算的优先级和结合律，首先明确运算顺序。在这个例子中，*和括号内的-优先级高于+。
    • 加括号后：(A + (B * (C - D)))
  2. 运算符后移：将操作符移动到其对应的操作数后面。
    • 将C - D转换为CD-
    • 将B * (C - D)转换为BCD-*
    • 将整个表达式A + (B * (C - D))转换为ABCD-*+
  3. 去除括号：由于后缀表达式的运算顺序已经通过操作符的位置明确，因此不再需要括号。
    • 最终后缀表达式：ABCD-*+

为什么使用后缀表达式？

后缀表达式（逆波兰表示法）对计算机来说更容易处理，因为它遵循一种直接且一致的解析模式，无需回溯。计算机可以使用一个栈来一次性从左到右处理表达式：

  • 处理后缀表达式 ABCD-*+

    ：

    • 遇到操作数（A, B, C, D），依次压入栈。
    • 遇到操作符（-），弹出栈顶的两个元素（D, C），计算C-D，将结果压回栈。
    • 遇到操作符（*），弹出栈顶的两个元素（上一步的结果和B），计算B*(C-D)，将结果压回栈。
    • 遇到操作符（+），弹出栈顶的两个元素（上一步的结果和A），计算A+B*(C-D)，得到最终结果。

后缀表达式求值过程

假设我们有后缀表达式 ABCD-*+EF/-，这里使用的是字母而非实际数字，为了解释过程，我们可以假设它们代表任意数值。求值的过程遵循以下步骤：

  1. 扫描表达式：从左到右扫描后缀表达式中的每一个字符。
  2. 处理操作数：如果扫描到的是操作数（如A、B、C、D、E、F），则将其压入栈中。
  3. 处理操作符：如果扫描到的是操作符（如+、-、*、/），则从栈中弹出两个顶端元素。第一个弹出的元素是右操作数，第二个弹出的是左操作数，然后使用这个操作符对这两个操作数执行运算。将运算结果压回栈中。
  4. 重复直至表达式尾端：重复步骤2和3直到整个表达式被扫描完毕。
  5. 结果：表达式扫描完成后，栈顶的元素就是整个表达式的计算结果。

例子详解

以表达式 ABCD-*+EF/- 为例，其求值过程如下：

  • 进栈：A, B, C, D （栈中内容：ABCD）
  • **操作符-**：弹出 D 和 C，计算 C-D，假设结果为 R1，压入栈（栈中内容：ABR1）
  • **操作符\***：弹出 R1 和 B，计算 B*R1，假设结果为 R2，压入栈（栈中内容：AR2）
  • **操作符+**：弹出 R2 和 A，计算 A+R2，假设结果为 R3，压入栈（栈中内容：R3）
  • 进栈：E, F （栈中内容：R3EF）
  • **操作符/**：弹出 F 和 E，计算 E/F，假设结果为 R4，压入栈（栈中内容：R3R4）
  • **操作符-**：弹出 R4 和 R3，计算 R3-R4，得到最终结果 R5，压入栈（栈中内容：R5）

最终栈顶的 R5 就是整个表达式的计算结果。这个过程利用了栈的“后进先出”特性，确保了每次运算都用到了最近的操作数和正确的操作顺序。




▲
▼


内敛而不懦弱 寂静而有力量


© - p1nk的生命线 ： 2001 ~ 2025 - Powered by Hexo