0829-C04数据结构3

1、链表图示

2、stack的运用-进制转换的处理

/*
'a' = 97
'A' = 65
'0' = 48 
8
52346
2
*/
#include <stack>
#include <bits/stdc++.h>
using namespace std;

int n, m;
string s; 
stack<int> stk;
 
int main(){	
	cin >> n >> s >> m;
	//1.先将n进制的s转换为十进制 按权展开, pow
	int len = s.size();
	int num = 0, k = 0;
	for (int i=len-1; i>=0; i--){
		int t = 0; 
		if ('0'<=s[i] && s[i]<='9')	t = s[i] - 48;	// num += (s[i] - 48)*pow(n, k++); 	/*0~9: 字符(0~9)转换为数字(0~9), ASCII -48*/
		else t = s[i] - 55; 						//字符'A'~'F', A(65)  10 
		num += t*pow(n, k++);
	}
//	cout << num << endl;
	while (num){
		stk.push(num%m);
		num/=m;
	}
	while (stk.size()){
		if (stk.top() > 9) cout << (char)(stk.top() + 55);
		else cout << stk.top();
		stk.pop();
	} 
	return 0;
}

3、数组名表示首地址

#include <bits/stdc++.h>
using namespace std;

int a[100] = {999,1,2,3,4,5,78,6,7,8,9}; 
//char a[100] = "helloworld"; 

int main(){
	for (int i=0; i<5; i++){
//		cin >> a[i];
//		scanf("%d", &a[i]); 
		scanf("%d", a+i); 
	} 
	cout << *a << endl;	//数组名表示的是数组的首地址 
	for (int i=0; i<10; i++){
//		printf("%d ", a[i]);
		printf("%d ", *(a+i));	//地址的偏移量 
	}
	
	return 0;
}

4、单向链表的基本操作

#include <bits/stdc++.h>
using namespace std;

//结点 node  结构体指针 
struct node{
	int data;
	node *next;	
}; 

node *head, *r, *p;

//输出链表 
void print(){
	p = head;
	while (p->next != NULL){
		cout << p->data <<' '; 
		p = p->next; 
	} 
	cout << p->data << endl;
} 

//删除第k个节点 
void deleteNode(int k){
	p = head;
	//移动到k的前一个节点 
	for(int i=1; i<=k-2; i++){
		p = p->next; 
	}
	cout << p->data <<endl; 
	//删除:
	p->next = p->next->next; 
} 

//在第k个节点的位置上插入num 
void insertNode(int k, int num){
	node *s = new node;
	s->data = num, s->next = NULL; 
	
	p = head;
	//移动到k的前一个节点 
	for(int i=1; i<=k-2; i++) p = p->next; 
	
	//注意顺序不能交换 
	s->next = p->next; 
	p->next = s;
} 

int main(){
	head = new node;	//动态分配内存空间 
	head->data = 1, head->next = NULL;
	r = head;	
	
	for(int i=100; i<=110; i++){
		p = new node;
		p->data = i, p->next = NULL;
		r->next = p, r = p; 
	}
	//输出
	print(); 
	
	//删除第4个节点
	deleteNode(4); 
	print();
	
	insertNode(4, 777);	//在第4个位置插入节点777 
	print(); 

	return 0;
}

5、练习-T187711 【链表】基础链表插入

#include <bits/stdc++.h>
using namespace std;

//结点 node  结构体指针 
struct node{
	int data;
	node *next;	
}; 

int n, a, b, t; 
node *head, *r, *p;

//输出链表 
void print(){
	p = head->next;
	while (p->next != NULL){
		cout << p->data <<' '; 
		p = p->next; 
	} 
	cout << p->data << endl;
} 

//输入添加链表 
void addNode(){
	for(int i=1; i<=n; i++){
		cin >> t; 
		p = new node;
		p->data = t, p->next = NULL;
		r->next = p, r = p; 
	}
}

//在第k个节点的位置上插入num 
void insertNode(int a, int b){
	node *s = new node;
	s->data = b, s->next = NULL;
	
	p = head->next;
	while (p->next != NULL){
		if (p->data == a){
			s->next = p->next;
			p->next = s;
			break;
		}
		p = p->next; 
	} 
}

int main(){
	cin >> n;
	head = new node;	//动态分配内存空间 
	head->data = 1, head->next = NULL;
	r = head;
		
	addNode(); 
	cin >> a >> b;
	insertNode(a, b);	//在第a后面插入b 
	print(); 

	return 0;
}

6、stack的运用-后缀表达式

#include <bits/stdc++.h>
#include <stack> 
using namespace std;

stack<int> stk; 
string s; 

int main(){
	cin >> s;
	int len = s.size();
	for (int i=0; i<len; i++){
		int num = 0, flag = 0;
		while ('0'<=s[i] && s[i]<='9'){	//组合数字, 1.遇到数字则进栈 
			flag = 1; 
			num = num*10 + s[i]-48;
			i++;
		}
		if (flag) stk.push(num);
		num = 0; 
		if(s[i]=='+' || s[i]=='-' || s[i]=='*' || s[i] == '/') {	//2. 遇到符号弹栈 
			int b = stk.top(); stk.pop(); 	//先弹出第2操作数 
			int a = stk.top(); stk.pop();	//再弹出第1操作数 
			switch(s[i]) {
				case '+': stk.push(a+b);break; 
				case '-': stk.push(a-b);break; 
				case '*': stk.push(a*b);break; 
				case '/': stk.push(a/b);break; 
			}
		}
	}
	cout << stk.top();
	 
//	while (stk.size()){
//		cout << stk.top() << endl;
//		stk.pop();
//	}

	return 0;
}