循环链表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");
}
相关推荐
利用双向循环链表来实现对长整数的存储。每个节点只存储四位十进制数字。选择该数据结构来完成长整数的加减运算是因为要对长整数进行运算，需要对长整数进行存储，所以选择用链表对长整数存储，又由于存储的顺序是从...
这是数据结构的课堂上老师要求我们完成的一个程序 程序实现了关于循环链表的建立与显示
课件主要讲了循环链表，双向链表的操作，插入，删除等 循环链表、双向链表及线性表应用示例
循环链表 实现约瑟夫环 java 自己写的 测试通过 有注释
利用双向循环链表作为储存结构设计并实现一个通讯录程序。可以实现信息的添加、插入、删除、查询和统计等功能 1.2 课程设计要求 （1） 每条信息至少包含：姓名（name）、街道（street）、城市（city）、邮编、（eip...
用Java定义一个循环链表，实现链表的基本操作： 初始化*、获取头结点、添加新元素*、删除链表元素 、获取链表元素*、查找链表元素*、更新链表中某个元素、 判断链表是否为空、求链表元素个数、输出链表元素、清空...
图+查找+排序+循环链表+循环链表+数组+广义表+二叉树与树的转换+哈夫曼树
一、实验题目：循环链表的实现 二、实验目的： 1、实现循环表中插入函数add和addlast函数 2、实现循环表中的复制函数duplicate函数，查找元素函数includes，判空函数isEmpty和删除第一个元素函数removeFirst及删除...
设计算法以判断一个带头结点的单循环链表是否满足这样的条件，其中每个节点的元素值与其序号的差的绝对值不大于3.若成立，返回TRUE,否则返回FALSE，任务利用递增有序地单循环链表表示集合，分别求两个链表表示的集合...
通过循环链表实现约瑟夫环问题，用c语言实现。属于数据结构部分内容
双向循环链表解决约瑟夫实验报告， 双向循环链表解决约瑟夫实验报告 双向循环链表解决约瑟夫实验报告双向循环链表解决约瑟夫实验报告
使用c语言中的循环链表及结构体实现约瑟夫环问题
数据结构课程设计报告基于双向循环链表的通讯录设计
几乎不使用库函数，利用数据结构知识和C语言来写的循环链表电话本小程序
循环链表的基本操作 一、实验目的 熟练掌握线性表的基本操作在链式循环存储结构上的实现。 二、实验内容 1、在上一次单链表基本操作的基础上，修改程序，将其改为单循环链表，并实现相关操作。 （1）初始化单循环...
约瑟夫环的问题描述 ...一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针...利用单循环链表作为存储结构模拟此过程； ⑵．键盘输入总人数、初始报数上限值m及各人密码； ⑶．按照出列顺序输出各人的编号。
设计算法依次访问无头结点的单循环链表的各结点.设计算法以判断一个带头结点的单循环链表是否满足这样的条件：其中每个结点的元素值与其序号的差的绝对值不大于３。若成立, 返回TRUE, 否则返回FALSE。利用递增有序的...
合并有序单循环链表，不重新申请存储空间； 创建有序单循环链表，并指向尾结点； 新单循环链表的指针指向尾结点；
循环链表的实现，包括查找删除修改的实现，其中详细介绍了循环链表的原理，以及各个部分的代码实现
用循环链表的方式实现约瑟夫环，下面是部分代码， typedef struct node { int key; int seatnum; struct node *next; }node,*linklist; void createlist(linklist&l,int n) { l=(linklist)malloc(sizeof(node));...