一、矩阵对角线元素
求矩阵对角线元素之和。
输入格式
第一行包含整数N,表示数组行数和列数。
接下来N行,每行包含N个整数X。
输出格式
输出矩阵对角线元素之和。
数据范围
$1≤N≤1000$
$1≤X≤10000000$
输入样例
3
1 2 3
4 5 6
7 8 9
输出样例
30
代码
#include <iostream>
using namespace std;
typedef long long LL; // 定义长整型别名 LL
int main()
{
// 输入方阵的大小
int n;
cin >> n;
// 初始化变量以存储对角线元素之和
LL s = 0;
// 遍历矩阵的行
for (int i = 0; i < n; i ++)
{
// 遍历矩阵的列
for (int j = 0; j < n; j ++)
{
int x;
cin >> x;
// 如果元素在主对角线(i == j)或反对角线(i + j == n - 1),则将其加到总和中
if (i == j) s += x;
if (i + j == n - 1) s += x;
}
}
// 输出对角线元素之和
cout << s << endl;
return 0;
}
二、统计字符个数
输入一个字符串,分别统计该字符串中出现的数字字符个数,字母字符个数和其他类型字符个数。
输入格式
输入一行,表示一个字符串。注意字符串中可能包含空格。
输出格式
输出一行,共三个整数,分别表示字符串中出现的数字字符个数,字母字符个数和其他类型字符个数,用空格隔开。
数据范围
$1≤字符串长度≤1000$
输入样例
I love XJTU! 123
输出样例
3 9 4
代码
#include <iostream>
using namespace std;
int main()
{
string s;
getline(cin, s); // 从标准输入读取一行字符串
int digit = 0, letter = 0, other = 0;
// 遍历字符串中的每个字符
for (char c : s)
{
if (c >= '0' && c <= '9') digit ++; // 如果字符是数字,数字个数加一
else if (c >= 'A' && c <= 'Z' || c >= 'a' && c <= 'z') letter ++; // 如果字符是字母,字母个数加一
else other ++; // 否则,其他字符个数加一
}
// 输出统计结果
printf("%d %d %d\n", digit, letter, other);
return 0;
}
三、单链表
统计单链表中的节点的值等于给定值x的节点数。
#include <iostream>
using namespace std;
// 定义单链表节点结构
struct Node {
int val;
Node* next;
Node(int x) : val(x), next(nullptr) {}
};
// 统计值等于 x 的节点个数的函数
int countNodesWithValue(Node* head, int x) {
int count = 0;
for (Node *p = head; p; p = p->next)
if (p->val == x)
count ++;
return count;
}
// 主函数
int main() {
// 构建一个简单的单链表
Node* head = new Node(1);
head->next = new Node(2);
head->next->next = new Node(3);
head->next->next->next = new Node(2);
head->next->next->next->next = new Node(4);
// 给定值 x
int x = 2;
// 调用函数统计节点数
int result = countNodesWithValue(head, x);
printf("单链表:");
for (Node *p = head; p; p = p->next)
cout << p->val << ' ';
cout << endl;
// 输出结果
cout << "节点值等于 " << x << " 的节点数: " << result << endl;
return 0;
}
第三题的改编,请大家自行查漏补缺,不作为重点讲解
统计单链表中的节点的值等于给定值x的节点数。
要求:
- 写出单链表的节点定义。
- 用四种方式生成单链表(头插法、尾插法、带虚拟头节点的头插法、带虚拟头节点的尾插法)
输入格式
输入共2行,第一行有2个整数,分别为单链表长度n和给定值x。
第二行有n个整数,为单链表的节点值。
输出格式
输出一行,表示单链表中的节点的值等于给定值x的节点数。
数据范围
$1≤n≤100000$
$0≤x≤1000000$
输入样例一
6 3
3 2 2 3 6 1
输出样例一
2
输入样例二
10 5
1 2 3 4 5 6 7 8 9 10
输出样例二
1
结构体定义
两种完整写法:
struct ListNode
{
int val;
ListNode *next;
ListNode() : val(0), next(NULL) {}
ListNode(int x) : val(x), next(NULL) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
struct ListNode
{
int val;
ListNode *next;
ListNode()
{
}
ListNode(int x)
{
val = x;
next = NULL;
}
ListNode(int x, ListNode *_next)
{
val = x;
next = _next;
}
};
考试这样写就可以:
struct ListNode
{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
- val 表示节点的值
- next 表示指向下一个节点的指针
- ListNode(int x) 定义了节点的构造函数,初始化 val 为 x, next 为 NULL
基本的单链表操作有:
- 创建新节点:
ListNode* node = new ListNode(1);
- 添加节点:
node->next = new ListNode(2);
- 遍历链表:
ListNode* curr = head;
while(curr != NULL)
{
// ...
curr = curr->next;
}
for (ListNode *p = head; p; p = p->next)
{
// ...
}
- 删除节点:
node->next = node->next->next;
- 获取值:
int val = node->val;
- 判断是否为空:
if (node == NULL)
{
// 为空
}
完整代码
- 头插法
#include <iostream>
using namespace std;
struct ListNode
{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
int main()
{
int n, x;
ListNode *head = new ListNode(-1);
cin >> n >> x;
while (n--)
{
int t;
cin >> t;
// 头插法
if (head->val == -1) head->val = t;
else
{
ListNode *node = new ListNode(t);
node->next = head;
head = node;
}
}
int res = 0;
for (ListNode *p = head; p; p = p->next)
if (p->val == x)
res ++;
cout << res << endl;
return 0;
}
- 带虚拟头节点的头插法
#include <iostream>
using namespace std;
struct ListNode
{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
int main()
{
int n, x;
ListNode *dummy = new ListNode(-1);
cin >> n >> x;
while (n--)
{
int t;
cin >> t;
// 带虚拟头节点的头插法
ListNode *node = new ListNode(t);
node->next = dummy->next;
dummy->next = node;
}
int res = 0;
for (ListNode *p = dummy->next; p; p = p->next)
if (p->val == x)
res ++;
cout << res << endl;
return 0;
}
- 尾插法
#include <iostream>
using namespace std;
struct ListNode
{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
int main()
{
int n, x;
ListNode *head = new ListNode(-1), *tail = head;
cin >> n >> x;
while (n--)
{
int t;
cin >> t;
// 尾插法
if (head->val == -1) head->val = t;
else
{
ListNode *node = new ListNode(t);
tail->next = node;
tail = node;
}
}
int res = 0;
for (ListNode *p = head; p; p = p->next)
if (p->val == x)
res ++;
cout << res << endl;
return 0;
}
- 带虚拟头节点的尾插法
#include <iostream>
using namespace std;
struct ListNode
{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
int main()
{
int n, x;
ListNode *dummy = new ListNode(-1), *tail = dummy;
cin >> n >> x;
while (n--)
{
int t;
cin >> t;
// 带虚拟头节点的尾插法
ListNode *node = new ListNode(t);
tail->next = node;
tail = node;
}
int res = 0;
for (ListNode *p = dummy->next; p; p = p->next)
if (p->val == x)
res ++;
cout << res << endl;
return 0;
}
四、候选人投票
候选人得票的统计程序,设有$m$个选举人,$n$个候选人,输入一个得票的候选人的名字,要求输出每个候选人的得票结果。
#include <iostream>
#include <cstring>
using namespace std;
const int M = 3, N = 4;
struct Candidate
{
char name[20];
int s; // 票数
} can[N];
int main()
{
for (int i = 0; i < N; i ++)
{
cout << "请输入一个候选人的名字:";
cin >> can[i].name;
}
for (int i = 0; i < M; i ++)
{
cout << "请输入一个得票的候选人的名字:";
char str[20];
cin >> str;
for (Candidate &c : can)
if (!strcmp(c.name, str))
{
c.s ++;
puts("投票成功!");
break;
}
}
puts("投票结果如下:");
for (Candidate &c : can)
printf("候选人姓名:%s, 得票数:%d\n", c.name, c.s);
return 0;
}