《计算机软件基础》强化实践能力培养实践部分考核作业
强化实践能力培养的考核要求：
要求学生通过对本课程中所学知识的归纳、总结，能够体会数据结构的思想和方法，考生发挥自主学习精神，能独立完成实验要求，并提交实验报告。 实验报告的基本要求如下： （1）题目 （2）实验环境
（3）实验内容与完成情况：陈述程序设计的任务和程序所能够达到的功能，提交带有注释的源程序清单。 （4）调试分析：
1）调试过程中所遇到的问题及解决的方法； 2）算法的时间和空间复杂度分析（数据结构部分）；
3）经验和体会：列出遇到的问题和解决办法及没有解决的问题。 （5）测试结果：列出使用典型的数据输入用例所产生的输出结果。
强化实践能力培养的考核内容： （1） 编程实现计算器。（10分）
要求:输入：两个操作数和一个操作符的数学表达式.; 输出：输入的表达式和结果。
（2）利用栈的存储结构，编程实现任意表达式中各种括号（“（、）”，“[、]”，“{、}”）交叉使用时，语法的匹配是否合法判定。（10分）
（3）排序：实现冒泡排序、直接插入排序和直接选择排序的算法。（10分）
要求：手写。
1
山东大学《计算机软件基础》强化实践能力培养实践部分考核作业
课程名称： 试点学校名称(章)： 学生姓名： 学生准考证号码：
2
实验一 计算器
1.实验环境：VC++6.0 ，WindowsXp 2.实验目的：熟悉VC++6.0环境；
掌握C语言编程基本思想； 掌握基本操作符的使用； 掌握基本输入输出语句；
3.程序清单：
#include \ main() {
float a,b,output; char op;
printf(\scanf(\scanf(\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(\ return 0; }
printf(\} 4.时间复杂度: O(n) 5.空间复杂度: O(1)
6.测试结果：
3
实验二 栈在判断括号匹配中的应用
1.实验环境：VC++6.0 ，WindowsXp
2.实验目的：1．掌握顺序栈的类型定义方法。。
2．掌握栈先进后出运算原则在解决实际问题中的应用 3．掌握使用栈的原理来解决表达式中的括号配对问题。
3.程序清单： #include
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;//操作数元素
4
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;
5
char sh,ch,*st,*stt;
printf(\请输入算术表达式并以\结束输入:\\n\ scanf(\ 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 '{': {
6
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;}
7
}//出栈并与字符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\LL :while(w!='n'&&w!='N') {
creatstack(S); st=check(); if(st==-1) {
printf(\表达式中第( %d )个括号与对应括号不匹配,请重新输入\\n\
goto LL;} else
{printf(\表达式中括号匹配\\n\
8
}
printf(\继续请输入\退出请输入\ w=getchar(); getchar(); }
printf(\谢谢使用本系统!********\\n\}
4.实验分析：算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之
匹配，并且每对括号之间可以嵌套，但不能出现交叉情况。我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。
4.1括号不匹配的情况：
在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。 （1）当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号；
（2）从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况； （3）算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。
4.2括号匹配的情况
表达式中允许含有三种括号，括号对之间允许嵌套，本实验编写一个程序判断从键盘输入的任意表达式中括号是否配对，括号不配对包括以下几种情况： （1）左括号多余 （2）右括号多余
（3）左右括号不匹配，如左圆括号对着的是右方括号等。
5.运行结果：
1.表达式中括号匹配：
9
2.表达式中括号不匹配：
10
实验三 排序算法
一、实验题目：冒泡排序、直接插入排序和直接选择排序的算法。 二、实验环境：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 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 { /* 暂存下标为i的数。注意：下标从1开始，原因就是开始时 第一个数即下标为0的数，前面没有任何数，单单一个，认为 它是排好顺序的。 */ t=*(x+i); 11 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 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) 12
