数据结构之线性表-双向循环链表之凯撒密码-学习笔记-28

引入

前面我们简单了解了一下双链表,以及在插入和删除时的一些变化。这一节,我们就跟着一个凯撒密码,来看看双循环链表的初始化、插入、操作结点等过程。

凯撒密码

凯撒密码是一种代换密码。据说凯撒是率先使用加密函的古代将领之一,因此这种加密方法被称为凯撒密码。他的基本思想是

  • 通过把字母移动一定的位数来实现加密和解密。
  • 明文中的所有字母都在字母表上向后(或向前)按照一个固定数目进行偏移后被替换成密文。
  • 当偏移量是4的时候,所有的字母A将被替换成E,B变成F,以此类推W将变成A,X变成B,Y变成C,Z 变成 D。
  • 而这个偏移量就是凯撒密码加密和解密的密钥。

例题

有26个英文字母,我们需要设计一个程序

  • 用户输入可为正负的正整数
  • 如果是正数,那从左边取 N 位正整数移动到表尾
  • 如果是负数,那从右边取 N 位正整数移动到表头

输入 4
初始化:ABCDEFGHIJKLMNOPQRSTUVWXYZ
改变为:FGHIJKLMNOPQRSTUVWXYZABCDE

输入-5
初始化:ABCDEFGHIJKLMNOPQRSTUVWXYZ
改变为:VWXYZABCDEFGHIJKLMNOPQRSTU

初始化双链表

第一步:我们先初始化这个由 A~Z 组成的双循环链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
#include <stdlib.h>
#define NUM 26
#define LEN sizeof(struct WordList)

// 构建一个双循环链表结点的结构体
struct WordList{
char word;
struct WordList *prior;
struct WordList *next;
};

// 开始初始化这个结构体,让26个字母插入,并形成双循环链表
struct WordList *init(void){
struct WordList *w,*temp,*head;
int i=0; //用于计数
w=(struct WordList *)malloc(LEN);
head=temp=w;
//上面用于处理好头部
while(i<NUM){
w->word='A'+i; //赋值
w->prior=temp; //前驱是 w 的替身 temp
temp->next=w; //后继是 w
temp=w; //让 temp 再次成为 w 的替身
w=(struct WordList *)malloc(LEN); //w重新分配内存空间
i++; //计数加加
}
temp->next=head; //最后一个结点指向头部
head->prior=temp; //头部的前驱指向尾部,形成闭环
return head; //返回头部地址
}

这一步初始化很简单,记住

  • 头部处理好,头部在开始等于头结点,结尾需要将头部的前驱指向尾巴
  • 顺序不要错,先新结点,再老节点,避免出错

凯撒密码表操作

其实这个比较简单,就是让上面初始化好的指针的头部稍稍移动一下位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct WordList *caesar(struct WordList *w , int n){
// 如果输入的大于0,那就是指针向后移动几位,那就会从 n+1 位开始输出了
if(n>0){
do{
w=w->next;
}while(--n);
}
// 如果输入的小于0,那就是指针向前移动几位,那就会从 n-1 位开始输出了
if(n<0){
do{
w=w->prior;
}while(++n);
}
return w; //把指针位置移动之后的地址返回
}

思路

  • 我们要想到,既然是循环链表,那么谁都可以是「头指针」
  • 你把「头指针」移动到哪里就从哪里输出

最终代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <stdio.h>
#include <stdlib.h>
#define NUM 26
#define LEN sizeof(struct WordList)

// 构建一个双循环链表结点的结构体
struct WordList{
char word;
struct WordList *prior;
struct WordList *next;
};

// 开始初始化这个结构体,让26个字母插入,并形成双循环链表
struct WordList *init(void){
struct WordList *w,*temp,*head;
int i=0; //用于计数
w=(struct WordList *)malloc(LEN);
head=temp=w;
//上面用于处理好头部
while(i<NUM){
w->word='A'+i; //赋值
temp->next=w; //后继是 w
w->prior=temp; //前驱是 w 的替身 temp
temp=w; //让 temp 再次成为 w 的替身
w=(struct WordList *)malloc(LEN); //w重新分配内存空间
i++; //计数加加
}
temp->next=head; //最后一个结点指向头部
head->prior=temp; //头部的前驱指向尾部,形成闭环
return head; //返回头部地址
}

void print_word(struct WordList *w){
struct WordList *head;
head=w;
do{
printf("%c ",w->word);
}while((w=w->next)!=head);
}

struct WordList *caesar(struct WordList *w , int n){
if(n>0){
do{
w=w->next;
}while(--n);
}

if(n<0){
do{
w=w->prior;
}while(++n);
}

return w;
}


int main(){
struct WordList *word_p;
int n;
word_p=init();
printf("请输入一个整数:\n");
scanf("%d",&n);
word_p=caesar(word_p,n);
print_word(word_p);
}

尾巴

这是我的个人学习笔记,主要是应付考研复习使用,充斥着一些吐槽和个人观点,并不严谨,欢迎大家参考、指正。


-------------The End-------------
欢迎请我喝咖啡哦~!