单向循环链表的操作
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;//将刚刚出队的下一个结点置为1p=p->next;}//上述循环后，整个链表中还剩一个结点printf("%d\n",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