首页 考试资料幻灯片工程技术公务员考试小学教学中学教学大学教学外语资料
数据结构实验书


#define subs 45 #define mult 42 #define div 47

#define MAXSIZE typedef struct { int

stkdata[MAXSIZE];/*用数组来表示栈空间,定义长度为 MAXSIZE 的堆栈*/

int top; /*栈顶*/ }STKzone; typedef STKzone *STK; bool;

typedef enum{true=1,false=0} typedef enum{ok,error} STKzone expSTKzone; STK expSTK; STK initSTK(STKzone

status;

*stack_zone){

/*执行栈初始化,建栈指针*/ STK p; p=stack_zone; p->top=0; } status push(int *term,STK pstk){

/*将一结构型数据送入栈中*/ if(pstk->top==MAXSIZE) return error; /*栈满,进栈失败*/

pstk->stkdata[pstk->top] =*term; (pstk->top)++;/*栈顶指针移动*/ return ok;

}/*push*/ bool emptySTK(STK pstk){

/*判断栈是否为空栈*/ return(pstk->top==0); } status pop(int *pdata, STK pstk){

/*从栈中取出一结构型数据*/ if(emptySTK(pstk)) return error;

(pstk->top)--;/*退栈*/ *pdata return } void { synerror() =pstk->stkdata[pstk->top]; ok;

printf("n 表达式语法错!");

exit(); } int eval(char { switch(tag) { case case case } } main() { char c; int opd1,opd2,temp,c1; expSTK=initSTK(&expSTKzone); printf("n 后置表达式: "); while((c=getchar())!='n') { if(c== ' ') continue; case add:return(a1+a2); subs:return(a1-a2); mult:return(a1*a2); div:return(a1/a2); tag,int a1,int a2)

if((c>47)&&(c<58)) /*判断是否是 0—9 的字符*/ { putchar(c);

c1=c-48; /*把输入的字符型数字转换成数字*/ if(push(&c1,expSTK)==error)/*运算分量进栈*/ { printf("n 表达式太长n"); exit();} } else if((c==add)||(c==subs)||(c==mult)||(c==div)) { putchar(c); if(pop(&opd1,expSTK)==error) synerror(); if(pop(&opd2,expSTK)==error) synerror(); temp=eval(c,opd2,opd1);/*计算得到结果*/ push(&temp,expSTK);/*将运算结果进栈*/ } else }/*while*/ if(pop(&opd1,expSTK)==error) if(!(emptySTK(expSTK))) printf(“=%-3dn”,opd1); }/*main_end*/ 【测试数据】 输入: 输出: 输入: 输出: 【说明】 本算法中对后置法表示的表达式求值按如下规则进行:自左向右扫描,每遇到一个`n+1 元组 (opd1,opd2,?,opdn,opr) (其中 opd 为操作数, opr 为 n 元运算符), 就计算一次 opr (opd1,opd2,?,opdn) 23+↙ =5 145*+3/3-↙ 4 (即求(1+4*5)/3-3 的结果) (即求 2+3 的结果) synerror(); synerror();/*出现非法字符*/ /*将运算量 2 出栈*/ /*将运算量 1 出栈*/

synerror();

的值,其结果取代原来表达式中 n+1 元组的位置,再从表达式开头重复上述过程,直到表达式中不含运算 符为止。 【实验题】 1. 假设一个算术表达式中包含零对到多对圆括弧,括弧对之间允许嵌套但不允许交叉,编写一个算法并上 机实现:判断输入的表达式是否正确配对。 Status correct(string express);//括弧配对正确,返回 ok,否则返回 error

2. 用栈实现一般表达式(即中缀表达式)到后缀表达式的转换。

第四节 模拟服务台前的排队现象问题

【问题描述】 某银行有一个客户办理业务站,在单位时间内随机地有客户到达,设每位客户的业务办理时间是某个范围 内的随机值。设只有一个窗口,一位业务人员,要求程序模拟统计在设定时间内,业务人员的总空闲时间 和客户的平均等待时间。假定模拟数据已按客户到达的先后顺序依次存于某个正文数据文件中。对应每位 客户有两个数据,到达时间和需要办理业务的时间。 【数据描述】 typedef struct{ int arrive; int treat;//客户的信息结构 }QNODE; typedef struct node{ QNODE data; Struct }LNODE LNODE *front,*rear;// 队头指针和队尾指针 node *next;//队列中的元素信息

【算法描述】 { 设置统计初值; 设置当前时钟时间为 0; 打开数据文件,准备读;

读入第一位客户信息于暂存变量中; do{ if(等待队列为空,并且还有客户){ 累计业务员总等待时间; 时钟推进到暂存变量中的客户的到达时间; 暂存变量中的客户信息进队; 读取下一位客户信息于暂存变量; } 累计客户人数; 从等待队列出队一位客户; 将该客户的等待时间累计到客户的总等待时间; 设定当前客户的业务办理结束时间; while(下一位客户的到达时间在当前客户处理结束之前){ 暂存变量中的客户信息进队; 读取下一位客户信息于暂存变量; } 时钟推进到当前客户办理结束时间; }while(还有未处理的客户); 计算统计结果,并输出; //约定每轮循环,处理完一位客户 //等待队列为空时

【C 源程序】 #include<stdio.h> #include<stdlib.h> #define OVERFLOW -2 typedef struct{ int int }QNODE; typedef struct node{ QNODE data; arrive; treat; /*客户的信息结构*/

struct }LNODE;

node

*next;

/*队列中的元素信息*/

LNODE *front,*rear;/* QNODE curr,temp; char FILE void Fname[120]; *fp;

队头指针和队尾指针*/

EnQueue(LNODE **hpt,LNODE

**tpt,QNODE

e){

/*队列进队*/ LNODE *p=(LNODE if(!p) *)malloc(sizeof(LNODE)); /*存储分配失败*/

exit(OVERFLOW);

p->data=e; p->next=NULL; if(*hpt==NULL) *tpt=*hpt=p;

else *tpt=(*tpt)->next=p; } int DeQueue(LNODE /*链接队列出队*/ LNODE *p=*hpt; if(*hpt==NULL) return 1;/*队空*/ **hpt,LNODE **tpt,QNODE *cp){

*cp=(*hpt)->data; *hpt=(*hpt)->next; if(*hpt==NULL) free(p); return } void { main() int dwait=0,clock=0,wait=0,count=0,have=0,finish; printf("n enter file name:"); 0; *tpt=NULL;

scanf("%s",Fname);/*输入装客户模拟数据的文件的文件名*/ if((fp=fopen(Fname, "r"))==NULL){ /*打开数据文件*/

printf("cannot return; } front=NULL;rear=NULL; have=fscanf(fp, do{

open

123456789101112131415161718192021222324252627282930

 


 

  【Top

最新搜索

 


 

热点推荐