Catalog
  1. 1. 问题描述
    1. 1.1. 1.第一次实验的顺序实现
    2. 1.2. 2.顺序栈的实现
    3. 1.3. 3.N个元素的序列的所有出栈可能
    4. 1.4. 1.第一次实验
    5. 1.5. 2.顺序栈的实现
    6. 1.6. 3.所有出栈可能
    7. 1.7. 运行界面
      1. 1.7.1. 顺序栈的实现
      2. 1.7.2. 所有出栈可能
数据结构实验二

问题描述

1.第一次实验的顺序实现

2.顺序栈的实现

3.N个元素的序列的所有出栈可能

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
#include<iostream>
#include<cstdio>
#include<algorithm>

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define ElemType int
using namespace std;

typedef struct {
ElemType *elem;
int length;
int listsize;
}SqList;

void InitList_Sq(SqList &L)
{
L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
L.length = 0;
L.listsize = LIST_INIT_SIZE;
return;
}
int InputList_Sq(SqList &L)
{
ElemType n, temp;
ElemType *p, *q;
printf("请输入集合的元素个数:\n");
cin >> n;
if (n < 1 || n > L.listsize) {
printf("输入有误\n");
return 0;
}
if (L.length + n >= L.listsize) {
L.elem = (ElemType*)realloc(L.elem, (L.length + n - L.listsize + LISTINCREMENT) * sizeof(ElemType));
L.listsize += (L.length + n - L.listsize + LISTINCREMENT);
}
printf("请输入元素:");
for (int i = 0; i < n; i++) {
cin >> temp;
q = &(L.elem[i]);
*q = temp;
++L.length;
}
return 1;
}
void MergeList_Sq(SqList La, SqList Lb, SqList &Lc)
{
ElemType *pa, *pb, *pc, *pa_last, *pb_last;
pa = La.elem;
pb = Lb.elem;
Lc.listsize = Lc.length = La.length + Lb.length;
pc = Lc.elem = (ElemType*)malloc(Lc.listsize * sizeof(ElemType));
pa_last = La.elem + La.length - 1;
pb_last = Lb.elem + Lb.length - 1;
while (pa <= pa_last && pb <= pb_last) {
if (*pa < *pb)
*pc++ = *pa++;
else
*pc++ = *pb++;
}
while (pa <= pa_last)*pc++ = *pa++;
while (pb <= pb_last)*pc++ = *pb++;
return;
}
void Show_Sq(SqList L, char name)
{
int cnt = 0;
printf("集合%c中的元素为:",name);
for (int i = 0; i < L.length; i++) {
if (L.elem[i] != L.elem[i + 1]) {
cout << L.elem[i] << " ";
cnt++;
}
}
printf("去重后的元素个数为:%d\n", cnt);
return;
}

int main()
{
SqList La, Lb, Lc;
InitList_Sq(La);
InitList_Sq(Lb);
InitList_Sq(Lc);
InputList_Sq(La);
InputList_Sq(Lb);
sort(La.elem, La.elem + La.length);
sort(Lb.elem, Lb.elem + Lb.length);
Show_Sq(La,'A');
Show_Sq(Lb,'B');
MergeList_Sq(La, Lb, Lc);
Show_Sq(Lc,'C');

return 0;
}

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
#include<iostream>
#include<cstdio>

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define SElemType int

using namespace std;

typedef struct {
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;

void InitStack(SqStack &S)
{
S.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return;
}

int GetTop(SqStack S, SElemType &e)
{
if (S.top == S.base)
return 0;
e = *(S.top - 1);
return 1;
}

void Push(SqStack &S, SElemType &e)
{
if (S.top - S.base >= S.stacksize) {
S.base = (SElemType*)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e;
return;
}

int Pop(SqStack &S, SElemType &e)
{
if (S.top == S.base)
return 0;
e = *--S.top;
return 1;
}
void Show(SqStack S)
{
printf("栈中现有元素为: |");
for (auto it = S.base; it < S.top; it++)
cout << *it << " ";
printf("\n");
return;
}

int main()
{
int p;
SElemType x;
SqStack S;
InitStack(S);
while (1) {
printf("请选择您要进行的操作(1代表Push 2代表Pop 0代表退出) :");
scanf("%d", &p);
if (p == 1) {
printf("请输入要压入栈中的元素:");
cin >> x;
Push(S, x);
Show(S);
}
else if (p == 2) {
SElemType e = 0;
if (Pop(S, e)) {
printf("出栈元素为:");
cout << e << endl;
Show(S);
}
else
printf("栈中没有元素\n");
}
else {
Show(S);
break;
}
}
return 0;
}

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
#include<iostream>
#include<cstdio>

using namespace std;

int total, res, sta, n;
int r[2005], s[2005];

void dfs(int m) {
if (m == n + 1) { //若所有元素都入过栈,输出当前出栈序列
total++;
for (int i = 1; i <= res; i++)
cout << r[i] << ' ';
for (int i = sta; i > 0; i--)
cout << s[i] << ' ';
cout << endl;
return;
}
if (sta > 0) {
r[++res] = s[sta];
sta--;
dfs(m); //栈顶元素出栈
s[++sta] = r[res];
res--; //回溯操作
}
s[++sta] = m; //当前元素入栈
dfs(m + 1);
sta--; //回溯操作
}
int main() {
printf("请输入元素个数:");
scanf("%d", &n);
total = 0; res = 0; sta = 0;
dfs(1);
printf("共有%d种情况", total);
return 0;
}

运行界面

sy

顺序栈的实现

sy

所有出栈可能

sy

Author: Christopher Shen
Link: https://www.pasxsenger.com/2019/09/23/数据结构实验二/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Donate
  • 微信
  • 支付寶