约瑟夫问题介绍约瑟夫问题，又称约瑟夫置换、丢手绢问题。一般形式（本部分内容来自百度百科）约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3。代码问题描述本文以以下问题为例编号为1-10的10 个人围成一圈，从第一个开始报数，第9个被淘汰出圈，剩下的组成新的圈。依次这样下去，求最后一个人的编号解决注意：该段代码与上篇文章——《 循环链表定义及操作 》相接//解答约瑟夫问题 bool Joseph(LinkList* &L, int interval) { LinkList *p = L, *q; int i = 0, j = 0; int times = 0; //当前轮数 int num = 0; if(!L || p->next == L) { cout << "链表为空\n"; return false; } if(interval < 1) { cout << "报数淘汰口令不能小于1\n"; return false; } do{ i += interval; //找查第i个结点，p指向该结点的上一个结点 while(p->next){ if(p->next != L) { //如果不是头结点的话 j++; } if(j >= i) break; p = p->next; } times++; q = p->next; //临时保存被删结点以备释放空间 num = q->data; cout << "当前结点:" << q->data << " 上一个结点:" << p->data <<" 下一个结点:" << q->next->data << endl; p->next = q->next; delete q; //释放被删除结点内存 LinkListPrint(L); }while(L->next != L); //链表不为空，继续报数 cout << "最后一个出圈者的编号" << num << endl; return true; }完整代码代码#include <iostream> #include <string> using namespace std; typedef struct _LinkNode { int data; struct _LinkNode *next; }LinkList; bool InitList(LinkList* &L) { L = new LinkList; if(!L) return false; L->next = L; L->data = 0; return true; } bool ListInsert_back(LinkList* &L, LinkList *node) { LinkList *last = NULL; if(!L || !node) return false; if(L == L->next) { //头结点指针指向了自己（链表只有头结点） node->next = L; L->next = node; }else{ //非空的循环链表 last = L->next; //寻找尾结点（指向头结点的结点） while(last->next != L) { last = last->next; } node->next = L; last->next = node; } return true; } void LinkListPrint(LinkList *L) { LinkList *p; if(!L || L == L->next) { cout << "链表为空\n"; return; } p = L->next; while(p != L) { cout << p->data << "\t"; p = p->next; } cout << endl; } //解答约瑟夫问题 bool Joseph(LinkList* &L, int interval) { LinkList *p = L, *q; int i = 0, j = 0; int times = 0; //当前轮数 int num = 0; if(!L || p->next == L) { cout << "链表为空\n"; return false; } if(interval < 1) { cout << "报数淘汰口令不能小于1\n"; return false; } do{ i += interval; //找查第i个结点，p指向该结点的上一个结点 while(p->next){ if(p->next != L) { //如果不是头结点的话 j++; } if(j >= i) break; p = p->next; } times++; q = p->next; //临时保存被删结点以备释放空间 num = q->data; cout << "当前结点:" << q->data << " 上一个结点:" << p->data <<" 下一个结点:" << q->next->data << endl; p->next = q->next; delete q; //释放被删除结点内存 LinkListPrint(L); }while(L->next != L); //链表不为空，继续报数 cout << "最后一个出圈者的编号" << num << endl; return true; } int main() { LinkList *L, *s; int i = 0; if(InitList(L)) { cout << "创建一个空的循环链表\n"; }else{ exit(-1); } cout << "尾插10个元素...\n"; while((++i)<=10) { s = new LinkList; s->data = i; s->next = NULL; if(ListInsert_back(L, s)) { cout << "success\n"; }else{cout << "default\n";} } LinkListPrint(L); Joseph(L,9); return 0; } 输出结果注：0为头结点的数据，该结点并不计入约瑟夫环中（但最后也将其删除销毁链表释放内存）创建一个空的循环链表 尾插10个元素... success success success success success success success success success success 1 2 3 4 5 6 7 8 9 10 当前结点:9 上一个结点:8 下一个结点:10 1 2 3 4 5 6 7 8 10 当前结点:8 上一个结点:7 下一个结点:10 1 2 3 4 5 6 7 10 当前结点:10 上一个结点:7 下一个结点:0 1 2 3 4 5 6 7 当前结点:2 上一个结点:1 下一个结点:3 1 3 4 5 6 7 当前结点:5 上一个结点:4 下一个结点:6 1 3 4 6 7 当前结点:3 上一个结点:1 下一个结点:4 1 4 6 7 当前结点:4 上一个结点:1 下一个结点:6 1 6 7 当前结点:1 上一个结点:0 下一个结点:6 6 7 当前结点:6 上一个结点:0 下一个结点:7 7 当前结点:7 上一个结点:0 下一个结点:0 链表为空 最后一个出圈者的编号7
循环链表定义定义与单链表一样，操作时将末结点的指针指向开始结点即可typedef struct _LinkNode { int data; struct _LinkNode *next; }LinkList;循环链表操作初始化循环链表bool InitList(LinkList* &L) { L = new LinkList; if(!L) return false; L->next = L; L->data = 0; //往头结点塞个数据，这时候严格来讲为无头结点循环链表，第一个结点应该叫开始结点 return true; }插入（尾插）bool ListInsert_back(LinkList* &L, LinkList *node) { LinkList *last = NULL; if(!L || !node) return false; if(L == L->next) { //头结点指针指向了自己（链表只有头结点） node->next = L; L->next = node; }else{ //非空的循环链表 last = L->next; //寻找尾结点（指向头结点的结点） while(last->next != L) { last = last->next; } node->next = L; last->next = node; } return true; }输出数据void LinkListPrint(LinkList *L) { LinkList *p; if(!L || L == L->next) { cout << "链表为空\n"; return; } p = L->next; while(p != L) { cout << p->data << "\t"; p = p->next; } cout << endl; }
单链表代码定义typedef struct LinkNode { int data; //data存放结点的数据域（以int类型为例） struct LinkNode *next; //结点的指针域 }LinkNode, LinkList;单链表的操作初始化单链表bool initList(LinkList* &L) //L类型为引用类型的指针 { L = new LinkNode; //为L分配一个动态内存 if(!L) return false; //若分配失败则返回false //头结点指针指向空完成初始化，成功创建一个空的单链表并返回true L->next = NULL; return true; }插入结点注： L为插入的单链表，node为将要插入的结点前插法bool ListInsert_front(LinkList* &L, LinkNode *node) { //合法性检查 if(!L || !node) return false; node->next = L->next; //把新结点指针指向原来头结点所指向的结点 L->next = node; //把头结点指向新结点 }尾插法bool ListInsert_back(LinkList* &L, LinkList *node) { LinkNode *last = NULL; if(!L || !node) return false; last = L; //找到尾结点 while(last->next) last = last->next; //重置指针 node->next = NULL; last->next = node; return true; }任意位置插入//任意位置插入 /* * 参数： 要插入的单链表， 位置， 取值 */ bool LinkInsert(LinkList* &L, int i, int &e) { if(!L) return false; int j = 0; LinkList *p, *s; p = L; //让p寻找插入位置 while(p && j<i-1) { p = p->next; j++; } //如果插入位置大于链表节点数，最后p为空 //有一种情况为：若i <= 0 ,j<i-1不成立，但此时p为真，所以这里使用 !p || j>i-1 if(!p || j>i-1) { return false; } //当i = 0时，p为真且 j = i - 1， 此时指向头结点，直接来到下方这一步 s = new LinkNode; //生成新结点 //连接结点 s->data = e; //保存数据 s->next = p->next; p->next = s; return true; }输出单链表中的元素void LinkPrint(LinkList* &L) { LNode *p = NULL; if(!L) { cout << "此链表为空\n"; return; } p = L->next; while(p) { cout << p->data << "\t"; p = p->next; } cout << endl; }元素找查按位置查找与任意位置插入类似，只不过要注意访问头结点的情况（带头结点的单链表头结点数据域无初始化数据）/* * 参数： 单链表， 位置， 取值 */ bool GetLinkListElemAsAddress(LinkList* &L, int i, int &e) { if(!L || !L->next) return false; int j = 0; LinkList *p; p = L; while(p && j < i-1) { p = p->next; j++; } if(!p || j >= i - 1) //这里取等号是为了避免访问头结点数据 { return false; } e = p->data; return true; } 按值查找/* * 带头结点的单链表L中找查值为e的元素 * 参数：单链表， 取值, 返回所找元素的位置 */ bool GetLinkListElemAsValue(LinkList *L, int e, int &index) { LinkList *p; p = L->next; index = 1; if(!L || !L->next) { index = 0; return false; } while(p && p->data! = e) { p = p->next; index++; } if(!p) { index = 0; return false; //查无此值 } return true; }结点的删除bool LinkListDel(LinkList* &L, int i) { LinkList *p, *q; int index = 0; p = L; //合法性检查 if(!L || !L->next) { return false; } while((p->next) && (index < i-1)) { p = p->next; index++; } //删除位置不合理 if(!p->next || (index > i - 1)) { return false; } q = p->next; //临时存放被删结点地址 p->next = q->next;//改变删除结点前驱指针域 delete q; return true; }单链表的销毁分配动态内存后，记得销毁void LinkDestory(LinkList* &L) { //定义临时结点指向头结点 LinkList *p = L; cout << "销毁链表" << endl; //遍历并删除结点 while(p) { L = L->next; delete p; p = L; } }
链表链表的概念定义：链表是一种物理存储单元上非连续、非顺序的存储结构，由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。在链表的储存上，每个结点不仅包含所存的元素信息，还包含元素间的逻辑信息。链表的特性不支持随机访问：不能通过知道第一个元素的地址（即储存空间的首地址）可以轻松访问储存的所有数据。节点的储存空间利用率相对顺序表较低：链表中的每分一个结点需要划出一部分空间来储存指向下一个结点位置的指针支持储存空间的动态分配：链表中当前结点的位置是由其前驱结点中的地址信息所指示的。其结点可以散落在内存中的任意位置，且不需要一次性地划分所有结点所需的空间给它。在链表中进行插入操作无需移动元素（而顺序表需要）链表的形式单链表在每个结点除了包含的数据域外，还包含一个指针域，用以指向其后继结点。带头结点的单链表带头结点的单链表中，头指针head指向头结点，头结点的值域不含任何信息，从头结点的后继结点开始储存信息。头指针head 始终不等于NULL，head->next等于NULL的时候，链表为空。不带头结点的单链表不带头结点的单链表中的头指针head直接指向开始结点，当head等于NULL时，链表为空。双链表双链表就是在单链表结点上增添了一个指针域，指向当前节点的前驱。相比于单链表，双链表能够从终端结点反向走到开始结点。循环链表循环单链表只需要将单链表最后一个指针域（空指针）指向链表中的第一个结点即可。（如果循环单链表带头结点，则指向头结点；不带头结点，则指向开始结点）。循环单链表可以实现从任何一个结点出发，访问链表中任何结点。（注意：此处应该区分与顺序表随机访问的特点。循环单链表指的是从一个结点出发，而不是知道一个结点从而迅速找到任何一个结点，因此循环单链表不具有随机访问特性。）带头结点的循环单链表，当head等于head->next时，链表为空；不带头结点的循环单链表，当head等于NULL时，链表为空。循环双链表双链表终端节点的next指针指向链表中第一个结点，将链表中的第一个结点的prior指针指向终端结点。不带头结点的循环双链表，head等于NULL，链表为空带头结点的循环双链表是没有空指针的，其为空状态下，head->next与head->prior必然都等于head，故一下四种语句都可判断为空head->next == head; head->prior == head; head->next == head && head->prior == head; head->next == head || head->prior == head;静态链表静态链表借助一维数组表示。静态链表结点空间来自于一个结构体数组（一般链表结点空间来自整个内存），数组中每个结点含两个分量：数据元素分量data指针分量（指示了当前结点直接后继节点在数组中的位置）注意：静态链表的指针不是通常所说储存内存地址的指针型变量，而是储存数组下标的整型变量，其功能类似于指针，故在此称为指针顺序表与链表区别基于空间比较储存的分配方式顺序表储存空间时一次性分配的，链表的是多次分配的存储密度（注： 存储密度 = 结点值域所占存储量/结点结构所占存储总量）顺序表存储密度 = 1链表存储密度 < 1基于时间的比较存取方式顺序表可以随机存取，也可以顺序存取链表只能顺序存取插入/删除时移动元素个数顺序表平均需要移动一半元素链表不需要移动元素，仅需修改指针