引入

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

凯撒密码

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

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

例题

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

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

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

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

初始化双链表

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

#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;   //返回头部地址
}

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

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

凯撒密码表操作

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

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;  //把指针位置移动之后的地址返回
}

思路

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

最终代码实现

#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);
}

尾巴

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