循环链表CLinkList.h
#include <iostream>
using namespace std;
const int CardNumber=13;
//链表存储结构的定义
typedef struct CLinkList{
int data;
struct CLinkList *next;
}node;
void ShowMenu();
void ShowList(node **pNode);
//初始化
void ds_init(node **pNode);
//插入结点
//参数:链表的第一个结点，插入位置
void ds_insert(node **pNode,int i);
void ds_delete(node **pNode,int i);
int ds_search(node *pNode,int elem);
void Josephus();
//Josephus
node *create(int n);
//判断是否有环，方法1：判断步数
int HasLoop1(node *head);
//判断是否有环，方法2:快慢指针
int HasLoop2(node *head);
//魔术师发牌问题
void Magic();
void DestoryList(node **list);
node *CreateLinkList();
void Magician(node *head);
//拉丁方阵
void latin();
node *CreateLatinList(int num);
void PrintLatin(node *p,int i);
CLinkList.cpp
#include "CLinkList.h"
int main(){
int cmd;
int e;
CLinkList *head=NULL;
ShowMenu();
cin>>cmd;
while(cmd){
switch(cmd){
case 1:
ds_init(&head);
break;
case 2:
ShowList(&head);
break;
case 3:
ds_insert(&head,2);
ShowList(&head);
break;
case 4:
ds_delete(&head,2);
ShowList(&head);
break;
case 5:
cout<<"查找数据:100，位置为:"<<ds_search(head,100)<<endl;
break;
case 6:
Josephus();
break;
case 7:
HasLoop1(head);
break;
case 8:
HasLoop2(head);
break;
case 9:
Magic();
break;
case 10:
latin();
break;
case 0:exit(0);break;
default:
exit(-1);
break;
}
ShowMenu();
cin>>cmd;
}
return 0;
}
void ShowMenu(){
char *str="\t\t****************************";
cout<<str<<endl;
cout<<"\t\t1.初始化"<<endl;
cout<<"\t\t2.显示列表"<<endl;
cout<<"\t\t3.插入元素"<<endl;
cout<<"\t\t4.删除元素"<<endl;
cout<<"\t\t5.查找元素"<<endl;
cout<<"\t\t6.约瑟夫问题"<<endl;
cout<<"\t\t7.步数判断循环"<<endl;
cout<<"\t\t8.快慢指针判断循环"<<endl;
cout<<"\t\t9.魔术师发牌"<<endl;
cout<<"\t\t10.拉丁方阵"<<endl;
cout<<"\t\t0.退出"<<endl;
cout<<str<<endl;
}
void ShowList(node **pNode){
int i=0;
CLinkList *p;
cout<<"\t\t";
for(p=*pNode;p->next!=(*pNode);p=p->next){
if(i%5==0){
cout<<endl;
cout<<"\t\t";
}
cout<<p->data<<" ";
i++;
}
if(i%5==0){
cout<<endl;
cout<<"\t\t";
}
cout<<p->data<<" ";
cout<<endl;
}
void ds_init(node **pNode){
int item;
node *p,*q;
cout<<"输入结点的值，输入0完成初始化"<<endl;
while(1){
scanf("%d",&item);
fflush(stdin);
if(item==0){
return;
}
if(*pNode==NULL){
*pNode=(node *)malloc(sizeof(CLinkList));
(*pNode)->data=item;
(*pNode)->next=(*pNode);
}else{
for(p=*pNode;p->next!=(*pNode);p=p->next);
q=(node *)malloc(sizeof(CLinkList));
q->data=item;
q->next=(*pNode);
p->next=q;
}
}
}
void ds_insert(node **pNode,int i){
node *temp;
node *target;
int j,item;
cout<<"请输入需要插入元素的节点信息:";
scanf("%d",&item);
fflush(stdin);
if(i==1){
temp=(node *)malloc(sizeof(CLinkList));
if(!temp)exit(0);
for(target=*pNode;target->next!=*pNode;target=target->next);
temp->data=item;
temp->next=*pNode;
target->next=temp;
}else{
target=*pNode;
temp=(node *)malloc(sizeof(CLinkList));
if(!temp)exit(0);
j=1;
for(;j<(i-1);++j){
target=target->next;
}
temp->data=item;
temp->next=target->next;
target->next=temp;
}
}
void ds_delete(node **pNode,int i){
node *target;
node *temp;
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 elem){
node *target;
int i=1;
for(target=pNode;target->data!=elem&&target->next!=pNode;++i){
target=target->next;
}
if(target->data==elem){
return i;
}
if(target->next=pNode){
return 0;
}else{
return i;
}
}
node *create(int n){
node *p,*temp,*head;
int i=1;
head=(node *)malloc(sizeof(node));
p=head;
if(n!=0){
while(i<=n){
temp=(node *)malloc(sizeof(node));
temp->data=i++;
p->next=temp;
p=temp;
}
temp->next=head->next;
}
free(head);
ShowList(&(p->next));
return p->next;
}
void Josephus(){
int n=41;
int m=3;
int i;
node *p=create(n);
node *temp;
m%=n;
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);
}
//比较步数的方法
int HasLoop1(node *head){
node *cur1,*cur2;
int pos1,pos2;
pos1=0;
cur1=head;
while(cur1){
pos2=0;
cur2=head;
while(cur2){
if(cur1==cur2){
if(pos1==pos2){
break;
}else{
printf("有环，环的位置在%d处\n",pos2);
return 1;
}
}
cur2=cur2->next;
pos2++;
}
cur1=cur1->next;
pos1++;
}
return 0;
}
//快慢指针
int HasLoop2(node *head){
node *p,*q;
p=q=head;
while(p!=NULL&&q!=NULL&&p->next!=NULL){
p=p->next;
if(p->next!=NULL){
q=q->next->next;
}
printf("p:%d,q:%d\n",p->data,q->data);
if(p==q){
printf("有环链表\n");
return 1;
}
}
return 0;
}
void Magic(){
node *p;
int i;
p=CreateLinkList();
Magician(p);
printf("按如下顺序排序:\n");
for(i = 0; i < CardNumber; i++){
printf("黑桃%d ",p->data);
p=p->next;
}
DestoryList(&p);
}
node *CreateLinkList(){
node *head=NULL;
node *s,*r;
int i;
r=head;
for(i=1; i <= CardNumber; i++){
s = (node *)malloc(sizeof(node));
s->data = 0;
if(head == NULL){
head = s;
}else{
r->next = s;
}
r = s;
}
r->next = head;
return head;
}
//发牌顺序计算
void Magician(node *head){
node *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){
j--;
}
}
if(p->data == 0){
p->data = Countnumber++;
if(Countnumber == 14){
break;
}
}
}
}
//销毁工作
void DestoryList(node **list){
node *ptr=*list;
node *buff[CardNumber];
int i = 0;
while(i < CardNumber){
buff[i++] = ptr;
ptr = ptr->next;
}
for(i=0;i<CardNumber;++i){
free(buff[i]);
}
*list=NULL;
}
//拉丁方阵
void latin(){
node *p;
int num,i;
printf("请输入方阵大小:");
scanf("%d",&num);
fflush(stdin);
p=CreateLatinList(num);
for(i = 0; i< num; i++){
PrintLatin(p,i);
}
}
node *CreateLatinList(int num){
int i;
node *p,*q,*head;
head = (node *)malloc(sizeof(node));
q = p = head;
for(i=1;i<=num;i++){
p = (node *)malloc(sizeof(node));
p->data = i;
q->next = p;
q=p;
}
q->next = head->next;
free(head);
return q->next;
}
void PrintLatin(node *p,int i){
int j;
node *q,*head=p;
for(j = 1;j <= i; j++){
head=head->next;
}
q=head;
while(head->next!=q){
printf("%d ",head->data);
head=head->next;
}
printf("%d ",head->data);
printf("\n");
}
相关推荐
本文将深入探讨如何利用单向链表和双向循环链表来构建这样一个系统。我们将讨论标题中的"航班订票系统"、"单向链表"和"双向循环链表"这些核心概念。 首先，我们来看"单向链表"。单向链表是一种线性数据结构，每个...
在数据结构的世界里，循环链表作为一种特殊类型的链表，因其结构的环状特性而被广泛应用于需要循环访问节点数据的场景中。然而，在一些特定情况下，我们可能需要将循环链表中的元素顺序颠倒过来，这就涉及到了循环...
Linux操作系统中通用双向循环链表的实现分析 Linux操作系统是一个支持多用户、多任务、多线程和多CPU的开源操作系统，其内核功能强大、性能稳定并具有丰富的应用软件支持。Linux内核源代码主要由C语言和少量的汇编...
单循环链表是一种常见的数据结构，它在计算机科学中被广泛用于存储和处理有序或无序的数据序列。链表与数组不同，不依赖于物理位置的连续性，而是通过节点间的引用连接彼此。本篇文章将深入探讨单循环链表的概念、...
循环链表是一种特殊的链表结构，其特点在于链表的最后一个节点的指针域不再指向空，而是指向前一个节点，这样整个链表形成一个闭合的环形结构。在循环链表中，由于没有明显的尾端，因此在进行算法操作时需要特别注意...
循环链表是一种特殊的链式数据结构，其最后一个元素的指针指向了链表的第一个元素，形成一个闭合的环状结构。与线性链表不同，循环链表没有明显的起点和终点，使得在某些场景下遍历和操作更加方便。在C++编程中，不...
循环链表是一种特殊的链式数据结构，它与普通链表的主要区别在于最后一个元素的指针不是指向NULL，而是指向链表的第一个元素，从而形成一个闭合的环状结构。这种设计使得在遍历链表时可以更加高效，因为它可以从任何...
### 数据结构课程设计报告：基于双向循环链表的通讯录设计 #### 概要设计 在沈阳航空航天大学的计算机学院，计算机科学与技术专业的学生冯读庆在其数据结构课程设计中，选择了一个既具挑战性又实用的项目——基于...
双向循环链表是一种高级的数据结构，常用于需要前后移动指针的场景，如实现LRU缓存淘汰策略、编辑器的撤销重做功能等。本项目以C++语言实现了带头结点的双向循环链表，这将有助于我们深入理解这一概念。 首先，双向...
在IT领域，循环链表是一种常见且重要的数据结构，它在程序设计中有着广泛的应用。本文将深入探讨如何使用C语言实现一个基于循环链表的电话本程序。 首先，我们来理解循环链表的基本概念。循环链表与普通链表的主要...
在IT领域，数据结构是计算机科学的基础，循环链表作为一种重要的数据结构，广泛应用于各种算法设计和程序实现中。本文将深入探讨用C++实现的循环链表，包括其概念、特点、操作以及如何在实际编程中应用。 循环链表...
在本课程设计中，学生被要求使用C语言来实现一个基于双向循环链表的通讯录系统。这个系统应具备添加、插入、删除、查询和统计联系人信息的基本功能，并且要具备良好的用户界面和错误处理机制，以确保系统的稳定性和...
这是数据结构的课堂上老师要求我们完成的一个程序 程序实现了关于循环链表的建立与显示
在本实验中，我们利用双向循环链表来实现长整数的存储和四则运算，特别是加法和减法。这种数据结构的选择主要是因为它能够方便地处理长整数的存储和运算过程中的进位和借位操作。 首先，双向循环链表的每个节点仅...
循环链表作为一种重要的数据结构，在计算机科学领域尤其是算法设计与数据管理中扮演着关键角色。相较于普通链表，循环链表在末尾节点指向头节点，形成一个闭环，这一特性使其在某些操作上更为便捷，如遍历整个链表、...
### C语言循环链表的简单应用 #### 一、引言 在计算机科学中，链表是一种常用的数据结构，它由一系列节点组成，每个节点包含数据元素和指向链表中下一个节点的指针。循环链表是链表的一种特殊形式，其中最后一个...
这份名为"图+查找+排序+循环链表+循环链表+数组+广义表+二叉树与树的转换+哈夫曼树.pptx"的文档涵盖了多个关键知识点，下面将对这些主题进行详细解释。 1. **数组**：数组是最基本的数据结构，它允许存储具有相同...
《双向循环链表解决约瑟夫实验报告》 约瑟夫环问题，也称为约瑟夫问题或约瑟夫死亡循环，是一个著名的理论问题。它源于古罗马的一个传说，涉及一组囚犯围成一圈，按照一定的规则淘汰，直到只剩一人存活。在计算机...
双循环链表是一种数据结构，它在单链表的基础上增加了一个前向指针，使得每个节点不仅知道下一个节点，还知道上一个节点。这在处理需要逆向遍历或者需要快速访问相邻节点的问题时非常有用。下面我们将深入探讨双循环...