数据结构--浙江大学
广义表(Generalized List)
广义表是线性表的推广
对于线性表而言，n个元素都是基本的单元素；
广义表中，这些元素不仅可以是单元素也可以是另一个广义表。
多重链表
链表中的节点可能同时隶属于多个链
多重链表结点的指针域会有多个，但包含两个指针的链表并不一定是多重链表
多重链表有广泛的用途：基本上如树、图这样相对复杂的数据结构都可以采用多重链表方式实现存储。
矩阵可以用二维数组表示
，但二维数组表示有两个缺陷：其一是数组的大小需要事先确定；其二为，对于稀疏矩阵，将造成大量的存储空间浪费
堆栈
是一种线性结构也是一种特殊的线性表。
后缀表达式
中缀表达式：运算符位于两个运算数之间。如，a+b*c-d/e
求值策略：将中缀表达式转换为后缀表达式然后求值。例：2+9/3-5 ->
293/+5-
特点：1、运算数相对顺序不变；2、运算符号顺序发生改变，需要存储等待中的运算符号；要将当前运算符号与等待中的最后一个运算符号比较
后缀表达式：运算符位于两个运算之间。如，abc*+de/-
后缀表达式求值策略：从左向右扫描，逐个独步一时运算数和运算符号
堆栈具有一定操作约束的线性表，只在一端做插入、删除。后入先出。
栈的顺序存储结构通常由一个一维数组和一个记录栈顶元素位置的变量组成。
栈的链式存储结构实际上就是一个单链表，叫做链栈。插入和删除操作只能在链栈的栈顶进行。
中缀表达式如何转换为后缀表达式
1
2
3
4
5
6
7
8
| 从头到尾读取中缀表达式的每个对象，对不同对象按不同的情况处理。
1、运算数：直接输出
2、左括号：压入堆栈；
3、右括号：将栈顶的运算符弹出并输出，直到遇到左括号（出栈，不输出）；
4、运算符：
若优先级大于栈顶运算符时，则把它压栈；
若优先级小于等于栈顶运算符时，将栈顶运算符弹出并输出；再比较新的栈顶运算符，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压栈；
5、若各对象处理完毕，则把堆栈中存留的运算符一并输出。
|
堆栈的其他应用：
应用示例：中缀表达式转换为后缀表达式：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
| package cn.edu.zzu;
import sun.plugin2.main.server.Plugin;
import java.security.spec.PKCS8EncodedKeySpec;
import java.util.Scanner;
import java.util.Stack;
public class Main {
static Stack<Character> op = new Stack<>();
static Stack<Character> optemp = new Stack<>();
static final String MINUS = "-";
static final String PLUS = "+";
static final String MULTIPLY = "*";
static final String DIVIDE = "/";
static final String LEFT_BRACKET = "(";
static final String RIGHT_BRACKET = ")";
public static void main(String[] args) {
System.out.println("请输入一个式子。。。");
Scanner scanner = new Scanner(System.in);
String exp = scanner.nextLine();
System.out.println(exp);
System.out.print(getRp(exp));
}
private static String getRp(String exp) {
StringBuilder out = new StringBuilder();
char[] chars = exp.toCharArray();
int j = 0;
for (int i = 0; i < exp.length(); i++) {
String s = String.valueOf(chars[i]);
if (!s.equals(MINUS) && !s.equals(PLUS) && !s.equals(MULTIPLY) && !s.equals(DIVIDE) && !s.equals(LEFT_BRACKET) && !s.equals(RIGHT_BRACKET)) {
op.push(chars[i]);
} else {
if (s.equals(MINUS) || s.equals(PLUS)) {
if (optemp.empty() || optemp.peek().toString().equals(LEFT_BRACKET)) {
optemp.push(chars[i]);
} else {
while (!optemp.peek().toString().equals(LEFT_BRACKET)) {
op.push(optemp.pop());
if (optemp.empty()) {
break;
}
}
optemp.push(chars[i]);
}
} else if (s.equals(DIVIDE) || s.equals(MULTIPLY)) {
if (optemp.empty()) {
optemp.push(chars[i]);
} else {
if (optemp.peek().toString().equals(MINUS) || optemp.peek().toString().equals(PLUS)
|| optemp.peek().toString().equals(LEFT_BRACKET)) {
optemp.push(chars[i]);
} else {
while (optemp.peek().toString().equals(DIVIDE) || optemp.peek().toString().equals(MULTIPLY)) {
op.push(optemp.pop());
if (optemp.empty()) {
optemp.push(chars[i]);
break;
}
}
}
}
continue;
} else if (s.equals(LEFT_BRACKET)) {
optemp.push(chars[i]);
} else if (s.equals(RIGHT_BRACKET)) {
while (!optemp.peek().toString().equals(LEFT_BRACKET)) {
op.push(optemp.pop());
}
Character pop = optemp.pop();
}
}
}
while (!optemp.empty()) {
op.push(optemp.pop());
}
while (!op.empty()) {
out.append(op.pop());
}
char[] c1 = out.toString().toCharArray();
StringBuilder scout = new StringBuilder();
for (int i = 0; i < c1.length; i++) {
scout.append(c1[c1.length - i - 1]);
}
return scout.toString();
}
}
|