数据结构上机复习一

1.单链表基本操作

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
struct node
{
	int val;
	node* next;
};

bool insert(node* dummyhead,int k, int d)
{
	if (k < 0) return false;
	node* p = dummyhead;
	for (int i = 0; i < k; i++)
	{
		p = p->next;
		if (p == NULL)
			return false;
	}
	node* tmp = new node;
	tmp->val = d;
	tmp->next = p->next;
	p->next = tmp;
	return true;
}
bool remove(node* dummyhead,int k)
{
	if (k <= 0) return false;
	node* p = dummyhead;
	for (int i = 0; i < k - 1; i++)
	{
		p = p->next;
		if (p == NULL)
			return false;
	}
	p->next = p->next->next;
}
int main()
{
	int n;
	cin >> n;
	node* dummyhead = new node;
	dummyhead->next = NULL;
	node* p = dummyhead;
	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		node* tmp = new node;
		tmp->val = x;
		tmp->next = NULL;
		p->next = tmp;
		p = p->next;
	}

	int m;
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		int op;
		cin >> op;
		if (op == 0)
		{
			int k, d;
			cin >> k >> d;
			insert(dummyhead, k, d);
		}
		else
		{
			int d;
			cin >> d;
			remove(dummyhead, d);
		}
	}
	node* t = dummyhead->next;
	while (t)
	{
		cout << t->val<<" ";
		t = t->next;
	}
}

2.栈

class stack
{
public:
	int top = -1;
	int a[N];
	bool empty() { return top == -1; }
	void push(int x) { a[++top] = x; }
	int pop() { return a[top--]; }
	int peak() { return a[top]; }
};

3.队列

class queue
{
public:
	int front=0, rear=0;
	int a[N];
	bool empty() { return front == rear; }
	void push(int x) { a[rear++] = x; }
	int pop() { return a[front++]; }
};

4.键盘

#include <iostream>
using namespace std;
const int N = 5e4 + 10;

class stack
{
public:
	int top = -1;
	char a[N];
	bool empty() { return top == -1; }
	void push(char x) { a[++top] = x; }
	char pop() { return a[top--]; }
	char peak() { return a[top]; }
};


int main()
{
	stack L, R;
	char ch;
	while (cin >> ch)
	{
		if (ch == '{')
		{
			while (!L.empty())
				R.push(L.pop());
		}
		else if (ch == '}')
		{
			while (!R.empty())
				L.push(R.pop());
		}
		else if (ch == '<')
		{
			if (!L.empty())
				R.push(L.pop());
		}
		else if (ch == '>')
		{
			if (!R.empty())
				L.push(R.pop());
		}
		else if (ch == '#')
		{
			if (!L.empty())
				L.pop();
		}
		else
		{
			L.push(ch);
		}
	}
	while (!L.empty())
		R.push(L.pop());
	while (!R.empty())
		cout << R.pop();
}

5.括号匹配

#include <iostream>
#include <string>
using namespace std;

const int N = 1e5 + 10;

class stack
{
public:
	int top = -1;
	char a[N];
	bool empty() { return top == -1; }
	void push(char x) { a[++top] = x; }
	char pop() { return a[top--]; }
};
int main()
{
	string str;
	stack s;
	while (cin >> str)
	{
		int n = str.size();
		int miss = 0;
		int miss1 = 0, miss2 = 0;
		for (int i = 0; i < n; i++)
		{
			if (str[i] == '(')
				s.push('(');
			else
			{
				if (s.empty())
					miss1++;//缺左
				else
					s.pop();
			}
		}
		while (!s.empty())
		{
			s.pop();
			miss2++;//缺右
		}
		miss = miss1 + miss2;
		if (miss == 0)
			cout << "Match" << endl;
		else
		{
			cout << miss << endl;
			for (int i = 0; i < miss1; i++) cout << "(";//补左括号
			cout << str;
			for (int i = 0; i < miss2; i++) cout << ")";//补右括号
			cout << endl;
		}
			
	}
}

6.约瑟夫 讲解：acwing4400

#include <iostream>
#include <queue>
using namespace std;
const int N = 1e4 + 10;

int main()
{
	int n, m;
	cin >> n >> m;
	
	queue<int>q;
	for (int i = 1; i <= n; i++)
		q.push(i);

	int t = m - 1;
	for (int i = 0; i < n ; i++)//n次
	{
		for (int i = 0; i < t % q.size(); i++)
		{
			q.push(q.front());
			q.pop();
		}
		cout << q.front() << " ";
		q.pop();
		t++;
	}
}