2023秋数据结构平时实验题目和参考解答¶
第一次上机¶
使用数组实现一个字符串的栈¶
Description
请使用数组实现一个字符串的栈，最大容量为20。输出字符串逆序结果。
注意不要有不必要的输出，比如“请输入字符串”。
Input
一行字符串，长度可能大于最大容量。
Output
输入字符串的逆序输出。
Sample Input 1
HelloWorld!
Sample Output 1
!dlroWolleH
#include <iostream>
#include <cstring>
#include <math.h>
using namespace std;
class Stack {
private:
char stackArray[20];
int top;
public:
Stack():top(-1) {}
void push(char c) {
if (top < 19) {
top++;
stackArray[top] = c;
}
}
char pop() {
if (top >= 0) {
char c = stackArray[top];
top--;
return c;
} else {
return '\0';
}
}
bool isEmpty() const {
return (top == -1);
}
};
int main() {
Stack stack;
char input[66];
cin >> input;
for (int i=0; i < strlen(input); ++i)stack.push(input[i]);
while (!stack.isEmpty()) cout<< stack.pop();
return 0;
}
匹配括号¶
Description
输入一串字符串（长度不超过50），其中有普通的字符与括号组成（包括‘(’、‘)’、‘[’,']'）,要求验证括号是否匹配，如果匹配则输出0、否则输出1。
注意不要有不必要的输出，比如“请输入字符串”。
Input
一行字符串。
Output
一个整数表示答案。
Sample Input 1
dfa(sdf)df[dfds(dfd)]
Sample Output 1
0
#include <cstdio>
#include <vector>
using namespace std;
int main()
{
vector<char> container;
char c;
bool flag = true;
while ((c = getchar()) != EOF){
if (c == '(')
container.push_back(')');
else if (c == '[')
container.push_back(']');
else if ((c == ')') || (c == ']'))
{
if (container.back() != c)
{
flag = false;
break;
}
else
container.pop_back();
}
}
printf("%d\n", !(flag && container.empty()) );
return 0;
}
第二次上机¶
通用循环队列¶
Description
请实现一个通用的循环队列。大小上限为10。
向循环队列中插入一次数据，然后取出部分元素，之后再次插入数据。
Input
第1行输入数据类型。
第2行输入第一次插入循环队列的数据个数。
第3行第一次插入循环队列的数据。
第4行输入取出的元素个数。
第5行输入第二次插入循环队列的数据个数。
第6行输入第二次插入循环队列的数据。
Output
最终循环队列中的元素顺序输出。
Sample Input 1
int
6
1 2 3 4 5 6
4
5
7 8 9 10 11
Sample Output 1
5 6 7 8 9 10 11
Hint
浮点数输出忽略多余的0
#include <iostream>
#include <sstream>
template <typename T>
class CircularQueue {
public:
CircularQueue(int maxSize) : maxSize(maxSize), queue(new T[maxSize]), front(0), rear(-1), itemCount(0) {}
~CircularQueue() {
delete[] queue;
}
void insert(const T& data) {
if (itemCount == maxSize) {
// Queue is full, overwrite the front element
front = (front + 1) % maxSize;
}
rear = (rear + 1) % maxSize;
queue[rear] = data;
itemCount++;
}
void remove(int count) {
while (count-- > 0 && itemCount > 0) {
front = (front + 1) % maxSize;
itemCount--;
}
}
void display() {
int count = itemCount;
int index = front;
while (count-- > 0) {
std::cout << queue[index] << " ";
index = (index + 1) % maxSize;
}
std::cout << std::endl;
}
private:
T* queue;
int maxSize;
int front;
int rear;
int itemCount;
};
template <typename T>
void processQueue(CircularQueue<T>& circularQueue) {
int firstInsertCount, secondInsertCount, removeCount;
std::cin >> firstInsertCount;
for (int i = 0; i < firstInsertCount; ++i) {
T data;
std::cin >> data;
circularQueue.insert(data);
}
std::cin >> removeCount;
circularQueue.remove(removeCount);
std::cin >> secondInsertCount;
for (int i = 0; i < secondInsertCount; ++i) {
T data;
std::cin >> data;
circularQueue.insert(data);
}
circularQueue.display();
}
int main() {
std::string dataType;
std::cin >> dataType;
if (dataType == "int" || dataType == "double" || dataType == "float" || dataType == "char" || dataType == "long" || dataType == "short") {
std::istringstream iss(dataType);
if (dataType == "double") {
CircularQueue<double> circularQueue(10);
processQueue(circularQueue);
} else if (dataType == "float") {
CircularQueue<float> circularQueue(10);
processQueue(circularQueue);
} else if (dataType == "char") {
CircularQueue<char> circularQueue(10);
processQueue(circularQueue);
} else if (dataType == "long") {
CircularQueue<long> circularQueue(10);
processQueue(circularQueue);
} else if (dataType == "short") {
CircularQueue<short> circularQueue(10);
processQueue(circularQueue);
} else {
CircularQueue<int> circularQueue(10);
processQueue(circularQueue);
}
} else {
std::cout << "Unsupported data type." << std::endl;
}
return 0;
}
最近的相同字母¶
Description
使用队列寻找二维数组中曼哈顿距离最近的相同字母。
二维数组不大于6*6。
Input
第1行为2个整数，为二维数组的行数和列数。之后按行输入二维数组。
Output
曼哈顿距离最近的字母。
Sample Input 1
3 3
a b c
f e m
c b a
Sample Output 1
b
#include <queue>
#include <iostream>
#include <cmath>
using namespace std;
int n,m,ans,ans1;
int main(){
ans=666666;
cin>>n>>m;
queue<int>Q[26];
char tmp;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>tmp;
Q[tmp-'a'].push(i*m+j);
}
}
vector<int>P;
for(int i=0;i<26;i++)if(Q[i].size()>1)P.push_back(i);
int loc1,loc2,dis;
int loc1x,loc1y,loc2x,loc2y;
for(int i=0;i<P.size();i++){
int ch = P[i];
loc1=Q[ch].front();
Q[ch].pop();
while(!Q[ch].empty()){
loc2=Q[ch].front();
Q[ch].pop();
loc1x=loc1%m;loc1y=loc1/m;
loc2x=loc2%m;loc2y=loc2/m;
dis=abs(loc1x-loc2x)+abs(loc1y-loc2y);
if(dis<ans){
ans=dis;
ans1=ch;
}
loc1=loc2;
}
}
tmp='a'+ans1;
cout<<tmp;
return 0;
}
第三次上机¶
实现循环链表解决约瑟夫问题¶
Description
请使用循环链表解决约瑟夫问题。 约瑟夫问题为n个人围成一个圆圈，首先第1个人从1开始一个人一个人顺时针报数,报到第m个人，令其出列。然后再从下一个人开始，从1顺时针报数，报到第m个人，再令其出列，…，如此下去,直到圆圈中只剩一个人为止。此人即为优胜者。
Input
输入两个整数n和m，n为总人数，m为将被逐出的报数值。
Output
输出一个整数，为最后优胜者序号。
Sample Input 1
8 3
Sample Output 1
7
#include<iostream>
using namespace std;
struct Node {
Node *next;
Node();
int entry;
Node(int item, Node *add_on = NULL);
};
Node::Node( )
{
next = NULL;
}
Node::Node(int item, Node *add_on)
{
entry = item;
next = add_on;
}
enum Error_code{overflow,emptylist,notexist,notfound,success};
class LinkList{
public:
Error_code add(int &item);
Error_code remove(int &item);
Error_code find(int &item,Node *&res_node);
Error_code clear();
Error_code get_front(int &res);
int empty();
int size();
LinkList();
Node *get_next(Node *node);
private:
Node *head;
};
LinkList::LinkList()
{
head=new Node();
head->next=head;
}
Error_code LinkList::add(int &item)
{
Node *new_node = new Node (item, head->next);
if(new_node==NULL)
return overflow;
head->next=new_node;
return success;
}
Error_code LinkList::find(int &item,Node *&res_node)
{
res_node = NULL;
Node *cur=head->next;
while(cur!= head)
{
if(cur->entry==item)
{
res_node=cur;
return success;
}
cur=cur->next;
}
return notfound;
}
Error_code LinkList::remove(int &item)
{
Node *cur=head->next;
Node *prev=NULL;
if(cur==head)
return emptylist;
while(cur!=head)
{
if(cur->entry==item)
{
if(prev==NULL)
{
head->next=cur->next;
delete cur;
cur=NULL;
}
else
{
prev->next=cur->next;
delete cur;
cur=NULL;
}
return success;
}
prev=cur;
cur=cur->next;
}
return notfound;
}
Error_code LinkList::get_front(int &res)
{
if(empty())
{
return emptylist;
}
res=head->next->entry;
return success;
}
Error_code LinkList::clear()
{
Node *cur=head,*pre=NULL;
while(cur)
{
pre=cur;
cur=cur->next;
delete pre;
pre = NULL;
}
head=NULL;
return success ;
}
int LinkList::empty()
{
return (head->next==head);
}
int LinkList::size()
{
int res=0;
Node *cur=head->next;
while(cur!=head)
{
res++;
cur=cur->next;
}
return res;
}
Node *LinkList::get_next(Node *node)
{
if(empty())
{
return NULL;
}
if(node->next==head)
{
return node->next->next;
}
return node->next;
}
int main()
{
int n,m;
cin>>n>>m;
LinkList *ll=new LinkList();
while(n>0)
{
ll->add(n);
n--;
}
int i=1;
Node *cur;
ll->find(i,cur);
while(ll->size()!=1)
{
for(i=1;i<=m-1;i++)
{
cur=ll->get_next(cur);
}
Node *pre=cur;
cur=ll->get_next(cur);
ll->remove(pre->entry);
}
int res;
ll->get_front(res);
cout<<res<<endl;
return 0;
}
第四次上机¶
子集合问题¶
Description
请使用递归的方法，求出n个元素的集合中元素个数为m的子集合个数。
Input
第1行，2个整数，原集合大小n，子集合大小m。
第2行，n个整数，为子集合元素。
Output
输出所有子集合，子集合中元素顺序输出。
Sample Input 1
5 3
1 2 3 4 5
Sample Output 1
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
#include <iostream>
#include <vector>
using namespace std;
class Solution{
public:
int n;
int k;
int cnt_subset;
Solution() : cnt_subset(0) {}
void DFS(int start, int current_sum){
if (start == n)
{
if (current_sum == k)
++cnt_subset;
}
else
{
if (current_sum + 1 <= k)
DFS(start + 1, current_sum + 1);
else if (current_sum > k)
return;
DFS(start + 1, current_sum);
}
}
int num_subset(int n, int k){
this->n = n;
this->k = k;
DFS(0, 0);
return cnt_subset;
}
};
int main()
{
int n, k;
cin >> n >> k;
cout << Solution().num_subset(n, k) << endl;
return 0;
}
N皇后问题¶
Description
如何在N*N的棋盘上放置N枚棋子，使得任意两个棋子不出现在同一直线上？一共有多少种方法
Input
1个整数，放置棋子个数N
Output
1个整数，可能的放置方法个数。
Sample Input 1
8
Sample Output 1
92
#include <iostream>
#include <vector>
using namespace std;
#define MaxSize 32
class Solution{
public:
vector<int> place;
int n;
int cnt_solution;
Solution(): cnt_solution(0)
{
place.reserve(MaxSize);
}
bool able_place(int row, int col)
{
for (int i = 0; i < row; ++i)
{
if (place[i] == col || abs(place[i] - col) == row - i)
return false;
}
return true;
}
void DFS(int row)
{
if (row == n)
{
++cnt_solution;
}
else
{
for (int col = 0; col < n; ++col)
{
if (able_place(row, col))
{
place[row] = col;
DFS(row + 1);
}
}
}
}
int eight_queen(int n)
{
this->n = n;
DFS(0);
return cnt_solution;
}
};
int main()
{
int n;
cin >> n;
cout << Solution().eight_queen(n) << endl;
return 0;
}
求链表最小值¶
Description
请使用递归的方法，求出int链表中最小值。
Input
第1行1个整数，表示链表中元素个数N。
第2行N个整数，为链表中元素值。
Output
1个整数，为链表中最小值。
Sample Input 1
5
1 2 3 4 5
Sample Output 1
1
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
int findMin(ListNode* head) {
if (head == NULL) {
return 66666666;
}
int minOfRest = findMin(head->next);
return min(head->val, minOfRest);
}
int main() {
int N;
cin >> N;
ListNode* head = NULL;
ListNode* tail = NULL;
for (int i = 0; i < N; ++i) {
int value;
cin >> value;
ListNode* newNode = new ListNode(value);
if (head == NULL) {
head = newNode;
tail = newNode;
} else {
tail->next = newNode;
tail = newNode;
}
}
int result = findMin(head);
cout << result << endl;
while (head != NULL) {
ListNode* temp = head;
head = head->next;
delete temp;
}
return 0;
}
第五次上机¶
迷宫问题¶
Description
请解决迷宫问题，并打印出一条从入口到出口的路径。
前进方向：按照下-右-上-左的顺序。
用使用DFS解答该题。
Input
前8行输入一个8*8的int二维数组，其中0表示通路，1表示墙。
第9行输入入口坐标。
第10行输入出口坐标。
Output
输出8*8int二维数组，其中2表示路径，1表示墙，0表示未经过的点。
Sample Input 1
0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 0 0 1 1 0 0
0 1 1 1 0 0 0 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 0
0 1 1 1 0 1 1 0
1 1 0 0 0 0 0 0
0 0
0 7
Sample Output 1
2 0 1 0 0 0 1 2
2 0 1 0 0 0 1 2
2 0 0 0 1 1 0 2
2 1 1 1 0 0 0 2
2 2 2 1 0 0 0 2
0 1 2 2 2 1 0 2
0 1 1 1 2 1 1 2
1 1 0 0 2 2 2 2
#include <iostream>
#include <vector>
using namespace std;
const int rows = 8;
const int cols = 8;
// 定义迷宫和路径的二维数组
int maze[rows][cols];
int path[rows][cols];
// 定义四个方向的偏移量：下、右、上、左
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
// DFS函数
bool dfs(int x, int y, int ex, int ey) {
// 如果当前位置是出口，返回true
if (x == ex && y == ey) {
path[x][y] = 2; // 标记出口为路径
return true;
}
// 遍历四个方向
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
// 判断新位置是否合法
if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && maze[nx][ny] == 0 && path[nx][ny] == 0) {
path[x][y] = 2; // 标记当前位置为路径
if (dfs(nx, ny, ex, ey)) {
return true;
}
path[x][y] = 0; // 如果未找到路径，回溯，将当前位置重新标记为未经过
}
}
return false;
}
int main() {
// 读取迷宫和入口、出口坐标
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
cin >> maze[i][j];
if(maze[i][j]==1)path[i][j]=1;
else path[i][j] = 0; // 初始化路径数组
}
}
int sx, sy, ex, ey;
cin >> sx >> sy >> ex >> ey;
// 调用DFS函数
dfs(sx, sy, ex, ey);
// 输出路径
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
cout << path[i][j] << " ";
}
cout << endl;
}
return 0;
}
滑雪问题¶
Description
Michael喜欢滑雪这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。
Input
输入的第一行表示区域的行数n和列数m(1 <= n,m <= 100)。下面是n行，每行有m个整数，代表高度h，0<=h<=10000。 Output
输出最长区域的长度。
Sample Input
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
Sample Output
25
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_N = 100;
int grid[MAX_N][MAX_N];
int dp[MAX_N][MAX_N];
int rows, cols;
// 定义四个方向的偏移量：上、下、左、右
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
// 递归实现动态规划
int dfs(int x, int y) {
if (dp[x][y] != -1) {
return dp[x][y];
}
dp[x][y] = 1; // 初始化当前点的最长底滑坡为1
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] < grid[x][y]) {
dp[x][y] = max(dp[x][y], 1 + dfs(nx, ny));
}
}
return dp[x][y];
}
int main() {
// 读取输入
cin >> rows >> cols;
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
cin >> grid[i][j];
}
}
// 初始化dp数组
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
dp[i][j] = -1;
}
}
int maxLen = 0;
// 遍历每个点，以其为起点进行dfs
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
maxLen = max(maxLen, dfs(i, j));
}
}
cout << maxLen << endl;
return 0;
}