一、单向循环链表约瑟夫环问题是一个经典的循环链表问题题意是已知 n 个人分别用编号 123…n 表示围坐在一张圆桌周围从编号为 k 的人开始顺时针报数数到 m 的那个人出列他的下一个人又从 1 开始还是顺时针开始报数数到 m 的那个人又出列依次重复下去直到圆桌上剩余一个人。用解决约瑟夫环问题进行杀猴子思想用头指针移动到要杀的猴子的前一个然后跨过指向猴子的节点。#include stdio.h #include stdlib.h #include unistd.h typedef struct node_t { int data; struct node_t *next; }link_node_t,*link_list_t; int main(int argc, const char *argv[]) { int i; link_list_t pdel NULL;//用于指向被删除节点 link_list_t ptail NULL;//永远指向当前链表的尾 link_list_t pnew NULL;//永远指向新创建的节点 link_list_t h NULL; int all_num 7;//猴子总数 int start_num 2; //从几号猴子开始数 int kill_num 3;//数到几杀死猴 printf(请您输入猴子总数 起始号码 数到几杀死:\n); scanf(%d%d%d,all_num,start_num,kill_num); //1.创建出一个单向循环链表 //(1)创建有all_num个节点的单向链表 h (link_list_t)malloc(sizeof(link_node_t)); if(NULL h) { perror(malloc failed); return -1; } h-data 1; h-next NULL; ptail h;//尾指针指向当前的第一个节点 for(i 2; i all_num; i) { //创建新的节点 pnew (link_list_t)malloc(sizeof(link_node_t)); if(NULL pnew) { perror(malloc failed); return -1; } //将新节点装上数据 pnew-data i; pnew-next NULL; //将新节点链接到链表尾 ptail-next pnew;//链接到链表的尾 ptail pnew;//尾指针继续指向当前链表的尾 } //(2)将头指针保存到链表的尾形成单向循环链表 ptail-next h;//形成单向循环链表 #if 0 //用于调试程序 while(1) { printf(%d\n,h-data); h h-next; sleep(1); } #endif //2.开始杀猴子 //(1)将头指针移动到开始猴子的号码处 for(i 1; i start_num; i) h h-next; printf(start :%d\n,h-data); //(2)循环进行杀猴子 while(h ! h-next)//终止就剩一个猴子,只有一个节点 { //将头指针移动到即将删除节点的前一个节点 for(i 1; i kill_num-1; i) h h-next; pdel h-next; //跨过删除节点 h-next pdel-next; printf(kill is -------------%d\n,pdel-data); free(pdel); pdel NULL; //杀死猴子后从下一个节点开始继续开始数,将头指针移动到开始数的地方 h h-next; } printf(king is %d\n,h-data); return 0; }二、栈2.1 什么是栈1. 元素进栈和出栈的操作只能从一端完成另一端是封闭的2. 栈中无论存数据还是取数据都必须遵循“先进后出”的原则即最先入栈的元素最后出栈。以图1的栈为例很容易可以看出是元素1最先入栈然后依次是元素2、3、4入栈。在此基础上如果想取出元素1根据“先进后出”的原则必须先依次将元素4、3、2 出栈最后才轮到元素1出栈。栈是只能在一端进行插入和删除操作的线性表又称为堆栈进行插入和删除操作的一端称为栈顶另一端称为栈底。特点栈是先进后出FILO(First In Last Out)后进先出LIFO(Last In First Out)2.2 顺序栈2.2.1 特性逻辑结构线性结构存储结构顺序存储操作创建、入栈、清空、判空、判满2.2.2 代码实现头文件 seqstack.h#ifndef __SEQSTACK_H__ #define __SEQSTACK_H__ typedef int datatype; typedef struct seqstack { datatype *data; //指向栈的存储位置 int maxlen; //保存栈的最大长度 int top; //称为栈针用的时候可以当作顺序表里的last来使用 //top始终代表当前栈内最后一个有效元素的下标 } seqstack_t; //1.创建一个空栈len代表创建栈时的最大长度。 seqstack_t *createEmptySeqStack(int len); //2.判断是否为满,满返回1 未满返回0 int isFullSeqStack(seqstack_t *p); //3.入栈,data代表入栈的数据 int pushStack(seqstack_t *p, int data); //4.判断栈是否为空 int isEmptySeqStack(seqstack_t *p); //5.出栈返回出栈数据 int popSeqStack(seqstack_t *p); //6. 清空栈 void clearSeqStack(seqstack_t *p); //7. 获取栈顶数据(注意不是出栈操作如果出栈相当于删除了栈顶数据只是将栈顶的数据获取到不需要移动栈针) int getTopSeqStack(seqstack_t *p); //8. 求栈的长度,返回长度。 int lengthSeqStack(seqstack_t *p); #endif1创建一个空栈//1.创建一个空栈len代表创建栈时的最大长度。 seqstack_t *createEmptySeqStack(int len) { // 1. 申请空间存放栈的结构体 seqstack_t *p (seqstack_t *)malloc(sizeof(seqstack_t)); if(NULL p) { printf(createEmptySeqStack p malloc err\n); return NULL; } // 2. 初始化 p-data (datatype *)malloc(sizeof(datatype) * len); if(NULL p-data) { printf(createEmptySeqStack p-data malloc err\n); return NULL; } p-top -1; p-maxlen len; return p; }2判断栈是否为满//2.判断是否为满,满返回1 未满返回0 int isFullSeqStack(seqstack_t *p) { return p-top1 p-maxlen; }3入栈//3.入栈,data代表入栈的数据 int pushStack(seqstack_t *p, int data) { // 1. 容错判断 if(isFullSeqStack(p)) { printf(pushStack err\n); return -1; } // 2. 栈针向上移动 p-top; // 3. 数据入栈 p-data[p-top] data; return 0; }4判断栈是否为空//4.判断栈是否为空 int isEmptySeqStack(seqstack_t *p) { return p-top -1; }5出栈返回出栈数据// 5.出栈返回出栈数据 int popSeqStack(seqstack_t *p) { // 1. 容错判断 if (isEmptySeqStack(p)) { printf(popSeqStack err\n); return -1; } #if 1 return p-data[p-top--]; #else datatype temp p-data[p-top]; p-top--; return temp; #endif }6清空栈// 6. 清空栈 void clearSeqStack(seqstack_t *p) { p-top -1; }7获取栈顶数据// 7. 获取栈顶数据(注意不是出栈操作如果出栈相当于删除了栈顶数据只是将栈顶的数据获取到不需要移动栈针) int getTopSeqStack(seqstack_t *p) { if(isEmptySeqStack(p)) { printf(getTopSeqStack err\n); return -1; } return p-data[p-top];8求栈的长度// 8. 求栈的长度,返回长度。 int lengthSeqStack(seqstack_t *p) { return p-top 1; }2.3 链式栈2.3.1 特性逻辑结构线性结构存储结构链式存储栈的操作创建、入栈、出栈、清空、获取顺序栈和链式栈的区别是: 存储结构不同实现的方式也不同顺序栈用顺序表实现而链栈用链表实现。2.3.2 代码实现头文件linkstack.h#ifndef __LINKSTACK_H__ #define __LINKSTACK_H__ typedef int datatype; typedef struct linkstack { datatype data; struct linkstack *next; } linkstack_t; //1.创建一个空的栈 void createEmptyLinkStack(linkstack_t **ptop); //2.入栈,ptop是传入的栈针的地址data是入栈的数据 int pushLinkStack(linkstack_t **ptop, datatype data); //3.判断栈是否为空 int isEmptyLinkStack(linkstack_t *top); //4.出栈 datatype popLinkStack(linkstack_t **ptop); //5.清空栈 void clearLinkStack(linkstack_t **ptop); //6.求栈的长度 int lengthLinkStack(linkstack_t *top); //7.获取栈顶数据,不是出栈,不需要移动main函数中的top所以用一级指针 datatype getTopLinkStack(linkstack_t *top); #endif1创建空栈//1.创建一个空的栈 void createEmptyLinkStack(linkstack_t **ptop) { *ptop NULL; }2入栈//2.入栈,ptop是传入的栈针的地址data是入栈的数据 int pushLinkStack(linkstack_t **ptop, datatype data) { // 1. 创建一个新节点保存即将入栈的数据 linkstack_t *pnew (linkstack_t *)malloc(sizeof(linkstack_t)); if(NULL pnew) { printf(pushLinkStack err\n); return -1; } // 2. 初始化 pnew-data data; pnew-next NULL; // 将新节点插入到无头节点的前面 pnew-next *ptop; *ptop pnew; return 0; }3判断栈是否为空//3.判断栈是否为空 int isEmptyLinkStack(linkstack_t *top) { return top NULL; }4出栈//4.出栈 datatype popLinkStack(linkstack_t **ptop) { linkstack_t *pdel NULL; // 1. 容错判断 if(isEmptyLinkStack(*ptop)) { printf(popLinkStack err\n); return -1; } // 2. 定义一个临时变量保存出栈的数据也就是栈针指向节点中的数据域 datatype temp (*ptop)-data; // 3. 定义一个pdel指向出栈的节点也就是栈针指向的节点 pdel *ptop; // 4. 将栈针向后移动一个位置 (*ptop) (*ptop)-next; // 5. 释放出栈节点 free(pdel); pdel NULL; // 6. 返回出栈数据 return temp; }5清空栈//5.清空栈 void clearLinkStack(linkstack_t **ptop) { while(!isEmptyLinkStack(*ptop)) printf(%d , popLinkStack(ptop)); printf(\n); }6求栈的长度//6.求栈的长度 int lengthLinkStack(linkstack_t *top) { int len 0; while(top ! NULL) { len; top top-next; } return len; }7获取栈顶数据//7.获取栈顶数据,不是出栈,不需要移动main函数中的top所以用一级指针 datatype getTopLinkStack(linkstack_t *top) { if(isEmptyLinkStack(top)) { printf(getTopLinkStack err\n); return -1; } return top-data; }总结顺序栈和链式栈的区别是什么存储结构不同顺序栈是顺序存储内存连续链表是链式存储内存不连续。顺序栈的长度受限制而链栈不会。