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

《计算机软件基础》强化实践能力培养实践部分考核作业(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; h=k) /*循环到没有比较范围*/
{
for (j=0, k=0; j <h; j++) /*每次预置k=0，循环扫描后更新k*/
{
if (*(x+j) > *(x+j+1)) /*大的放在后面，小的放到前面*/
{
t = *(x+j);
*(x+j) = *(x+j+1);
*(x+j+1) = t; /*完成交换*/
k = j; /*保存最后下沉的位置。这样k后面的都是排序排好了的。*/
} } } }

冒泡排序算法分析：
在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。时间复杂度：算法时间复杂度O(n2)
2. 直接插入排序:
void insert_sort(int *x, int n)
{ int i, j, t;
for (i=1; i <n; i++) /*要选择的次数：1~n-1共n-1次*/
{ /* 暂存下标为i的数。注意：下标从1开始，原因就是开始时
第一个数即下标为0的数，前面没有任何数，单单一个，认为
它是排好顺序的。
*/
t=*(x+i);
for (j=i-1; j>=0 && t <*(x+j); j--) /*注意：j=i-1，j--，这里就是下标为i的数，在它前面有序列中找插入位置。*/
{
*(x+j+1) = *(x+j); /*如果满足条件就往后挪。最坏的情况就是t比下标为0的数都小，它要放在最前面，j==-1，退出循环*/
}
*(x+j+1) = t; /*找到下标为i的数的放置位置*/
} }

直接插入排序算法分析：在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排 好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
直接插入排序是稳定的。算法时间复杂度O(n2)
3. 直接选择排序:
void SelectSort(ElemType A[], int n)
{ int i, j, k;
ElemType x;
for ( i=0; i<=n-2; i++ )
{ //每一趟选择最小元素并与A[i]交换
k=i;
for (j=i+1; j<=n-1; j++) //查找最小元素的下标
if (A[j].stn <A[k].stn ) k=j;
if (k!=i) { //交换
x=A[i]; A[i]=A[k]; A[k]=x;
}
}
}
直接选择排序算法分析：也是一种简单的排序方法，它的基本思想是：第一次从R[0]~R[n-1]中选取最小值，与R[0]交换，第二次从R[1]~R[n-1]中选取最小值，与R[1]交换，....，第i次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换，.....，第n-1次从R[n-2]~R[n-1]中选取最小值，与R[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。直接选择排序的时间复杂度为 O(n2)