单向循环链表的操作
main函数：
#ifndef __loopLinkList_H__
#define __loopLinkList_H__
typedef int datatype;
union msg{ //若数据的类型也为int，则不需要这个联合体
datatype data;
int len; //放头结点，记录链表长度
};
typedef struct node{
union msg text;
struct node* next; //指针，由于指针指向这一整个节点，所以类型为struct node*
}loopLinkList;
loopLinkList* create_loopLinkList(void);
void insertHead_loopLinkList(loopLinkList* head,datatype num);
void insertTail_loopLinkList(loopLinkList* head,datatype num);
void deleteHead_loopLinkList(loopLinkList* head);
void deleteTail_loopLinkList(loopLinkList* head);
void show_loopLinkList(loopLinkList* head);
#endif
功能函数：
#include<stdio.h>
#include <stdlib.h>
#include "./13_loopLinkList.h"
//创建一个单向循环链表
loopLinkList* create_loopLinkList()
{
//定义头结点并初始化
loopLinkList* head=(loopLinkList*)malloc(sizeof(loopLinkList));
head->next=head;
head->text.len=0;
return head;
}
//判断链表是否为空
int isEmpty_loopLinkList(loopLinkList* head)
{
//1表示链表为空，0表示链表不为空
return head->next==head?1:0;
}
//头插
void insertHead_loopLinkList(loopLinkList* head,datatype num)
{
//申请一个空间定义一个新的结点
loopLinkList* temp=(loopLinkList*)malloc(sizeof(loopLinkList));
if(NULL == temp)
{
printf("结点定义失败！n");
return;
}
//初始化这个结点
temp->text.data=num;
temp->next=NULL;
//插入
temp->next=head->next;
head->next=temp;
head->text.len++;
return;
}
//尾插
void insertTail_loopLinkList(loopLinkList* head,datatype num)
{
//申请一个空间定义一个新的结点
loopLinkList* temp=(loopLinkList*)malloc(sizeof(loopLinkList));
if(NULL == temp)
{
printf("结点定义失败！n");
return;
}
//初始化这个结点
temp->text.data=num;
temp->next=NULL;
//找到链表最后一个结点
loopLinkList* p=head;
while(p->next!=head)
{
p=p->next;
}
//插入temp
temp->next=head;
p->next=temp;
head->text.len--;
return;
}
//按位置插入
void insertByPositon_loopLinkList(loopLinkList* head,datatype num,int pos)
{
if(pos<1 || pos >head->text.len+1)
{
printf("插入位置不合法！n");
}
loopLinkList* temp = (loopLinkList*)malloc(sizeof(loopLinkList));
temp->text.data=num;
temp->next=NULL;
loopLinkList* p=head;
int i;
for(i=0;i<pos-1;i++)
{
p=p->next;
}
temp->next=p->next;
p->next=temp;
head->text.len++;
return;
}
//头删
void deleteHead_loopLinkList(loopLinkList* head)
{
if(isEmpty_loopLinkList(head))
{
printf("链表为空,删除失败！n");
return;
}
loopLinkList* temp=head->next;
head->next=temp->next;
free(temp);
head->text.len--;
return;
}
//尾删
void deleteTail_loopLinkList(loopLinkList* head)
{
if(isEmpty_loopLinkList(head))
{
printf("链表为空,删除失败！n");
return;
}
loopLinkList* p=head;
while(p->next->next!=head)
{
p=p->next;
}
free(p->next);
p->next=head;
head->text.len--;
return;
}
//按位置删除
void deleteBypos_loopLinkList(loopLinkList* head,int pos)
{
if(isEmpty_loopLinkList(head))
{
printf("链表为空,删除失败！n");
return;
}
loopLinkList* p=head;
int i;
for(i=0;i<pos-1;i++)
{
p=p->next;
}
free(p->next);
p->next=p->next->next;
head->text.len--;
return;
}
//遍历
void show_loopLinkList(loopLinkList* head)
{
loopLinkList* p=head;
if(isEmpty_loopLinkList(head))
{
printf("链表为空！n");
return;
}
while(p->next!=head)
{
p=p->next;
printf("%d ",p->text.data);
}
printf("n");
return;
}
//约瑟夫问题
void josepg_loopLinkList(int n ,int k,int m)
{
loopLinkList* head = create_loopLinkList();
//将1到n的数据插入到循环列表中
int i=0;
for(i=1;i<=n;i++)
{
insertTail_loopLinkList(head,i);
}
//删除头结点，将头指针指向头结点后的第一个有效数据
loopLinkList* p=head;
while(p->next!=head)
{
p=p->next;
}
//p就是当前链表的尾结点
//移动头指针到第一个有效数据
head=head->next;
//释放头结点
free(p->next);
//将尾结点的指针指向第一个有效数据
p->next=head;
//通过循环找到编号为1的位置
p=head;
for(i=0;i<k-1;i++)
{
p=p->next;
}
//p就是编号为1的位置
while(p->next != p)//当链表中只有一个结点时退出循环
{
//找到要出列的那个数的前一个结点
for(i=0;i<m-2;i++)
{
p=p->next;
}
//p就是要出列的前一个结点
//将要数列的那个结点存起来，后面方便释放
loopLinkList* temp = p->next;
//将p的指针域指向要出列的结点的下一个结点，即将要出列的那个节点删除
p->next = temp->next;
//打印出列的结点里面的数
printf("%d ",temp->text.data);
//释放该结点
free(temp);
temp=NULL;
//将刚刚出队的下一个结点置为1
p=p->next;
}
//上述循环后，整个链表中还剩一个结点
printf("%dn",p->text.data);
free(p);
p=NULL;
}
头文件：
#ifndef __loopLinkList_H__
#define __loopLinkList_H__
typedef int datatype;
union msg{ //若数据的类型也为int，则不需要这个联合体
datatype data;
int len; //放头结点，记录链表长度
};
typedef struct node{
union msg text;
struct node* next; //指针，由于指针指向这一整个节点，所以类型为struct node*
}loopLinkList;
loopLinkList* create_loopLinkList(void);
void insertHead_loopLinkList(loopLinkList* head,datatype num);
void insertByPositon_loopLinkList(loopLinkList* head,datatype num,int pos);
void insertTail_loopLinkList(loopLinkList* head,datatype num);
void deleteHead_loopLinkList(loopLinkList* head);
void deleteTail_loopLinkList(loopLinkList* head);
void show_loopLinkList(loopLinkList* head);
void josepg_loopLinkList(int n,int k,int m);
void deleteBypos_loopLinkList(loopLinkList* head,int pos);
#endif