数据结构第二次上机代码

发表于 更新于 分类于 ， 阅读次数： Waline： 本文字数： 8.1k 阅读时长 ≈ 7 分钟
vs2015 c++环境 进制转换 汉诺塔 括号匹配 舞伴
报告
# 进制转换

简易版本：不考虑了负数 输入要大于0 进制数不要大于10

高级版本（点击）：报告上交后发出 可以负数 任意进制

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
#include<stdio.h>
#include<stdlib.h>
#define OK 1 //通过
#define ERROR 0 //错误 
#define OVERFLOW -2 //堆栈溢出
#define MAXSIZE 50 //容量 
typedef int Status; //函数类型,其值为状态码
typedef int ElemType; //抽象数据类型
					   //顺序结构储存
typedef struct
{
	ElemType* base;
	ElemType* top;
	int stacksize;
}SqStack;
typedef enum
{
	f, t
}Bool;
//初始化
Status initStack(SqStack* S)
{
	S->base = new ElemType[MAXSIZE];
	if (!S->base)
	{
		exit(OVERFLOW);
	}
	S->top = S->base;
	S->stacksize = MAXSIZE;
	return OK;
}
//判空
Bool isEmpty(SqStack* S)
{
	return S->base == S->top ? t : f;
}
//长度
int getLength(SqStack* S)
{
	return S->top - S->base;
}
//入栈
Status pushElem(SqStack* S, ElemType e)
{
	if (getLength(S) == S->stacksize)return ERROR;
	*(S->top) = e;
	S->top++;
	return OK;
}
//出栈
ElemType popElem(SqStack* S)
{
	if (isEmpty(S))return NULL;
	S->top--;
	return *(S->top);
}
//取栈顶
ElemType getTop(SqStack* S)
{
	if (!isEmpty(S))return *(S->top - 1);
	return NULL;
}
//进制转换
Status conversion(int n, int k)
{
	SqStack* S = new SqStack;
	initStack(S);
	while (n)
	{
		pushElem(S, n%k);
		n = n / k;
	}
	while (!isEmpty(S))
	{
		printf("%d", popElem(S));
	}
	return OK;
}
int main(void)
{
	int n=0, k = 0;
	while (!(n > 0))
	{
		printf("请输入需要转换的数(大于0)： ");
		scanf_s("%d", &n);
	}
	while (!(k>=2))
	{
		printf("请输入进制数（例如 2且大于2）");
		scanf_s("%d", &k);
	}
	conversion(n, k);
	printf("\n");
	system("pause");
	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
#include<stdio.h>
#include<stdlib.h>
void hanoi(int n, char A, char B, char C)
{
	if (n==1)
	{
		printf("%c -> %c\n", A, C);
	}
	else
	{
		hanoi(n - 1, A, C, B);
		printf("%c -> %c\n", A, C);
		hanoi(n - 1, B, A, C);
	}
}
int main(void)
{
	int n = 0;
	while (!(n > 0))
	{
		printf("请输入汉罗塔层数的数(大于0)： ");
		scanf_s("%d", &n);
	}
	hanoi(n, 'A', 'B', 'C');
	system("pause");
}

括号匹配

逻辑和书差不多 不过改了一些 暂时不能细说 改进版本(点击)

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
156
157
158
159
160
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
#define OK 1 //通过
#define ERROR 0 //错误 
#define OVERFLOW -2 //堆栈溢出
#define MAXSIZE 50 //容量 
typedef int Status; //函数类型,其值为状态码
typedef char ElemType; //抽象数据类型
//顺序结构储存
typedef struct
{
	ElemType* base;
	ElemType* top;
	int stacksize;
}SqStack;
typedef enum
{
	f, t
}Bool;
//初始化
Status initStack(SqStack* S)
{
	S->base = new ElemType[MAXSIZE];
	if (!S->base)
	{
		exit(OVERFLOW);
	}
	S->top = S->base;
	S->stacksize = MAXSIZE;
	return OK;
}
//判空
Bool isEmpty(SqStack* S)
{
	return S->base == S->top ? t : f;
}
//长度
int getLength(SqStack* S)
{
	return S->top - S->base;
}
//入栈
Status pushElem(SqStack* S, ElemType e)
{
	if (getLength(S) == S->stacksize)return ERROR;
	*(S->top) = e;
	S->top++;
	return OK;
}
//出栈
ElemType popElem(SqStack* S)
{
	if (isEmpty(S))return NULL;
	S->top--;
	return *(S->top);
}
//取栈顶
ElemType getTop(SqStack* S)
{
	if (!isEmpty(S))return *(S->top - 1);
	return NULL;
}
//清空栈
Status cleanStack(SqStack* S)
{
	S->top = S->base;
	return OK;
}
//匹配括号
Status matchBrackets(SqStack* S)
{
	bool flag = true;
	char ch;
	int i = 1;
	cout << "请输入英文状态下的括号，可复制 (){}[]，以#结束" << endl;
	cin >> ch;
	while (ch!='#'&&flag)
	{
		switch (ch)
		{
		case '(':
		case '{':
		case '[':
			pushElem(S, ch);
			break;
		case ')':
			if (!isEmpty(S)&&getTop(S)=='(')
			{
				popElem(S);
			}
			else
			{
				flag = false;
				cout << ch<<"输入错误，匹配"<<i <<" ( 失败" << endl;
			}
			break;
		case '}':
			if (!isEmpty(S) && getTop(S) == '{')
			{
				popElem(S);
			}
			else
			{
				flag = false;
				cout << ch << "输入错误，匹配" << i << " { 失败" << endl;
			}
			break;
		case ']':
			if (!isEmpty(S) && getTop(S) == '[')
			{
				popElem(S);
			}
			else
			{
				flag = false;
				cout << ch << "输入错误，匹配" << i << " ] 失败" << endl;
			}
			break;
		case '#':
			break;
		case '\n':
			 break;
		default:
			flag = false;
			cout << ch;
			cout << "输入非法内容\n";
			break;
		}
		++i;
		cin >> ch;
	}
	if (isEmpty(S) && flag)
	{
		cout << "匹配成功" << endl;
		return OK;
	}
	else
	{
		cout << "匹配失败" << endl;
		cleanStack(S); return ERROR;
	}
	
}
int main(void)
{
	SqStack* S = new SqStack;
    initStack(S);
	matchBrackets(S);//演示一排输入
	cout << "第二次匹配" << endl;
	matchBrackets(S);//演示一次输一个
	cout << "第三次匹配" << endl;
	matchBrackets(S);//演示括号匹配错误
	cout << "第四次匹配" << endl;
	matchBrackets(S);//演示输入错误内容
	printf("\n");
	system("pause");
	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
#include <iostream>
#include <fstream> //定义读写已命名文件的类型
#include <vector>
#include <sstream> //多定义的类型则用于读写存储在内存中的string对象
using namespace std;
#include<stdio.h>
#include<stdlib.h>
#define OK 1 //通过
#define ERROR 0 //错误 
#define OVERFLOW -2 //堆栈溢出
#define MAXSIZE 50 //容量 
typedef int Status; //函数类型,其值为状态码
typedef string ElemType; //抽象数据类型
 //循环队列
typedef struct
{
	ElemType* base;
	int front;
	int rear;
}SqQueue;
typedef enum
{
	f, t
}Bool;
//初始化
Status initQueue(SqQueue* Q)
{
	Q->base = new ElemType[MAXSIZE];
	if (!Q->base)
	{
		return OVERFLOW;
	}
	Q->front = Q->rear = 0;
	return OK;
}
//判空
Bool isEmpty(SqQueue* Q)
{
	return Q->front == Q->rear ? t : f;
}
//长度
int getLength(SqQueue* Q)
{
	return (Q->rear - Q->front + MAXSIZE) % MAXSIZE;
}
//是否满
Bool isFull(SqQueue* Q)
{
	return (Q->rear + 1) % MAXSIZE == Q->front ? t : f;
}
//入队 
Status enQueue(SqQueue* Q, ElemType e)
{
	if (isFull(Q))
	{
		return ERROR;
	}
	Q->base[Q->rear] = e;
	Q->rear = (Q->rear + 1) % MAXSIZE;
	return OK;
}
//出队
ElemType deQueue(SqQueue* Q)
{
	if (isEmpty(Q))return ERROR;
	ElemType e = Q->base[Q->front];
	Q->front = (Q->front + 1) % MAXSIZE;
	return e;
}
//取队头
ElemType getHead(SqQueue* Q)
{
	if (!isEmpty(Q))return Q->base[Q->front];
	return NULL;
}
int main()
{
	
	//读文件  
	ifstream inFile("D:\\桌面\\舞伴.csv", ios::in);//inFile来自fstream,ifstream为输入文件流(从文件读入)
	string lineStr;
	vector<vector<string>> strArray;
	while (getline(inFile, lineStr)) //getline来自sstream
	{
		//存成二维表结构
		stringstream ss(lineStr);//来自sstream
		string str;
		vector<string> lineArray;
		//按照逗号分隔
		while (getline(ss, str, ','))
			lineArray.push_back(str);//一行数据以vector
		strArray.push_back(lineArray);//每一行vector数据都放到strArray中去
	}
	//输出结果
	for (int i = 0; i<strArray.size(); i++)
	{
		for (int j = 0; j<strArray[i].size(); j++)
			cout << strArray[i][j] << "\t";
		cout << endl;
	} 
	SqQueue* QM = new SqQueue; initQueue(QM);
	SqQueue* QW = new SqQueue; initQueue(QW);
	for (int i = 0; i<strArray.size(); i++)
	{
		for (int j = 0; j<strArray[i].size()-1 ; j++)
		{ 
			if ("男"== strArray[i][j+1])
			{
				enQueue(QM, strArray[i][j]);
			}
			else if ("女" == strArray[i][j + 1])
			{
				enQueue(QW, strArray[i][j]);
			}	
		}
	}
	int k = 1;
	while ((!isEmpty(QM))&&(!isEmpty(QW)))
	{
		cout << k << deQueue(QM) << "    和\t" << deQueue(QW) << " 跳舞" << endl; k++;
	}
	if (isEmpty(QM))
	{
		cout << getHead(QW) << " 等待下一次匹配" << endl;
	}
	if (isEmpty(QW))
	{
		cout << getHead(QM) << " 等待下一次匹配" << endl;
	}
	system("pause");
	return 0;
}