看前须知

要点介绍和简要声明.

第三次上机题汇总

连续线段——结构体多级排序.

猴子选大王(约瑟夫问题)+3种解决约瑟夫问题的方法.

多项式相乘.

文件加密（环）——要求循环链表熟练的删除操作.

词频统计（数组或链表实现）.

题目内容

问题描述（建议用链表实现）

有一种文本文件加密方法，其方法如下：

1. 密钥由所有ASCII码可见字符（ASCII码编码值32-126为可见字符）组成，密钥长度不超过32个字符；

2. 先将密钥中的重复字符去掉，即：只保留最先出现的字符，其后出现的相同字符都去掉；

3. 将不含重复字符的密钥和**其它不在密钥中的可见字符（按字符升序）**连成一个由可见字符组成的环，密钥在前，密钥的头字符为环的起始位置；

4. 设原密钥的第一个字符（即环的起始位置）作为环的开始位置标识，先从环中删除第一个字符（位置标识则移至下一个字符），再沿着环从下一个字符开始顺时针以第一个字符的ASCII码值移动该位置标识至某个字符，则该字符成为第一个字符的密文字符；然后从环中删除该字符，再从下一个字符开始顺时针以该字符的ASCII码值移动位置标识至某个字符，找到该字符的密文字符；依次按照同样方法找到其它字符的密文字符。当环中只剩一个字符时，则该剩下的最后一个字符的密文为原密钥的第一个字符。

下面以可见字符集只由小写字母组成为例来说明对应密文字符集生成过程。如果密钥为：helloworld，将密钥中重复字符去掉后为：helowrd，将不在密钥中的小写字母按照升序添加在密钥后，即形成字符串：helowrdabcfgijkmnpqstuvxyz，该字符串形成的环如下图所示：

明码的第一个字母为h，h也是环的起始位置。h的ASCII码制为104，先把h从环中删除，再从下一个字母e开始顺时针沿着环按其ASCII值移动位置标识（即：在字母e为移动第1次，共移动位置标识104次）至字母w，则h的密文字符为w。w的ASCII码制为119，然后将w从环中删除，再从下一个字母r开始顺时针沿着环移动位置标识119次至字母为l，则w的密文字符为l。依次按照同样方法找到其它字母的密文字符。环中剩下的最后一个字母为x，则x的密文字符为明码的第一个字母h。按照这种方法形成的密文转换字符表为：

上方为原文字符，下方为对应的密文字符。由所有ASCII可见字符集组成的字符集密文字符生成方式与上例相同。

编写程序实现上述文件加密方法。密钥从标准输入读取，待加密文件为当前目录下的in.txt文件，该文件中的字符若是可见字符，则按照上述方法进行加密，否则原样输出（例如：回车换行符），加密后生成的密文文件为当前目录下的in_crpyt.txt。

【输入形式】

密钥是从标准输入读取的一行字符串，可以包含任意ASCII码可见字符（ASCII码编码值32-126为可见字符），长度不超过32个字符。

输入形式

密钥是从标准输入读取的一行字符串，可以包含任意ASCII码可见字符（ASCII码编码值32-126为可见字符），长度不超过32个字符。

输出形式

加密后生成的密文文件为当前目录下的in_crpyt.txt。

样例

【样例输入】

C Programming(Second Edition)

假设in.txt文件内容为：

This book is meant to help the reader learn how to program in C. It is the definitive reference guide, now in a second edition. Although the first edition was written in 1978, it continues to be a worldwide best-seller. This second edition brings the classic original up to date to include the ANSI standard.

From the Preface:

【样例输出】

in_crpyt.txt文件内容为：

样例说明

输入的密钥为C Programming(Second Edition)，由该密钥生成的字符串环中字符依次为：

C Progamin(SecdEt)!"#$%&’*+,-./0123456789:;<=>?@ABDFGHIJKLMNOQRTUVWXYZ[]^_`bfhjklpqsuvwxyz{|}~

形成的字符转换字符表（第一行为原ASCII字符，第二行为对应的密文字符）为：

按照该密文转换字符表将in.txt中的内容转换成加密字符输出到in_crpyt.txt中。

题解

易错点和难点

这道题最大的难点就是在如何读懂题意（这个我总不能再解释一遍吧好兄弟），建议抽一个大段空闲时间静静地读，理解题意，如果题意理解没有问题，那么这道题其实更之前的加密没有区别

跟之前的一样，首先是去重，然后是升序追加，之后是环加密，最后是加密文本。对于环加密对循环链表的操作，一定要小心的的要提前存储第一个头节点，因为最后的操作还需要用到，其次要小心的还有删除节点是一定要使链表还是循环的，不能出现断开的情况，不然的话之后的操作会出现越界访问的情况。

参考代码

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct node {
	int data;
	struct node *next;
};
typedef struct node Node;
typedef struct node *Nodep;
Nodep head=NULL,p,t,q;
char s[2000];
char tmp[2000];
char enc[2000];//加密数组 
int i,j,k,flag,times;
char temp,ch;
void DelRepeated();//去重函数
void Upcat();//升序追加函数
void CircleEncryption();//环加密
void Output(FILE *fp1,FILE *fp2);//输出函数
int main() {
	FILE *fp1 = fopen("in.txt","r");
	FILE *fp2 = fopen("in_crpyt.txt","w");
	gets(s);
	DelRepeated();//去重 
	Upcat();//升序追加
	CircleEncryption();//环加密
	Output(fp1,fp2);//输出函数
	return 0;
}
void DelRepeated() {
	int n=strlen(s);
	for(i=0; i<n; i++) {
		for(j=i+1; j<n; j++) {
			if(s[j]==s[i]) {
				s[j]='0';//重复设为 0 
			}
		}
	}
	j=0;
	for(i=0; i<n; i++) {
		if(s[i]!='0') {//重复不输出 
			tmp[j]=s[i];
			j++;
		}
	}// tmp为去重数组
	//puts(tmp);
}
void Upcat() {
	memset(s,0,sizeof(s));
	k=0;
	for(i=32; i<=126; i++) {
		flag=0;
		for(j=0; j<strlen(tmp); j++) {
			if(tmp[j]==i) {
				flag=1;//判断去重数组里面有没有该字母 
				break;
			}
		}
		if(flag==0) {
			s[k]=i;
			k++;
		} else {
			continue;
		}
	}
	strcat(tmp,s);//升序追加
	//puts(tmp);
}
void CircleEncryption() {
	int cnt=0;
	for(i=0; i<strlen(tmp); i++) {
		if(head == NULL) {
			p=(struct node *)malloc(sizeof(struct node ));
			head = p;
		} else {
			p->next =(struct node *)malloc(sizeof(struct node));
			p = p->next;
		}
		p->data=tmp[i];
		p->next=NULL;
	}
	p->next=head;//构成循环链表 
	temp=head->data; // temp存头节点的字母
	ch = temp;       //ch待加密的字母
	times = head->data; //times移动次数
	q=head;
	head=head->next;
	p->next=p->next->next;
	free(q);         //删除头节点
	p=head;
	while(p->next!=p) {
		for(i=1; i<times-1; i++) { //找到加密字母 
			p=p->next;
		}
		enc[(int)ch-32]=p->next->data;//加密 
		ch=p->next->data;//ch待加密的字母
		times = ch;//times移动次数
		q=p->next;
		p->next=p->next->next;
		free(q); //删除节点 
		p=p->next;
		cnt++;
	}
	enc[(int)ch-32]=p->data;  
	enc[(int)(p->data)-32]= temp;//最后对头节点加密 
	//puts(enc);
}
void Output(FILE *fp1,FILE *fp2) {
	memset(s,0,sizeof(s));
	ch=fgetc(fp1);
	i=0;
	while(ch!=EOF) {
		s[i]=ch;
		i++;
		ch=fgetc(fp1);
	}  //s是待加密的文本
	for(i=0; i<strlen(s); i++) {
		if(s[i]>=32&&s[i]<=126) fputc(enc[s[i]-32],fp2);
		else fputc(s[i],fp2);
	}
}

补充测试的数据

【样例输入】

%^&*dfg!@#$%WRTG

假设in.txt文件内容为：

He’d been talking of nothing else for two weeks. Some rich builder and his wife were coming to dinner and Uncle Vernon was hoping to get a huge order from him (Uncle Vernon’s company made drills). I think we should run through the schedule one more time, said Uncle Vernon. We should all be in position at eight o’clock. Petunia, you will be -? In the lounge, said Aunt Petunia promptly, waiting to welcome them graciously to our home. Good, good. And Dudley? I’ll be waiting to open the door. Dudley put on a foul, simpering smile. May I take your coats, Mr. and Mrs. Mason? They’ll love him! cried Aunt Petunia rapturously. Excellent, Dudley, said Uncle Vernon. Then he rounded on Harry. And you? I’ll be in my bedroom, making no noise and pretending I’m not there, said Harry tonelessly. Exactly, said Uncle Vernon nastily. I will lead them into the lounge, introduce you, Petunia, and pour them drinks. At eight-fifteen-I’ll announce dinner, said Aunt Petunia.

From the Preface:

【样例输出】

in_crpyt.txt文件内容为：

BsV5[Yss6[zvX>E6O[+}[6+zNE6O[sX’s[}+G[z=+[=ss>‘e[[[P±s[GEuN[YDEX5sG[v65[NE’[=E}s[=sGs[u±E6O[z+[5E66sG[v65[S6uXs[UsG6+6[=v’[N+|E6O[z+[Osz[v[NDOs[+G5sG[}G±[NE-[3S6uXs[UsG6+6V’[u±|v6_[-v5s[5GEXX’&e[[J[zNE6>[=s['N+DX5[GD6[zNG+DON[zNs['uNs5DXs[+6s[-+Gs[zE-sp['vE5[S6uXs[UsG6+6e[[[]s['N+DX5[vXX[Ys[E6[|+‘EzE+6[vz[sEONz[+VuX+u>e[[[LszD6Evp[+D[=EXX[Ys[qc[J6[zNs[X+D6Osp['vE5[!D6z[LszD6Ev[|G±|zX_p[=vEzE6O[z+[=sXu±s[zNs-[OGvuE+D’X[z+[+DG[N±se[[9++5p[O++5e[[[!65[dD5Xs_c[JVXX[Ys[=vEzE6O[z+[+|s6[zNs[5++Ge[[[dD5Xs_[|Dz[+6[v[}+DXp[‘E-|sGE6O[’-EXse[[[Av_[J[zv>s[+DG[u+vz’p[AGe[[[v65[AG’e[[[Av’+6c[{Ns_VXX[X+;s[NE-t[[uGEs5[!D6z[LszD6Ev[Gv|zDG+D’X_e[[o?usXXs6zp[dD5Xs_p['vE5[S6uXs[UsG6+6e[[[{Ns6[Ns[G+D65s5[+6[BvGG_e[[[!65[+Dc[JVXX[Ys[E6[-[Ys5G+±p[-v>E6O[6+[6+E’s[v65[|Gszs65E6O[JV-[6+z[zNsGsp['vE5[BvGG[z+6sXs’'X_e[[o?vuzX_p['vE5[S6uXs[UsG6+6[6v’zEX_e[[[J[=EXX[Xsv5[zNs-[E6z+[zNs[X+D6Osp[E6zG+5Dus[_+Dp[LszD6Evp[v65[|+DG[zNs-[5GE6>'e[[[!z[sEONzq}E}zss6qJVXX[v66+D6us[5E66sGp['vE5[!D6z[LszD6Eve[[