数据结构习题(4)

for(i=0;i

题 算法与数据结构实验题 9.3 异或二 二 ★ 实验任务

有一串数字，把一定区间内的数字异或起来得到一个数。 有时候，这个数字会变成 0。

(其中 ^ 表示异或。把数字用二进制表示后。每位按照异或产生新的数。) 1 ^ 1 = 0 ^ 0 = 0 , 1 ^ 0 = 0 ^ 1 = 1.

(如 4 ^ 5 = (100) ^ (101) = (001) = 1) Ps : 各种课上都有讲过。 问有多少个区间，这个数字会变为 0。(区间内至少有一个数) ★ 数据输入

第一行为一整数 N。(1<=N<=200000) 接下来 N 行第 i 行整数 x。

表示这串数字的第 i 个数。(数字在 int 非负整数范围) ★ 数据输出

输出有多少个区间。 输入示例 输出示例 4 0 0 0 0 10

#include

void temp(int &a,int &b) { int t=a; a=b; b=t;

}

void Max_Heapify(int *a,int i,int n) { int l=2*i; int r=2*i+1; int largest; if(l<=n&&a[l]>a[i]) largest=l; else largest=i; if(r<=n&&a[r]>a[largest]) largest=r; if(largest!=i) { temp(a[i],a[largest]); Max_Heapify(a,largest,n); } }

int main(){ int n; int i,j; int s=0; int sum[200024]={0}; scanf(\ for(i=0;i0;i--) { Max_Heapify(sum,i,n); } int m=n; for(i=m;i>1;i--) { temp(sum[1],sum[i]); n--; Max_Heapify(sum,1,n); } sum[m+1]=-1; int count=0; for(i=1;i

s+=count; i++; } count=0; } printf(\}

数据结构与算法实验题3.4 后缀表达式 ★实验任务

通常算式的表达不止一种，有一种叫做后缀表达式，而我们平常使用的是中缀表 达式（a+b 是中缀表达式，而 ab+是后缀表达式），现在想对一些中缀表达式计算 出他们的后缀表达式，你能帮助他吗？ ★数据输入

读入一个只包含+, -, *, / ，%，（，）的非负整数计算表达式（%为求余操作）， 该表达式的后缀表达式。

每个输入为一行字符串，字符串长度不超过 100000，整数和运算符之间用一个 空格分隔。没有非法表达式。 ★数据输出

对于每个输入，输出该表达式的后缀表达式，数与数之间、符号与数之间、符号 与符号之间都应有一个空格隔开（注意行末无空格）。 输入示例 输出示例

681 + 62 - 83 % 5 681 62 + 83 5 % - #include #include #include struct MyStack { char ele[100001]; int num; void initMessage(){ num=0; } void push(char c){ ele[num]=c; num++; } void pop(){ num--; } char top() { return ele[num-1]; } int isEmpty(){

return num<=0?1:0; } bool hasContined(){ for(int i=0;i

}; //( ( ( 1 * ( 2 * ( 3 + 4 / 5 ) ) - ( ( ( 6 + ( ( ( 8 + 9 ) * 5 ) / 4 ) ) - 4 ) ) ) ) ) int main(){ char a[100001]; MyStack stack; stack.initMessage(); gets(a); for(int i=0;i

else if(a[i]=='('){ stack.push(a[i]); } else if(a[i]==')'){ stack.popContined(); } else if(a[i]=='+'||a[i]=='-'){ if(stack.isEmpty()){ stack.push(a[i]); } else{ if(stack.top()=='*'||stack.top()=='/'||stack.top()=='%'){ while(stack.top()!='(') { printf(\ stack.pop(); if((i!=strlen(a)-1))putchar(' '); if(stack.isEmpty())break; } stack.push(a[i]); } else if(stack.top()=='('){ stack.push(a[i]); } else{ printf(\ if(i!=strlen(a)-1)putchar(' '); stack.pop(); stack.push(a[i]); } } } else{ if(stack.isEmpty()){ stack.push(a[i]); } else if(stack.top()=='+'||stack.top()=='-'||stack.top()=='('){ stack.push(a[i]); } else{ while(1){ if(stack.top()=='('||stack.top()=='+'||stack.top()=='-'||stack.isEmpty()) break; printf(\