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

《《计算机软件基础》强化实践能力培养实践部分考核作业(一)》由会员分享，可在线阅读，更多相关《《计算机软件基础》强化实践能力培养实践部分考核作业(一)（13页珍藏版）》请在装配图网上搜索。

1、强化实践能力培养的考核要求：要求学生通过对本课程中所学知识的归纳、总结，能够体会数据结构的思 想和方法，考生发挥自主学习精神，能独立完成实验要求，并提交实验报告。实验报告的基本要求如下：(1)题目(2)实验环境(3)实验内容与完成情况：陈述程序设计的任务和程序所能够达到的功能，提交带有注释的源程序清单。(4)调试分析：1 )调试过程中所遇到的问题及解决的方法；2 )算法的时间和空间复杂度分析(数据结构部分)；3 )经验和体会：列出遇到的问题和解决办法及没有解决的问题。(5)测试结果：列出使用典型的数据输入用例所产生的输出结果。强化实践能力培养的考核内容：(1)编程实现计算器。(10分)要求:输

2、入：两个操作数和一个操作符的数学表达式.；输出：输入的表达式和结果。(2)利用栈的存储结构，编程实现任意表达式中各种括号(“(、)”，“、”，“、”)交叉使用时，语法的匹配是否合法判定。(10分)(3)排序：实现冒泡排序、直接插入排序和直接选择排序的算法。(10分)要求：手写课程名称:学生姓名:试点学校名称（章）：学生准考证号码：实验一计算器1 .实验环境：VC+6.0 , WindowsXp2 .实验目的：熟悉VC+6.0环境；掌握C语言编程基本思想；掌握基本操作符的使用；掌握基本输入输出语句；3 .程序清单：#include stdio.hmain()float a,b,output;ch

3、ar 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 .空

4、间复杂度：O(1)6 .测试结果：实验二栈在判断括号匹配中的应用1 .实验环境：VC+6.0 , WindowsXp2 .实验目的：1.掌握顺序栈的类型定义方法。2 .掌握栈先进后出运算原则在解决实际问题中的应用3 .掌握使用栈的原理来解决表达式中的括号配对问题3.程序清单：#include#include#include#define MAX_STACK_SIZE 100typedef struct SqStackchar data;struct SqStack *next;SqStack;/ 链元素typedef struct Stackstruct SqStack *base; 栈底指针

5、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;

6、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=11ch=11ch=)a=-

7、1;Aj=1;if(ch=11ch=(|ch=)&(sh=)a=-1;Aj+;break;if(a=-1)break;w+;if(ch=11ch=(|ch=|ch=|ch=11ch=) 判断是否满足入栈和出栈条件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

8、;case :if( Pop(S)!=)a=-1;Aj+;break; else Aj+;break;/出栈并与字符ch匹配比较ch=*(+st);sh=*(+stt);if(S.base=S.top)&(ch=|ch=11ch=) 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 )个

9、括号与对应括号不匹配n,Aj)；goto LL;elseprintf（表达式中括号匹配n）;printf(继续请输入y,退出请输入n!n);w=getchar();getchar();printf(*谢谢使用本系统!*n)；4 .实验分析：算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之 匹配，并且每对括号之间可以嵌套，但不能出现交叉情况。我们可以利用一个栈结构保存每 个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。4.1 括号不匹配的情况：在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。(1)当遇到某一个右括号时，栈已空，说明到目前为止，右

10、括号多于左括号；(2)从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况；(3)算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。4.2 括号匹配的情况表达式中允许含有三种括号，括号对之间允许嵌套，本实验编写一个程序判断从键盘输 入的任意表达式中括号是否配对，括号不配对包括以下几种情况：(1)左括号多余(2)右括号多余(3)左右括号不匹配，如左圆括号对着的是右方括号等。5 .运行结果：1 .表达式中括号匹配:匾谓术嚷达解以“/结束输入 蠢算辱暨退出请输入，一 石输入算术表达式并以结束输人二 3-4J/5+6*3- 表法式巾军号匹配 郊续I青榆入退出请榆入备

11、输入算术表达式并以结束输入; (+*9- 赛达式中括号喳己 藤续请输入“了 .退出请输入 W n MKKMKXKX-射谢使用本系统? KMMMKXXNiPiEss any key to cort inue2 .表达式中括号不匹配:结束输入:请输入算术:T(1+2-蠡霍I慈蒲注罐匹配.请重新输入蠡瀛露加嚼鼾/4+2*4-3z5*L3诩1=表达式电第S .、请需入算采表达式并E号不匹配，请重新输入：C(l+2/42*4_3/5*r3t81 =苣达式中括号匹配出续请输大，退出请输入7 r*谢谢使用本系统，”Pitess Any key co continue实验三排序算法一、实验题目：冒泡排序、直接

12、插入排序和直接选择排序的算法、实验环境：windowXP、VC+6.0 三、实验目的：通过编程熟练掌握实现冒泡排序、直接插入排序和直接选择排 序的算法。四：程序清单:1.冒泡排序:int j, k, h, t;for (h=n-1; h0; h=k) /*for (j=0, k=0; j *(x+j+1)/*void bubble_sort(int *x, int n)循环到没有比较范围*/每次预置k=0,循环扫描后更新k*/大的放在后面，小的放到前面*/t = *(x+j);*(x+j) = *(x+j+1);*(x+j+1) = t; /*完成交换*/k = j; /* 保存最后下沉的位置

13、。这样k后面的都是排序排好了的。*/ 冒泡排序算法分析：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对 相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即： 每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。时 间复杂度：算法时间复杂度O(n2)2 .直接插入排序：void insert_sort(int *x, int n) int i, j, t;for (i=1; i =0 & t =2个数 已经是排 好顺序的，现在要把第n个数插到前面的有序数中，使得这 n个 数也是排好顺序的。如此反复循环，直到全部排好顺序。直接插入排序是稳定的。算法时

14、间复杂度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;直接选择排序算法分析：也是一种简单的排序方法，它的基本思想是：第一次从R0卜Rn-1中选取最小值，与R0交换，第二次从R1卜Rn-1中选取最小值， 与R1交换，.，第i次从Ri-1卜Rn-1中选取最小值，与Ri-1交换，.，第 n-1次从Rn-2卜Rn-1中选取最小值，与Rn-2交换，总共通过n-1次，得到一 个按排序码从小到大排列的有序序列。直接选择排序的时间复杂度为O(n2)