(四)循环链表及双向链表

文章目录

循环链表

对于单链表,由于每个结点只储存了向后的指针,到了尾部标识就停止了向后链的操作。也就是说,按照这样的方式,只能索引后继节点,不能索引前驱节点。不从头结点出发就无法访问到全部节点,故有了循环链表

单循环链表

定义

  • 将单链表中终端节点的指针端由空指针改为指向头结点,就使得整个单链表形成一个环,这种头尾相接的单循环链表简称单循环链表
  • 《(四)循环链表及双向链表》
  • 注:并不是说循环链表一定要有头结点
  • 循环链表的单链表的主要差距就在于循环的判断空链表的条件上,原来判断head->next是否为NULL,现在则是head->next是否等于head
  • 终端节点用尾指针rear表示,查找终端节点为O(1),而开始节点是rear->next->next,也是O(1)
//链表存储结构定义
typedef struct CLiinkList
{ 
	int data;
	struct CLiinkList *next;
}node;

初始化操作

//初始化循环链表
void ds_init(node **pNode)
{ 
	int item;
	node *temp;
	node *target;
	//采用从键盘输入方法来获取值
	while(1)
	{ 	
		scanf("%d",&item);
		fflush(stdin);
		if(item == 0)
			return;
		if((*pNode) == NULL)
		{ 
			//循环链表只有一个节点
			*pNode = (node*)malloc(sizeof(node));
			if(!(*pNode))
			{ 
				exit(0);
			}
			(*pNode)->data = item;
			(*pNode)->next = *pNode;
		}
		else
		{ 
			//找到next指向第一个节点的节点
			for(target = (*pNode);target->next != (*pNode);target = target->next)
				;
			//生成一个新的节点
			temp = (node*)malloc(sizeof(node));
			if(!temp)
				exit(0);
			
			temp->data = item;
			temp->next = *pNode;
			target->next = temp;
		}
	}
}

插入操作

//插入节点
//参数:链表的第一个节点,插入位置,插入元素
Status ds_insert(node **pNode,int i,int e)
{ 
	node *temp;
	node *target;
	node *p;
	int j = 1;
	
	if(i == 1)
	{ 
		//新插入的节点作为第一个节点
		temp = (node*)malloc(sizeof(node));
		
		temp->data = e;
		//寻找最后一个节点
		for(target = (*pNode);target->next != (*pNode);target = target->next)
				;
		temp->nexxt = (*pNode);
		target->next = temp;
		*pNode = temp;
	}
	else
	{ 
		target = *pNode;
		for( ;j < (i-1);++j)
		{ 
			target = target->next;
		}
		temp = (node*)malloc(sizeof(node));
		temp->data = e;
		p = target->next;
		target->next = temp;
		temp->next = p;
	}
	return OK;
}

删除操作

int ds_delete(node **pNode,int i)
{ 
	node *temp;
	node *target;
	int j = 1;

	if(i == 1)
	{ 
		for(target = (*pNode);target->next != (*pNode);target = target->next)
			;
		temp = *pNode;
		
		*pNode = (*pNode)->next;
		target->next=*pNode;
		free(temp);
	}
	else
	{ 
		target = *pNode;
		for( ;j < i-1;++j)
		{ 
			target = target->next;
		}
		temp = target->next;
		target->next = temp->next;
		free(temp);
	}
}

返回节点所在位置

//返回节点的所在位置
int ds_search(node *pNode,int e)
{ 
	node *target;
	int i = 1;
	
	for(target = pNode;target->data != e && target->next != pNode;i++)
	{ 
		target = target->next;
	}
	if(target->next == pNode)//表中不存在该元素
	{ 
		return ERROR;
	}
	else
	{ 
		return i;
	}
}

约瑟夫问题

  • 约瑟夫问题
    据说著名犹太历史学家Josephus有过以下的故事:
    在罗马人占领乔塔帕特后,39个犹太人与Josephus
    及他的朋友躲到一个洞中,39个犹太人决定宁愿死也
    不要被敌人抓到,于是决定了一个自杀方式,41个人
    排成一个圆圈,由第1个人开始报数,每报数到第3人
    该人就必须自杀,然后再由下一个重新报数,直到所
    有人都自杀身亡为止。
    然而Josephus和他的朋友并不想遵从,Josephus要
    他的朋友先假装遵从,他将朋友与自己安排在第16个
    与第31个位置,于是逃过了这场死亡游戏。
  • 问题:用循环链表模拟约瑟夫问题,把41个人自杀的顺序编号输出
//n个人围圈报数,报m出列,最后剩下几号?
#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( 0 != n)
    { 
        while(i <= n)
        { 
            s = (node*)malloc(sizeof(node));
            s->data = i++;   //为循环链表初始化,第一个节点为1,第二个节点为2
            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;


    while(p != p->next)
    { 
        for(i = 1;i < m - 1;i++)
        { 
            p = p->next;
        }
        printf("%d->",p->next->data);
        temp = p->next; //删除第m个节点
        p->next = temp->next;

        free(temp);

        p = p->next;
    }

    return 0;
}

循环链表的特点

  • 在单链表中,有了头结点就可以用O(1)的时间访问第一个节点,但对于访问最后一个节点,必须要挨个向下索引,所以需要O(n)的时间
  • 但是循环链表,用O(1)的时间就可以由链表指针访问到最后一个节点

《(四)循环链表及双向链表》

  • rear指向尾节点,尾指针

    • 判断是否为空链表:rear是否等于rear->next
  • 例题:实现将两个线性表(a1,a2,…an)和(b1,b2,…,bn)连接成一个线性表(a1,…,an,b1,…bn)

    • 若采用单链表或头指针的单循环表做这题,都需要遍历第一个链表,找到an,然后将b1连接到an后面,执行时间为O(n)
    • 若使用单循环链表的尾指针实现,则只需要修改指针,不需要遍历,执行时间为O(1)
    • 图解《(四)循环链表及双向链表》
    • 代码:
//假设A、B为非空单循环链表的尾指针
LinkList Connect(LinkList A,LinkList B)
{ 
	LinkList p = A->next;       //保存A表的头结点位置
	A->next = B->next->next;   //B表开始的节点链接到A表尾
	free(B->next);  //释放B表的头结点
	B->next = p;
	return B;   //返回新循环链表的尾指针
}

判断单链表中是否有环

  • 有环的定义,链表的尾结点指向了链表中的某个节点
    《(四)循环链表及双向链表》
  • 方法一:
    • 使用p、q两个指针,p总是向前走,但q每次都从头开始走,对于每个节点,看p走的步数是否和q一样。如图,当p从6走到3时,用了6步,此时若从head出发,则只需两步就到3,因而步数步数不等,出现矛盾,存在环
// 比较步数的方法
int HasLoop1(LinkList L)
{ 
	LinkList cur1 = L; //定义节点 cur1
	int pos1 = 0; //cur的步数
	while(cur1)       //cur1 节点存在
	{ 
		LinkList cur2 = L;  //定义节点cur2
		int pos2 = 0; //cur2的步数
		while(cur2)   // cur2节点不为空
		{ 
			if(cur2 == cur1)  //当cur1 与cur2到达相同节点时
			{ 
				if(pos1 == pos2) //走过的步数相同
					break;
				else 
				{ 
					printf("环的位置在第%d个节点处。\n\n",pos2);
					return 1;   //有环并返回1
				}
			}
			cur2 = cur2->next;  //如果没有环,继续下一个节点
			pos2++; //cur2步数自增
		}
		cur1 = cur1->next;   //cur1继续向后一个节点
		pos1++;      //cur1 步数自增
	}
	retutn 0;
} 
- 使用p、q两个指针,p每次向前走一步,q每次向前走两步,若在某个时候p == q,则存在环(快慢指针)
//快慢指针方法
int HasLoop2(LinkList L)
{ 
	int step1 = 1;
	int step2 = 2;
	LinkList p = L;
	LinkList q = L;

	while(p != NULL && q != NULL && q->next != NULL)
	{ 
		if(p == q)
			return 1;
	}
	return 0;
}

例题

魔术师发牌问题

  • 问题描述:魔术师利用一副牌中的13张黑牌,预先将他们排好后叠放在一起,牌面朝下。对观众说:“我不看牌,只数数就可以猜到每张牌是什么,我大声数数,你们听,不信?现场演示。魔术师将最上面的那张牌数为1,把他翻过来正好是黑桃A,将黑桃A放在桌子上,第二次数1,2,将第一张牌放在这些牌的下面,将第二张牌翻过来,正好是黑桃2,也将它放在桌子上这样依次进行将13张牌全部翻出,准确无误。
  • 问题:牌的开始顺序是如何安排的?
//发牌顺序计算
void Magician(LinkList head)
{ 
	LinkList p;
	int j;
	int countNum = 2;
	p = head;
	p->data = 1; //第一张牌放1

	while(1)
	{ 
		for(j = 0; j < countNum;j++)
		{ 
			p = p->next;
			if(p->data != 0)  //该位置有牌就移动到下一个位置
			{ 
				j--;
			}
		}
		
		if(p->data == 0)
		{ 
			p->data = countNum;
			countNum ++;
			if(countNum == 14)
				break;
		}
	}
}

拉丁方针问题

  • 拉丁方阵是一种n * n的方阵,方阵中恰有n种不同的元素,每种元素恰有n个,并且每种元素在一行和一列中恰好出现一次。著名数学家和物理学家欧拉使用拉丁字母来作为拉丁方阵里元素的符号拉丁方阵因此而得名
  • 例如下图是一个3X3的拉丁方阵:
    《(四)循环链表及双向链表》
  • 核心代码
void latin(int n)
{ 
	LinkList p,q,head;
	int j;
	head = p = (LinkList)malloc(sizeof(LinkList));
	p->data = 1;
	for(j = 2;i <= n;j++)
	{ 
		q = (LinkList)malloc(sizeof(LinkList));
		q->data = j;
		p->next = q;
		p = p->next;
	}
	head = p;
	p->next = head;
	
	for(j = 1;j <= n * n;j++)
	{ 
		if(n % j == 0)
			printf("\n");
		printf("%d ",&head->data);
		head = head->next;
	}

}

双向链表

  • 双向链表可以有效提高算法的时间性能,用空间换取时间

结构定义

typedef struct DualNode
{ 
	ElemType data;
	struct DualNode *prior;//前驱节点
	struct DualNode *next;//后继节点
}DualNode,*DuLinkList;

《(四)循环链表及双向链表》

双向链表的循环链表

《(四)循环链表及双向链表》

双向链表的插入操作

  • 插入操作不复杂,但是注意顺序不要搞错了
    《(四)循环链表及双向链表》
  • 代码实现:结合图来看
s->next = p;
s->prior = p->prior;
p->prior->next = s;
p->prior = s;

一定不要搞错顺序

双向链表的删除操作

《(四)循环链表及双向链表》

  • 代码实现:结合图看
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
    原文作者:奇怪的代码
    原文地址: https://blog.csdn.net/qq_41446703/article/details/106162050
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞