• 数据结构上机实验——栈和队列的实现、栈和队列的应用、进制转换、约瑟夫环问题

    文章目录

    栈和队列上机实验

    1.要求

      1.利用栈的基本操作实现将任意一个十进制整数转化为R进制整数。

      2.利用循环队列实现.约瑟夫环问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到k的那个人出圈；他的下一个人又从1开始报数，数到k的那个人出圈；依此规律重复下去，直到圆桌周围的人只剩最后一个。模拟该游戏，并输出出圈顺序。

                

    2.栈的实现（以顺序栈为例）

      栈的基本概念：

      栈（stack）是一种数据结构，它是一种只能在一端进行插入和删除操作的特殊线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

      
      栈的基本结构和初始化：

      我们定义了一个名为Stack的模板类，用于实现可以存储各种数据类型的栈的数据结构。我们创建了三个Stack的成员函数：_base、_top 和 _size。

      _base: 它作为动态分配的栈内存的起始位置。

      _top:表示栈顶的位置。 在构造函数中，它被初始化为指向InitStackSize个新分配的SElemType元素的数组的末尾。

      _size: 是一个整数，用于表示栈的当前大小，即栈中元素的数量。 在构造函数中，它被初始化为InitStackSize。

      构造函数: Stack()函数负责初始化这个栈。 它首先为_base和_top分配InitStackSize个SElemType大小的内存，并将_size设置为InitStackSize。

      析构函数: ~Stack()函数负责清理和释放由Stack对象持有的内存。 它首先删除_base指向的数组，然后将_base和_top设置为0，将_size设置为0。这是为了确保在对象销毁后，不会错误地引用任何内存地址。

      注意：数据结构的的实现是很灵活的，对于栈而言，顺序结构和链式结构都可以实现，当然，_base，_top等成员变量也可以设计成整型或者是指针，只要满足该数据类型的特征，就都可以设计。

    template<class T>
class Stack
{
	//构造函数
	Stack()
	{
		_base = _top = new SElemType[InitStackSize];
		_size = InitStackSize;
	}

	//析构函数
	~Stack()
	{
		delete[] _base;
		_top = _base = nullptr;
		_size = 0;
	}

private:
	SElemType* _base, * _top;
	int _size;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

      
      入栈和扩容操作：

      我们现在实现栈最基本的入栈操作，首先创建一个Push函数，它用于将一个元素压入栈中。如果栈满了，它会进行扩容操作。

      如果 _top 指针和 _base 指针之间的距离等于 _size（这意味着栈已经满了），那么将进行扩容操作。扩容操作包括创建一个新的数组（大小为原数组的两倍），然后复制原数组的元素到新数组中。 最后，更新 _base 指针指向新数组，_top 指针指向新数组的末尾，_size 变为新数组的大小。

      入栈操作，如果栈没有满，那么将 val 的值赋给 _top 指针所指向的位置，并将 _top 指针向前移动一位。 最后，_size 加一。

    void Push(const SElemType& val)
{
	//栈满，扩容
	if (_top - _base == _size)
	{
		//转移栈中的元素
		SElemType* newbase = new SElemType[_size * 2];
		for (int i = 0; i < _size; i++)
		{
			newbase[i] = _base[i];
		}

		//删除原来栈中元素
		delete[] _base;
		_base = newbase;
		_top = newbase + _size;
		_size *= 2;
	}

	//入栈操作
	*_top = val;
	_top++;
	_size++;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

      
      出栈操作：

      我们现在实现出栈操作，先创建一个名为Pop的函数，用于从栈中删除并返回栈顶元素。

      函数声明：Pop(SElemType& e) 是一个函数，它接受一个类型为 SElemType 的引用作为参数，命名为 e。引用的使用意味着我们可以在函数内部修改传入的参数，而不仅仅是它的副本。

      栈检查：在函数体中，首先检查栈的大小（_size），如果为0，说明栈是空的。 此时，会打印一条消息 ‘该栈为空，无法删除\n’ 并结束函数。出栈操作：如果栈非空，我们执行出栈操作。首先，将栈顶元素的值赋给参数 e。然后，将 _top 指针向前移动一位（即向下移动到栈顶元素的前一个位置），因为我们已经取出了栈顶元素。最后，_size 减一，因为栈中少了一个元素。

      这样，Pop 函数就能够从栈中删除并返回栈顶元素，同时还能处理空栈的情况。

    void Pop(SElemType& e)
{
	if (_size == 0)
	{
		cout << "该栈为空，无法删除\n";
		return;
	}

	//出栈操作
	e = *_top;
	_top--;
	_size--;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

      栈测试：

    在这里插入图片描述

                

    3.队列的实现（以顺序队列为例）

      队列的基本概念：

      队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。 和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

      
      队列的基本结构和初始化：

      我们定义了一个名为Queue的C++模板类，用于实现可以存储不同数据类型的队列数据结构。我们创建了四个成员变量：

      _base：这是一个指向队列元素的指针。

      _front：这是队列的头部索引。

      _rear：这是队列的尾部索引。

      _capacity：这是队列的容量。

      构造函数：Queue的构造函数初始化了队列的基础元素数组。将队列的前端和后端索引设为0，并将队列的容量设为 ‘QueueSize’。这个 ‘QueueSize’ 应该是在类外部定义的常数，表示队列的最大容量。

      析构函数：当 Queue 对象被销毁时，析构函数将被调用。 这个析构函数删除了队列的基础元素数组，将 _base 设为 nullptr，将队列的前端和后端索引设为0，并将队列的容量设为0。这是为了释放队列占用的内存，并重置队列的状态。

    template<class T>
class Queue
{
public:
	//构造函数
	Queue()
	{
		_base = new QElemType[QueueSize];
		_front = _rear = 0;
		_capacity = QueueSize;
	}

	//析构函数
	~Queue()
	{
		delete[] _base;
		_base = nullptr;
		_front = _rear = 0;
		_capacity = 0;
	}
	
private:
	QElemType* _base;
	int _front, _rear;
	int _capacity;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

      
      入队和扩容操作：

      我们现在实现队列的入队函数，用于将一个元素添加到队列中。

      if (_front == (_rear + 1) % _capacity): 这是一个判断语句，它检查队列是否已满。这里的_front，_rear和_capacity可能是队列的私有成员变量。其中_front代表队列的第一个元素的位置，_rear代表队列的最后一个元素的位置（下一个插入元素的位置），_capacity代表队列的最大容量。如果_front等于_rear + 1 % _capacity，这意味着队列的下一个位置（_rear）已经被占用了，即队列已满。

      扩容：QElemType* newqueue = new QElemType[_capacity * 2];: 如果队列已满，这段代码会创建一个新的、容量是原队列两倍的队列。for (int i = _front; i < _rear; i++): 这个循环复制原队列中从_front到_rear - 1的所有元素到新的队列中。delete[] _base;: 释放原队列所占用的内存。_base = newqueue;: 将新队列的指针赋值给_base，这样原队列的指针就指向了新的队列。然后更新队列的容量即可。

      入队： 就在队列的最后一个位置插入新的元素。更新队列的最后一个位置即可。如果增加后超过了队列的容量，则取模（%）操作会将其限制在队列的范围内（0到_capacity-1）。

      顺序队列的一些操作和判断：

      空队列判断条件： rear == front

      尾指针的移动方式： rear = (rear+1)%QueueSize

      头指针的移动方式： front=(front+1)%QueueSize

      判断队列满： front == (rear+1)%QueueSize

    在这里插入图片描述

    void Push(const QElemType& val)
{
	//判断队列是否已满
	if (_front == (_rear + 1) % _capacity)
	{
		QElemType* newqueue = new QElemType[_capacity * 2];
		for (int i = _front; i < _rear; i++)
		{
			newqueue[i] = _base[i];
		}

		//删除原来栈中元素
		delete[] _base;
		_base = newqueue;
		_capacity *= 2;
	}

	_base[_rear] = val;
	//如果想让队列超过QueueSize的长度，一定要%_capacity;
	_rear = (_rear + 1) % _capacity;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

      
      出队操作：

      实现队列出队操作我们先判断队列是否为空， 它检查队列的前端（_front）和后端（_rear）是否相等。如果相等，这意味着队列为空，没有元素可以删除。则输出信息直接返回，不执行任何操作。

      如果队列不为空，这行代码将_base数组中索引为_front的元素赋值给引用参数e。这意味着，当你调用Pop函数时，通过引用参数e来获取被出队的元素。当元素被删除后，前端位置需要更新以指向下一个未被删除的元素。 这里使用模运算符（%）来确保前端位置在超过队列容量时回到队列的开始位置。

    void Pop(QElemType& e)
{
	if (_front == _rear)
	{
		cout << "队列为空，无法删除\n";
		return;
	}

	e = _base[_front];
	_front = (_front + 1) % _capacity;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

      队列测试：

    在这里插入图片描述

                

    4.利用栈实现进制转换

      我们可以利用栈将一个十进制数转换为另一个进制数：

      函数首先声明了两个字符串变量s和table，以及两个整型量m和n。table是一个包含16个字符的字符串，用于表示16进制的数。

      然后函数要求用户输入要转换的十进制数m和目标进制数n。函数检查如果输入的数m为0，则直接输出0，因为0在任何进制下都等于0。

      接下来如果输入的数m为负数，则将其转换为正数，并标记flag为true，表示这个数之前是负数。然后我们创建了一个名为st的堆，利用堆的性质，可以存储转换后的字符。在while循环中，函数将输入的数m不断模以目标进制数n，取出每次的余数，将余数对应的字符从table中取出，并压入堆栈st中。 同时，更新输入的数m为原来的数除以目标进制数。

      如果之前标记过flag为true（即输入的数是负数），则在堆栈中压入一个’-'字符。最后，函数将堆栈中的所有字符取出并拼接到字符串s中，然后输出这个字符串。这个字符串就是转换后的数。

    void Decimal_Conversion()
{
	string s, table = "0123456789ABCDEF";
	int m, n;
	cout << "请输入:m为输入的数,n为转换的进制\n";
	cout << "m=";
	cin >> m;
	cout << "n=";
	cin >> n;
	bool flag = false;
	if (m == 0) cout << "0";

	//如果是负数，则转成正数，并标记一下
	if (m < 0)
	{
		m = 0 - m;
		flag = true;
	}

	Stack<char> st;

	//按进制换算成对应的字符添加到s
	while (m)
	{
		st.Push(table[m % n]);
		m /= n;
	}
	if (flag)
	{
		st.Push('-');
	}

	while (!st.Empty())
	{
		s += st.Top();
		st.Pop();
	}
	cout << s << endl;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39

      测试：
      
    10转化为2进制：1010

    在这里插入图片描述  
    150转化为8进制：226

    在这里插入图片描述
      
    100001转化为16进制：186A1

    在这里插入图片描述
    在这里插入图片描述
                

    5.利用队列解决约瑟夫环问题

      我们可以利用队列解决约瑟夫环问题。约瑟夫环：描述了一组共m个人围成一圈，从第n个人开始报数，报到m的人出列，然后从下一个人重新开始报数，直到所有的人都出列的问题。

      首先，函数向用户提示输入约瑟夫环的两个人数m和n。然后，使用队列que来模拟人们围成的圆圈。初始时，将1到m的人依次入队。使用一个计数器count，从1开始计数，每次循环都会增加1，直到达到目标n。

      如果计数器count小于目标n，表示当前人不需要出列，将队头元素取出（即这个人），从队列中删除（模拟这个人跳过），然后将这个元素重新插入队尾（这个人回到圆圈的尾部）。 然后，计数器count加1，为下一次循环做准备。

      如果计数器count等于目标n，表示当前人需要出列，将队头元素取出并打印（这个人是出列的人），然后从队列中删除这个元素（模拟这个人完全出列），然后将计数器count重置为1，继续下一轮循环。

      当队列为空时，说明所有的人已经出列，退出循环。

    void Joseph_Exchange()
{
	cout << "约瑟夫环问题：请输入一共有m人，第n人出局:\n";
	int m, n;
	cout << "m=";
	cin >> m;
	cout << "n="; 
	cin >> n;

	//填入队列中
	Queue<int> que;
	for (int i = 1; i <= m; i++)
	{
		que.Push(i);
	}

	//从第n开始计数
	for (int i = 1; i <= n; i++)
	{
		QElemType tmp = que.Head();
		que.Pop();
		que.Push(tmp);
	}

	//计数器，计到目标就输入
	int count = 1;
	while (!que.Empty())
	{
		if (count < n)
		{
			QElemType tmp = que.Head();
			que.Pop();
			que.Push(tmp);
			count++;
		}
		else if (count == n)
		{
			cout << que.Head() << " ";
			que.Pop();
			count = 1;
		}
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43

      测试：

    在这里插入图片描述
                

    6.全部源码

    Stack.h

    #pragma once

#define SElemType int
#define InitStackSize 100

template<class T>
class Stack
{
public:
	//构造函数
	Stack()
	{
		_base = _top = new SElemType[InitStackSize];
		_size = InitStackSize;
	}

	//析构函数
	~Stack()
	{
		delete[] _base;
		_top = _base = nullptr;
		_size = 0;
	}

	//入栈
	void Push(const SElemType& val)
	{
		//栈满，扩容
		if (_top - _base == _size)
		{
			//转移栈中的元素
			SElemType* newbase = new SElemType[_size * 2];
			for (int i = 0; i < _size; i++)
			{
				newbase[i] = _base[i];
			}

			//删除原来栈中元素
			delete[] _base;
			_base = newbase;
			_top = newbase + _size;
			_size *= 2;
		}

		//入栈操作
		*_top = val;
		_top++;
		_size++;
	}

	//出栈
	void Pop(SElemType& e)
	{
		if (_size == 0)
		{
			cout << "该栈为空，无法删除\n";
			return;
		}

		//出栈操作
		e = *_top;
		_top--;
		_size--;
	}

	//重载出栈
	void Pop()
	{
		if (_size == 0)
		{
			cout << "该栈为空，无法删除\n";
			return;
		}

		//出栈操作
		_top--;
	}

	//输出栈顶元素
	SElemType Top()
	{
		if (_base == _top)
		{
			cout << "栈空，没有元素\n";
			return -1;
		}

		return *(_top - 1);
	}

	//判断栈空
	bool Empty()
	{
		if (_base == _top)
		{
			return true;
		}
		else
		{
			return false;
		}
	}

	//打印栈中的元素
	void Print()
	{
		SElemType* cur = _base;
		if (_base == _top)
		{
			cout << "该栈为空\n";
			return;
		}
		else
		{
			cout << "该栈中的元素为:";
			while (cur != _top)
			{
				cout << *cur << " ";
				cur++;
			}
			cout << endl;
		}
	}

private:
	SElemType* _base, * _top;
	int _size;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128

                

    Queue.h

    #pragma once

#define QueueSize 100
#define QElemType int

template<class T>
class Queue
{
public:
	//构造函数
	Queue()
	{
		_base = new QElemType[QueueSize];
		_front = _rear = 0;
		_capacity = QueueSize;
	}

	//析构函数
	~Queue()
	{
		delete[] _base;
		_base = nullptr;
		_front = _rear = 0;
		_capacity = 0;
	}

	//入队操作
	void Push(const QElemType& val)
	{
		//判断队列是否已满
		if (_front == (_rear + 1) % _capacity)
		{
			QElemType* newqueue = new QElemType[_capacity * 2];
			for (int i = _front; i < _rear; i++)
			{
				newqueue[i] = _base[i];
			}

			//删除原来队列中元素
			delete[] _base;
			_base = newqueue;
			_capacity *= 2;
		}

		_base[_rear] = val;
		//如果想让队列超过QueueSize的长度，一定要%_capacity;
		_rear = (_rear + 1) % _capacity;
	}

	//出队操作
	void Pop(QElemType& e)
	{
		if (_front == _rear)
		{
			cout << "队列为空，无法删除\n";
			return;
		}

		e = _base[_front];
		_front = (_front + 1) % _capacity;
	}

	//重载出队操作
	void Pop()
	{
		if (_front == _rear)
		{
			cout << "队列为空，无法删除\n";
			return;
		}

		_front = (_front + 1) % _capacity;
	}

	//输出队头元素
	QElemType Head()
	{
		if (_front == _rear)
		{
			cout << "队列为空，无队头元素\n";
			return -1;
		}
		
		return _base[_front];
	}

	//判断是否为空队列
	bool Empty()
	{
		if (_front == _rear)
		{
			return true;
		}
		else
		{
			return false;
		}
	}

	//打印队列中的元素
	void Print()
	{
		if (_front == _rear)
		{
			cout << "该队列为空\n";
			return;
		}
		else
		{
			cout << "该队列中的元素为:";
			for (int i = _front; i < _rear; i++) 
			{
				std::cout << _base[i] << " ";
			}
			cout << endl;
		}
	}

private:
	QElemType* _base;
	int _front, _rear;
	int _capacity;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123

                

    test.cpp

    #define _CRT_SECURE_NO_WARNINGS 1

#include
using namespace std;

#include"Stack.h"
#include"Queue.h"

void stack_test()
{
	Stack<int> st;
	st.Print();
	cout << "该栈是否为空:" << st.Empty() << endl;
	st.Push(1);
	st.Push(2);
	st.Push(3); 
	st.Push(4);
	st.Print();
	cout << "栈顶元素为:" << st.Top() << endl;
	st.Pop();
	st.Pop();
	st.Print();
	cout << "该栈是否为空:" << st.Empty() << endl;
	st.Push(5);
	st.Push(6);
	st.Push(7);
	st.Push(8);
	st.Print();
	cout << "栈顶元素为:" << st.Top() << endl;
	st.Pop();
	st.Pop();
	st.Print();
}

void queue_test()
{
	Queue<int> que;
	que.Print();
	cout << "该队列是否为空:" << que.Empty() << endl;
	que.Push(1);
	que.Push(2);
	que.Push(3);
	que.Push(4);
	que.Print();
	cout << "队头元素为:" << que.Head() << endl;
	que.Pop();
	que.Pop();
	que.Print();
	cout << "该队列是否为空:" << que.Empty() << endl;
	que.Push(5);
	que.Push(6);
	que.Push(7);
	que.Push(8);
	que.Print();
	cout << "队头元素为:" << que.Head() << endl;
	que.Pop();
	que.Pop();
	que.Print();
}

void Decimal_Conversion()
{
	string s, table = "0123456789ABCDEF";
	int m, n;
	cout << "请输入:m为输入的数,n为转换的进制\n";
	cout << "m=";
	cin >> m;
	cout << "n=";
	cin >> n;
	bool flag = false;
	if (m == 0) cout << "0";

	//如果是负数，则转成正数，并标记一下
	if (m < 0)
	{
		m = 0 - m;
		flag = true;
	}

	Stack<char> st;

	//按进制换算成对应的字符添加到s
	while (m)
	{
		st.Push(table[m % n]);
		m /= n;
	}
	if (flag)
	{
		st.Push('-');
	}

	while (!st.Empty())
	{
		s += st.Top();
		st.Pop();
	}
	cout << s << endl;
}

void Joseph_Exchange()
{
	cout << "约瑟夫环问题：请输入一共有m人，第n人出局:\n";
	int m, n;
	cout << "m=";
	cin >> m;
	cout << "n="; 
	cin >> n;

	//填入队列中
	Queue<int> que;
	for (int i = 1; i <= m; i++)
	{
		que.Push(i);
	}
	
	//从第n开始计数
	for (int i = 1; i <= n; i++)
	{
		QElemType tmp = que.Head();
		que.Pop();
		que.Push(tmp);
	}

	//计数器，计到目标就输入
	int count = 1;
	while (!que.Empty())
	{
		if (count < n)
		{
			QElemType tmp = que.Head();
			que.Pop();
			que.Push(tmp);
			count++;
		}
		else if (count == n)
		{
			cout << que.Head() << " ";
			que.Pop();
			count = 1;
		}
	}
}

int main()
{
	//stack_test();
	//queue_test();
	//Decimal_Conversion();
	Joseph_Exchange();
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
  • 相关阅读:
    SpringMVC（第一个项目HelloWorld））
    c++编写简易版2048小游戏
    C语言从入门到精通 第八章（用函数实现模块化程序设计）
    MySQL的一个Bug修复提高了4倍性能
    高频面试题：谈谈你对 Spring Boot 自动装配机制的理解
    java 大厂面试指南：性能优化 + 微服务 + 并发编程 + 开源框架 + 分布式
    视频号视频提取小程序，快速下载视频号视频
    OpenCascade & VTK STEP/IGES文件读取显示
    OpenCV（二十八）：连通域分割
    双指针算法解决 移动零 和 复写零问题
  • 原文地址：https://blog.csdn.net/Crocodile1006/article/details/133840278