数据结构之循环链表

循环链表

文章目录：

引述循环链表的特点循环单链表和循环双链表的初始化循环单链表的头插法和尾插法循环链表的应用（拓展）

3.循环单链表和循环双链表的初始化

4.循环单链表的头插法和尾插法

#include <stdio.h> #include <stdlib.h> typedef struct node { int data; struct node *next;//指针域 int size;//循环链表的长度 }node,*linklist;//linklist为定义的指针结构体变量 void create_list_head(linklist *l)//头插法建立循环链表 { int i,j,x; linklist p,q; printf("please input length"); scanf("%d",&j); (*l)=(node*)malloc(sizeof(node)); (*l)->next=NULL;//必须定义，缺少error (*l)->size=j; for(i=0;i<j;i++)//头插法输入数据 { scanf("%d",&x); p=(node*)malloc(sizeof(node)); p->data=x; p->next=(*l)->next; (*l)->next=p; } //q=(node*)malloc(sizeof(node)); q=(*l)->next; while(q->next!=NULL)//找到最后一个结点 { q=q->next; } //printf("%d",q->data); q->next=(*l)->next;//将最后一个结点指向第一个结点 } void create_list_tail(linklist *l)//尾插法建立循环链表 { int i,j,x; linklist p,r,t; printf("please input the length"); scanf("%d",&j); (*l)=(node*)malloc(sizeof(node)); (*l)->next=NULL; (*l)->size=j; t=(*l); for(i=0;i<j;i++) { scanf("%d",&x); p=(node*)malloc(sizeof(node)); p->data=x; t->next=p; t=p;//每新建一个结点在结束时都为最后一个结点，下一个节点在这个结点后面插入 } t->next=NULL; r=(*l)->next; while(r->next!=NULL) { r=r->next; } r->next=(*l)->next; } void print_list_he(linklist *l)//打印输出 { int i; linklist p; p=(*l)->next; for(i=0;i<(*l)->size;i++) { printf("%d\n",p->data); p=p->next; } } int main() { linklist a; create_list_head(&a); create_list_tail(&a); print_list_he(&a); return 0; }

5.循环链表的应用

1.约瑟夫问题 #include <stdio.h> #include <stdlib.h> typedef struct node { int data; struct node *next; }LinkNode; LinkNode *create(int n);//创建循环链表，没有头结点，没有头指针，只有尾指针 int main() { int n = 41;//总人数 int m = 3;//报数周期 int i;//循环 LinkNode *p = create(n);//创建循环链表，没有头结点，没有头指针，只有尾指针，指针p指向第一结点 LinkNode *q; m %= n;//m==3 while (p != p->next)//当p不是只有一个结点的链表的时候 { for (i = 1; i < m - 1; i++)//便于m的修改 { p = p->next;//指针p指向报数的前一个结点 } printf("%d->", p->next->data);//打印报数的结点 q = p->next;//指针q指向报数的结点 p->next = q->next;//跳过报数的结点 free(q);//删除结点 p = p->next;//指针p移动 } printf("\n最后一个结点是%d\n", p->data);//最后一个结点 return 0; } LinkNode *create(int n)//创建循环链表，没有头结点，没有头指针，只有尾指针 { LinkNode *head = (LinkNode *)malloc(sizeof(LinkNode)); LinkNode *p = head; LinkNode *ne = NULL; int i = 0;//循环 for (i = 1; i <= n; i++) { ne= (LinkNode *)malloc(sizeof(LinkNode)); ne->data = i; p->next = ne; p = ne; } ne->next = head->next;//最后的结点指针指向第一个结点，形成循环链表 free(head);//删除头指针 return ne->next;//返回第一个结点 } 2.连接两个线性表·

3判断单链表是否有环

//具体代码 #include<stdio.h> #include<stdlib.h> #include<time.h> #define ERROR 0 #define OK 1 #define TRUE 1 #define FALSE 0 typedef int Status; typedef int ElemType; typedef struct Node { ElemType data; struct Node *next; } Node,*Linklist; Status init(Linklist *L) { *L=(Linklist)malloc(sizeof(Node)); if(!(*L)) return ERROR; (*L)->next=NULL; return OK; } int Listlength(Linklist L) { int i=0; Linklist p=L->next; while(p) { i++; p=p->next; } return i; } void Createlisthead(Linklist *L,int n) { Linklist p; int i; srand(time(0)); *L=(Linklist)malloc(sizeof(Node)); (*L)->next=NULL; for(i=0;i<n;i++) { p=(Linklist)malloc(sizeof(Node)); p->data=rand()%100+1; p->next=(*L)->next; (*L)->next=p; printf("%5d",p->data); } } void Createlisttail(Linklist *L,int n) { Linklist p,r; int i; srand(time(0)); *L=(Linklist)malloc(sizeof(Node)); r=*L; for(i=0;i<n;i++) { p=(Node *)malloc(sizeof(Node)); p->data=rand()%100+1; r->next=p; r=p; printf("%5d",p->data); } r->next=(*L)->next->next;//尾部指向第二个结点 } //比较步数的方法 int Loop1(Linklist L) { Linklist cur1=L;//定义结点cur1 int pos1=0;//初始化cur1的步数 while(cur1)//如果cur1结点存在 { Linklist cur2=L;//定义结点cur2； int pos2 =0;//初始化cur2的步数； while(cur2) //cur2结点不为空 { if(cur2=cur1) { if(pos1=pos2) { break; } else { printf("环的位置是在第%d个结点处\n",pos2); return 1; } } cur2=cur2->next; pos2++; } cur1=cur1->next; pos1++; } return 0; } //利用快慢指针的方法判断单链表有环无环 int Loop2(Linklist L) { int step1=1; int step2=2; Linklist p=L; Linklist q=L; while(p!=NULL && q!=NULL && q->next!=NULL) { p=p->next; if(q->next!=NULL) q=q->next->next; printf("p:%d,q:%d\n",p->data,q->data); if(p==q) return 1; } return 0; } int main() { Linklist L; Status i; char opp; ElemType e; int find; i=init(&L); printf("初始化L后：Listlength(L)=%d\n",Listlength(L)); printf("\n 1.创建有环链表（尾插法) \n 2.创建无环链表(头插法)\n 3.判断链表是否有环\n 0.退出\n\n"); while(opp!='0') { printf("请输入opp序号\n\n"); scanf("%c",&opp); switch(opp) { case '1': Createlisttail(&L,10); printf("成功创建有环L(尾插法)\n"); printf("\n"); break; case '2': Createlisthead(&L,10); printf("成功创建无环L，(头插法)\n"); printf("\n"); break; case '3': printf("方法一：比较步数\n\n"); if(Loop1(L)) { printf("链表有环\n\n"); } else { printf("链表无环\n\n"); } printf("方法2：快慢指针\n\n"); if(Loop2(L)) { printf("链表有环\n\n"); } else { printf("链表无环\n\n"); } printf("\n"); break; case '0': exit(0); } } } 4魔术师发牌问题

#include<stdio.h> #include<stdlib.h> #define cardnumber 13 typedef struct node { int data; struct node *next; }sqlist,*linklist; linklist init() { linklist head=NULL;//声明头结点 linklist s,r;//建立结点 int i; r=head;//声明指向头结点的结点 for(i=1;i<=cardnumber;i++) { s=(linklist)malloc(sizeof(node)); s->data=0;//将链表内的所有元素置0； if(head==NULL) head=s; else r->next=s;//尾插法建立链表 r=s; } r->next=head;//循环到最后一个元素时，将最后一个结点指向头结点，形成单循环链表 } void magic(linklist head) { linklist 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; countnumber++; if(countnumber==14) break; } } } int main() { linklist p; int i; p=init(); magic(p); printf("按如下顺序排列：\n"); for(i=0;i<cardnumber;i++) { printf("黑桃%d",p->data); p=p->next; } return 0; } 5拉丁方阵问题

#include<stdio.h> #include<stdlib.h> typedef struct Node{ int data; struct Node* next; }Node,*LinkList; void CreateSimpleCycleList_tail(LinkList *L,int number){ /* 创建一个单循环链表，没有头结点，尾指针指向第一个节点。 * */ int count; LinkList ne,temp; *L = (LinkList)malloc(sizeof(struct Node)); if(!(*L)){ printf("Error:malloc\n"); exit(1); } (*L)->next = *L; //初始化了循环链表 for(count = 1; count <= number; count++ ){ ne= (LinkList)malloc(sizeof(struct Node)); if(!ne){ printf("Error:malloc\n"); exit(1); } ne->data = count; ne->next = (*L)->next; (*L)->next = ne; *L = ne; } //创建了单循环链表，有头结点 temp = (*L)->next;//建立头结点 (*L)->next = temp->next;//链接成单循环链表 *L = temp->next;//将*L指针一直指向循环后 下一个元素 free(temp); //将头结点删除 } void ShowLatinSquare(LinkList L,int number){ /* * 输出拉丁方阵：count_Out是外循环计数共number次(number是单链表的长度)， * 是控制拉丁方阵的行数。count_In是内循环的次数，共number次，输出每一行。 * */ int count_Out = 1,count_In; LinkList temp = L; while(count_Out <= number){ count_In = 1; while(count_In <= number){ printf("%d ",L->data); count_In++; L = L->next; } printf("\n"); L = L->next; //输出完一行后，L要后移两个位置 //但是48行代码已经移动一个，在这 //后移一个即可。 count_Out++; } } int main(){ int order; LinkList L; printf("please enter the order of Latin Square: "); scanf("%3d",&order); CreateSimpleCycleList_tail(&L,order); ShowLatinSquare(L,order); return 0; }

看到这里，循环链表的知识就整理完了，之后会更新静态链表的相关知识！