魔术师发牌问题 (C语言实现) ------- 算法笔记008

素颜马尾好姑娘i 2023-07-02 11:30 7阅读 0赞

## 问题背景 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz_size_16_color_FFFFFF_t_70]

> 实质还是循环双向链表的应用，多了一个判断循环的步骤

## 实现代码 ##

#include <stdio.h>
    #include <stdlib.h>
    #define numPokers 13
    typedef struct node{ 
    	int data;
    	struct node *next;
    }Node,*List; 
    //定义一组牌A-K ;A用1表示，对应的J,Q,K也是相应的数字表示
    int pokers [13]={ 1,2,3,4,5,6,7,8,9,10,11,12,13};
    //创建一组空牌；并未赋值
    List createPoker(List head){ 
    	int num=13;
    	int i; 
    	List p=head;
    	for(i=0;i<num;i++){ 
    		List new =(List)malloc(sizeof(Node));
    		new->data=0;//每张牌初始赋值为0
    		p->next=new;
    		p=new;
    	} 
    	p->next=head->next;
    	p=head->next;
    	free(head);
    	return p;
    }
    
    
    int main(int argc, char *argv[]) { 
    	int num=numPokers;
    	List p=NULL;
    	List head=(List)malloc(sizeof(Node));
    	head=createPoker(head);
    	p=head;
    	
    	head->data=1;
    	//算法开始
    	while(num--){ 
    		int index=numPokers-num;  //index由1增至13
    		int steps=index; //步数
    		//忽略第一张已经赋值过的牌
    		if(steps!=1){ 
    			while(steps--){  
    				p=p->next;
    				//当检测牌已经赋过值了，跳过这张牌
    				if(p->data!=0){ 
    					steps++;
    				}
    			}
    			p->data=pokers[index-1];
    		
    		}
    			
    	}
    	p=head;
    	//打印输出
    	while(p->next!=head){ 
    		printf("%d\t",p->data);
    		p=p->next;
    	}
    	printf("%d\n",p->data);
    
    
    	return 0;
    }

> 算法复杂度 O(n^2)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200129203459387.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz,size_16,color_FFFFFF,t_70