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

计算机软件基础强化实践能力培养实践部分考核作业强化实践能力培养的考核要求： 要求学生通过对本课程中所学知识的归纳、总结，能够体会数据结构的思想和方法，考生发挥自主学习精神，能独立完成实验要求，并提交实验报告。 实验报告的基本要求如下： （1）题目 （2）实验环境 （3）实验容与完成情况：述程序设计的任务和程序所能够达到的功能，提交带有注释的源程序清单。 （4）调试分析： 1）调试过程中所遇到的问题与解决的方法； 2）算法的时间和空间复杂度分析（数据结构部分）； 3）经验和体会：列出遇到的问题和解决办法与没有解决的问题。 （5）测试结果：列出使用典型的数据输入用例所产生的输出结果。强化实践能力培养的考核容：（1） 编程实现计算器。（10分） 要求:输入：两个操作数和一个操作符的数学表达式.; 输出：输入的表达式和结果。（2）利用栈的存储结构，编程实现任意表达式中各种括号（“（、）”，“、”，“、”）交叉使用时，语法的匹配是否合法判定。（10分）（3）排序：实现冒泡排序、直接插入排序和直接选择排序的算法。（10分）要求：手写。大学计算机软件基础强化实践能力培养实践部分考核作业课程名称： 试点学校名称(章)：学生： 学生：12 / 12实验一 计算器1.实验环境：VC+6.0，WindowsXp2.实验目的：熟悉VC+6.0环境；掌握C语言编程基本思想；掌握基本操作符的使用；掌握基本输入输出语句；3.程序清单：#include stdio.h main()float a,b,output;char op;printf(please input two numbers and operatorn);scanf(%f%fn,&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 operatorn);return 0;printf(%5.2f%c%5.2f=%5.2fn,a,op,b,output);4.时间复杂度: O(n)5.空间复杂度: O(1)6.测试结果：实验二 栈在判断括号匹配中的应用1.实验环境：VC+6.0，WindowsXp2.实验目的：1掌握顺序栈的类型定义方法。2掌握栈先进后出运算原则在解决实际问题中的应用3掌握使用栈的原理来解决表达式中的括号配对问题。3.程序清单：#include#include#include#define MAX_STACK_SIZE 100typedef 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 string100;typedef struct nodechar key;element_tr;/运算符栈typedef struct Nodeint 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;elseAj+;break;case : if( Pop(S)!=)a=-1;Aj+;break;elseAj+;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; h0; h=k) /*循环到没有比较围*/ for (j=0, k=0; 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 =0 & t =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+ ) /每一趟选择最小元素并与Ai交换 k=i; for (j=i+1; j=n-1; j+) /查找最小元素的下标 if (Aj.stn Ak.stn ) k=j; if (k!=i) /交换x=Ai; Ai=Ak; Ak=x; 直接选择排序算法分析：也是一种简单的排序方法，它的基本思想是：第一次从R0Rn-1中选取最小值，与R0交换，第二次从R1Rn-1中选取最小值，与R1交换，.，第i次从Ri-1Rn-1中选取最小值，与Ri-1交换，.，第n-1次从Rn-2Rn-1中选取最小值，与Rn-2交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。直接选择排序的时间复杂度为 O(n2)