当前位置：首页 > ds >正文

exp1_code

ds 2025/7/27 2:33:25

#include <iostream>
using namespace std;

// 链栈节点结构
struct StackNode {
int data;
StackNode* next;
StackNode(int val) : data(val), next(nullptr) {}
};

// 顺序栈实现
class SeqStack {
private:
int* data;
int top;
int capacity;
public:
SeqStack(int size = 10) : capacity(size), top(-1) {
data = new int[capacity];
}

~SeqStack() {
delete[] data;
}

bool isEmpty() const {
return top == -1;
}

bool isFull() const {
return top == capacity - 1;
}

bool push(int val) {
if (isFull()) return false;
data[++top] = val;
return true;
}

bool pop(int& val) {
if (isEmpty()) return false;
val = data[top--];
return true;
}

bool getTop(int& val) const {
if (isEmpty()) return false;
val = data[top];
return true;
}
};

// 链栈实现
class LinkStack {
private:
StackNode* topNode;
public:
LinkStack() : topNode(nullptr) {}

~LinkStack() {
while (topNode) {
StackNode* temp = topNode;
topNode = topNode->next;
delete temp;
}
}

bool isEmpty() const {
return topNode == nullptr;
}

void push(int val) {
StackNode* newNode = new StackNode(val);
newNode->next = topNode;
topNode = newNode;
}

bool pop(int& val) {
if (isEmpty()) return false;
val = topNode->data;
StackNode* temp = topNode;
topNode = topNode->next;
delete temp;
return true;
}

bool getTop(int& val) const {
if (isEmpty()) return false;
val = topNode->data;
return true;
}
};

// 循环队列实现
class CirQueue {
private:
int* data;
int front;
int rear;
int capacity;
public:
CirQueue(int size) : capacity(size + 1), front(0), rear(0) {
data = new int[capacity];
}

~CirQueue() {
delete[] data;
}

bool isEmpty() const {
return front == rear;
}

bool isFull() const {
return (rear + 1) % capacity == front;
}

bool enQueue(int val) {
if (isFull()) return false;
data[rear] = val;
rear = (rear + 1) % capacity;
return true;
}

bool deQueue(int& val) {
if (isEmpty()) return false;
val = data[front];
front = (front + 1) % capacity;
return true;
}

int getLength() const {
return (rear - front + capacity) % capacity;
}
};

// 测试栈功能
void testStacks() {
cout << "测试顺序栈:" << endl;
SeqStack seqStack(5);
for (int i = 1; i <= 5; i++) {
seqStack.push(i);
}
int val;
while (seqStack.pop(val)) {
cout << val << " ";
}
cout << endl;

cout << "测试链栈:" << endl;
LinkStack linkStack;
for (int i = 1; i <= 5; i++) {
linkStack.push(i);
}
while (linkStack.pop(val)) {
cout << val << " ";
}
cout << endl;
}

// 解决约瑟夫环问题（仅输出安全位置）
void solveJosephus() {
const int n = 41; // 总人数
const int m = 3; // 报数间隔
const int survivors = 2; // 最后存活人数

CirQueue queue(n);
for (int i = 1; i <= n; i++) {
queue.enQueue(i);
}

int count = 0;
int out;

// 淘汰过程，直到剩下survivors个人
while (queue.getLength() > survivors) {
queue.deQueue(out);
count++;
if (count % m == 0) {
// 移除淘汰顺序输出
} else {
queue.enQueue(out);
}
}

// 输出最后存活的位置
cout << "约瑟夫和他的朋友选择的安全位置是:" << endl;
while (!queue.isEmpty()) {
queue.deQueue(out);
cout << out << " ";
}
cout << endl;
}