4.数据结构_七贤镇

文章目录

线性结构
- 向量-vector
- - 构造
  - 基本操作
- 队列
- - 基本操作
  - 例题：猫狗收容所
- 栈
- - 基本操作
  - 逆序输出
  - 括号匹配
  - 表达式求值

线性结构向量-vector

长度不定的数组

构造

#include #include #include //c#include//memset#includeusing namespace std;void print(vector myVector,int n){	printf("vecor%d; ",n);	for(int i=0;i myVector1;	vector myVector2(myArray,myArray+5);//1,2,3,4,5	vector myVector3(5,2);//2,2,2,2,2	vector myVector4(myVector2);//1,2,3,4,5	vector myVector5(myVector4.begin(),myVector4.begin()+3);//1,2,3print(myVector1,1);print(myVector2,2);print(myVector3,3);print(myVector4,4);print(myVector5,5);}

基本操作

#include #include #include //c#include//memset#includeusing namespace std;int main() {	int myArray[] = {1, 2, 3, 4, 5};	vector myVector(myArray, myArray + 5); //1,2,3,4,5	int n = myVector.size();	myVector.pop_back();//1,2,3,4	myVector.push_back(6);//1,2,3,4,6	myVector.insert(myVector.begin() + 1, 9); //1,9,2,3,4,6	myVector.insert(myVector.begin(), 3, 7); //7,7,7,1,9,2,3,4,6	myVector.insert(myVector.begin(), myArray, myArray + 2); //1,2 ,7,7,7,1,9,2,3,4,6	myVector.erase(myVector.begin() + 6);//1,2 ,7,7,7,1,2,3,4,6	myVector.erase(myVector.begin() + 1, myVector.begin() + 3); //1,7,7,1,2,3,4,6	myVector.clear();}

队列基本操作 【4.数据结构】

#include #include #include //c#include//memset#includeusing namespace std;int main() {	queue myQueue;	for (int i = 0; i < 10; i++) {myQueue.push(i);//入队	}	int sum = 0;	while (!myQueue.empty()) { //判空sum += myQueue.front(); //访问队首myQueue.pop();//出队	}	printf("%d\n", sum) ;	return 0;}

例题：猫狗收容所

题目描述
有家动物收容所只收留猫和狗，但有特殊的收养规则，收养人有两种收养方式，
第一种为直接收养所有动物中最早进入收容所的，
第二种为选择收养的动物类型（猫或狗），并收养该种动物中最早进入收容所的。
给定一个操作序列int[][2] ope(C++中为vector)代表所有事件。
若第一个元素为1，则代表有动物进入收容所，第二个元素为动物的编号，正数代表狗，负数代表猫；
若第一个元素为2，则代表有人收养动物，
第二个元素若为0，则采取第一种收养方式，若为1，则指定收养狗，若为-1则指定收养猫。
请按顺序返回收养的序列。若出现不合法的操作，即没有可以符合领养要求的动物，则将这次领养操作忽略。

#include #include #include //c#include//memset#includeusing namespace std;struct Animal {	int number;	int order;//对各个动物 进来的顺序进行编号	Animal() {	}	Animal(int n, int o): number(n), order(o) {	}};queue cats;queue  dogs;int main() {	int n;	scanf("%d", &n);	int order = 0;	for (int i = 0; i < n; i++) {int method, type;scanf("%d%d", &method, &type);//动物进入收容所，method==1if (method == 1) {if (type > 0) {dogs.push(Animal(type, order++));} else {cats.push((Animal(type, order)));}}//有人收养动物 ，method==2else {//第二个元素若为0,直接收养所有动物中最早进入收容所的if (type == 0 && !dogs.empty() && !cats.empty()) {if (dogs.front().order < cats.front().order) {printf("%d", dogs.front().number);dogs.pop();//记得弹出队头元素} else {printf("%d", cats.front().number);cats.pop();}} else if (type == 0 && !dogs.empty() && cats.empty()) {printf("%d", dogs.front().number);dogs.pop();} else if (type == 0 && dogs.empty() && !cats.empty()) {printf("%d", cats.front().number);cats.pop();}//若为1，则指定收养狗else if (type == 1 && !dogs.empty()) {printf("%d", dogs.front().number);dogs.pop();}//若为-1则指定收养猫 。else if (type == -1 && !cats.empty()) {printf("%d", cats.front().number);cats.pop();}}	}	printf("\n");	return 0;}

栈基本操作

#include #include #include //c#include//memset#includeusing namespace std;int main() {	stack myStack;	for (int i = 0; i < 10; i++) {myStack.push(i);//入栈	}	int sum = 0;	while (!myStack.empty()) { //判空printf("%d ", myStack.top()) ;sum += myStack.top(); //访问栈顶myStack.pop();//出栈	}	printf("\n%d\n", sum) ;	return 0;	return 0;}

逆序输出括号匹配

#include #include #include //c#include//memset#includeusing namespace std;int main() {	string str;	while (cin >> str) {//用栈来记录 左括号的下标，而不是字符stack brackets;string answer(str.size(), ' '); //定义一个空字符串记录哪一位适配for (int i = 0; i < str.size(); i++) {if (str[i] == '(') {brackets.push(i);} else if (str[i] == ')') {if (!brackets.empty()) {brackets.pop();//匹配成功弹出} else {answer[i] = '?'; //右括号 没有适配}}}while (!brackets.empty()) {answer[brackets.top()] = '$';brackets.pop();}//)(rttyy())$$)(cout << str << endl;cout << answer << endl;//??$	}	return 0;}

表达式求值

用栈实现中缀表达式转后缀表达式：
- 初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。
- 从左到右处理各个元素，直到末尾。可能遇到三种情况：
  - ① 遇到操作数。直接加入后缀表达式。
  - ② 遇到界限符。遇到“(”直接入栈；遇到“)”则依次弹出栈内运算符并加入后缀表达式，直到弹出“(”为止。注意：“(”不加入后缀表达式。
  - ③ 遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到“(” 或栈空则停止。之后再把当前运算符入栈。
- 按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。
用栈实现后缀表达式的计算：
- ①从左往右扫描下一个元素，直到处理完所有元素
- ②若扫描到操作数则压入栈，并回到①；否则执行③
- ③若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到①
用栈实现中缀表达式的计算：
- 初始化两个栈，操作数栈和运算符栈
- 若扫描到操作数，压入操作数栈
- 若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈（期间也会弹出运算符，
  每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈）