06、数据结构和算法 - 实战：线性表（4）

约瑟夫环

据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第3个人。接着，杀掉第3个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决。Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

约瑟夫问题和循环链表相同。

问题：用循环链表模拟约瑟夫问题，把41个人自杀的顺序编号输出。

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
   
     
	int data;
	struct node *next;
}node;

node *create(int n)
{
   
     
	node *p = NULL, *head;
	head = (node*)malloc(sizeof(node));
	p = head;
	node *s;
	int i = 1;

	if( n != 0)
	{
   
     
		while(i<=n)
		{
   
     
			s = (node*)malloc(sizeof(node));
			s->data = i;
			i++;
			p->next = s;
			p = s;
		}
		s->next = head->next;//不指向头节点，而是第一个结点，构成一个环，释放头结点
	}
	free(head)
	return s->next;
}

int main()
{
   
     
	int n = 41;
	int m = 3;
	int i;
	node *p = create(n);
	node *temp;
	
	m %= n; //在这里是2
	while( p != p->next )
	{
   
     
		for(i = 1; i < m-1; i++)
		{
   
     
			p = p->next;
		}
		printf("%d -> ",p->next->data);
		
		temp = p->next;
		p->next = temp->next;
		free(temp);
		
		p = p->next;
	}
	printf("%d\n",p->data);
	return 0;
}

循环链表的改进

去掉头指针，将尾指针指向头结点

判断空链表的条件：rear是否等于rear->next。
例题1：实现将两个链表连接成一个线性表（a1, a2, a3…b1, b2…）的运算
普通思路：用头指针表示的单循环表上，遍历第一个链表，找到an，然后将b1放在an的后面，bn的next指向a的头结点。执行时间为O（n）
优化思路：只需要修改二者的尾指针

例题2：判断单链表中是否有环（链表的尾结点指向了链表中的某个结点）

方法一：使用p，q两个节点，p总是向前走，q是每次从头开始走，对于每个结点，看p的步数和q是否一样。例如，p从1-2-3-4-5-6-3，用了6步，此时q从head出发，只需要两步，因此步数不等，存在环。
方法二：快慢指针，p向前走一步，q走两步，某个时候p==q，则存在环。

魔术师发牌问题

一位魔术师掏出一叠扑克牌，魔术师取出其中13张黑桃，洗好后，把牌面朝下。说：“我不看牌，只数一数就能知道每张牌是什么？”魔术师口中念一，将第一张牌翻过来看正好是A；魔术师将黑桃A放到桌上，继续数手里的余牌，第二次数1，2，将第一张牌放到这叠牌的下面，将第二张牌翻开，正好是黑桃2，也把它放在桌子上。第三次数1，2，3，前面二张牌放到这叠牌的下面，取出第三张牌，正好是黑桃3，这样依次将13张牌翻出，全部都准确无误。求解：魔术师手中牌的原始顺序是什么样子的？
代码如下：

#include <stdio.h>
#include <stdlib.h>
#define CardNumber 13
typedef struct node
{
   
     
	int data;
	struct node *next;
}sqlist,*linklist;

linklist CreateLinkList()
{
   
     
	linklist head = NULL;
	linklist s, r;
	int i;
	
	r = head;
	for(i = 1; i<= CardNumber ; i++)
	{
   
     
		s = (linklist)malloc(sizeof(sqlist));
		s->data = 0;
		
		if(head == 	NULL)
			head = s;
		else 
			r->next = s;
		r=s;
	}
	r->next = head;
	return head;
}

//发牌顺序计算
void Magician(linklist head)
{
   
     
	linklist p;
	int j;
	int Countnumber = 2;

	p = head;
	p->data = 1; //第一张牌放1
	
	while(1)
	{
   
     
		for( j = 0 ;j <Countnumber ; j++)
		{
   
     
			p = p->next;
			if(p->data != 0)
			{
   
     
				p->next;
				j--;
			}
		}
		if(p->data == 0)
		{
   
     
			p->data = Countnumber;
			Countnumber++;
			if(Countnumber == 14)
				break;
		}
	}
}
int main()
{
   
     
	linklist p ;
	int i;
	p =  CreateLinkList();
	Magician(p);

	printf("排列顺序：\n");
	for(i = 0; i < CardNumber ; i++)
	{
   
     
		printf("黑桃%d", p->data);
		p = p->next;
	}
	return 0;
}

双向链表

结点结构

插入操作

删除操作

例题

要求实现用户输入一个数使得26个字母的排列发生变化，例如用户输入3，输出结果：DEFGHIJKLMNOPQRSTUVWXYZABC。也支持负数输入，例如-3，XYZABCDEFGHIJKLMNOPQRSTUVW
代码实现如下：

#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0
typedef char ElemType;
typedef int Status;

typedef struct DualNode
{
   
     
	ElemType data;
	struct DualNode *prior;
	struct DualNode *next;
}DualNode, *DuLinkList;

Status InitList(DuLinkList *L)
{
   
     
	DualNode *p,*q;
	int i;
	*L = (DuLinkList)malloc(sizeof(DualNode));
	if(!(*L))
		return ERROR;
	(*L)->next = (*L)->prior = NULL;
	p = (*L);
	for(i = 0; i < 26; i ++)
	{
   
     
		q = (DuLinkList)malloc(sizeof(DualNode));
		if(!q)
			return ERROR;
		q->data = 'A' + i;
		q->prior = p;
		q->next = p->next;
		p->next = q;
		p = q; 
	}
	p->next = (*L)->next;
	(*L)->next->prior = p;
	return OK;
}

void Caesar(DuLinkList *L, int i)
{
   
     
	if( i > 0)
	{
   
     
		do
		{
   
     
			(*L) = (*L)->next;
		}while( --i);
	}
	if( i < 0)
	{
   
     
		do
		{
   
     
			(*L) = (*L)->next;
		}while( ++i);
	}
}
int main()
{
   
     
	DuLinkList L;
	int i,n ;
	InitList(&L);
	
	printf("请输入一个整数：");
	scanf("%d",&n);
	printf("\n");
	
	Caesar(&L ,n );
	
	for(i = 0; i< 26 ;i ++)
	{
   
     
		L = L->next;
		printf("%c", L->data);
	}
	return 0;
}