算法笔记第七章数据结构

算法笔记第七章数据结构

1.栈
简单计算器，实现C++代码如下：

#include
#include
#include
#include
#include
#include

首先读入数据后将其存储为字符串的形式，引入。因为数据中存在数字与计算 *** 作符因此要存储为string形式。其次对数据进行检测，将数据中的空格删除掉，使用string的迭代器iterator从后往前进行检测，检测到为空格就用erase函数擦除该迭代器对应的元素。因为是循环输入数据，因此设定的栈需要进行检查，因为最后得到的结果在栈顶，因此栈一般都是非空，所以需要检查是否为空，若空的话就把元素都pop出来。这样就完成了全部的准备工作。因为输入的是后缀表达式，因此需要先将其转换为计算方便的后缀表达式，Change（）函数的功能就是进行中缀表达式转后缀表达式的 *** 作。由于数据有两种可能： *** 作数与 *** 作符。因此需要建立一个结构体node，里面定义三个量，分别为double型的 *** 作数变量，char型的 *** 作符变量，bool类型的flag变量。flag变量用来显示读入的字符为 *** 作数还是 *** 作符， *** 作数赋为true， *** 作符赋为false。然后进行检测，如果是 *** 作数的话，那该字符的字符值应该在‘0’与‘9’之间，可以等于这两个数。判断完其为 *** 作数后并不能直接压入队列（定义一个队列用来存放后缀表达式）因为其可能与之后的数组成十位、百位等数因此需要判断其下一位是否也为 *** 作符，将该数赋值给一个temp临时存储变量。进行一个while循环，如果是 *** 作数的话就temp10再加上该 *** 作数形成新的temp。循环推出后将temp压入queue中。如果是 *** 作符的话就与栈顶的 *** 作符判断，此时需要定义 *** 作符的优先级。本题只实现了±/四则运算，所以可以定义一个map的映射，定义一个描述优先级的map op。将±的优先级赋值为1，*/的优先级赋值为2.这样就可以区分运算赋的优先级了。如果读入的字符是 *** 作符且优先级高于栈顶 *** 作符的优先级就将栈顶 *** 作符d出到queue中去，一直d出直到栈顶 *** 作符的优先级低于读入 *** 作符的优先级为止。将读入 *** 作符压入栈中。最后判断都做完之后判断栈是不是空的，一般都会存在一个 *** 作符或多个残余，将栈剩下的 *** 作符压入queue中去，如此中缀表达式就转成了后缀表达式。接着进行计算 *** 作，Cal（）函数即为计算后缀表达式的函数，计算后缀表达式的步骤为读取queue中的后缀表达式，若为 *** 作数则将其压入栈中，若为 *** 作符，则根据 *** 作符的定义进行计算，连取两个栈顶元素，第二个为第一 *** 作数第一个为第二 *** 作数。计算完后将计算的结果压入栈中，如此直到读完queue为止。
【】string的长度为length函数，其他的是size函数。

2.队列
3.链表
动态链表，使用指针实现。

#include
#include
struct node {
	int data;
	node* next;
};
node* Create(int Array[]) {
	node* head, *pre, *p;
	head = new node;
	head->next = NULL;
	pre = head;
	for (int i = 0; i < 5; i++) {
		p = new node;
		p->data = Array[i];
		p->next = NULL;
		pre->next = p;
		pre = p;
	}
	return head;
}
int search(node* head, int x) {
	int count = 0;
	node* p = head->next;
	while (p != NULL) {
		if (p->data == x)count++;
		p = p->next;
	}
	return count;
}
void insert(node* head, int pos, int x) {
	node* q,*temp;
	q = head;
	for (int i = 0; i < pos - 1; i++) {
		q = q->next;
	}
	temp = new node;
	temp->data = x;
	temp->next = q->next;
	q->next = temp;
}
void del(node* head, int x) {
	node* q = head->next;
	node* pre = head;
	while (q != NULL) {
		if (q->data == x) {
			pre->next = q->next;
			delete(q);
			q = pre->next;
		}
		else {
			pre = q;	
			q = q->next;
		}
	}
}
int main() {
	int Array[5] = { 5,4,3,2,1 };
	node* l=Create(Array);
	l = l->next;
	while (l != NULL) {
		printf("%d", l->data);
		l = l->next;
	}
}

链表创建、插入、查找。
静态链表，使用hash实现，数组的下标就是地址。

#define _CRT_SECURE_NO_WARNINGS
#include
struct node {
	char data;
	int next;
	bool flag;
}; node p1[99999];
int main() {
	char data;
	int	N;
	int address1,address2;
	int address;
	int next;
	int temp = 0;
	for (int i = 0; i < 99999; i++) {
		p1[i].flag = false;
	}
	scanf("%d %d %d", &address1 ,&address2 ,& N);
	for (int j = 0; j < N; j++) {
		scanf("%d %c %d", &address, &data, &next);
		p1[address].data = data;
		p1[address].next = next;
	}
	p1[address1].flag = true;
	temp = address1;
	while (temp != -1) {
		temp = p1[temp].next;
		p1[temp].flag = true;
	}
	temp = address2;
	while (1) {
		if (p1[temp].flag == 1) {
			if (temp != -1) {
				printf("%05d", temp);
				break;
			}
			else {
				printf("-1");
				break;
			}
		}
		else {
			temp = p1[temp].next;
		}
	}
}

#define _CRT_SECURE_NO_WARNINGS
#include
#include
using namespace std;
struct node {
	int data;
	int next;
	int address;
	bool flag;
} p[100000];
bool cmp(node a, node b) {
	if (a.flag == false || b.flag == false) {
		return a.flag > b.flag;
	}
	else {
		return a.data < b.data;
	}
}
int main() {
	int begin;
	int N;
	int address;
	int s;
	int count=0;
	int m;
	scanf("%d %d", &N, &begin);
	for (int i = 0; i < N; i++) {
		scanf("%d", &address);
		scanf("%d %d", &p[address].data, &p[address].next);
		p[address].address = address;
	}
	s = begin;
	for (int j = 0; j < 100000; j++) {
		p[j].flag = false;
	}
	while (s != -1) {
		p[s].flag = true;
		s = p[s].next;
		count++;
	}
	sort(p, p + 100000, cmp);
	if (count!=0) {
		printf("%d %05dn", count, p[0].address);
		for (m = 0; m < count-1; m++) {
			p[m].next = p[m + 1].address;
			printf("%05d %d %05dn", p[m].address, p[m].data, p[m].next);
		}
		m = 4;
		p[4].next = -1;
		printf("%05d %d %dn", p[m].address, p[m].data, p[m].next);
	}
	else {
		printf("0 -1");
	}
	return 0;
}

【】在使用scanf时，若读取的某个变量值在之后的读取的变量中要用到，则需要分两个scanf来写，先读取该变量，再读取要用到该变量的变量（通常是数组下标）。