有趣的数据结构算法7——双向循环链表的实例应用

比眉伴天荒 2021-11-29 20:36 199阅读 0赞

### 有趣的数据结构算法7——双向循环链表的实例应用 ###

*  问题复述
 *  解题思路
 *  实现代码
 *  GITHUB下载连接

# 问题复述 #

要求实现用户输入一个数字改变26个字母的排列顺序。正常情况下26个字母的排列顺序是A B C D E F G H I J K L M N O P Q R S T U V W X Y Z。  
当用户输入3时，字母的排列顺序改为D E F G H I J K L M N O P Q R S T U V W X Y Z A B C。  
当用户输入-3时，字母的排列顺序改为X Y Z A B C D E F G H I J K L M N O P Q R S T U V W 。  
刚学完循环链表和双向链表的我看到这个问题，太简单了。我相信：  
![在这里插入图片描述][2019072313192254.jpg_pic_center]

# 解题思路 #

我们可以将26个英文字母排列成一个双向循环链表，头指针指向A，此时如果输入的数字是正数，则

for (int i = 0; i < num; i++){
        	//num代表输入的数字
    	s = s->Next;
    }

此时如果输入的数字是负数，则

for (int i = 0; i < -num; i++){
        	 //num代表输入的数字
    	s = s->Before;
    }

此时再从s结点开始遍历整个链表，便可以得到全新排列的26个字母。

# 实现代码 #

#include <stdio.h>
    #include <stdlib.h>
    
    struct Node{
        
    	char c;
    	struct Node* Next;
    	struct Node* Before;
    };
    
    typedef struct Node* List;
    
    //声明函数
    List createList();
    void ScanList(List list);
    void mission(int num, List list);
    
    int main(void){
        
    	List ok;
    	int num;
    	ok = createList();
    	printf("请输入一个数字：");
    	scanf("%d", &num);
    	mission(num, ok);
    }
    
    List createList(){
        
    	List s, p;
    	List Head;
    	char c = 'A';
    	
    	int i;
    	Head= (List)malloc(sizeof(struct Node));
    	s = Head;				//头结点节点初始化
    	s->c = c;
    	s->Next = s;		
    	s->Before = s;
    	for (i = 1; i < 26; i++){
        	
    		c = c + 1;
    		p = (List)malloc(sizeof(struct Node));
    		s->Next = p;		//此处一共具有三个List节点，head始终指向头部
    		p->Before = s;		//p节点是临时节点，用作每一次插入新节点。
    		Head->Before = p;	//s节点每次都进行s=s->Next更新，始终指向尾节点。
    		p->Next = Head;
    		s = s->Next;
    		p->c = c;
    	}
    	return Head;
    }
    
    void ScanList(List list){
        
    	List s = list;
    	printf("%c ", s->c);	//从头到尾遍历链表
    	s = s->Next;
    	while (s != list){
        
    		printf("%c ", s->c);
    		s = s->Next;
    	}
    }
    
    void mission(int num, List list){
        
    	List s = list;
    	if (num > 0)
    	{
        
    		for (int i = 0; i < num; i++){
        	//num代表输入的数字
    			s = s->Next;
    		}
    	}
    	else{
        
    		for (int i = 0; i < -num; i++){
        	//num代表输入的数字
    			s = s->Before;
    		}
    	}
    	ScanList(s);
    }

# GITHUB下载连接 #

[https://github.com/bubbliiiing/Data-Structure-and-Algorithm][https_github.com_bubbliiiing_Data-Structure-and-Algorithm]

希望得到朋友们的喜欢。  
有问题的朋友可以提问噢。

[2019072313192254.jpg_pic_center]: /images/20211129/d2f15f2ffa3a4fb09e6b5d06ff14a16a.png
[https_github.com_bubbliiiing_Data-Structure-and-Algorithm]: https://github.com/bubbliiiing/Data-Structure-and-Algorithm