学习笔记：数据结构与算法（六）：线性表（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;
}
版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: