数据结构-实验三

实验三

[TOC]

3.1栈的顺序存储结构

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

// 定义顺序栈的最大大小
#define MAXSIZE 5

// 定义顺序栈
typedef struct {
    int data[MAXSIZE];
    int top;
} SqStack;

// 初始化顺序栈
void InitStack(SqStack& S) {
    S.top = -1;
}

// 判断顺序栈是否为空
bool IsEmpty(SqStack S) {
    return S.top == -1;
}

// 判断顺序栈是否已满
bool IsFull(SqStack S) {
    return S.top == MAXSIZE - 1;
}

// 入栈操作
bool Push(SqStack& S, int elem) {
    if (IsFull(S)) {
        cout << "栈已满，无法入栈。" << endl;
        return false;
    }

    S.data[++S.top] = elem;
    
    return true;
}

// 出栈操作
bool Pop(SqStack& S, int& elem) {
    if (IsEmpty(S)) {
        cout << "栈为空，无法出栈。" << endl;
        return false;
    }

    elem = S.data[S.top--];
    cout << "出栈元素：" << elem << "，当前栈顶指针：" << S.top << endl;
    return true;
}

// 获取顺序栈栈顶元素
bool GetTop(SqStack S, int& elem) {
    if (IsEmpty(S)) {
        cout << "栈为空，无法获取栈顶元素。" << endl;
        return false;
    }

    elem = S.data[S.top];
    cout << "栈顶元素为：" << elem << endl;
    return true;
}

// 显示菜单
void DisplayMenu() {
    cout << "===============菜单===============" << endl;
    cout << "1. 建栈" << endl;
    cout << "2. 取栈顶元素" << endl;
    cout << "3. 入栈" << endl;
    cout << "4. 出栈" << endl;
    cout << "5. 退出" << endl;
    cout << "===================================" << endl;
    cout << "请选择操作：";
}

int main() {
    // 顺序栈
    SqStack sqStack;
    InitStack(sqStack);

    int choice;
    int elem;

    do {
        DisplayMenu();
        cin >> choice;

        switch (choice) {
        case 1:
            InitStack(sqStack);
            cout << "建栈成功。" << endl;
            break;

        case 2: GetTop(sqStack, elem);
            break;

        case 3:
            cout << "请输入要入栈的元素（以-1结束）：";
            cout << "入栈元素：";
            while (true) {
                cin >> elem;

                if (elem == -1) {
                    cout << "入栈结束。" << endl;
                    break;
                }

                if (Push(sqStack, elem)) {
                    cout<< elem << " ";
                }
                else {
                    break;
                }
            }
                cout << "当前栈顶指针：" << sqStack.top << endl;
         
            break;

        case 4:  Pop(sqStack, elem);
            break;

        case 5:
            cout << "程序退出。" << endl;
            break;

        default:
            cout << "无效的选择，请重新输入。" << endl;
        }

    } while (choice != 5);

    return 0;
}

C++

3.2栈的链式存储

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

// 定义链表节点
struct Node {
    int data;
    Node* next;
};

// 定义链式栈
typedef struct {
    Node* top;
} LinkedStack;

// 初始化链式栈
void InitStack(LinkedStack& S) {
    S.top = nullptr;
}

// 判断链式栈是否为空
bool IsEmpty(LinkedStack S) {
    return S.top == nullptr;
}

// 入栈操作
bool Push(LinkedStack& S, int elem) {
    Node* newNode = new Node;
    newNode->data = elem;
    newNode->next = S.top;
    S.top = newNode;

    return true;
}

// 出栈操作
bool Pop(LinkedStack& S, int& elem) {
    if (IsEmpty(S)) {
        cout << "栈为空，无法出栈。" << endl;
        return false;
    }

    Node* temp = S.top;
    elem = temp->data;
    S.top = temp->next;
    delete temp;

    cout << "出栈元素：" << elem << endl;
    return true;
}

// 获取链式栈栈顶元素
bool GetTop(LinkedStack S, int& elem) {
    if (IsEmpty(S)) {
        cout << "栈为空，无法获取栈顶元素。" << endl;
        return false;
    }

    elem = S.top->data;
    cout << "栈顶元素为：" << elem << endl;
    return true;
}

// 显示菜单
void DisplayMenu() {
    cout << "===============菜单===============" << endl;
    cout << "1. 建栈" << endl;
    cout << "2. 取栈顶元素" << endl;
    cout << "3. 入栈" << endl;
    cout << "4. 出栈" << endl;
    cout << "5. 退出" << endl;
    cout << "===================================" << endl;
    cout << "请选择操作：";
}

int main() {
    // 链式栈
    LinkedStack linkedStack;
    InitStack(linkedStack);

    int choice;
    int elem;

    do {
        DisplayMenu();
        cin >> choice;

        switch (choice) {
        case 1:
            InitStack(linkedStack);
            cout << "建栈成功。" << endl;
            break;

        case 2:
            GetTop(linkedStack, elem);
            break;

        case 3:
            cout << "请输入要入栈的元素（以-1结束）：";
            cout << "入栈元素：";
            while (true) {
                cin >> elem;

                if (elem == -1) {
                    cout << "入栈结束。" << endl;
                    break;
                }

                if (Push(linkedStack, elem)) {
                    cout << elem << " ";
                }
                else {
                    break;
                }
            }
            cout << endl;
            break;

        case 4:
            Pop(linkedStack, elem);
            break;

        case 5:
            cout << "程序退出。" << endl;
            break;

        default:
            cout << "无效的选择，请重新输入。" << endl;
        }

    } while (choice != 5);

    return 0;
}

C++

3.3队列的链式存储

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

// 定义循环队列的最大大小
#define MAXSIZE 6

// 定义循环队列
typedef struct {
    int data[MAXSIZE];
    int front;
    int rear;
} CircularQueue;

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

// 判断循环队列是否为空
bool IsEmpty(CircularQueue Q) {
    return Q.front == Q.rear;
}

// 判断循环队列是否已满
bool IsFull(CircularQueue Q) {
    return (Q.rear + 1) % MAXSIZE == Q.front;
}

// 入队操作
bool Enqueue(CircularQueue& Q, int elem) {
    if (IsFull(Q)) {
        cout << "队列已满，无法入队。" << endl;
        return false;
    }
   Q.data[Q.rear] = elem;
   Q.rear = (Q.rear + 1) % MAXSIZE; 
    return true;
}

// 出队操作
bool Dequeue(CircularQueue& Q, int& elem) {
    if (IsEmpty(Q)) {
        cout << "队列为空，无法出队。" << endl;
        return false;
    }

    elem = Q.data[Q.front];
    Q.front = (Q.front + 1) % MAXSIZE;
   

    cout << "出队元素：" << elem << endl;
    return true;
}

// 获取队头元素
bool GetFront(CircularQueue Q, int& elem) {
    if (IsEmpty(Q)) {
        cout << "队列为空，无法获取队头元素。" << endl;
        return false;
    }

    elem = Q.data[Q.front];
    cout << "队头元素为：" << elem << endl;
    return true;
}

// 显示菜单
void DisplayMenu() {
    cout << "===============菜单===============" << endl;
    cout << "1. 建队列" << endl;
    cout << "2. 取队头元素" << endl;
    cout << "3. 入队" << endl;
    cout << "4. 出队" << endl;
    cout << "5. 退出" << endl;
    cout << "===================================" << endl;
    cout << "请选择操作：";
}

int main() {
    // 循环队列
    CircularQueue circularQueue;
    InitQueue(circularQueue);

    int choice;
    int elem;

    do {  
        DisplayMenu();
        cin >> choice;

        switch (choice) {
        case 1:
            InitQueue(circularQueue);
            cout << "建队列成功。" << endl;
            break;

        case 2:
            GetFront(circularQueue, elem);
            break;

        case 3:
            cout << "请输入要入队的元素（以-1结束）：";
            cout << "入队元素：";
            while (true) {
                cin >> elem;

                if (elem == -1) {
                    cout << "入队结束。" << endl;
                    break;
                }

                if (Enqueue(circularQueue, elem)) {
                    cout << elem << " ";
                }
                else {
                    break;
                }
            }
            cout << endl;
            break;

        case 4:
            Dequeue(circularQueue, elem);
            break;

        case 5:
            cout << "程序退出。" << endl;
            break;

        default:
            cout << "无效的选择，请重新输入。" << endl;
        }

    } while (choice != 5);

    return 0;
}

C++

3.4队列的链式存储

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

// 定义链表节点
struct Node {
    int data;
    Node* next;
};

// 定义链式队列
typedef struct {
    Node* front;
    Node* rear;
} LinkedQueue;

// 初始化链式队列
void InitQueue(LinkedQueue& Q) {
    Q.front = Q.rear = nullptr;
}

// 判断链式队列是否为空
bool IsEmpty(LinkedQueue Q) {
    return Q.front == nullptr;
}

// 入队操作
bool Enqueue(LinkedQueue& Q, int elem) {
    Node* newNode = new Node;
    newNode->data = elem;
    newNode->next = nullptr;

    if (IsEmpty(Q)) {
        Q.front = Q.rear = newNode;
    }
    else {
        Q.rear->next = newNode;
        Q.rear = newNode;
    }

    return true;
}

// 出队操作
bool Dequeue(LinkedQueue& Q, int& elem) {
    if (IsEmpty(Q)) {
        cout << "队列为空，无法出队。" << endl;
        return false;
    }

    Node* temp = Q.front;
    elem = temp->data;

    Q.front = temp->next;
    delete temp;

    if (Q.front == nullptr) {
        Q.rear = nullptr; 
    }

    cout << "出队元素：" << elem << endl;
    return true;
}

// 获取队头元素
bool GetFront(LinkedQueue Q, int& elem) {
    if (IsEmpty(Q)) {
        cout << "队列为空，无法获取队头元素。" << endl;
        return false;
    }

    elem = Q.front->data;
    cout << "队头元素为：" << elem << endl;
    return true;
}

// 显示菜单
void DisplayMenu() {
    cout << "===============菜单===============" << endl;
    cout << "1. 建队列" << endl;
    cout << "2. 取队头元素" << endl;
    cout << "3. 入队" << endl;
    cout << "4. 出队" << endl;
    cout << "5. 退出" << endl;
    cout << "===================================" << endl;
    cout << "请选择操作：";
}

int main() {
    // 链式队列
    LinkedQueue linkedQueue;
    InitQueue(linkedQueue);

    int choice;
    int elem;

    do {
        DisplayMenu();
        cin >> choice;

        switch (choice) {
        case 1:
            InitQueue(linkedQueue);
            cout << "建队列成功。" << endl;
            break;

        case 2:
            GetFront(linkedQueue, elem);
            break;

        case 3:
            cout << "请输入要入队的元素（以-1结束）：";
            cout << "入队元素：";
            while (true) {
                cin >> elem;

                if (elem == -1) {
                    cout << "入队结束。" << endl;
                    break;
                }

                if (Enqueue(linkedQueue, elem)) {
                    cout << elem << " ";
                }
                else {
                    break;
                }
            }
            cout << endl;
            break;

        case 4:
            Dequeue(linkedQueue, elem);
            break;

        case 5:
            cout << "程序退出。" << endl;
            break;

        default:
            cout << "无效的选择，请重新输入。" << endl;
        }

    } while (choice != 5);

    return 0;
}

C++
数据结构-实验三
http://example.com/2024/02/05/实验三/
作者
yanhuigang
发布于
2024年2月5日
许可协议