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

1《计算机软件基础》强化实践能力培养实践部分考核作业强化实践能力培养的考核要求：要求学生通过对本课程中所学知识的归纳、总结，能够体会数据结构的思想和方法，考生发挥自主学习精神，能独立完成实验要求，并提交实验报告。实验报告的基本要求如下：（1）题目（2）实验环境（3）实验内容与完成情况：陈述程序设计的任务和程序所能够达到的功能，提交带有注释的源程序清单。（4）调试分析：1）调试过程中所遇到的问题及解决的方法；2）算法的时间和空间复杂度分析（数据结构部分）；3）经验和体会：列出遇到的问题和解决办法及没有解决的问题。（5）测试结果：列出使用典型的数据输入用例所产生的输出结果。强化实践能力培养的考核内容：（1）编程实现计算器。（10分）要求:输入：两个操作数和一个操作符的数学表达式.;输出：输入的表达式和结果。（2）利用栈的存储结构，编程实现任意表达式中各种括号（“（、）”，“[、]”，“{、}”）交叉使用时，语法的匹配是否合法判定。（10分）（3）排序：实现冒泡排序、直接插入排序和直接选择排序的算法。（10分）要求：手写。2山东大学《计算机软件基础》强化实践能力培养实践部分考核作业课程名称：试点学校名称(章)：学生姓名：学生准考证号码：3实验一计算器1.实验环境：VC++6.0，WindowsXp2.实验目的：熟悉VC++6.0环境；掌握C语言编程基本思想；掌握基本操作符的使用；掌握基本输入输出语句；3.程序清单：#includestdio.hmain(){floata,b,output;charop;printf(pleaseinputtwonumbersandoperator\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(wrongoperator\n);return0;}printf(%5.2f%c%5.2f=%5.2f\n,a,op,b,output);}4.时间复杂度:O(n)5.空间复杂度:O(1)6.测试结果：4实验二栈在判断括号匹配中的应用1.实验环境：VC++6.0，WindowsXp2.实验目的：1．掌握顺序栈的类型定义方法。。2．掌握栈先进后出运算原则在解决实际问题中的应用3．掌握使用栈的原理来解决表达式中的括号配对问题。3.程序清单：#includestdio.h#includestdlib.h#includestring.h#defineMAX_STACK_SIZE100typedefstructSqStack{chardata;structSqStack*next;}SqStack;//链元素typedefstructStack{structSqStack*base;//栈底指针structSqStack*top;//栈顶指针}Stack;//栈StackS;inta,Aj=0;//全局变量charstring[100];typedefstructnode{charkey;}element_tr;//运算符栈typedefstructNode{intdata;}element_nd;//操作数元素5voidcreatstack(Stack&S){S.top=S.base=NULL;}//建立初始化链栈voidpush(Stack&S,chare){SqStack*Q;Q=(SqStack*)malloc(sizeof(SqStack));Q-next=S.top;S.top=Q;S.top-data=e;++Aj;}//左括号入栈charPop(Stack&S){chare;SqStack*q;e=S.top-data;q=S.top-next;free(S.top);S.top=q;returne;}//括号出栈intcheck(){a=1,Aj=0;intw=0;6charsh,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'{':{7push(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;}8}//出栈并与字符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;returna;}voidmain()//主函数{intst;charw='y';printf(\n*******括号配对判别********\n);LL:while(w!='n'&&w!='N'){creatstack(S);st=check();if(st==-1){printf(表达式中第(%d)个括号与对应括号不匹配,请重新输入\n,Aj);gotoLL;}else{printf(表达式中括号匹配\n);9}printf(继续请输入y,退出请输入n!\n);w=getchar();getchar();}printf(********谢谢使用本系统!********\n);}4.实验分析：算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之匹配，并且每对括号之间可以嵌套，但不能出现交叉情况。我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。4.1括号不匹配的情况：在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。（1）当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号；（2）从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况；（3）算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。4.2括号匹配的情况表达式中允许含有三种括号，括号对之间允许嵌套，本实验编写一个程序判断从键盘输入的任意表达式中括号是否配对，括号不配对包括以下几种情况：（1）左括号多余（2）右括号多余（3）左右括号不匹配，如左圆括号对着的是右方括号等。5.运行结果：1.表达式中括号匹配：102.表达式中括号不匹配：11实验三排序算法一、实验题目：冒泡排序、直接插入排序和直接选择排序的算法。二、实验环境：windowXP、VC++6.0三、实验目的：通过编程熟练掌握实现冒泡排序、直接插入排序和直接选择排序的算法。四：程序清单：1.冒泡排序：voidbubble_sort(int*x,intn){intj,k,h,t;for(h=n-1;h0;h=k)/*循环到没有比较范围*/{for(j=0,k=0;jh;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.直接插入排序:voidinsert_sort(int*x,intn){inti,j,t;for(i=1;in;i++)/*要选择的次数：1~n-1共n-1次*/{/*暂存下标为i的数。注意：下标从1开始，原因就是开始时第一个数即下标为0的数，前面没有任何数，单单一个，认为它是排好顺序的。*/t=*(x+i);12for(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.直接选择排序:voidSelectSort(ElemTypeA[],intn){inti,j,k;ElemTypex;for(i=0;i=n-2;i++){//每一趟选择最小元素并与A[i]交换k=i;for(j=i+1;j=n-1;j++)//查找最小元素的下标if(A[j].stnA[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)