wordpress 新手指南/网站seo外包

问题描述 :

目的：使用C++模板设计循环链表的抽象数据类型（ADT）。并在此基础上，使用循环链表ADT的基本操作，设计并实现单链表的简单算法设计。

内容：

（1）请使用模板设计循环链表的抽象数据类型。（由于该环境目前仅支持单文件的编译，故将所有内容都集中在一个源文件内。在实际的设计中，推荐将抽象类及对应的派生类分别放在单独的头文件中。参考网盘中的单链表ADT原型文件，自行设计循环链表的ADT。）

 

（2）ADT的简单应用：使用该ADT设计并实现循环链表应用场合的一些简单算法设计。

应用2：编号为1,2,...,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。现在给定一个随机数m>0，从编号为1的人开始，按顺时针方向1开始顺序报数，报到m时停止。报m的人出圈，同时留下他的密码作为新的m值，从他在顺时针方向上的下一个人开始，重新从1开始报数，如此下去，直至所有的人全部出列为止。请在使用循环链表ADT的基础上，设计一个算法求出圈的顺序（以编号表示）。限定人数至少为1.

参考函数原型：

template<class ElemType>

void Joseph(CirLinkList<ElemType> &A, int m);

 

//约瑟夫环专用结点类型

struct node{

    int number;

    int code;

};

 

输入说明 :

第一行：人数n

第二行：每个人所持的密码

第三行：给定的随机数m

输出说明 :

第一行：建立的循环链表的遍历结果（数据格式见测试数据范例）

空行

第三行：出圈的顺序（编号与编号之间以“->”分隔）

输入范例 :

7 
3 8 1 22 4 9 15
5

输出范例 :

(1,3)->(2,8)->(3,1)->(4,22)->(5,4)->(6,9)->(7,15)

5->2->6->7->4->3->1

解题代码： 

// 循环链表.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <sstream>
#include <stack>
#include <map>
#include <ctime>
#include <array>
#include <set>
#include <list>
using namespace std;
template<class ElemType>
struct LinkNode
{ElemType data;LinkNode<ElemType>* next;LinkNode(LinkNode<ElemType>* ptr = NULL) { next = ptr;  //构造函数1，用于构造头结点}LinkNode(const ElemType& item, LinkNode<ElemType>* ptr = NULL) {//构造函数2，用于构造其他结点   //函数参数表中的形参允许有默认值，但是带默认值的参数需要放后面next = ptr;data = item;}//int getNum(){ return number; } //取得结点的序号 ElemType getData() { return data; //取得结点的数据域的值 }   void SetLink(LinkNode<ElemType>* link) { next = link; //修改结点的next域 } void SetLink(ElemType value) { data = value; //修改结点的next域} 
};
//带头结点的循环单链表 template<class ElemType>class CirLinkList {
private:LinkNode<ElemType>* head;   // 头结点LinkNode<ElemType>* tail;   // 尾结点
public://无参数的构造函数CirLinkList() { head = NULL;tail = NULL; }CirLinkList(CirLinkList<ElemType>& List);//拷贝构造函数~CirLinkList() { //析构函数del_clear();}LinkNode<ElemType>* front(LinkNode<ElemType>* p){LinkNode<ElemType>* p1=head;while (p1->next != p)p1 = p1->next;return p1;}void delp(LinkNode<ElemType>* p){if (p == head && p == tail){//only have one//没写删除元素head = NULL;tail = NULL;delete p;return;}if (p == head){LinkNode<ElemType>* p1 = head->next;head = p1;tail->next = head;return;}if (p == tail){LinkNode<ElemType>* p1 = front(p);p1->next = head;tail = p1;return;}if (p != head && p != tail){LinkNode<ElemType>* p1 = front(p);p1->next = p->next;return;}return;}void del(int n){//删除链表指定元素LinkNode<ElemType>* p = getPlace(n);if (p == head && p == tail){//only have one//没写删除元素head = NULL;tail = NULL;delete p;return;}if (p == head){LinkNode<ElemType>* p1 = head->next;head = p1;tail->next = head;return;}if (p == tail){LinkNode<ElemType>* p1 = getPlace(n - 1);p1->next = head;tail = p1;return;}if (p != head && p != tail){LinkNode<ElemType>* p1 = getPlace(n - 1);p1->next = p->next;return;}return; }void del_clear(){//释放链表return;}int size() const//ok{//返回链表的长度int cnt = 0;LinkNode<ElemType>* p;bool fir = 0;p = head;if (p == NULL){return 0;}while (1){if (p == head && fir == 1)break;//------------//循环操作cnt++;//------------fir = 1;p = p->next;}return cnt;}bool empty() const//ok{//判断链表是否为空表if (size() == 0 || head == NULL){return 0;}return 1;}LinkNode<ElemType>* getHead() //ok{ //获取循环链表头结点return head; }LinkNode<ElemType>* getTail() //ok{ //获取循环链表尾结点return tail; }void changeTail(LinkNode<ElemType>*p){tail = p;return;}void changeHead(LinkNode<ElemType>*p){head = p;return;}LinkNode<ElemType>* getNextn(LinkNode<ElemType>* p, int n){while (n--){p = p->next;}return p;}LinkNode<ElemType>* getPlace(int n){LinkNode<ElemType>* p;p = head;if (p == NULL){cout << "wrong! NULL List!!!" << endl;return NULL;}while (n--){p = p->next;}return p;}ElemType getNum(int n){LinkNode<ElemType>* p = getPlace(n);return p->data;}bool Insert_next(int pos, ElemType num){//在链表的第pos个位置之后插入num元素}bool InsFirst(ElemType num)//ok{//在首结点之前插入一个结点if (head == NULL){//空链表插入head = new LinkNode<ElemType>;head->data = num;tail = head;tail->next = head;return 0;}LinkNode<ElemType>* p = new LinkNode<ElemType>;p->next = head;p->data = num;head = p;tail->next = head;return 1;}void push_back(ElemType num)//ok{if (head == NULL){//空链表插入head = new LinkNode<ElemType>;head->data = num;tail = head;tail->next = head;return;}LinkNode<ElemType>* p = new LinkNode<ElemType>;p->data = num;p->next = head;tail->next = p;tail = p;return;}bool ListTraverse() const//ok{LinkNode<ElemType>* p;bool fir = 0;p = head;if (p == NULL){cout << "wrong! NULL List!!!" << endl;return 0;}while (1){if (p == head && fir == 1)break;//------------//循环操作cout << p->data;if (p->next != head)cout << "->";elsecout << endl;//------------fir = 1;p = p->next;}return 1;}
};
//CirLinkList<int> a;
//===============================================================
struct node{int number;int code;
};
int main()
{int n;node num;int i, j;CirLinkList<node> a;cin >> n;for (i = 0; i < n; i++){cin >> num.code;num.number = i + 1;a.push_back(num);}int t;cin >> t;queue<node>ans;LinkNode<node>* p,*p1;bool fir = 0;p1 = a.getHead();p = p1;while (1){if (p == p1 && fir == 1)break;//------------//循环操作ans.push(p->data);//------------fir = 1;p = p->next;}while (!ans.empty()){num = ans.front();cout << "(" << num.number << "," << num.code << ")";if (ans.size() != 1)cout << "->";elsecout << endl;ans.pop();}p = a.getHead();while (a.size() != 0){p = a.getNextn(p,t-1);num = p->data;t = num.code;a.delp(p);p = p->next;ans.push(num);}cout << endl;while (!ans.empty()){num = ans.front();cout << num.number;if (ans.size() != 1)cout << "->";elsecout << endl;ans.pop();}return 0;
}