双向循环链表：字母表实现前后移动

末蓝、 2022-06-01 04:40 135阅读 0赞

# 问题描述 #

**要求实现用户输入一个数使得26个字母的排列发生变化，例如用户输入3，使得结果为：DEFHIJKLMNOPQRSTUVWXYZABC，**

**同时需要支持负数，使得输入-3时，结果为：XYZABCDEFGHIJKLMNOPQRSTUVW。实现位置的前后都能移动且数据都是连着的，当然数据结构选择双向循环链表啦。**

# **问题拓展** #

问题实际上是有关**凯撒密码**，凯撒密码的思想是通过把字母移动一定的位数来实现加密和解密。

明文中的所有字母都在字母表上向后（或向前）按照一个固定数目进行偏移后被替换成密文。

# **代码展示** #

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #define OK 1
    #define ERROR 0
    
    typedef int Status;
    typedef char EleType;
    //双向循环链表 结点数据结构
    typedef struct DulNode
    {
    	EleType data;//数据域
    	struct DulNode* next;//后继结点指针域
    	struct DulNode* prior;//前驱结点指针域
    }DulNode,*DulLinkList;
    //取了别名 DulNode* 相当于DulLInkList
    
    //创建双向循环链表
    Status CreatDulLink(DulLinkList* list)
    {
    	if (list == NULL)
    	{
    		return ERROR;
    	}
    	DulNode* head = (DulNode*)malloc(sizeof(DulNode));//创建头结点
    	if (head == NULL)
    	{
    		return ERROR;
    	}
    
    	DulNode* p = head;//p 移动指针，起初指向头结点
    	p->next = p->prior = NULL;
    
    	for (size_t i = 0; i < 26; i++)
    	{
    		DulNode* node = (DulNode*)malloc(sizeof(DulNode));//创建结点
    		node->data = 'A' + i;
    		
    		//下面3步将创建的node结点放到双向循环链表中
    		node->next = p->next;//直接赋值NULL也可以
    		node->prior = p;
    		p->next = node;
    		//p 始终指向链表最后一个结点
    		p = node;
    	}
    	//下2步 将尾结点和第一个结点关联形成双向循环链表，越过头结点。
    	p->next = head->next;
    	head->next->prior = p;
    	//循环链表指向第一个元素
    	*list = p->next;
    	//释放头结点
    	free(head);
    	return OK;
    }
    //将循环链表指向第num个位置
    Status Caesar(DulLinkList* list,int num)
    {
    	DulLinkList tmp = *list;
    	//双向循环链表指针往后移
    	if (num > 0)
    	{
    		int i = 0;
    		//num = 1 往后移动1位, temp = temp -> next
    		while (i < num)
    		{
    			tmp = tmp->next;
    			i++;
    		}
    		*list = tmp;
    	}
    	//双向循环链表指针往前移
    	if (num < 0)
    	{
    		int i = 0;
    		//num = -1 往前移动1位，temp = temp->prior
    		while (i < num*-1)
    		{
    			tmp = tmp->prior;
    			i++;
    		}
    		*list = tmp;
    	}
    	return OK;
    }
    //销毁链表释放内存
    Status DestroyDulLink(DulLinkList list)
    {
    	if (list == NULL)
    	{
    		return ERROR;
    	}
    	DulNode* node = list;//node为移动指针，node 开始指向循环链表第一个结点
    	//循环链表遍历完判断，尾结点的指针域指向第一个结点
    	while (node->next != list)
    	{
    		DulNode* temp = node;
    		node = node->next;
    		free(temp);
    	}
    	//释放最后一个结点
    	free(node);
    	return OK;
    }
    //循环链表展示
    Status ShowCaesar(DulLinkList list)
    {
    	if (list == NULL)
    	{
    		return ERROR;
    	}
    	DulNode* node = list;//node为移动指针，node 开始指向循环链表的开始的一个结点
    	//循环链表遍历完判断，尾结点的next指针域指向开始第一个结点
    	while (node->next != list)
    	{
    		printf("%c",node->data);
    		node = node->next;
    	}
    	printf("\n");
    	return OK;
    }
    
    int main(int argc, char *argv[])
    {
    	DulLinkList list = NULL;
    	CreatDulLink(&list);
    	DulLinkList origal = list;
    	int num = 0;
    	while (1)
    	{
    		list = origal;
    		printf("请输入位移数字(0退出)：");
    		scanf("%d", &num);
    		if (!num)
    		{
    			break;
    		}
    
    		Caesar(&list, num);
    		ShowCaesar(list);
    	}
    	DestroyDulLink(list);
    	return 0;
    }

# **运行结果** #

![SouthEast][]

[SouthEast]: /images/20220601/79222477b1fa425fa1fddc1f762f47a6.png