《计算机软件基础》强化实践能力培养实践部分考核作业(1)

《计算机软件基础》强化实践能力培养实践部分考核作业

强化实践能力培养的考核要求：

要求学生通过对本课程中所学知识的归纳、总结，能够体会数据结构的思想和方法，考生发挥自主学习精神，能独立完成实验要求，并提交实验报告。 实验报告的基本要求如下： （1）题目 （2）实验环境

（3）实验内容与完成情况：陈述程序设计的任务和程序所能够达到的功能，提交带有注释的源程序清单。 （4）调试分析：

1）调试过程中所遇到的问题及解决的方法； 2）算法的时间和空间复杂度分析（数据结构部分）；

3）经验和体会：列出遇到的问题和解决办法及没有解决的问题。 （5）测试结果：列出使用典型的数据输入用例所产生的输出结果。

强化实践能力培养的考核内容： （1） 编程实现计算器。（10分）

要求:输入：两个操作数和一个操作符的数学表达式.; 输出：输入的表达式和结果。

（2）利用栈的存储结构，编程实现任意表达式中各种括号（“（、）”，“[、]”，“{、}”）交叉使用时，语法的匹配是否合法判定。（10分）

（3）排序：实现冒泡排序、直接插入排序和直接选择排序的算法。（10分）

要求：手写。

山东大学《计算机软件基础》强化实践能力培养实践部分考核作业

课程名称： 试点学校名称(章)： 学生姓名： 学生准考证号码：

实验一 计算器

1.实验环境：VC++6.0 ，WindowsXp 2.实验目的：熟悉VC++6.0环境；

掌握C语言编程基本思想； 掌握基本操作符的使用； 掌握基本输入输出语句；

3.程序清单：

#include "stdio.h" main() {

float a,b,output; char op;

printf("please input two numbers and operator\n"); scanf("%f%f\n",&a,&b); scanf("%c",&op); switch(op) {

case '+':output=a+b;break; case '-':output=a-b;break; case '*':output=a*b;break;

case '/':output=(float)a/b;break; default:printf("wrong operator\n"); return 0; }

printf("%5.2f%c%5.2f=%5.2f\n",a,op,b,output); } 4.时间复杂度: O(n) 5.空间复杂度: O(1)

6.测试结果：

实验二 栈在判断括号匹配中的应用

1.实验环境：VC++6.0 ，WindowsXp

2.实验目的：1．掌握顺序栈的类型定义方法。。

2．掌握栈先进后出运算原则在解决实际问题中的应用 3．掌握使用栈的原理来解决表达式中的括号配对问题。

3.程序清单： #include<stdio.h> #include<stdlib.h> #include<string.h> #define MAX_STACK_SIZE 100 typedef struct SqStack{ char data;

struct SqStack *next; }SqStack;//链元素 typedef struct Stack{

struct SqStack *base; //栈底指针 struct SqStack *top; //栈顶指针 }Stack;//栈 Stack S;

int a,Aj=0;//全局变量 char string[100]; typedef struct node{ char key;

}element_tr;//运算符栈 typedef struct Node{ int data;

}element_nd;//操作数元素

void creatstack(Stack &S) {

S.top=S.base=NULL; }//建立初始化链栈

void push(Stack &S,char e) {

SqStack* Q;

Q=(SqStack*)malloc(sizeof(SqStack)); Q->next=S.top; S.top=Q; S.top->data=e; ++Aj; }//左括号入栈 char Pop(Stack &S) { char e; SqStack *q; e=S.top->data; q=S.top->next; free(S.top); S.top=q; return e; }//括号出栈 int check( ) { a=1,Aj=0; int w=0;

char sh,ch,*st,*stt;

printf("请输入算术表达式并以"="结束输入:\n"); scanf("%s",string); getchar(); st=stt=string; ch=*st; sh=*++stt; while(ch!='=') {

if(w==0)

if(ch==']'||ch=='}'||ch==')') {a=-1; Aj=1;}

if((ch=='['||ch=='('||ch=='{')&&(sh=='=')) {a=-1; Aj++; break;} if(a==-1) break; w++;

if(ch=='['||ch=='('||ch=='{'||ch==']'||ch=='}'||ch==')')//判断是否满足入栈和出栈条件 switch(ch) { case '[': { push(S,ch); break;} case '{': {

push(S,ch); break;} case '(': { push(S,ch); break;}//左括号入栈 case ']': if(Pop(S)!='[') {a=-1; Aj++; break;} else { Aj++; break;} case ')':

if( Pop(S)!='(') {a=-1; Aj++; break;} else {Aj++; break;} case '}':

if( Pop(S)!='{') { a=-1; Aj++; break;} else {Aj++; break;}

}//出栈并与字符ch匹配比较 ch=*(++st); sh=*(++stt);

if((S.base==S.top)&&(ch==']'||ch=='}'||ch==')')) { a=-1; Aj++;} if(a==-1) break;} if(S.base!=S.top) a=-1; return a; }

void main()//主函数 {

int st; char w='y';

printf("\n*******括号配对判别********\n"); LL :while(w!='n'&&w!='N') {

creatstack(S); st=check(); if(st==-1) {

printf("表达式中第( %d )个括号与对应括号不匹配,请重新输入\n",Aj);

goto LL;} else

{printf("表达式中括号匹配\n");

}

printf("继续请输入"y",退出请输入"n"!\n"); w=getchar(); getchar(); }

printf("********谢谢使用本系统!********\n"); }

4.实验分析：算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之

匹配，并且每对括号之间可以嵌套，但不能出现交叉情况。我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。

4.1括号不匹配的情况：

在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。 （1）当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号；

（2）从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况； （3）算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。

4.2括号匹配的情况

表达式中允许含有三种括号，括号对之间允许嵌套，本实验编写一个程序判断从键盘输入的任意表达式中括号是否配对，括号不配对包括以下几种情况： （1）左括号多余 （2）右括号多余

（3）左右括号不匹配，如左圆括号对着的是右方括号等。

5.运行结果：

1.表达式中括号匹配：

2.表达式中括号不匹配：

实验三 排序算法

一、实验题目：冒泡排序、直接插入排序和直接选择排序的算法。 二、实验环境：windowXP、VC++6.0

三、实验目的：通过编程熟练掌握实现冒泡排序、直接插入排序和直接选择排序的算法。 四：程序清单：

1. 冒泡排序：

void bubble_sort(int *x, int n) {

int j, k, h, t;

for (h=n-1; h>0; …… 此处隐藏：3267字，全部文档内容请下载后查看。喜欢就下载吧 ……