当前位置:   article > 正文

BUAA 2019 数据结构第一次上机_北航数据结构上机

北航数据结构上机

BUAA 2019 数据结构第一次上机

虽然数据结构已经学完,但感觉学得不是很好,趁着现在有时间,整理一下以前上机的题目.


1 表达式计算(支持空格,连乘,连除)

【问题描述】

从标准输入中读入一个整数算术运算表达式,如5 - 1 * 2 * 3 + 12 / 2 / 2 = 。计算表达式结果,并输出。

要求:
1、表达式运算符只有+、-、*、/,表达式末尾的’=’字符表示表达式输入结束,表达式中可能会出现空格;
2、表达式中不含圆括号,不会出现错误的表达式;
3、出现除号/时,以整数相除进行运算,结果仍为整数,例如:5/3结果应为1。

【输入形式】

在控制台中输入一个以’=’结尾的整数算术运算表达式。

【输出形式】

向控制台输出计算结果(为整数)。

【样例1输入】

5 - 1 * 2 * 3 + 12 / 2 / 2 =

【样例1输出】

2

【样例2输入】

500 =

【样例2输出】

500

【样例1说明】

输入的表达式为5 - 1 * 2 * 3 + 12 / 2 / 2 =,按照整数运算规则,计算结果为2,故输出2。

【样例2说明】

输入的表达式为500 = ,没有运算符参与运算,故直接输出500。

算法之一提示:
1、可以利用gets函数,读取整行表达式;
2、对于空格,可以考虑首先去除表达式中的所有空格
3、可以设一计数器用来记录已读取、但未参加运算的运算符的个数,根据该计数器来判断如何进行运算;
4、可以设计一函数:实现二元整数算术运算。

【评分标准】

该题要求输出整数表达式的计算结果,共有5个测试点。上传C语言文件名为example1c.c。

思路:

这题没有括号,难度是初级。 下面说说思路:

我们建立两个栈,一个用来存数字,一个用来存操作符,如: + , - , * , / 但需要注意的是操作符运算的优先级 即先乘除,后加减

那么我们就在压栈的时候把乘除操作做完(即取数字栈栈顶的两个数字,对其进行乘 / 除), 并把乘除操作后的数字压入栈中这个很重要

需要注意的是,在下面的代码中是先判断符号栈栈顶是不是乘除号,后把当前读入符号压入栈中,也就意味着最后一次压入的操作符可能是乘除号,我们需要在此做特殊操作

经过以上操作之后,符号栈中只有加减号了,那么直接对栈中元素遍历,就完事了。

这个题就只考察了栈的概念和基本操作。嗯,就这样。

题解:

不要照搬,查重还是很厉害的

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
#include <math.h>
char opt[12315];
int top1,top2;
char s[12315];
long  long stack[12315];
int main()
{
    int i;
    long long temp;
    scanf("%[^=]",&s);                        //读入 = 前的字符串
    int len = strlen(s);
    for(i = 0; i < len; i++)
    {
        temp = 0;
        if(s[i] == ' ') continue;        	 //若是' ' 跳过
        if(s[i] >= '0' && s[i] <='9')		 // 读入数字
        {
            while(s[i] >= '0' && s[i] <='9') temp = temp*10 + s[i++] - '0';
            stack[++top1] = temp;			//将当前读入的数字压如栈
            i--;                            //为什么要i--呢, 因为前面多加了一个
        }
        else
        {
            char opts = s[i];				//读入操作符
            if( (opt[top2] == '*'|| opt[top2] == '/')&&top1>=2&&top2>=1)      //如果符号栈栈顶为乘除,先算乘除,此时要求数字栈有至少2个数
            {
                if(opt[top2] == '*') temp = stack[top1-1]*stack[top1];        //取出栈顶两个数字进行计算
                else temp = stack[top1-1]/stack[top1];
                top1--;
                top2--;
                stack[top1] = temp;   										  //把计算结果压入栈中
            }
            opt[++top2] = opts;												 //  把本次读入的操作符压入栈中
        }

    }
    if((opt[top2] == '*' || opt[top2] == '/' )&&top1>=2 && top2>=1)           //如果最后一次压入符号栈中的数字是乘除
    {
        if(opt[top2]== '*') temp = stack[top1-1]*stack[top1];
        else temp = stack[top1-1]/stack[top1];
        top1--;
        top2--;
        stack[top1] = temp;
    }
    temp = stack[1];														 //从第一个数开始
    for(i = 1; i< top1; i++)
    {
        if(opt[i]== '+') temp = temp + stack[i+1];							//运算加减
        else temp = temp - stack[i+1];
    }
    printf("%lld",temp);
    return 0;
}



  • 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

2 扩展字符A

【问题描述】
从键盘输入包含扩展符’-'的字符串,将其扩展为等价的完整字符,例如将a-d扩展为abcd,并输出扩展后的字符串。

要求:只处理[a-z]、[A-Z]、[0-9]范围内的字符扩展,即只有当扩展符前后的字符同时是小写字母、大写字母或数字,并且扩展符后的字符大于扩展符前的字符时才进行扩展,其它情况不进行扩展,原样输出。例如:a-R、D-e、0-b、4-B等字符串都不进行扩展。

【输入形式】
从键盘输入包含扩展符的字符串
【输出形式】
输出扩展后的字符串

【输入样例1】
ADEa-g-m02
【输出样例1】
ADEabcdefghijklm02

【输入样例2】
cdeT-bcd
【输出样例2】
cdeT-bcd

【样例说明】
将样例1的输入ADEa-g-m02扩展为:ADEabcdefghijklm02;样例2的输入cdeT-bcd中,扩展符前的字符为大写字母,扩展符后的字符为小写字母,不在同一范围内,所以不进行扩展。
【评分标准】
该题要求扩展字符,提交程序文件expand.c。

思路:

水题,不想讲什么思路了,简单判断一下就行。

题解:


#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
char *low = "abcdefghijklmnopqrstuvwxyz";               //把大写字母,小写字母,数字写进数组里
char *upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
char *num = "0123456789";
char s[505];
int main() 
{
    scanf("%s",s);                                      //读入字符串
    int i;
    for(i = 0; i< strlen(s);i++)                        //大家别学,我是懒得改了,一般的话前面定义个int len = strlen(s)
    {
        if(s[i] >= 'a' && s[i] <='z') printf("%c",s[i]);            //若遇字母,数字,直接输出
        if(s[i] >= 'A' && s[i] <='Z') printf("%c",s[i]);
        if(s[i] >= '0' && s[i] <='9') printf("%c",s[i]);
        if(s[i] == '-')                                             //若遇'-' 进行讨论
        {   
            if(islower(s[i-1])&&islower(s[i+1]) && s[i-1] < s[i+1])                                 // s[i] 前后两都是小写字母,并且前面的字母的ASCII码比后面小
            {
                char *j;
                int flag = 0;
                for(j = low; j< low + 26; j++)                                                      //从s[i-1]的字母输出到s[i+1]的字母
                {
                    if(*j == s[i+1]) break;
                    if(*j == s[i-1]) {flag = 1;continue;}
                    if(flag == 1) printf("%c",*j);
                }
            }
            else if(isupper(s[i-1])&&isupper(s[i+1]) && s[i-1] < s[i+1])                            //判断大写字母 , 与小写字母同理
            {
                char *j;
                int flag = 0;
                for(j = upper; j< upper + 26; j++)
                {
                    if(*j == s[i+1]) break;
                    if(*j == s[i-1]) {flag = 1;continue;}
                    if(flag == 1) printf("%c",*j);
                }
            }
            else if(s[i-1]>='0'&&s[i-1]<='9'&&s[i+1]>='0'&&s[i+1]<='9' && s[i-1] < s[i+1])          //判断数字,与小写字母同理
            {
                char *j;
                int flag = 0;
                for( j = num; j < num +10; j++)
                {
                    if(*j == s[i+1]) break;
                    if(*j == s[i-1]) {flag = 1;continue;}
                    if(flag == 1) printf("%c",*j);
                }
            }
            else printf("%c",s[i]);

        }
    }
    return 0;
}


  • 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

3 超长正整数的减法

【问题描述】
编写程序实现两个超长正整数(每个最长80位数字)的减法运算。

【输入形式】

从键盘读入两个整数,要考虑输入高位可能为0的情况(如00083)。

  1. 第一行是超长正整数A;
  2. 第二行是超长正整数B;

【输出形式】
输出只有一行,是长整数A减去长整数B的运算结果,从高到低依次输出各位数字。要求:若结果为0,则只输出一个0;否则输出的结果的最高位不能为0,并且各位数字紧密输出。
【输入样例】

234098
134098703578230056

【输出样例】
-134098703577995958

【样例说明】
进行两个正整数减法运算, 234098 -134098703578230056 = -134098703577995958。

【评分标准】
完全正确得20分,每个测试点4分,提交程序文件名为subtract.c。

思路:

高精度的模版题。

高精度的思路就是用数组来模拟一个巨大的数字(位数很大的那种),同过对数组的位数的操作达到加,减,乘,除等效果

这个应该是程序设计基础的时候就做过吧。。。 没做过自己想想,也不难,这题也不多说了

注意下面的代码仅仅适用于两个正数相减的情况

题解:

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

const int maxn = 5e5 + 5;
char s1[maxn],s2[maxn],s3[maxn];				//将两个大数字分别保留在s1,s2中,s3临时用
int a[maxn], b[maxn], c[maxn];					//将s1,s2的每一位转化成数字,存在a,b,中,c中存a,b相减后的结果


// 为方便说,下面说的数字a,数字b,就是从s1,s2读入的数字,别理解歪了,和数组a,数组b区分开
int main(){
	scanf("%s%s",s1,s2);
	int lena = strlen(s1);
	int lenb = strlen(s2);
	if(lena < lenb || (lena == lenb && strcmp(s1,s2) < 0)){   //如果数a比数b小,输出负号并交换两个数,做到大数减小数
		putchar('-');
		strcpy(s3,s1);
		strcpy(s1,s2);
		strcpy(s2,s3);
		int t = lena;
		lena = lenb;
		lenb = t;
	}
	// 很重要倒着将数字存入int数组中,为什么呢?你想想你算减法的时候是不是从个位往前算的 233
	for(int i = 0; i < lena; i++) a[lena - i] = s1[i] - '0'; // from 1 to lena  
	for(int i = 0; i < lenb; i++) b[lenb - i] = s2[i] - '0'; // from 1 to lenb

	int i = 1;
 	while( i <= lena && i <= lenb){
 		if(a[i] - b[i] < 0) {a[i] += 10; a[i+1]--;}			//不够减向上一位借个1 是不是很形象
 		c[i] = a[i] - b[i];									//将计算结果输入保存结果的数字中
 		i++;
 	}
 	// 默认lena >= lenb
 	while( i <= lena ) {									//如果数字a位数很多,数字b位数比他少,那么上一步结束后i == lenb 还有一些未处理的数字在数组a中
 		if(a[i] < 0) {a[i]  += 10; a[i+1]--;}				//这一步就是对这些数字进行操作
 		c[i] = a[i];										
 	}

 	// 上一步结束后 i == lena 但是次数可能会有前导0,下一步就是把前导零删除
 	while(!c[i] && i > 1) i--;								
 	for(int j = i; j >= 1; j--) printf("%d",c[j]);			//倒序输出,为什么要倒序呢?还记不记得上面你已经倒序了一次,这回就是给他正过来

	return 0;

}



  • 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

4 小数形式与科学计数法转换(简)

【问题描述】

编写一个程序,将用小数表示的浮点数,转换成科学计数法的形式输出。输入的数据没有符号,小数点前后必有数字,且全为有效数据,即小数点后的末尾数字不为0;小数点前若只有一位数字,可以为0,否则小数点前的最高位数字不为0。

提示:以字符串形式保存相关数据。

【输入形式】

从控制台输入一小数,最后有回车换行符,所有输入的字符数不会超过100。

【输出形式】

以科学计数法形式输出数据。输出的数据由以下几部分构成:
1.底数部分是一个小数或整数,若为小数,则小数点前后必有数字,而且都为有效数字。即:小数点前只有一位大于0的数字,小数点后的末尾数字不能为0。若为整数,则只有一位数字,不带小数点。
2.必有小写字母“e”。
3.指数部分是一个整数,若大于等于0,则不带正号“+”。若小于0,则需要带负号“-”,且整数的最高位数字不为0。

【输入样例1】

0.000000000000002

【输出样例1】

2e-15

【输入样例2】

8.9845623489651700659

【输出样例2】

8.9845623489651700659e0

【输入样例3】

367298599999093453490394859509568659795603.4

【输出样例3】

3.672985999990934534903948595095686597956034e41

【样例说明】

以小数形式输入数据,然后转换成科学计数法形式输出。

【评分标准】

该题要求以科学计数法形式输出数据,提交程序文件名为notation.c。

思路:

谔,这个题也不难,也是模拟就能做的题。。。不多讲了

题解:

#include <stdio.h>
#include <string.h>
char s[105];                        //s用来存读入的数字
int num[105];
int main()
{
    int wei=0,i,flag = 0,zf = 0,fcnt = 0,k = 0;
    scanf("%s",s);              //读入数字
    for(i = 0; i< strlen(s);i++) {
        if(s[i] == '.') flag = 1;       //出现小数点了,标记一下
        if(flag == 1) wei++;            //小数点后的数字,小数位数
        if(s[0]=='-') zf = -1;          //如果是负数,记录一下
        if(s[i] != '0'  && s[i] != '-' && s[i] != '.') fcnt = 1;    //发现第一个非零数,标记一下 可能有0.0000123的情况
        if(fcnt == 1 && s[i] != '.') num[k++] = s[i] - '0';         //读入非零数  非零数的个数为K
    }
    wei--;                                                          
    if(zf == -1) printf("-");           //是负数
    for(i = 0; i< k;i++) {
        if(i==1) printf(".%d",num[i]);          //科学技术法的形式,整数位只有一个数
        else printf("%d",num[i]);
    }
    int zhishu = k - 1 - wei;                   //指数就等于总共的非零数的个数 - 小数点后的位数 - 1
    printf("e%d",zhishu);                       //输出指数
    return 0;

}

  • 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

5 全排列数的生成

【问题描述】输入整数N( 1 <= N <= 10 ),生成从1~N所有整数的全排列。
【输入形式】输入整数N。
【输出形式】输出有N!行,每行都是从1~N所有整数的一个全排列,各整数之间以空格分隔。各行上的全排列不重复。输出各行遵循“小数优先”原则, 在各全排列中,较小的数尽量靠前输出。如果将每行上的输出看成一个数字,则所有输出构成升序数列。具体格式见输出样例。
【样例输入1】1
【样例输出1】1
【样例说明1】输入整数N=1,其全排列只有一种。
【样例输入2】3
【样例输出2】
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
【样例说明2】输入整数N=3,要求整数1、2、3的所有全排列, 共有N!=6行。且先输出1开头的所有排列数,再输出2开头的所有排列数,最后输出3开头的所有排列数。在以1开头的所有全排列中同样遵循此原则。
【样例输入3】10
【样例输出3】
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 10 9
1 2 3 4 5 6 7 9 8 10
1 2 3 4 5 6 7 9 10 8
1 2 3 4 5 6 7 10 8 9
1 2 3 4 5 6 7 10 9 8
1 2 3 4 5 6 8 7 9 10
1 2 3 4 5 6 8 7 10 9
1 2 3 4 5 6 8 9 7 10
1 2 3 4 5 6 8 9 10 7
……………………
【样例说明3】输入整数N=10,要求整数1、2、3、……、10的所有全排列。上例显示了输出的前10行。
【运行时限】要求每次运行时间限制在20秒之内。超出该时间则认为程序错误。提示:当N增大时,运行时间将急剧增加。在编程时要注意尽量优化算法,提高运行效率。
【评分标准】该题要求输出若干行整数。。

思路:

这个题比较有意思,用到了dfs的搜索的思路,很简单的dfs,也不想说了。。。。。 别怪我懒,了解一点dfs就能做。

题解:

#include<stdio.h>
int a[10],book[10]={0};
int n;
void dfs(int step) {
    int i;
    if(step==n){
        for(i=0;i<n;i++){
            printf("%d ",a[i]);
        }
        printf("\n");
        return;
    }
    for(i=0;i<n;i++){
        if(book[i]==0){             //第i个数还没有用过
            a[step]=i+1;
            book[i]=1;              //标记第i个数,表示已经用过
            dfs(step+1);
            book[i]=0;              //解除第i个数的标记
        }
    }
}


int main(){
    scanf("%d",&n);
    dfs(0);
    return 0;
}


  • 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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/知新_RL/article/detail/823091
推荐阅读
相关标签
  

闽ICP备14008679号