2021秋数据结构平时实验题目和参考解答¶
括号匹配¶
Description
输入一串字符串，其中有普通的字符与括号组成（包括‘（’、‘）’、‘[’,']'）,要求验证括号是否匹配，如果匹配则输出0、否则输出1.
Input 字符串长度<=100
Output 验证括号是否匹配，如果匹配则输出0、否则输出1.
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)
{
// printf("c = %c\n", c);
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
寻找最近的相同字母位置
Input
输入:第一行输入字母矩阵的大小 m * n.
第二行输入要查找的字母坐标.
之后输入 m * n 个字母.
m < 10, n < 10.
Output 输出: 距离查找字母最近的相同字母坐标.(坐标从(0,0) 开始)
找不到输出-1 -1
Sample Input 1
3 2 1 1 q w a x x a Sample Output 1
2 0
#include <cstdlib>
#include <deque>
#include <iostream>
using namespace std;
struct Point
{
int x;
int y;
char data;
Point(int x, int y, char data) : x(x), y(y), data(data) {}
};
Point *find_nearest(int src_x, int src_y, char **matrix, int row, int col)
{
bool visited[row][col] = {0};
deque<Point *> q;
char key = matrix[src_x][src_y];
q.push_back(new Point(src_x, src_y, matrix[src_x][src_y]));
visited[src_x][src_y] = true;
while (!q.empty())
{
Point *pt = q.front();
for (int i = pt->x - 1; i <= pt->x + 1; ++i)
{
for (int j = pt->y - 1; j <= pt->y + 1; ++j)
{
if (!visited[i][j])
{
visited[i][j] = true;
if (i != 0 && i != row - 1 && j != 0 && j != col - 1)
{
char elem = matrix[i][j];
Point *ptr_point = new Point(i, j, elem);
if (elem == key)
// 这里有个问题，deque里面存放的指向堆的指针并没有被释放
return ptr_point;
q.push_back(ptr_point);
}
}
}
}
delete q.front();
q.pop_front();
}
return NULL;
}
int main()
{
int row, col, x, y;
cin >> row >> col;
char **matrix = (char **)malloc(sizeof(char *) * (row + 2));
for (int i = 0; i < row + 2; ++i)
matrix[i] = (char *)calloc(col + 2, sizeof(char));
cin >> x >> y;
for (int i = 1; i < row + 1; ++i)
{
for (int j = 1; j < col + 1; ++j)
cin >> matrix[i][j];
}
Point *ptr_point = find_nearest(x + 1, y + 1, matrix, row + 2, col + 2);
if (ptr_point)
cout << ptr_point->x - 1 << " " << ptr_point->y - 1;
else
cout << "-1 -1";
return 0;
}
LifeGame¶
题目描述
生命游戏在一个 \(6 \times 6\) 的网格上进行，每个格子有"活"或"死"两种状态。每个格子有 8 个相邻格子（上下左右及对角线）。
演化规则如下：
- 活细胞：若相邻活细胞数 \(\leq 1\) 或 \(\geq 4\)，则死亡；否则存活
- 死细胞：若相邻活细胞数恰好为 \(3\)，则复活；否则保持死亡
给定初始状态和演化次数，求最终状态。
输入
第一行三个整数：演化次数 \(times\)，初始活细胞的行号 \(row\)，列号 \(col\)
随后若干行，每行两个整数表示一个活细胞的行列坐标，以 -1 -1 结束
数据范围： \(1 \leq times \leq 100\)，\(1 \leq row, col \leq 6\)
输出
\(6\) 行，每行 \(6\) 个整数（0 或 1），表示最终状态，整数间空格分隔
样例输入
2 2 2
2 3
3 2
3 3
-1 -1
样例输出
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 1 0 0
0 0 1 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0
注：代码中 numOfNeighbor 函数有 bug，循环条件 j <= col - 1 应为 j <= col + 1
#include <cstdio>
#include <cstring>
#define MAXROW 6
#define MAXCOL 6
class Life
{
private:
bool grid[MAXROW + 2][MAXCOL + 2];
bool isAlive(int row, int col)
{
return grid[row][col];
}
void setDeath(int row, int col)
{
grid[row][col] = 0;
}
int numOfNeighbor(int row, int col)
{
int num = 0;
for (int i = row - 1; i <= row + 1; i++)
{
for (int j = col - 1; j <= col - 1; j++)
num += grid[i][j];
}
if (isAlive(row, col))
num--;
return num;
}
public:
Life()
{
memset(grid, 0, sizeof(grid));
}
void setAlive(int row, int col)
{
grid[row][col] = 1;
}
void updateState()
{
for (int i = 1; i <= MAXROW; i++)
{
for (int j = 1; j <= MAXCOL; j++)
{
int num = numOfNeighbor(i, j);
if (isAlive(i, j))
{
if (num <= 1)
setDeath(i, j);
else if (num >= 4)
setDeath(i, j);
}
else if (num == 3)
setAlive(i, j);
}
}
}
void printState()
{
for (int i = 1; i <= MAXROW; i++)
{
printf("%d", grid[i][1]);
for (int j = 2; j <= MAXCOL; j++)
printf(" %d", grid[i][j]);
printf("\n");
}
}
};
int main()
{
Life l;
int times, row, col;
scanf("%d %d %d", ×, &row, &col);
while ((row != -1) || (col != -1))
{
l.setAlive(row, col);
scanf("%d %d", &row, &col);
}
for (int i = 0; i < times; ++i)
l.updateState();
l.printState();
return 0;
}
合并升序列表¶
题目描述
给定两个升序排列的单链表，请将它们合并为一个新的升序链表并输出。
新链表由两个链表中的所有节点组成，且保持升序排列。
输入
输入共两行：
- 第一行：一个正整数 \(m\)，表示第一个链表的长度，随后在同一行输入 \(m\) 个升序排列的整数
- 第二行：一个正整数 \(n\)，表示第二个链表的长度，随后在同一行输入 \(n\) 个升序排列的整数
数据范围：
- \(1 \leq m, n \leq 1000\)
- \(-10^4 \leq \text{节点值} \leq 10^4\)
输出
输出一行，为合并后的升序链表，各元素之间用空格分隔。
样例输入
4 1 3 5 7
3 2 4 6
样例输出
1 2 3 4 5 6 7
样例解释
将链表 1 → 3 → 5 → 7 与链表 2 → 4 → 6 合并后，得到升序链表 1 → 2 → 3 → 4 → 5 → 6 → 7。
#include <iostream>
using namespace std;
struct LinkNode
{
LinkNode *next;
int data;
LinkNode() : next(nullptr) {}
LinkNode(int x) : next(nullptr), data(x) {}
};
struct List
{
LinkNode *head;
LinkNode *tail;
List()
{
LinkNode *dummy_header = new LinkNode();
head = dummy_header;
tail = dummy_header;
}
void push_back(int x)
{
tail->next = new LinkNode(x);
tail = tail->next;
}
void print_list()
{
for (auto p = head->next; p != nullptr; p = p->next)
cout << p->data << " ";
cout << endl;
}
void merge(List l1, List l2)
{
LinkNode *p1 = l1.head->next;
LinkNode *p2 = l2.head->next;
while ((p1 != nullptr) && (p2 != nullptr))
{
if (p1->data < p2->data)
{
this->push_back(p1->data);
p1 = p1->next;
}
else
{
this->push_back(p2->data);
p2 = p2->next;
}
}
while (p1 != nullptr)
{
this->push_back(p1->data);
p1 = p1->next;
}
while (p2 != nullptr)
{
this->push_back(p2->data);
p2 = p2->next;
}
}
};
int main()
{
List l1, l2, l3;
int m, n;
cin >> m;
for (int i = 0; i < m; ++i)
{
int x;
cin >> x;
l1.push_back(x);
}
cin >> n;
for (int i = 0; i < n; ++i)
{
int x;
cin >> x;
l2.push_back(x);
}
l3.merge(l1, l2);
l3.print_list();
return 0;
}
八皇后问题拓展¶
如何在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)
{
// cout << "row = " << row << endl;
// for (int i = 0; i < row; ++i)
// cout << place[i] << " ";
// cout << endl;
if (row == n)
{
++cnt_solution;
if (cnt_solution <= 3)
{
cout << place[0] + 1;
for (int i = 1; i < row; ++i)
cout << " " << place[i] + 1;
cout << endl;
}
}
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
请使用递归的方法，求出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;
}
其他题目¶
1. 单链表的实现¶
题目描述¶
实现一个单链表，支持以下操作：
- add x：在链表头部插入元素 x
- remove x：删除链表中第一个值为 x 的节点
- find x：查找链表中是否存在值为 x 的节点
- clear：清空链表
输入¶
第一行一个整数 N，表示操作次数。
随后 N 行，每行一个操作命令。
输出¶
对于每个 find 操作，若找到输出 1，否则输出 0。
最后，若链表为空输出 empty linklist，否则输出链表中所有元素（从头到尾）。
样例输入¶
5 add 3 add 5 find 3 remove 3 find 3
样例输出¶
1 0 5
代码¶
#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);
Error_code clear();
int empty();
void print();
LinkList();
private:
Node *head;
};
LinkList::LinkList()
{
head=NULL;
}
Error_code LinkList::add(int &item)
{
Node *new_node = new Node (item, head);
if(new_node==NULL)return overflow;
head=new_node;
return success;
}
Error_code LinkList::find(int &item)
{
if(head==NULL)
{
return emptylist;
}
Node *cur=head;
while(cur!=NULL)
{
if(cur->entry==item)
{
return success;
}
cur=cur->next;
}
return notexist;
}
Error_code LinkList::remove(int &item)
{
if(head==NULL)
{
return emptylist;
}
Node *pre=NULL,*cur=head;
while(cur!=NULL)
{
if(cur->entry==item)
{
if(pre==NULL)
{
head=head->next;
}
else
{
pre->next=cur->next;
}
delete cur;
cur=NULL;
return success;
}
pre=cur;
cur=cur->next;
}
return notexist;
}
Error_code LinkList::clear()
{
Node *cur=head,*pre=cur;
while(cur)
{
pre=cur;
cur=cur->next;
delete pre;
pre = NULL;
}
head=NULL;
}
int LinkList::empty()
{
if(head==NULL)
return 1;
return 0;
}
void LinkList::print()
{
if(empty())
{
return;
}
Node *cur= head;
while(cur->next)
{
cout<<cur->entry<<" ";
cur=cur->next;
}
cout<<cur->entry;
}
int main()
{
int N;
cin>>N;
string op;
int num;
Error_code err[100];
int count[100]={0};
LinkList *ll=new LinkList();
int i;
for(i=0;i<N;i++)
{
cin>>op;
if(op=="add")
{
cin>>num;
ll->add(num);
}
else if(op=="remove")
{
cin>>num;
ll->remove(num);
}
else if(op=="find")
{
cin>>num;
count[i]=1;
err[i]=ll->find(num);
}
else if(op=="clear")
{
ll->clear();
}
}
for(i=0;i<N;i++)
{
if(count[i]!=0)
{
if(err[i]==success)
{
cout<<"1"<<endl;
}
else
{
cout<<"0"<<endl;
}
}
}
if(ll->empty())
{
cout<<"empty linklist"<<endl;
}
else
{
ll->print();
}
return 0;
}
2. 岛屿数量¶
题目描述¶
给定一个 m × n 的二维网格，网格由 1（陆地）和 0（水）组成。计算网格中岛屿的数量。
岛屿总是被水包围，且每座岛屿只能由水平和垂直方向上相邻的陆地连接形成。
输入¶
第一行两个整数 m 和 n，表示网格的行数和列数。
随后 m 行，每行 n 个整数（0 或 1），表示网格。
输出¶
输出一个整数，表示岛屿的数量。
样例输入¶
4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
样例输出¶
3
代码¶
#include<bits/stdc++.h>
using namespace std;
struct Islands{
public:
Islands(int m,int n);
int result;
void dfs(int a[15][15],int x,int y);
bool isisland(int a[15][15],int x,int y);
void solve(int a[15][15]);
private:
int array[100][100];
int row;
int col;
};
Islands::Islands(int m,int n)
{
row=m;
col=n;
result=0;
}
void Islands::solve(int a[15][15])
{
for(int i=0;i<row;i++)
for(int j=0;j<col;j++){
if(a[i][j]==1){
result++;
dfs(a,i,j);
}
}
}
void Islands::dfs(int a[15][15],int x,int y)
{
a[x][y]=0;
if(x==row-1&&y==col-1)
return ;
if(x-1>=0 && a[x-1][y]==1)
dfs(a,x-1,y);
if(x+1<row && a[x+1][y]==1)
dfs(a,x+1,y);
if(y-1>=0 && a[x][y-1]==1)
dfs(a,x,y-1);
if(y+1<col && a[x][y+1]==1)
dfs(a,x,y+1);
}
int main()
{
int m,n;
cin>>m>>n;
int array[15][15];
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
cin>>array[i][j];
}
}
Islands island(m,n);
island.solve(array);
cout<<island.result;
return 0;
}
3. 高精度乘法¶
题目描述¶
给定两个正整数（可能非常大，超出普通整型范围），计算它们的乘积。
输入¶
两行，每行一个正整数。
输出¶
输出两个数的乘积。
样例输入¶
123456789
987654321
样例输出¶
121932631112635269
代码¶
#include<bits/stdc++.h>
using namespace std;
struct Node
{
char Num;
Node *Prev,*Next;
};
class BigInteger
{
Node *Head,*End,*TempNode;
void AddHead(char Num);
void AddEnd(char Num);
public:
BigInteger();
BigInteger(const BigInteger &BigNum);
void GetNumber();
void disp();
BigInteger operator + (const BigInteger &BigNum);
BigInteger operator * (const BigInteger &BigNum);
BigInteger operator = (const BigInteger &BigNum);
~BigInteger();
};
BigInteger::BigInteger()
{
Head=End=TempNode=NULL;
}
BigInteger::BigInteger(const BigInteger &BigNum)
{
Node *p;
Head=End=TempNode=NULL;
p=BigNum.Head;
while(p)
{
AddEnd(p->Num);
p=p->Next;
}
}
BigInteger::~BigInteger()
{
Node *NextNode;
if(Head==NULL)
return;
TempNode=Head;
while(TempNode)
{
NextNode=TempNode->Next;
delete TempNode;
TempNode=NextNode;
}
Head=NULL;
End=NULL;
TempNode=NULL;
}
void BigInteger::AddHead(char Num)
{
TempNode=new Node;
TempNode->Num=Num;
TempNode->Prev=NULL;
if(!Head)
{
Head=End=TempNode;
TempNode->Next=NULL;
}
else
{
TempNode->Next=Head;
Head->Prev=TempNode;
Head=TempNode;
}
}
void BigInteger::AddEnd(char Num)
{
TempNode=new Node;
TempNode->Num=Num;
TempNode->Next=NULL;
if(!Head)
{
Head=End=TempNode;
TempNode->Prev=NULL;
}
else
{
TempNode->Prev=End;
End->Next=TempNode;
End=TempNode;
}
}
void BigInteger::GetNumber()
{
char key;
int count=0,num=0;
while((key=getchar())!=10)
{
if(key>='0' && key<='9')
{
num=key-'0';
AddEnd(num);
num=0;
}
}
}
BigInteger BigInteger::operator + (const BigInteger &BigNum2)
{
BigInteger &BigNum1=*this,result;
Node *temp1,*temp2;
int TempNum,rest=0;
temp1=BigNum1.End;
temp2=BigNum2.End;
while(temp1 && temp2)
{
TempNum=int(temp1->Num)+int(temp2->Num)+rest;
if(TempNum>9)
{
TempNum=TempNum-10;
rest=1;
}
else
rest=0;
result.AddHead(char(TempNum));
temp1=temp1->Prev;
temp2=temp2->Prev;
}
if(temp2)temp1=temp2;
while(temp1)
{
int(TempNum)=int(temp1->Num)+rest;
if(TempNum>9)
{
TempNum=TempNum-10;
rest=1;
}
else
rest=0;
result.AddHead(char(TempNum));
temp1=temp1->Prev;
}
if(rest)
result.AddHead(char(rest));
return result;
}
BigInteger BigInteger::operator * (const BigInteger &BigNum2)
{
BigInteger &BigNum1=*this,temp,result;
Node *temp1,*temp2,*tempa,*tempb;
int TempNum,rest,i=0,rest2;
temp1=BigNum1.End;
temp2=BigNum2.End;
while(temp2)
{
rest=0;
while(temp1!=NULL)
{
TempNum=int(temp1->Num)*int(temp2->Num)+rest;
if(TempNum>9)
{
rest=TempNum/10;
TempNum=TempNum%10;
}
else
rest=0;
temp.AddHead(char(TempNum));
temp1=temp1->Prev;
}
if(rest!=0)temp.AddHead(char(rest));
for(int k=i;k>=1;k--)temp.AddEnd(char(0));
i++;
temp1=BigNum1.End;
temp2=temp2->Prev;
tempa=result.End;
if(result.Head!=NULL)
{
result.End=temp.Head;
result.Head=NULL;
}
tempb=temp.End;
rest2=0;
while(tempa!=NULL && tempb!=NULL)
{
TempNum=int(tempa->Num)+int(tempb->Num)+rest2;
if(TempNum>9)
{
TempNum=TempNum-10;
rest2=1;
}
else
rest2=0;
result.AddHead(char(TempNum));
tempa=tempa->Prev;
tempb=tempb->Prev;
}
if(tempb)tempa=tempb;
while(tempa)
{
int(TempNum)=int(tempa->Num)+rest2;
if(TempNum>9)
{
TempNum=TempNum-10;
rest2=1;
}
else
rest2=0;
result.AddHead(char(TempNum));
tempa=tempa->Prev;
}
if(rest2)
result.AddHead(char(rest2));
if(temp.Head!=NULL)
{
temp.End=temp.Head;
temp.Head=NULL;
}
tempb=NULL;
}
return result;
}
BigInteger BigInteger::operator = (const BigInteger &BigNum)
{
if(this==&BigNum)
return *this;
Node *p;
TempNode=Head=End=NULL;
p=BigNum.Head;
while(p)
{
AddEnd(p->Num);
p=p->Next;
}
return *this;
}
void BigInteger::disp()
{
if(Head)
{
cout<<int(Head->Num);
TempNode=Head->Next;
}
else return;
while(TempNode)
{
cout<<int(TempNode->Num);
TempNode=TempNode->Next;
}
cout<<endl;
}
int main()
{
BigInteger BigNum1,BigNum2,BigNum3;
BigNum1.GetNumber();
BigNum2.GetNumber();
BigNum3=BigNum1*BigNum2;
BigNum3.disp();
return 0;
}
4. 高精度加法¶
题目描述¶
给定两个正整数（可能非常大，超出普通整型范围），计算它们的和。
输入¶
一行，两个正整数，用空格分隔。
输出¶
输出两个数的和。
样例输入¶
999999999999999999 1
样例输出¶
1000000000000000000
代码¶
#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int ans[1000010];
int a[1000010],b[1000010];
int main(){
cin>>s1>>s2;
int len1=s1.size(),len2=s2.size();
for(int j=0,i=len1-1;i>=0;i--){
a[j++]=s1[i]-'0';
}
for(int j=0,i=len2-1;i>=0;i--){
b[j++]=s2[i]-'0';
}
int carry=0;
int len=0;
for(int i=0;i<max(len1,len2);i++){
int t=a[i]+b[i]+carry;
ans[len++]=t%10;
carry=t/10;
}
if(carry!=0){
ans[len++]=carry;
}
for(int i=len-1;i>=0;i--){
cout<<ans[i];
}
return 0;
}
5. 合并两个升序列表¶
题目描述¶
给定两个升序排列的单链表，请将它们合并为一个新的升序链表并输出。
输入¶
第一行一个整数 N，表示第一个链表的长度，随后在同一行输入 N 个升序排列的整数。
第二行一个整数 M，表示第二个链表的长度，随后在同一行输入 M 个升序排列的整数。
输出¶
输出合并后的升序链表，各元素之间用空格分隔。
样例输入¶
4 1 3 5 7
3 2 4 6
样例输出¶
1 2 3 4 5 6 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);
int empty();
void print();
LinkList();
Node *head;
};
LinkList::LinkList()
{
head=new Node(-1,NULL);
}
Error_code LinkList::add(int &item)
{
Node *p=head;
while(p->next!=NULL)
{
p=p->next;
}
Node *new_node = new Node (item, NULL);
p->next=new_node;
return success;
}
int LinkList::empty()
{
if(head==NULL)
return 1;
return 0;
}
void LinkList::print()
{
if(empty())
{
return;
}
Node *cur= head->next;
while(cur->next)
{
cout<<cur->entry<<" ";
cur=cur->next;
}
cout<<cur->entry;
}
int main()
{
int N,M;
cin>>N;
int number;
LinkList *L1=new LinkList();
LinkList *L2=new LinkList();
LinkList *L3=new LinkList();
for(int i=0;i<N;i++)
{
cin>>number;
L1->add(number);
}
cin>>M;
for(int i=0;i<M;i++)
{
cin>>number;
L2->add(number);
}
Node *p1=L1->head->next,*p2=L2->head->next;
while(p1!=NULL&&p2!=NULL)
{
Node *pr;
if(p1->entry>=p2->entry) pr=p2;
if(p2->entry>p1->entry) pr=p1;
L3->add(pr->entry);
if(pr->entry==p1->entry)
{
p1=p1->next;
}
else
{
p2=p2->next;
}
}
if(p1==NULL)
{
while(p2!=NULL)
{
L3->add(p2->entry);
p2=p2->next;
}
}
if(p2==NULL)
{
while(p1!=NULL)
{
L3->add(p1->entry);
p1=p1->next;
}
}
L3->print();
return 0;
}
6. 螺旋方阵¶
题目描述¶
输入一个正整数 N，生成一个 N × N 的螺旋方阵。螺旋方阵从左上角开始，按照顺时针螺旋方向依次填入 1 到 N² 的数字。
输入¶
一个正整数 N（N ≤ 10）。
输出¶
N 行，每行 N 个整数，表示螺旋方阵，整数间用空格分隔。
样例输入¶
4
样例输出¶
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7
代码¶
#include<stdio.h>
#define SIZE 10
void Helix(int a[][SIZE],int n,int turn)
{
int i,j;
static int num=1;
i=turn;
for(j=turn;j<n;j++){
if(a[i][j]==0){
a[i][j]=num;
num++;
}
}
j=n-1-turn;
for(i=turn+1;i<n;i++){
if(a[i][j]==0){
a[i][j]=num;
num++;
}
}
i=n-1-turn;
for(j=n-2-turn;j>=turn;j--){
if(a[i][j]==0){
a[i][j]=num;
num++;
}
}
j=turn;
for(i=n-1-turn;i>=turn;i--){
if(a[i][j]==0){
a[i][j]=num;
num++;
}
}
if(num>n*n){
return;
}
turn++;
Helix(a,n,turn);
}
int main(void)
{
int N,k,p,cot=0;
scanf("%d",&N);
int arr[N][N];
for(k=0;k<N;k++){
for(p=0;p<N;p++){
arr[k][p]=0;
}
}
Helix(arr,N,0);
for(k=0;k<N;k++){
cot=0;
for(p=0;p<N;p++){
cot++;
printf("%d",arr[k][p]);
printf(" ");
if(cot==N){
printf("\n");
}
}
}
return 0;
}
7. 模拟栈¶
题目描述¶
实现一个栈，支持以下操作：
- push c：将字符 c 压入栈中
- pop：弹出栈顶元素
执行完所有操作后，依次输出栈中剩余的元素（从栈顶到栈底）。
输入¶
第一行一个整数 k，表示操作次数。
随后 k 行，每行一个操作。
输出¶
输出栈中剩余的元素，用空格分隔。
样例输入¶
5
push a
push b
push c
pop
push d
样例输出¶
d b a
代码¶
#include<iostream>
#include<cstring>
enum Error_code{underflow,overflow,success};
const int maxstack = 10;
class MyStack{
public:
MyStack();
bool empty();
Error_code top(char &item);
Error_code pop();
Error_code push(char &item);
private:
int count;
char entry[maxstack];
};
MyStack::MyStack(){
count=0;
memset(entry,0,sizeof(entry));
}
bool MyStack::empty()
{
bool outcome=true;
if(count>0)
{
outcome=false;
}
return outcome;
}
Error_code MyStack::pop(){
if(count==0){
return underflow;
}
count--;
return success;
}
Error_code MyStack::top(char &item){
if(count==0){
return underflow;
}
item = entry[count-1];
return success;
}
Error_code MyStack::push(char &item){
if(count>=maxstack){
return overflow;
}
entry[count++]=item;
return success;
}
using namespace std;
int main(){
MyStack stack;
int k;
cin>>k;
for(int i=0;i<k;i++){
string s;
cin>>s;
if(s=="push"){
char c;
cin>>c;
stack.push(c);
}
else {
stack.pop();
}
}
char tmp;
while(!stack.empty()){
stack.top(tmp);
cout<<tmp<<" ";
stack.pop();
}
return 0;
}
8. 实现队列¶
题目描述¶
实现一个循环队列，支持入队操作。队列最大容量为 8。
输入 N 个整数依次入队。若 N > 8，先输出 This queue is overflow!，然后只输出队列中的前 8 个元素；否则输出队列中所有元素。
输入¶
第一行一个整数 N，随后同一行输入 N 个整数。
输出¶
队列中的元素，用空格分隔。
样例输入¶
5 1 2 3 4 5
样例输出¶
1 2 3 4 5
代码¶
#include<bits/stdc++.h>
using namespace std;
enum Error_code{underflow, overflow, success};
const int maxqueue = 8;
class CirQueue {
public:
CirQueue();
bool empty() ;
Error_code serve();
Error_code append(int &item);
Error_code retrieve(int &item);
bool full();
int size() ;
void clear();
Error_code serve_and_retrieve(int &item);
private:
int count;
int front, rear;
int entry[maxqueue];
};
CirQueue::CirQueue()
{
count = 0;
rear = maxqueue - 1;
front = 0;
}
bool CirQueue::empty()
{
return count == 0;
}
Error_code CirQueue::append(int &item)
{
if (count >= maxqueue) return overflow;
count++;
rear = ((rear + 1) == maxqueue) ? 0 : (rear + 1);
entry[rear] = item;
return success;
}
Error_code CirQueue::serve()
{
if (count <= 0) return underflow;
count--;
front = ((front + 1) == maxqueue) ? 0 : (front + 1);
return success;
}
Error_code CirQueue::retrieve(int &item)
{
if (count <= 0) return underflow;
item = entry[front];
return success;
}
int CirQueue::size()
{
return count;
}
bool CirQueue::full()
{
return count==maxqueue;
}
void CirQueue::clear()
{
count = 0;
rear = maxqueue-1;
front = 0;
}
Error_code CirQueue::serve_and_retrieve(int &item)
{
if (count <= 0) return underflow;
item = entry[front];
count--;
front = ((front + 1) == maxqueue) ? 0 : (front + 1);
return success;;
}
int main()
{
CirQueue C;
int N;
cin>>N;
int j;
int number;
for(int i=0;i<N;i++)
{
cin>>number;
C.append(number);
}
if(N>8)
{
cout<<"This queue is overflow!"<<endl;
while(!C.empty())
{
int t;
C.serve_and_retrieve(t);
cout<<t;
j++;
if(j!=8)
cout<<" ";
}
}
else{
while(!C.empty())
{
int t;
C.serve_and_retrieve(t);
cout<<t<<" ";
}
}
return 0;
}
9. 寻找相同的字母位置¶
题目描述¶
给定一个 m × n 的字符矩阵，以及矩阵中的一个起始位置 (x, y)。使用广度优先搜索（BFS），找到矩阵中与起始位置字符相同的另一个位置。按照上下左右的顺序搜索。
输入¶
第一行两个整数 m 和 n，表示矩阵的行数和列数。
第二行两个整数 x 和 y，表示起始位置。
随后 m 行，每行 n 个字符，表示矩阵。
输出¶
输出找到的相同字符的位置坐标，用空格分隔。若未找到，输出 -1 -1。
样例输入¶
3 4
0 0
a b c d
e a f g
h i j k
样例输出¶
1 1
代码¶
#include<bits/stdc++.h>
using namespace std;
const int maxqueue=8;
enum Error_code{overflow,underflow,success};
struct Pos{
int x;
int y;
};
class Queue{
public:
Queue();
bool empty();
Error_code serve();
Error_code retrieve(Pos &item);
Error_code append(Pos &item);
bool full()
{
return count==maxqueue;
}
Error_code serve_and_retrieve(Pos &item);
private:
int count,rear,front;
Pos entry[maxqueue];
};
Queue::Queue()
{
count=0;
front=0;
rear=maxqueue-1;
memset(entry,0,sizeof(entry));
}
Error_code Queue::append(Pos &item)
{
if(count>=maxqueue)
{
return overflow;
}
else
{
count++;
rear=((rear+1)==maxqueue)? 0:(rear+1);
entry[rear]=item;
return success;
}
}
bool Queue::empty()
{
return count==0;
}
Error_code Queue::serve()
{
if(empty())
return underflow;
count--;
front=((front+1)==maxqueue)? 0:(front+1);
return success;
}
Error_code Queue::serve_and_retrieve(Pos &item)
{
if(empty())
return underflow;
item=entry[front];
count--;
front=((front+1)==maxqueue)? 0:(front+1);
return success;
}
Error_code Queue::retrieve(Pos &item)
{
if(empty())
return underflow;
item=entry[front];
count--;
front=((front+1)==maxqueue)? 0:(front+1);
return success;
}
const int maxrow=10,maxcol=10;
int main()
{
char mat[maxrow][maxcol];
Queue numbers;
int m,n;
cin>>m>>n;
int x,y;
cin>>x>>y;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
cin>>mat[i][j];
}
}
int mask[maxrow][maxcol];
memset(mask,0,sizeof(mask));
char target=mat[x][y];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
mask[x][y]=1;
Pos res={-1,-1};
Pos number={x,y};
numbers.append(number);
while(!numbers.empty())
{
Pos tmp;
numbers.serve_and_retrieve(tmp);
if(mat[tmp.x][tmp.y]==target&&!(tmp.x==x&&tmp.y==y))
{
res.x=tmp.x;
res.y=tmp.y;
break;
}
for(int i=0;i<4;i++)
{
int new_x=tmp.x+dx[i];
int new_y=tmp.y+dy[i];
Pos temp={new_x,new_y};
if(new_y>=0&&new_x>=0&&new_y<n&&new_x<m&&mask[new_x][new_y]==0)
{
numbers.append(temp);
mask[new_x][new_y]=1;
}
}
}
cout<<res.x<<" "<<res.y;
return 0;
}
10. 字符串出入栈¶
题目描述¶
输入 n 个字符，依次压入栈中，然后依次弹出并输出，实现字符的逆序输出。
输入¶
第一行一个整数 n，表示字符个数。
第二行 n 个字符。
输出¶
逆序输出这 n 个字符，用空格分隔。
样例输入¶
5
a b c d e
样例输出¶
e d c b a
代码¶
#include <iostream>
using namespace std;
enum Error_code
{
underflow,overflow,success
};
const int maxstack=100;
class Mystack
{
public:
Mystack();
bool empty();
Error_code push(char &item);
Error_code pop();
Error_code top(char &item);
private:
int count;
char entry[maxstack];
};
Mystack::Mystack()
{
count=0;
}
bool Mystack::empty()
{
bool outcome=true;
if(count>0)
{
outcome=false;
}
return outcome;
}
Error_code Mystack::push(char &item)
{
Error_code outcome=success;
if(count>=maxstack)
{
outcome=overflow;
}
else
{
entry[count++]=item;
}
return outcome;
}
Error_code Mystack::pop()
{
Error_code outcome=success;
if(count==0)
{
outcome=underflow;
}
else
{
--count;
}
return outcome;
}
Error_code Mystack::top(char &item)
{
Error_code outcome=success;
if(count==0)
{
outcome=underflow;
}
else
{
item=entry[count-1];
}
return outcome;
}
int main()
{
int n;
char item;
Mystack strings;
cout << " Type in an integer n followed by n characters." << endl
<< " The characters will be printed in reverse order." << endl;
cin >> n;
int i=0;
for(i=0;i<n;i++)
{
cin >> item;
strings.push(item);
}
cout << endl << endl;
while(!strings.empty())
{
strings.top(item);
cout << item << " ";
strings.pop();
}
cout << endl;
return 0;
}