北航第四次数据结构与程序设计编程题复习
到期末了，所以再来复习一下以前的作业。
北航第四次数据结构与程序设计编程题
- 一、栈操作（栈-基本题）
- 二、C程序括号匹配检查
- 三、计算器（表达式计算-后缀表达式实现，结果为浮点）
- 四、文本编辑操作模拟（简）a
- 五、银行排队模拟（生产者-消费者模拟） - 分类别
一、栈操作（栈-基本题）
【问题描述】
假设给定的整数栈初始状态为空，栈的最大容量为100。从标准输入中输入一组栈操作，按操作顺序输出出栈元素序列。栈操作：1表示入栈操作，后跟一个整数（不为1、0和-1）为入栈元素；0表示出栈操作；-1表示操作结束。
【输入形式】
从标准输入读取一组栈操作，入栈的整数和表示栈操作的整数之间都以一个空格分隔。
【输出形式】
在一行上按照操作的顺序输出出栈元素序列，以一个空格分隔各元素，最后一个元素后也要有一个空格。如果栈状态为空时进行出栈操作，或栈满时进行入栈操作，则输出字符串“error”，并且字符串后也要有一空格。所有操作都执行完后，栈也有可能不为空。
【样例输入】
1 3 1 5 1 7 0 0 1 8 0 1 12 1 13 0 0 0 0 1 90 1 89 0 -1
【样例输出】
7 5 8 13 12 3 error 89
【样例说明】
入栈元素依次为3、5、7，然后有两次出栈动作，所以先输出7和5，这时栈中只有元素3；之后元素8入栈，又出栈，输出8；随后元素12和13入栈，再进行4次出栈操作，输出13、12和3，这时栈为空，再进行出栈操作会输出error；最后90和89入栈，进行一次出栈操作，输出89，栈中剩余1个元素。
【评分标准】
该题要求按照操作的顺序输出出栈元素序列，提交程序名为stack.c。
- 本题的思路就是：输入1，后面接一个入栈元素；输入0，则进行弹栈操作；栈满输入和栈空弹栈，都输出error。
- 因此可以用一个flag变量来记录第一个输入的数字，以此判断入栈还是弹栈，然后再判断接下来要不要继续输入元素。
- 如果flag显示为结束标志符即-1，则结束输入。
#include #include #include #define MAX 100 int arr[100],Top=-1; enum ope {PUSH=1,POP=0,END=-1}; int isFull() { return Top==MAX; } int isEmpty() { return Top==-1; } void Push(int x) { if(isFull()) { printf("error "); return; } arr[++Top]=x; } int Pop() { if(isEmpty()) { printf("error "); return 0; } return arr[Top--]; } int main() { enum ope flag; scanf("%d",&flag); int item; while(flag!=END) { if(flag==PUSH) { scanf("%d",&item); Push(item); } else if(flag==POP) { int pop=Pop(); if(pop!=0) printf("%d ",pop); } scanf("%d",&flag); } }这里有两个小tip：
- enum ope {PUSH=1,POP=0,END=-1};建议大家多用枚举类型，这道题里面因为只有1,0，-1三个标志符，而且代码量不大，所以你觉得没什么问题，那万一有10个20个标志符呢？单纯的1,2,3,4…会让代码的可读性大大下降，用这种方式，在调试的时候会非常容易知道操作类型。
- scanf("%d",&flag);代码循环里的这一个也需要注意一下，不要在%d后面加一个空格，因为读到最后一个数，也就是-1的时候，-1的后面不一定有空格，那么我们的程序在读到-1的时候，如果读不到后面的空格，程序就进行不完，因此不需要在scanf里带空格。因为我们现在读的是整型，scanf识别的空格会自动跳过的。
二、C程序括号匹配检查
【问题描述】
编写一程序检查C源程序文件中{}、()等括号是否匹配,并输出第一个检测到的不匹配的括号及所对应括号所在的行号（程序中同一类括号只有一个不匹配）。
注意：
1.除了括号可能不匹配外，输入的C源程序无其它语法错误。
2.字符常量、字符串常量及注释中括号不应被处理，注释包括单行注释//和多行/* */注释
3.字符常量和字符串常量中不包含转义字符’和"；
4.程序中出现有意义括号的个数不超过200个；
不匹配判断规则：
1.当检测的程序括号为’{‘时，若其前序尚未匹配的括号为’(‘时，输出该’('左括号及所在行号；
2.当遇到一个不匹配的右括号’)‘或’}'时，输出该右括号及所在行号；
3.当程序处理完毕时，还存在不匹配的左括号时，输出该左括号及所在行号。
【输入形式】
打开当前目录下文件example.c，查询其括号是否匹配。该文件中每行字符数不超过200。
【输出形式】
若存在括号不匹配时，应输出首先能判断出现不匹配的括号及其所在的行号。当出现括号不匹配时，按下面要求输出相关信息：
without maching at line
其中为‘{’, ‘}’， ‘(’, ‘)’等符号，为该符号所在的行号。
若整个程序括号匹配，则按下面所示顺序输出括号匹配情况，中间没有空格。
(){(()){}}
【样例输入1】
若当前目录下输入文件example.c中内容如下：
#include
int main(){
printf(“{ hello world }\n”); // }
)
【样例输出1】
without maching ‘)’ at line 4
【样例输入2】
若当前目录下输入文件example.c中内容如下：
#include
int main(){
printf(“{ hello world }d\n”); /* }*/
【样例输出2】
without maching ‘{’ at line 2
【样例输入3】
若当前目录下输入文件example.c中内容如下：
#include
int main(){
printf(“{ hello world }d\n”); /* }*/
}
【样例输出3】
(){()}
【样例说明】
样例1：在注释部分和字符串中的括号不考虑，在将程序处理之后得到的括号序列是（）{（）），遇到右括号时与最近的左括号匹配，发现最后一个小括号和大括号不匹配。
样例2：处理之后的括号序列是（）{（），在最后缺少了右大括号，那么应该输出与之相对应的左括号不匹配。
【评分标准】
通过所有测试点得满分。
做这个题之前可以看看link我的这篇问斩里的一个题：括号匹配问题，是这个问题的简化版，因为输出的字符串只包含（）{ } [ ]，但这道题就相对比较复杂了。
先来说几个注意点：
-
如果括号简化一后为 { ），那其实这两个括号都不匹配，但是，输出还得是），因为遍历到 { 的时候，我们并不知道程序后面还有没有跟他匹配的 } ,但是一个右括号，前面没有一个匹配左括号，那显然直接就可以判断不匹配。不匹配规则2说的意思也是这个。
-
多行注释需要注意：
/* ……
* ……
* ……
* /
*的前后都不一定是/。
-
四种情况下，不需要让括号入栈：
单行注释//
多行注释/**/
单引号
双引号，如果碰到了这些情况，则直接让循环一直++到注释或引号结束。
-
遇到 { ，如果栈空直接入栈，否则判断栈顶是否是（，是的话，输出（还有他的行数，不是的话，{ 入栈。
#include #include #include typedef struct { char item; int line; }bracket; char all_brackets[100]; bracket judge_match[100]; int Top=-1; int Topall=-1; int main() { FILE* fp=fopen("example.c","r"); int ch; int line=1; while((ch=fgetc(fp))!=EOF) { //{ if(ch=='{') { if(Top>-1&&judge_match[Top].item=='(') { printf("without matching '(' at line %d",judge_match[Top].line); return 0; } else { Top++; judge_match[Top].item='{'; judge_match[Top].line=line; all_brackets[++Topall]='{'; } } //} else if(ch=='}') { if(Top==-1)//空栈 { printf("without matching '}' at line %d",line); return 0; } else if(judge_match[Top].item!='{') { printf("without matching '}' at line %d",line); return 0; } else { all_brackets[++Topall]='}'; Top--; } } //( else if(ch=='(') { Top++; judge_match[Top].item='('; judge_match[Top].line=line; all_brackets[++Topall]='('; } //) else if(ch==')') { if(Top==-1)//空栈 { printf("without matching ')' at line %d",line); return 0; } else if(judge_match[Top].item!='(') { printf("without matching ')' at line %d",line); return 0; } else { all_brackets[++Topall]=')'; Top--; } } //\n else if(ch=='\n') { line++; } //单引号情况 else if(ch=='\'') { while((ch=fgetc(fp))!='\'') continue; fseek(fp,-1,SEEK_CUR); } //双引号 else if(ch=='\"') { while((ch=fgetc(fp))!='\"') continue; } //单行注释与多行注释 else if (ch=='/') { int back=fgetc(fp); if(back=='/')//单行注释 { back=fgetc(fp); while(!(back=='\n'||back==EOF)) { back=fgetc(fp); } line++; } else if(back=='*')//多行注释，内部如果检测到\n需要对行数加一 { back=fgetc(fp); int back1=fgetc(fp); while(1) { if(back=='\n') { line++; back=back1; back1=fgetc(fp); } else { if(back=='*'&&back1=='/') break; else { back=back1; back1=fgetc(fp); } } } } } //字符或数字不用考虑，直接进行下一次循环 } if(Top!=-1) { printf("without matching '%c' at line %d",judge_match[0].item,judge_match[0].line); return 0; } for(int i=0;i printf("%c",all_brackets[i]); } return 0; } OP,NUM}; typedef struct item { enum set type; union { char ope; float num; }uni; }ITEM; OP,NUM}; typedef struct item { enum set type; union { char ope; float num; }uni; }ITEM; void remove_zero(char*);去掉原始表达式中出现的空格 void toReversePoland(char*);这个函数用于把中缀表达式转换成后缀 void CalExpess(ITEM*,int);这个用于计算后缀表达式的值 int Priority(char);判断优先级 int main() { char ch='a'; char arr[100]; gets(arr); remove_zero(arr); toReversePoland(arr); return 0; } void remove_zero(char* a) { int i=0,j=0; while(a[j]!='\0') { if(a[j]!=' ') { a[i]=a[j]; j++; i++; } else j++; } a[i]='\0'; } void toReversePoland(char* a) { ITEM arr[100]; int index=0; char operation[100]; int Top=-1; for(int i=0;i if(a[i]='0'&&a[i] float num=a[i]-'0'; for(int j=i+1;j if(a[j]='0'&&a[j] num=num*10+(a[j]-'0'); } else { arr[index].type=NUM; arr[index].uni.num=num; i=j-1; index++; break; } } } else if(a[i]=='=') break; else if(a[i]=='+'||a[i]=='-'||a[i]=='*'||a[i]=='/') { if(Top==-1) operation[++Top]=a[i]; else { while(Top-1&&operation[Top]!='('&&(Priority(operation[Top])=Priority(a[i]))) { arr[index].type=OP; arr[index].uni.ope=operation[Top]; index++; Top--; } operation[++Top]=a[i]; } } else if(a[i]=='(') { operation[++Top]='('; } else if(a[i]==')') { char top=operation[Top]; while(top!='(') { arr[index].type=OP; arr[index].uni.ope=top; index++; Top--; top=operation[Top]; } Top--; } } while(Top!=-1) { arr[index].type=OP; arr[index].uni.ope=operation[Top]; index++; Top--; } // for(int i=0;i // if(arr[i].type==OP) // printf("%c ",arr[i].uni.ope); // else // printf("%.2f ",arr[i].uni.num); // } CalExpess(arr,index); } int Priority(char a) { if(a=='+'||a=='-') return 1; if(a=='*'||a=='/') return 2; } void CalExpess(ITEM* a,int n) { float num[100]; int Top=-1; for(int i=0;i if(a[i].type==NUM) { num[++Top]=a[i].uni.num; } else { if(a[i].uni.ope=='+') { float x=num[Top]; Top--; float y=num[Top]; num[Top]=x+y; } else if(a[i].uni.ope=='-') { float x=num[Top]; Top--; float y=num[Top]; num[Top]=y-x; } else if(a[i].uni.ope=='*') { float x=num[Top]; Top--; float y=num[Top]; num[Top]=x*y; } else if(a[i].uni.ope=='/') { float x=num[Top]; Top--; float y=num[Top]; num[Top]=y/x; } } } printf("%.2f",num[0]); } // if(arr[i].type==OP) // printf("%c ",arr[i].uni.ope); // else // printf("%.2f ",arr[i].uni.num); // } int type; int pos; char arr[100]; }OPE; int type; int pos; char arr[100]; }OPE; OPE stack[100]; char arr[600]; int top=0; int flag=0; void Insert(int,char*); void Delete(int,int); void Undo(); int main() { gets(arr); int prev; scanf("%d",&prev); for(;top scanf("%d %d %s",&stack[top].type,&stack[top].pos,stack[top].arr); } int type; int pos; char inarr[100]; int delnum; scanf("%d",&type); while(type!=-1) { if(type==1) { scanf("%d %s",&pos,inarr); Insert(pos,inarr); } else if(type==2) { scanf("%d %d",&pos,&delnum); Delete(pos,delnum); } else if(type==3) { flag=1; Undo(); top--; flag=0; } scanf("%d",&type); } printf(arr); } void Insert(int pos,char* str) { if(flag==0) { stack[top].type=1; stack[top].pos=pos; strcpy(stack[top].arr,str); top++; } int len_all=strlen(arr); memmove(arr+pos+strlen(str),arr+pos,len_all-pos+1); strncpy(arr+pos,str,strlen(str)); } void Delete(int pos,int delnum) { if(flag==0) { int len_longest=strlen(arr)-pos; if(delnumlen_longest) delnum=len_longest; char delarr[100]; strncpy(delarr,arr+pos,delnum); delarr[delnum]='\0'; stack[top].type=2; stack[top].pos=pos; strcpy(stack[top].arr,delarr); top++; } memmove(arr+pos,arr+pos+delnum,strlen(arr)+1-pos-delnum); } void Undo() { if(top==0) return; if(stack[top-1].type==1) { int delnum=strlen(stack[top-1].arr); Delete(stack[top-1].pos,delnum); } else { Insert(stack[top-1].pos,stack[top-1].arr); } } int id;//客户排队号 int wtime;//客户等待周期数 int contact;//业务类型 }CustType; CustType Cqueue[100];//等待服务的客户队列，一个循环队列 int Winnum=MINSVR;//银行当前提供服务的窗口数。3 int id;//客户排队号 int wtime;//客户等待周期数 int contact;//业务类型 }CustType; CustType Cqueue[100];//等待服务的客户队列，一个循环队列 int Cfront=0;//队头 int Crear=MAXSIZE-1;//队尾 int Cnum=0;//队中元素个数 int isEmpty(){return Cnum==0;}; int isFull(){return Cnum==MAXSIZE;}; int Winnum=MINSVR;//银行当前提供服务的窗口数。30};//记录每个窗口剩余服务时间，可取值0,1,2,3。 void updateCustqueue();//更新等待队列中客户等待时间 void enCustqueue(CustType c);//客户入等待队列 CustType deCustqueue();//客户出队，同时输出其等待时间 void arriveCust(int);//获取新客户，并加入等待队列 int service();//从队列中获取客户进行服务 int main() { int clock,simulationtime; scanf("%d",&simulationtime); int* each_period_num=(int*)malloc(sizeof(int)*simulationtime); for(int i=0;i scanf("%d",&each_period_num[i]); } for(int clock=1;;clock++) { updateCustqueue(); if(clock int i,type; static int count=1; CustType c; for(int i=0;i c.id=count; count++; c.wtime=0; scanf("%d",&c.contact); enCustqueue(c); } while((Cnum/Winnum)=THRESHOLD&&Winnum if(isFull()) { printf("full"); exit(1); } Crear=(Crear+1)%MAXSIZE; Cqueue[Crear]=c; Cnum++; } CustType deCustqueue() { CustType c; if(isEmpty()) { printf("empty"); exit(1); } c=Cqueue[Cfront]; Cfront=(Cfront+1)%MAXSIZE; Cnum--; return c; } void updateCustqueue() { int i; for(i=0;i if(WINDOW[j]0) WINDOW[j]--; } } int service() { int i; CustType c; for(int i=0;i if(isEmpty()) return 0; else { int j=0; for(;j if(WINDOW[j]==0) break; } if(jc=deCustqueue(); WINDOW[j]=c.contact; printf("%d : %d\n",c.id,c.wtime);} } } while((Cnum/Winnum)
-
免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们，邮箱：ciyunidc@ciyunshuju.com。本站只作为美观性配图使用,无任何非法侵犯第三方意图,一切解释权归图片著作权方,本站不承担任何责任。如有恶意碰瓷者,必当奉陪到底严惩不贷!
