计算机软件技术基础试验指导书.doc

计算机软件技术基础实验指导书一、 实验目的：计算机软件技术基础是一门应用性很强的课程，上机实验是课程的重要环节。本实验是结合计算机软件技术基础课程的学习而开设的实验。本实验目的如下：1. 通过上机实验，加深对软件技术理论知识的理解，增强感性认识和培养实际操作能力；2. 通过使用具体的编程语言，了解算法的实现过程。二、 适用专业： 理学院各本科专业三、 实验学时数： 16学时四、 实验内容及学时安排：试验一：练习C/C+语言编程编译环境，并用数组实现顺序存储的线性表，包括建立线性表插入一个数据元素，删除一个数据元素。学时数：2学时实验内容：建立线性表，访问线性表，实现线性表的链式存储试验二：用链表的形式实现链式的线性表，包括建立线性表插入一个数据元素，删除一个数据元素。学时数：2学时试验三：用数组的形式建立栈和队列，并实现其基本运算:进栈、出栈、进队、出队。学时数：2学时试验四：栈的应用-表达式求值。学时数：2学时实验五：实现二叉树排序。学时数：2学时实验六：实现顺序查找和对分查找。学时数：2学时实验七：实现冒泡排序、插入排序学时数：2学时实验八：P、V操作模拟学时数：2学时五、 教材及参考文献1.沈被娜等，计算机软件技术基础，清华大学出版社，2003.72宫云战，计算机软件技术基础，机械工业出版社，2000.13.严尉敏，吴伟民，数据结构（第二版），清华大学出版社，19924.汤子瀛，哲凤屏，汤小丹，计算机操作系统，西安电子科技大学，20045.冯玉才，数据库系统基础，华中工学院出版社，1984六、 实验环境TC 2.0 或 VC+ 6.0七、 成绩考核上机实验考核采取实验报告和上机抽查检验相结合的方式。每次实验结束后都写出实验报告。附：实验四和实验八的参考程序1、 实验四的参考程序#include #include #include /判断是否为字符的函数的头文件#define maxsize 100typedef int elemtype;typedef struct sqstack sqstack;/由于sqstack不是一个类型 而struct sqstack才是char ch7=+,-,*,/,(,),;/把符号转换成一个字符数组int f17=3,3,5,5,1,6,0;/栈内元素优先级/-struct sqstackelemtype stackmaxsize;int top;/-void Initstack(sqstack *s)s-top=0;/-void Push(sqstack *s,elemtype x)if(s-top=maxsize-1)printf(Overflown);elses-top+;s-stacks-top=x;/-void Pop(sqstack *s,elemtype *x)if(s-top=0)printf(underflown);else*x=s-stacks-top;s-top-;/-elemtype Gettop(sqstack s)if(s.top=0)printf(underflown);return 0;else return s.stacks.top;/-elemtype f(char c)switch(c)case +: return 0;case -: return 1;case *: return 2;case /: return 3;case (: return 4;case ): return 5;default: return 6;/-char precede(char c1,char c2)int i1=f(c1);int i2=f(c2); /把字符变成数字if(f1i1f1i2) /通过原来设定找到优先级return ;else if(f1i1f1i2)return ;else return =;/-int Operate(elemtype a,elemtype theta,elemtype b) int sum;switch(theta)case 0: sum=a+b;break;case 1: sum=a-b;break;case 2: sum=a*b;break;default:sum=a/b;return sum;/-EvaluateExpression()char c;int i=0,sum=0;int k=1,j=1;/设置了开关变量elemtype x,theta,a,b;sqstack OPTR,OPND;Initstack(&OPTR);Push(&OPTR,f(;); /把表达式结束符压入栈Initstack(&OPND);c=getchar();if(c=ch2|c=ch3|c=ch5|c=ch6) / * / ) ; /表达式的首字符为上述情况时是违法的printf(错误1 n);k=0;return 0; if(c=ch0) c=getchar();/如果是+，则继续读下一个字符，把前面的+覆盖if(c=ch1) j=0;c=getchar();/也把-号覆盖while(c!=;|chGettop(OPTR)!=;)if(isdigit(c) /判断字符c是否数字sum=0;while(isdigit(c)if(!j)sum=sum*10-(c-0);/实现了数字串前面有负号/（之前是：sum=-(sum*10)-(c-0)结果是121321）elsesum=sum*10+(c-0);c=getchar();Push(&OPND,sum);/如果还是数字先不压栈，把数字串转化成十进制数字再压栈j=1;elseif(k)switch(precede(chGettop(OPTR),c)case: Pop(&OPTR,&theta); Pop(&OPND,&b); Pop(&OPND,&a);/注意这里是谁先出栈 Push(&OPND,Operate(a,theta,b); break;/在这里判断是否以运算符结束是不对的return(Gettop(OPND);/-int main()int result;printf(输入你的算术表达式：n);result=EvaluateExpression();printf(结果是 :%dn,result);return 0;2、 实验八的参考程序#includeusing namespace std;typedef void (*ElemType)();int SV=100; /SV is a shared s=1; /信号量struct Node ElemType data; Node *next;struct queueNode *front,*rear;void INIQUEUE(queue &q)Node *p; p=new Node;p-data=NULL; p-next=NULL; q.front=p; q.rear=p;void push(queue &q, ElemType x)Node *p;p=new Node; p-data=x; p-next=NULL;q.rear-next=p;q.rear=p;int empty(queue &q) if (q.front=q.rear) return 1; else return 0;ElemType gethead(queue &q) if (q.front=q.rear) return NULL; else return q.front-next-data; ElemType pop(queue &q) if (empty(q)coutError: the queue is empty!next;if (p-next=NULL)q.front-next=NULL;q.rear=q.front;elseq.front-next=p-next;data=p-data;delete (p);return data;void sleep(queue &q,ElemType pf)push(q,pf);void wakeup(queue &q)if (empty(q) cout队列为空，没有等待进程endl; return;elseElemType pf;pf=pop(q); pf(); int P(ElemType data,queue &q)s=s-1;cout信号量s=sendl;if (s0) cout共享数据被占用，请等待.endlendl;sleep(q,data);return 0;elsereturn 1;void V(queue &q) s=s+1; cout信号量s=sendl; if (s=0) cout释放共享数据，唤醒被挂起的进程（函数）.endlendl; wakeup(q); else cout释放共享数据. 没有被挂起的进程（函数）endlendl; void P1_1()cout进入P1_1(),开始使用共享数据SV.endl;coutSV=SVendlendl;void P1_2()cout结束使用共享数据SV,退出P1_2()endlendl;void P2_1()cout进入P2_1(),开始使用共享数据SV.endl;coutSV=SVendlendl;void P2_2(