7-1 阅览室
题目：
天梯图书阅览室请你编写一个简单的图书借阅统计程序。当读者借书时，管理员输入书号并按下S键，程序开始计时；当读者还书时，管理员输入书号并按下E键，程序结束计时。书号为不超过1000的正整数。当管理员将0作为书号输入时，表示一天工作结束，你的程序应输出当天的读者借书次数和平均阅读时间。
注意：由于线路偶尔会有故障，可能出现不完整的纪录，即只有S没有E，或者只有E没有S的纪录，系统应能自动忽略这种无效纪录。另外，题目保证书号是书的唯一标识，同一本书在任何时间区间内只可能被一位读者借阅。
代码：
1 #include<bits/stdc++.h>
2 using namespace std;
3 int main()
4 {
5 int a, b, book, ans = 0, k = 0, day;
6 char se[5];
7 map<int,int> m;
8 cin >> day;
9 while(day)
10 {
11 scanf("%d", &book);
12 scanf("%s%d:%d", &se, &a, &b);
13 if(book > 0)
14 {
15 if(se[0] == 'S')
16 m[book] = a * 60 + b;
17 else if(se[0] == 'E')
18 {
19 if(m.find(book) != m.end())
20 {
21 ans += a * 60 + b - m[book];
22 k++;
23 m.erase(book);
24 }
25 }
26 }
27 else
28 {
29 if(k != 0)
30 cout << k << " " << (int)(1.0 * ans / k + 0.5) << endl;
31 else
32 cout << "0 0" << endl;
33 k = 0;
34 ans = 0;
35 m.clear();
36 day--;
37 }
38 }
39 return 0;
40 }
View Code
思路：就是用map数组进行操作，而且进行时间操作的时候记得全部转换为分钟进行计算，也就是小时记得乘以60
注意：第一次用struct做的wa掉的点是同一本书被借多次，有不匹配，所以在用数组进行循环遍历的时候，排除多余的S或者E的时候是错的
7-9 树的遍历
题目：给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
代码：
1 #include<stdio.h>
2 #include<string.h>
3 #include<queue>
4 #include<stdlib.h>
5 #include<iostream>
6 using namespace std;
7 int btree[100]={0};//用于承装后续遍历的数字
8 int ctree[100]={0};//用于承装中序遍历的数据
9 struct node
10 {
11 node *l;
12 node *r;
13 int data;
14 };
15
16 int num=0;
17 int n;
18 node *creattree(int btree[],int ctree[],int n)//反向推算创建二叉树，注意这是指针
19 {
20 if(n<=0) return NULL;
21 node *T=new node();
22 int root=btree[n-1];//找到根节点
23 int k;
24 T->data=root;//创建树的节点
25 for(int i=0;i<n;i++)//由于中序遍历使两边分开
26 {
27 if(ctree[i]==root)
28 {
29 k=i;
30 break;
31 }
32 }
33 T->l=creattree(btree,ctree,k);//左子树
34 T->r=creattree(btree+k,ctree+k+1,n-(k+1));//右子树
35 return T;
36 }
37 void print(node *T)//层次遍历输出二叉树
38 {
39 node *p;//为中间变量
40 node *pr[100];
41 int rear=-1,front=-1;
42 rear++;
43 pr[rear]=T;//将根节点放入到队列之中
44 while(rear!=front)
45 {
46 front++;
47 p=pr[front];//用来读取数据
48 cout<<p->data;
49 num++;//用来控制空格的输出，最后一位不用空格
50 if(num<n)
51 cout<<" ";
52 if(p->l!=NULL)
53 {
54 rear++;
55 pr[rear]=p->l;
56 }
57 if(p->r!=NULL)
58 {
59 rear++;
60 pr[rear]=p->r;
61 }
62 }
63 }
64 //个人理解，rear是用来存取数据的，而front是跟着屁股后面来输出的
65 int main()
66 {
67 int N;
68 int j,k,l;
69 cin>>N;
70 n=N;
71 for(j=0;j<N;j++)
72 {
73 cin>>btree[j];
74 }
75 for(j=0;j<N;j++)
76 {
77 cin>>ctree[j];
78 }
79 node *T=creattree(btree,ctree,n);
80 print(T);
81 return 0;
82
83 }
View Code
思路：可以多看看数据结构树上的描写进行想，然后用指针，结构体进行理解，暂时还没有理解，但想先存下来然后记记板子
7-10 关于堆的判断
将一系列给定数字顺序插入一个初始为空的小顶堆H[]。随后判断一系列相关命题是否为真。命题分下列几种：
-
x is the root：x是根结点； -
x and y are siblings：x和y是兄弟结点； -
x is the parent of y：x是y的父结点； -
x is a child of y：x是y的一个子结点。
题目：
代码：
1 #include<iostream>
2 #include<cmath>
3 #include<cstring>
4 #include<string>
5 #include<cstdio>
6 #include<algorithm>
7 #include<set>
8 #include<queue>
9 #include<stack>
10 #define MAX_VERTS 500
11 using namespace std;
12 int num[10000] = {0};
13 void createHael(int len){
14 for(int i = len/2-1; i >= 0; i--){
15 if(num[i]>num[2*i+1]){
16 int temp = num[i];
17 num[i] = num[2*i+1];
18 num[2*i+1] = temp;
19 if(2*(2*i+1)+1<len&&num[2*i+1]>num[2*(2*i+1)+1]||2*(2*i+1)+2<len&&num[2*i+1]>num[2*(2*i+1)+2]){
20 createHael(len);
21 }
22 }
23 if(num[i]>num[2*i+2]){
24 int temp = num[i];
25 num[i] = num[2*i+2];
26 num[2*i+2] = temp;
27 if(2*(2*i+2)+1<len&&num[2*i+2]>num[2*(2*i+2)+1]||2*(2*i+2)+2<len&&num[2*i+2]>num[2*(2*i+2)+2]){
28 createHael(len);
29 }
30 }
31 // for(int j = 0; j < len; j++){
32 // cout << num[j] << " ";
33 // }
34 // cout << endl;
35 }
36 }
37
38 int find(int t,int n){
39 for(int i = 0; i < n; i++){
40 if(num[i]==t){
41 return i;
42 }
43 }
44 }
45 int main(){
46 int n, m, a, b;
47 string s1,s2,s3,s4,s5,s6;
48 cin >> n >> m;
49 for(int i = 0; i < n; i++){
50 cin >> num[i];
51 createHael(i);
52 }
53
54 for(int i = 0; i < m; i++){
55 cin >> a >> s1;
56 if(s1=="and"){
57 cin >> b >> s2 >> s3;
58 if(ceil(find(a,n)*1.0/2)-1==ceil(find(b,n)*1.0/2)-1){
59 cout << "T" << endl;
60 }else{
61 cout << "F" << endl;
62 }
63 }else{
64 cin >> s2;
65 if(s2=="a"){
66 cin >> s3 >> s4 >> b;
67 if(ceil(find(a,n)*1.0/2)-1==find(b,n)){
68 cout << "T" << endl;
69 }else{
70 cout << "F" << endl;
71 }
72 }else{
73 cin >> s3;
74 if(s3=="root"){
75 if(find(a,n)==0){
76 cout << "T" << endl;
77 }else{
78 cout << "F" << endl;
79 }
80 }else{
81 cin >> s4 >> b;
82 if(ceil(find(b,n)*1.0/2)-1==find(a,n)){
83 cout << "T" << endl;
84 }else{
85 cout << "F" << endl;
86 }
87 }
88 }
89 }
90 }
91 return 0;
92 }
View Code
思路:先理解小根堆是什么，然后用二叉树下标的关系，用本下标i和i/2进行比较，多次进行比较，直到不能比较，或者本来就是这个位置最大