数据结构基础（控院）¶
数据结构与算法可视化实现
🧪1：线性表
Info
有序线性表的交并集操作。
Python
🧪2：栈
# 元素查找
def find(n, a):
for i in range(len(a)):
if n == a[i]:
return 1
return 0
# 输出并集
def union(a, b):
print('并集：',end = '')
c = []
for i in range(len(a)):
if not find(a[i], c):
c.append(a[i])
for i in range(len(b)):
if not find(b[i], c):
c.append(b[i])
c.sort(reverse=False)
for i in c:
print(i, end = ' ')
# 输出交集
def intersection(a, b):
print('交集：',end = '')
d = []
for i in range(len(a)):
if find(a[i], b) and (not find(a[i],d)):
d.append(a[i])
d.sort(reverse=False)
if len(d) == 0:
print('无交集')
return
for i in d:
print(i, end = ' ')
if __name__ == "__main__":
# 建立有序表
a = list(map(int, input("输入表 A (元素为整数，以空格为间隔): ").split(' ')))
b = list(map(int, input("输入表 B (元素为整数，以空格为间隔): ").split(' ')))
# 整理顺序
a.sort(reverse=False)
b.sort(reverse=False)
union(a, b)
print('\n')
intersection(a, b)
print('\n')
Info
中缀表达式转后缀表达式并输出结果。
C
#include<stdio.h>
#include<stdlib.h>
#define MAXN 100
#define INF 1e5
/************************** README ******************************
将测试数据写在test.txt中，运行run.sh来测试
测试数据格式：[表达式];[参考答案]
思路：
1) 遇到数据，直接入数据栈
2）遇到运算符，与运算符栈栈顶元素比较优先级
如果运算符栈为空，或者优先级比栈顶运算符的优先级较高，则直接入栈
否则，将栈顶元素弹出，直到栈顶优先级比运算符低，再入栈
3）如遇“ ( ”，则直接压入运算符栈
如遇“ ) ”，则依次弹出栈顶运算符，并压入数据栈，直到遇到" ( "为止，丢弃括号
4）重复以上步骤
5）将运算符栈剩余的运算符依次弹出并压入数据栈
6）拼接数据栈中的元素并输出，结果即为中缀表达式所对应的后缀表达式
*****************************************************************/
// 优先级匹配
int cal_pri(char a){
if(a == '+' || a == '-'){
return 1;
}else if(a == '*' || a == '/'){
return 2;
}else if(a == '('){
return 0;
}else if(a == ')'){
return 3;
}else{
return -1;
}
}
// 四则运算
double calculate(double num1, double num2, char op){
if(num2 == 0 && op == '/'){
return INF;
}
switch(op){
case '+': return (double)(num1 + num2);
case '-': return (double)(num1 - num2);
case '*': return (double)(num1 * num2);
case '/': return (double)(num1 / num2);
}
}
int find(char *s, char a){
int i = 0;
while(s[i]!='\0'){
if(s[i] == a){
return i;
}
i++;
}
return -1;
}
int main(){
// 初始化
double num_stack[MAXN];
char op_stack[MAXN];
int num_top, op_top;
num_top = op_top = -1;
FILE *fp;
// 读取测试点文件
fp = fopen("test.txt","r");
if(fp == NULL){
printf("读取测试文件失败\n");
return 0;
}else{
printf("读取测试文件成功\n");
}
char s[MAXN];
int t = 1;
while(fgets(s, MAXN, fp) != NULL){
int i = 0;
double temp = 0.0;
int flag = 1; // 数字正负号
int error = 0; // 计算错误判断
int dot = 0; //小数点判断
int pri = 0;
double ans = 0;
num_top = op_top = -1;
if(find(s, ';') >= 0){ // 用';'隔开表达式和答案
s[find(s, ';')] = '\0';
}
printf("\ntest %d: ", t++);
printf("%s\n",s);
printf("后缀表达式： ");
while(s[i]!='\n' && s[i]!='\0'){
if(s[i] >= '0' && s[i] <= '9'){ //以字符输出，以double存储
flag = 1;
dot = 0;
temp = 0.0;
// 判断是否负数
if((i == 1 && s[i-1] == '-')||(i > 1 && s[i-1] == '-' && (s[i-2] < '0' || s[i-2] > '9'))){
printf("%c", s[i-1]);
flag = -1;
}
// 获取数据
while((s[i] >= '0' && s[i] <= '9') || s[i] == '.'){
printf("%c",s[i]);
if(s[i] == '.'){
dot = 1;
i++;
continue;
}
temp = temp * 10.0 + s[i] - '0';
if(dot){
dot ++;
}
i++;
}
// 小数处理
while(dot > 1){
temp /= 10;
dot --;
}
num_top ++;
num_stack[num_top] = temp * flag;
printf(" ");
}
else{
// 判断是否是减法
if(s[i] == '-' && (i == 0 || (i > 0 && s[i+1]>='0' && s[i+1]<='9' && (s[i-1]<'0' || s[i-1]>'9')))){
i++;
continue;
}
// 计算优先级
pri = cal_pri(s[i]);
if(pri == -1){
printf("存在无效运算符\n");
error = 1;
break;
}else{
// 优先级比栈顶元素高则入栈
if(op_top == -1 || s[i] == '(' || pri > cal_pri(op_stack[op_top])){
op_top ++;
op_stack[op_top] = s[i];
}
// 优先级低则弹出栈顶元素并计算，再入栈
else if(pri <= cal_pri(op_stack[op_top])){
while(pri <= cal_pri(op_stack[op_top])){
printf("%c ", op_stack[op_top]);
ans = calculate(num_stack[num_top - 1], num_stack[num_top], op_stack[op_top]);
if(ans == INF){
error = 1;
break;
}
num_top -= 1;
num_stack[num_top] = ans;
op_top --;
}
op_top ++;
op_stack[op_top] = s[i];
}
// 弹出括号间的所有运算符
if(op_stack[op_top] == ')'){
op_top --;
while(op_stack[op_top] != '('){
printf("%c ", op_stack[op_top]);
ans = calculate(num_stack[num_top - 1], num_stack[num_top], op_stack[op_top]);
if(ans == INF){
error = 1;
break;
}
num_top -= 1;
num_stack[num_top] = ans;
op_top --;
}
op_top --;
}
}
i++;
}
if(error){
break;
}
}
// 清空栈
while(op_top >= 0){
if(op_stack[op_top] == ')' || op_stack[op_top] == '('){
op_top --;
continue;
}
printf("%c ",op_stack[op_top]);
ans = calculate(num_stack[num_top - 1], num_stack[num_top], op_stack[op_top]);
if(ans == INF){
error = 1;
break;
}
num_top -= 1;
num_stack[num_top] = ans;
op_top --;
if(error){
break;
}
}
printf("\n");
if(error){
printf("计算结果： 数学错误\n");
}else{
printf("计算结果： %lf\n", num_stack[0]);
}
printf("参考答案： ");
if(s[i] == '\0'){
i++;
while(s[i] != '\0'){
printf("%c", s[i]);
i++;
}
printf("\n");
}else{
printf("暂无\n");
}
}
fclose(fp);
return 0;
}