BUAA数据结构期中考试2023

BUAA数据结构期中考试2023

1. 密码对应表

题目

问题描述

有一种加密方法为：其使用一个字符串（可以含重复字母，字符个数不超过50）作为密钥。例如：若密钥字符串为Fea25Ther，则需 要先将大写字母转换成小写字母，并去掉密钥单词中的非字母及重复字母得到单词串feathr，然后将其反序，最后将字母表中的其 它字母以反序追加到后面：

加密字母的对应关系如下：

编写程序根据输入的密钥，生成相应的密码对应表串。

输入形式

从标准输入读入密钥字符串（字符个数不超过50，其中可包含空白符或其它非字母字符），末尾有换行符（不属于密钥字符串）。

输出形式

先向控制台输出原字母表，然后在下一行输出生成的对应密码表。

样例输入

Fea25Ther

样例输出

abcdefghijklmnopqrstuvwxyz

rhtaefzyxwvusqponmlkjigdcb

样例说明

输入的密钥字符串为Fea25Ther，先将大写字母转换成小写字母，并去掉密钥单词中的非字母及重复字母得到单词串feathr，然后将 其反序，最后将字母表中的其它字母以反序追加到后面，便得到密码表。

评分标准

该题要求生成密码对应表，提交程序名为：key.c。

问题分析

本题几乎是第二次作业第三题的原题，甚至比原题还要简单——没有涉及文件的输入输出操作。此处相比原题只有了两处变动：

1. 输入的可能不是字母，所以我们只需要在读的时候针对字符串的每一位都判断一下是否是字母再操作。
2. 可能有大写字母，我们要把它转化成小写字母。
3. 先要对处理完的字符串逆序

由于基本是原题，此处不再给出具体分析过程，所有思路都蕴含在注释中。

完整代码

#include <stdio.h>
#include <string.h>
# include <ctype.h>char secret_key [27];  // 加密对应表int main()
{char org_word[55] = {0};  // 最开始读取的秘钥gets(org_word);int already_used[26] = {0};  // 记录哪些积木已经被用过了（字母1-26编号）int count = 0;for(int i = 0; org_word[i]; i++){if (isalpha(org_word[i])){  // 判断当前位置是否是字母org_word[i] = tolower(org_word[i]);  // 是字母，转化成小写形式if(!already_used[org_word[i] - 'a']){  // 没被用过already_used[org_word[i] - 'a'] = 1;secret_key[count++] = org_word[i];           }}       }   //接下来要对secret_key逆序，可以有很多种方法，考试时可以就用最笨的方法——开一个tmp数组存储其逆序后的结果，然后copy回去char tmp[100]= {0};for (int i=0; i < count; i++){tmp[count-1-i] = secret_key[i];}// 现在tmp已经是secret_key逆序后的数组了strcpy(secret_key, tmp);for(int i = 25; i >= 0; i--){if(!already_used[i]){           secret_key [count++] = 'a' + i;}}// 输出for(int i = 0; i < 26; i++){printf("%c", 'a' + i);}printf("\n");for (int i = 0; i < 26; i++)printf("%c", secret_key[i]);return 0;
}

2. 基于前移法的链表查找

题目

问题描述

链表结构存在一个严重不足，就是需要顺序查找才能找到所需要的元素，查找性能低，下面为一个改进链表查找效率的方法。 链表构造规则如下：

1. 初始时链表为空；
2. 若元素不在链表中，将其加到链表尾；
3. 若元素在链表中，则将该元素移到链表头（若元素已在链表头则不移动）。

编写程序，对输入的一组整数，依次在上述规则构建的链表中查找每个整数。 假如依次输入了15个整数，分别为：-200 120 85 97 2900 85 696 -120 85 120 85 120 85 97 120，前五个数据输入后，构建的链表如 下所示：

结点中前面的数据表示输入的整数，后面的数据是该整数的出现次数。输入第六个数据后，构建的链表如下所示：

所有整数输入完毕后，构建的链表如下所示：

输入形式

先从控制台读取整数的个数n（n>0），然后在下一行输入n个整数，各整数间以一个空格分隔，输入的整数不会超过int的表示范围。

输出形式

先输出创建链表时总的整数比较次数，然后依次分行输出链表中前五个整数及其出现次数（整数和出现次数间以一个空格分隔）；若链表中 结点的个数少于五个，则按照实际结点个数输出。

样例输入

15

-200 120 85 97 2900 85 696 -120 85 120 85 120 85 97 120

样例输出

41

120 4

97 2

85 5

-200 1

2900 1

样例说明

输入了15个整数；按照上述链表创建规则，输入第一个整数后，没有比较整数，这时总的比较次数为0；输入第五个整数后，整数比较次数为 14；输入第六个整数后，整数比较次数为17；所有整数输入完毕后，总的比较次数为41，这时整数120位于链表头，出现了4次。

评分标准

该题要求按照改进的链表查找整数，提交程序名为link.c。

问题分析

本题难度不大，按照要求模拟即可，其实在考场上我们更可能去关心的是用链表去写还是数组去实现。显然本题想考链表，但用数组去写代码肯定更简单，ds很少卡时间，唯一担心的就是会不会有某几个测试点数据量特别大，导致数组开不够大（事实上我有同学就用数组过了），所以还是建议直接用链表去实现。

具体实现过程

本题要频繁地在头结点位置插入结点，我个人喜欢带一个哑结点以简化插入结点时的逻辑，所以我们先定义结点类型，然后声明两个指针指向链表头，尾：

# include <stdio.h>
# include <stdlib.h>
typedef struct node {int num;int time;struct node* next;
} node;node* head = NULL;  // 指向链表头（哑结点）
node* tail = NULL;  // 指向表尾

在主函数中初始化：

int main()
{int n;scanf("%d", &n);head = (node*) malloc(sizeof(node));head->next = NULL;tail = head;    return 0;
}

然后进行数据的读入，每读进来一个数，我们要判断链表中是否已经有结点的数据域（num）等于该数，这需要我们把链表遍历一遍，同时设置一个flag记录是否出现过。对于没有出现过的数，只需把其插入链表尾即可；对于出现过的数，我们找到其位置p然后应该进行如下的操作：

1. p所指的结点的time域加一；
2. 在链表中删除p结点，这里有一个细节，如果p是尾结点的话，我们还要把tail指针前移一位，因为我们对于上述“插入表尾”的操作依赖于tail指针（当然，也可以完全不用tail指针，每次插入表尾的时候都从头把链表跑一遍也OK）；
3. 把p结点接到表头；

我们来实现这个逻辑：

    int tmp;  // 暂存读入的数据for (int i = 0; i < n; i++) {scanf("%d", &tmp);if (i==0) {  // 读入的第一个数，不用进行任何判断，直接接到head后就行tail -> next = (node*) malloc(sizeof(node));tail = tail -> next;tail -> num = tmp;tail -> time = 1;tail -> next = NULL;} else {node *p = head -> next;  // p从头到尾跑一遍，看看链表中是否出现过该数int flag = 0;  // 标志，记录是否出现过while (p) {if (p -> num == tmp) {  // p所指的结点的num域与tmp相等// 在链表中删除p结点，注意这个删除的意思不是要把p free掉if (p -> next == NULL) {  // 要是p结点是尾结点tail = find_pre(tail);  // 改变tail}p -> time ++;find_pre(p) -> next = p -> next;  // 让p的前一个结点指向后一个结点（删除p）// 把p接到head后p -> next = head -> next;head -> next = p;flag = 1;  // 标志设为1break;}p = p -> next;  // 当前结点的num域不与tmp相等，继续找下一个结点}if (!flag) {  // 没找到，把p接到表尾即可tail -> next = (node*) malloc(sizeof(node));tail = tail -> next;tail -> num = tmp;tail -> time = 1;tail -> next = NULL;}}}

其中的find_pre函数实现的功能是找到当前结点的上一个结点，对链表进行删除和插入时经常用到，其实现如下：

node* find_pre(node*p){node *q = head;while(q){if (q->next==p)return q;q=q->next;}   
}

这样我们就已经按照题目要求构建出了链表，接下来依照题意还要做两件事：

1. 记录一共比较了多少次，只需要设置一个compare_num变量，每次从表头开始找，经过每一个结点时给其+1即可；
2. 判断最后链表中的结点个数是否大于5，这也只需要用一个all_num变量记录，每一次在表尾插入结点时给其加一即可；

而后我们在最后先输出compare_num，再判断一下all_num是否大于5，输出对应的数据即可。

完整代码

#include <stdio.h>
#include <stdlib.h>
typedef struct node
{int num;int time;struct node *next;
} node;node *head = NULL; // 指向链表头（哑结点）
node *tail = NULL; // 指向表尾node *find_pre(node *p)
{node *q = head;while (q){if (q->next == p)return q;q = q->next;}
}int main()
{int n;scanf("%d", &n);head = (node *)malloc(sizeof(node));head->next = NULL;tail = head;int tmp;              // 暂存读入的数据int all_num = 1;      // 记录总的结点个数int compare_time = 0; // 记录比较的次数for (int i = 0; i < n; i++){scanf("%d", &tmp);if (i == 0){ // 读入的第一个数，不用进行任何判断，直接接到head后就行tail->next = (node *)malloc(sizeof(node));tail = tail->next;tail->num = tmp;tail->time = 1;tail->next = NULL;}else{node *p = head->next; // p从头到尾跑一遍，看看链表中是否出现过该数int flag = 0;         // 标志，记录是否出现过while (p){compare_time++;if (p->num == tmp){ // p所指的结点的num域与tmp相等// 在链表中删除p结点，注意这个删除的意思不是要把p free掉if (p->next == NULL){                          // 要是p结点是尾结点tail = find_pre(tail); // 改变tail}p->time++;find_pre(p)->next = p->next; // 让p的前一个结点指向后一个结点（删除p）// 把p接到head后p->next = head->next;head->next = p;flag = 1; // 标志设为1break;}p = p->next; // 当前结点的num域不与tmp相等，继续找下一个结点}if (!flag){ // 没找到，把p接到表尾即可all_num++;tail->next = (node *)malloc(sizeof(node));tail = tail->next;tail->num = tmp;tail->time = 1;tail->next = NULL;}}}// 输出printf("%d\n", compare_time);if (all_num < 5){node *temp = head->next;while (temp){printf("%d %d\n", temp->num, temp->time);temp = temp->next;}}else{node *temp = head->next;for (int i = 0; i < 5; i++){printf("%d %d\n", temp->num, temp->time);temp = temp->next;}}return 0;
}