信息学辅导--数据结构之五--队列1

五、队列 （一）、队列的概念及运算1.队列的定义： 队列是一种限定在一端进行插入，另一端进行删除的特殊线性表。正象排列买东西，排在前面的人买完东西后离开队伍（删除），而后来的人总是排在队伍未尾（插入）。通常把队列的删除和插入分别称为出队和入队。允许出队的一端称为队头，允许入队的一端称为队尾。所有需要进队的数据项，只能从队尾进入，队列中的数据项只能从队头离去。由于总是先入队的元素先出队（先排队的人先买完东西），所以队列又称为先进先出(FirstInFirstOut)表，简称FIFO表。 2.队列的数学性质： 假设队列为a1,a2,..,an，那么a1就是队头元素，an为队尾元素。队列中的元素是按a1,a2,..,an的顺序进入的，退出队列也只能按照这个次序依次退出。也就是说，只有在a1离开队列之后，a2才能退出队列，只有在a1,a2,..,an-1都离开队列之后，an才能退出队列。图1是队列的示意图。 般情况下，两个指针的初值设为0，这时队列为空，没有元素。在此我们约定：初始化队列时，空队列时令front:=0;rear:=0,另外还约定，在非空队列中，头指针front总是指向队列中实际队头元素的前面一个位置，而尾指针rear总是指向队尾元素。 图2(a)画出了一个由６个元素构成的队列，数组定义Q[1..10]。Q(i)i=3,4,5,6,7,8，头指针head＝2，尾指针rear＝8。队列中拥有的元素个数为:L=rear-head。现要让排头的元素出队，则需将头指针加１。即head=head+1这时头指针向上移动一个位置，指向Q(3)，表示Q(3)已出队。见图2(b)。如果想让一个新元素入队，则需尾指针向上移动一个位置。即rear=rear+1这时Q(9)入队，见图2(c)。当队尾已经处理在最上面时，即rear=10，见图2(d)，如果还要执行入队操作，则要发生"上溢"，但实际上队列中还有三个空位置，所以这种溢出称为"假溢出"。 图1 3.队列的运算： 为一种抽象数据类型，常用的队列运算有: 运算含 义 Getfirst_Queue(Q)这是一个函数，函数值返回队列Q的队头元素。Enter_Queue(Q,x)Del_Queue(Q)IsNull_Queue(Q)Init_Queue(Q) 将元素x插入队列Q的队尾。此运算也常简称为将元素x入 队。 将Q的队头元素删除，简称为出队。 这是一个函数，若Q是一个空队列，则函数值为1，否则为0。使队列Q成为空队列。 (三)、队列基本算法的实现 1、顺序队列的定义 ConstMAXSIZE＝100var Queue:array[1..MAXSIZE]ofdatatype;//存放队列中数据元素的存储单元front,rear:integer;//队头、队尾指针(没有使用结构体类型，很多人不大习惯用结构体类型)1 （二）、队列的存储方式 队列的顺序存储结构可以简称为顺序队列，也就是利用一组地址连续的存储单元依次存放队列中的数据元素。在队列的运算中需设两个指针：head：队头指针，指向实际队头元素的前一个位置，rear：队尾指针，指向实际队尾元素所在的位置。一 2、初始化队列，使队列Queue成为空队列front=0;rear=0; 3、判队空 if（front=rear）then{队列为空}else4、判队满 if(rear=MAXSIZE) {队列非空}; then{队列满}else{队列未满}; 循环队列在入队或出队时，可以利用取模运算实现队头及队尾位置的移动： Front:=(front+1)modMAXSIZE;Rear:=(rear+1)modMAXSIZE; 当front或rear为MAXSIZE-1时，上述两个计算的结果就为0,使得队首和队尾的位置自动由后面转到前面，形成循环的效果。 循环队列中，约定在非空循环队列中，头指针front总是指向队列中实际队头元素的前面一个位置，而尾指针rear总是指向队尾元素。 队空：rear=front 队满：(rear+1)modMAXSIZE=front 5、入队操作：将元素x插入队列Queue的队尾。此运算也常简称为将元素x入队。rear:=rear+1;queue[rear]:=x; 6、出队操作：将Queue的队头元素删除，简称为出队。front:=front+1; 7、返回队列Queue的队头元素变量:=queue[front+1]; (四)、循环队列1、循环队列的概念 在顺序队列中，当队尾指针已经指向了队列的最后一个位置时，此时若有元素入列，就会发生“溢出”。一种情况是队列中所有存储单元都占用了，发生溢出时称“真溢出”；另一种情形，在图2（d）中，虽然队尾指针已经指向最后一个位置，但事实上队列中还有3个空位置。也就是说，队列的存储空间并没有满，但队列却发生了溢出，我们称这种现象为“假溢出”。 为了克服“假溢出”现象，这里引入循环的概念，将数组存储区看成是一个首尾相接的环形区域。当存放到n-1地址后，下一个地址就“翻转”为0。这就好比把存储空间弯起来，形成一个头尾相接的环形，这时的队列称为循环队列。 图4（MAXSIZE=8） 图4－a空队列（初态）：此时front:=0;rear:=0。 图4－b元素A入队：rea:r=(rear+1)modMAXSIZE，此时front=0，rear=1。图4－c元素B、C入队：执行rear:=(rear+1)modMAXSIZE两次，此时front=0，rear=3。 图4－d元素A出队：front::=(front+1)modMAXSIZE，此时front=1，rear=3。图4－e元素D、E、F、G、H入队：执行rear:=(rear+1)modMAXSIZE五次，此时front=1，rear=0，队满（(rear+1)modMAXSIZE=front）。 2 2、循环队列的算法 （1）循环队列的定义： 循环队列实质上仍然还是顺序存储结构，只是形式上有所改变而已。constMAXSIZE＝100;var queue:array[0..MAXSIZE-1]ofdatatype;//存放队列中数据元素的存储单else front:=(front+1)modend; MAXSIZE; (6)取队列中的队首元素 functionGetfirst_Queue:datatype元 front,rear:integer;//队头、队尾指针（2）将循环队列置为空Procedurebegin Init_Queue;//将循环队列初始化front:=0;end; rear:=0;(3)function判断循环队列是否为空 begin intIsNull_Queue:Boolean;if(rear=front)intend; elseintIsNull_Queue:=false;IsNull_Queue:=true(4)procedure在循环队列中插入新的元素xbegin Enter_Queue(x:datatype);ifelse((rear+1)modMAXSIZE=front)thenwrite(‘队列满！’) begin rear:=(rear+1)Queue[rear]:=x;modMAXSIZE;end; end;(5)procedure删除队列中队首元素Begin Del_Queue;if(front==rear)write(‘队列空！then ’) Begin ifelse write(‘(front=队列空！rear)then’)} Getfirst_Queue:=(Queue[(front+1)modMAXSIZE]);(五)、队列的应用 1、舞伴问问题叙述 假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开 始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。问题分析 先入队的男士或女士亦先出队配成舞伴。因此该问题具体有典型的先进先出特性，可用队列作为算法的数据结构。 在算法中，假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。当这两个队列构造完成之后，依次将两队当前的队头元素出队来配成舞伴，直至某队列变空为止。此时，若某队仍有等待配对者，算法输出此队列中等待者的人数及排在队头的等待者的名字，他（或她）将是下一轮舞曲开始时第一个可获得舞伴的人。具体参考程序代码 programvar dancers;dancer_name:array[1..100]dancer_sex:array[1..100]F_dancer:arrayofofchar;string;//性别，//姓名 'F'表示女性，'M'表示男性F_front,F_rear:integer;[1..100]ofinteger;M_dancer:array[1..100]M_front,M_rear:integer;of//integer;女士队列//男士队列begin num,i,count:integer; F_front:=0;F_rear:=0;M_front:=0;M_rear:=0; write('请输入参加跳舞的人数：');readln(num);writeln('依次输入跳舞者的性别、姓名：');fori:=1tonumdobeginwrite(i,':');readln(dancer_sex[i],dancer_name[i]);end;队头//输入性别，姓名end.elsebeginif(M_front<>M_rear)thenbegin//输出男队剩余人数及队头者名字count:=M_rear-M_front;writeln('还有',count,'位男士等待下一舞曲。');writeln(dancer_name[M_dancer[M_front+1]],'将第一个获得舞伴。');//取男队end;end;fori:=1tonumdo//依次将跳舞者依其性别入队,只记录跳舞者数组的下标beginif(dancer_sex[i]='F')thenbegininc(F_rear);F_dancer[F_rear]:=i;//排入女队endelsebegininc(M_rear);M_dancer[M_rear]:=i;//排入男队end;end; writeln('跳舞舞伴：');while(F_front<>F_rear)and(M_front<>M_rear)dobegin//依次输出男女舞伴名inc(F_front);//女士出队write(dancer_name[F_dancer[F_front]],'');//打印出队女士名inc(M_front);//男士出队writeln(dancer_name[M_dancer[M_front]]);//打印出队男士名end; if(F_front<>F_rear)thenbegin//输出女士剩余人数及队头女士的名字count:=F_rear-F_front;writeln('还有',count,'位女士等待下一舞曲。');writeln(dancer_name[F_dancer[F_front+1]],'将第一个获得舞伴'); end 2、加油站加油【问题描述】设车辆在随机的时刻来到加油站加油不暇接，平均每小时20辆。站上有两台加油泵，若两台泵都被占用，就让后面的来车排队等候，试在60分钟内模拟加油站的工作及汽车排队的情况。(设给每辆车加油的平均时间为5分钟)。【算法分析】从某种意义上说，程序是对客观世界的模拟，我们注意到，有的程序模拟的是确定性的客观世界，一般地说这种模拟能得出一个确定的结果。另一些模拟却是不确定性模拟，在通常情况下我们很难确定某些量的值，至多只能根据统计资料估计其可能的值。日常生活中的排队人数就属于这一类。这类模拟称为概率模拟。首先，我们要注意到的是解此类问题的前提是数据，汽车会在什么时间到达完全是随机的。但平均数20/小时给了我们某种确定的东西，即平均每三分钟就有一辆汽车到达，换句话说，每分钟内有汽车到达的可能性为1/3。这个数据为我们建立模拟提供了确切的依据。取一分钟为模拟间隔（当然间隔还可以取得更小一些，间隔越小，模拟结果的可信度就越高）在这一分钟里，要完成的操作是（1）看是否有车来到（是否有车并不是由输入数据确定，而是由电脑随机模拟确定），若有车再看是否有空闲的油泵，如有立即给其加油，否则排队等待。（2）检查两泵的工作情况：若泵忙且加油时间未到，则加油时间减一，若减一后加油时间为零，则把该泵置为空闲。用Pascal语言实现模拟，须用到伪随机数函数random()random：随机产生一个[0,1)之间的小数(不能取到1)random（x）：随机产生一个0~x-1之间的整数Randomize;初始化随机种子，必须放在主程序前面由上面的分析可以大体写出算法如下：（采用循环队列）programoil;constMAXSIZE=100;varQueue:array[0..MAXSIZE-1]ofinteger;front,rear:integer;//车辆进加油站等待队列flag1,flag2:integer;//加油泵工作状态，0－空闲，其他－正在加油的车辆编号队头//取女队 time1,time2:integer;num:integer;total:integer;////车辆总数//加油泵剩余加油时间（每辆车加油5分钟）begin i,j:integer;车辆等待总时间Randomize;rear:=0;//初始化“随机种子”front:=0; time1:=0;flag1:=0;num:=0;flag2:=0;time2:=0;forbegin i:=1tototal:=0;60do//模拟时间60分钟，一分钟为模拟间隔时间j:=(rear-front)ifmodMAXSIZE;//计算有多少辆车等待加油total:=total+j;(j<0)thenj:=j+MAXSIZE;//累加等待加油总时间 ifif(time1<>0)thendec(time1);//加油泵1在工作，加油时间减一分钟begin (time1=0)then//加油泵1空闲begin if(front<>rear)then//有汽车等待加油（队列非空）flag1:=Queue[(front+1)time1:=5;//每辆车加油时间 modMAXSIZE];//加油泵endfront:=(front+1)modMAXSIZE;//队首汽车出队加油1工作的汽车编号else end; flag1:=0;//置加油泵1空闲ifif(time2<>0)thendec(time2);begin (time2=0)thenbegin if(front<>rear)thenflag2:=Queue[(front+1)time2:=5; front:=(front+1)modMAXSIZE;modMAXSIZE];else endend; flag2:=0;ifbegin (random<0.33333)then//有汽车到达ifinc(num);//汽车到达编号（到达汽车数量）begin (flag1=0)then//加油泵1空闲flag1:=num;//直接加油endtime1:=5;else ifbegin (flag2=0)thenflag2:=num;time2:=5;elseendbegin //无空闲加油泵，汽车进等待加油队列Queue[rear]:=num;rear:=(rear+1)modMAXSIZE;end; end; end; writeln('Totalwriteln('Totalcarnumberis:',num);end. writeln('Averagewaittimewaittimeis:',total); is:',(total/num):5:2); 3、凯撒加密(Caesarcipher)【问题描述】 凯撒加密(Caesarcipher)是一种简单的消息编码方式：它根据字母表将消息中的每个字母移动常量位k。举个例子 如果k等于3，则在编码后的消息中，每个字母都会向前移动3位：a会被替换为d；b会被替换成f；依此类推。字母表末尾将回卷到字母表开头。于是，w会被替换为z，x会被替换为a。 在解码消息的时候，每个字母会反方向移动同样的位数。因此，如果k等于3，下面这条编码后的消息： vlpsolflwbiroorzvfrpsohalwb会被解码成： simplicityfollowscomplexity 朱丽叶斯.凯撒在他的一些机密政府通信中真正用到了这种加密。遗憾的是，凯撒加密相当容易被破解。字母的移动只有26种可能；要破解密码，只需尝试各种密钥值，直到有一种可行即可。 使用重复密钥(repeatingkey)可以对这种编码技术做出改进，这时不再将每个字母移动常位数，而是利用一列密钥值将各个字母移动不同的位数。如果消息长于这列密钥值，可以从头再次使用这列密钥。 例如，假设密钥值为： 317425 则第1个字母会移动3位，第2个字母会移动1位，依此类推，将第6个字母移动5位之后，我们会从头再次使用这列密钥。于是第7个字母会移动3位，第8个字母会移动1位。反之解码的过程类似。 注意：加密与解密都是针对字母（大小写均可）进行。 样例：明文：thisisatest! 密钥：2112 密文：vijuktbvgtu 【算法分析】 我们都知道队列的特点是FIFO(先进先出)，将密钥存储在队列中，使用了一个密钥后，将这个密钥添加到队尾，这样较长的信息可以重复使用该密钥。programCaesar;constMAXSIZE=50;varkey:array[0..MAXSIZE-1]ofinteger;front,rear:integer;//密钥队列i,k:integer;ch:char;En,De,str:string; proceduremenu;//菜单，1.加密，2.解密，3.退出，密钥只能是数字//beginwriteln('=================================');writeln('1.Encrypt');writeln('2.Decrypt');writeln('3.Exit');writeln('=================================');write('choose(1-3):');end; functionencrypt(ch:char;k:integer):char;//加密函数，把字符向右循环移位kbeginif((ch>='A')and(ch<='Z'))thenencrypt:=chr(65+((ord(ch)-65+k)mod26))//ord('A')=65elseencrypt:=chr(97+((ord(ch)-97+k)mod26))//ord('a')=97end; functionDecrypt(ch:char;k:integer):char;//解密函数，把字符向左循环移位kbeginif(ch>='A')and(ch<='Z')thenDecrypt:=chr(65+((ord(ch)-65-k+26)mod26))elseDecrypt:=chr(97+((ord(ch)-97-k+26)mod26))end;functionInit_key():integer;//将输入的密钥转换为整数加入队列中vari:integer;beginfori:=1tolength(str)dobeginif((str[i]>='0')and(str[i]<='9'))thenbeginrear:=(rear+1)modMAXSIZE;key[rear]:=ord(str[i])-ord('0');//数字字符转换为对应的整数endelsebeginInit_key:=0;//密钥中有非整数字符exit;end;end;Init_key:=1;end;beginfront:=0;rear:=0;menu;readln(ch);//循环队列初始化//显示菜单//读取选择按键while(ch<>'3')dobeginstr:='';De:='';En:='';if(ch='1')then//加密beginwrite('Inputtheexpressly:');readln(En); write('inputreadln(str);theKey://密钥采用字符串连续输入 '); if(Init_key()=0)elsewrite('KeyisError!')then//将密钥加入队列中 begin fori:=1tolength(En)do//扫描明文每个字符if((En[i]>='A')begin begin and(En[i]<='Z'))or((En[i]>='a')and(En[i]<='z'))then front:=(front+1)k:=key[(front+1)rear:=(rear+1)modmodMAXSIZE;MAXSIZE];//密钥队列队首保存至K中key[rear]:=k;modMAXSIZE;//密钥队列队首出队//将endDe:=De+encrypt(En[i],k);//加密字符逐字放入密文字符串中K入队else end; De:=De+En[i]; writeln('Theciphertextis:',De);//end;end;输出密文ifbegin (ch='2')then//解密readln(De); write('Inputtheciphertext:');write('Inputreadln(str); theKey:');if(Init_key()=0)thenelsewriteln('KeyisError!')forbegin i:=1if((De[i]>='A')begin tolength(De)do begin and(De[i]<='Z'))or((De[i]>='a')and(De[i]<='z'))then k:=key[(front+1)front:=(front+1)modrear:=(rear+1)modMAXSIZE;MAXSIZE];key[rear]:=k; modMAXSIZE;endEn:=En+Decrypt(De[i],k);else En:=En+De[i]; writeln('Theend; expresslyis:',En);end; end;if(ch='3')halt;then//结束程序 readln(ch);menu;//显示菜单，构成循环 end. end;4、求细胞数 一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。如:阵列 0234500067103456050020456006710000000089有4个细胞。算法步骤： （1）从文件中读入m*n矩阵阵列，将其转换为0-1矩阵存入bz数组中；（2）沿bz数组矩阵从上到下，从左到右，找到遇到的第一个细胞； （3）将细胞的位置入队Q，并沿其上、下、左、右四个方向上的细胞位置入队，入队后的位置bz数组置为0； （4）将Q队的队头出队，沿其上、下、左、右四个方向上的细胞位置入队，入队后的位置bz数组置为0； （5）重复4，直至Q队空为止，则此时找出了一个细胞；（6）重复2，直至矩阵找不到细胞；（7）输出找到的细胞数。 dx[i]、dy[i]数组为记录上、下、左、右四个方向的搜索位置。dx=-1,dy=0： 上，dx=0,dy=1：右，dx=1,dy=0：下，dx=0,dy=－1：左。 此题的算法其实就是深度搜索算法，是队列最主要的应用，以后学习搜索算法end;end;时还会遇到类似的题。 programconstdx:array[1..4]xibao; ofvarint:text; dy:array[1..4]of-1..1=(-1,0,1,0); -1..1=(0,1,0,-1);name,s:string; pic:array[1..50,1..79]bz:array[1..50,1..79]m,n,i,j,num:integer; ofofboolean;byte;procedureh:array[1..4000,1..2]ofbyte;varbegin i,t,w,x,y:integer;doing(p,q:integer);inc(num);bz[p,q]:=false; t:=1;w:=1;h[1,1]:=p;h[1,2]:=q;{repeat 遇到的第一个细胞入队}forbegin i:=1to4do{沿细胞的上下左右四个方向搜索细胞}x:=h[t,1]+dx[i];y:=h[t,2]+dy[i]; if(x>0)thenbeginand(x<=m)inc(w);h[w,1]:=x;h[w,2]:=y;bz[x,y]:=false;end;{and(y>0)and(y<=n)andbz[x,y] 为细胞的入队}inc(t);{end; 队头指针加begin end;untilt>w;{直至队空为止1}}fillchar(bz,sizeof(bz),true);num:=0; //初始化数组bz全部元素都为truewrite('inputassign(int,name);reset(int);file:');readln(name);readln(int,m,n);forbegini:=1tomdo forbeginj:=1readln(int,s);tondo ifpic[i,j]=0pic[i,j]:=ord(s[j])-ord('0');thenbz[i,j]:=false; close(int); forend. writeln('NUMBERfori:=1j:=1tomtodo ndoifofbz[i,j]cells=',num);readln;thendoing(i,j);{在矩阵中寻找细胞}（六）栈和队列 1、进制转换 我们可以用这样的方式来表示一个十进制数：将每个阿拉伯数字乘以一个以该数字所处位置的（值减１）为指数，以１０为底数的幂之和的形式。例如：１２３可 表示为１＊１０２＋２＊１０１＋３＊１００ 这样的形式。 与之相似的，对二进制数来说，也可表示成每个二进制数码乘以一个以该数字所处位置的（值－１）为指数，以２为底数的幂之和的形式。一般说来，任何一个正整数Ｒ或一个负整数－Ｒ都可以被选来作为一个数制系统的基数。如果是以Ｒ或－Ｒ为基数，则需要用到的数码为０，１，．．．．Ｒ－１。例如，当Ｒ＝７时，所需用到的数码是０，１，２，３，４，５和６，这与其是Ｒ或－Ｒ无关。如果作为基数的数绝对值超过１０，则为了表示这些数码，通常使用英文字母来表示那些大于９的数码。例如对１６进制数来说，用Ａ表示１０，用Ｂ表示１１，用Ｃ表示１２，用Ｄ表示１３，用Ｅ表示１４，用Ｆ表示１５。 在负进制数中是用－Ｒ作为基数，例如－１５（十进制）相当于１１０００１（－２进制），并且它可以被表示为２的幂级数的和数： １１０００１＝１＊（－２）５＋１＊（－２）４＋０＊（－２）３＋０＊（－２） ２ ＋０＊（－２）１＋１＊（－２） ０ 设计一个程序，读入一个十进制数和一个负进制数的基数,并将此十进制数转换为此负进制下的数：－Ｒ∈｛－２，－３，－４，．．．，－２０｝输入： 输入的每行有两个输入数据。第一个是十进制数Ｎ（－32768＜＝Ｎ＜＝32767）；第二个是负进制数的基数－Ｒ。输出： 结果显示在屏幕上，相对于输入，应输出此负进制数及其基数，若此基数超过１０，则参照１６进制的方式处理。输入 ３００００－２－２００００－２２８８００－１６ －２５０００－１６输出 ３００００＝１１０１１０１０１０１１１００００（ｂａｓｅ－２）－２００００＝１１１１０１１０００１０００００（ｂａｓｅ－２）２８０００＝１９１８０（ｂａｓｅ－１６）－２５０００＝７ＦＢ８（ｂａｓｅ－１６） 2、单词统计 读入一英文句子，单词之间用空格或逗号隔开，统计其中单词个数，并输出各个字母出现的频率。(句子末尾不一定用"."结束)如果含有其他的字符，则只要求输出错误信息及错误类型。 含有大写字母错误类型error1数字（0-9）错误类型error2其他非法字符错误类型error3 如输入：Itis12!输出：error123输入：iam,astudent输出：4 3、编码解码： 从键盘输入一个英文句子，设计一个编码、解码程序。(string)编码过程：先键入一个正整数N(1<=N<=26)。这个N决定了转换关系。例如当N=1，输入的句子为ABCXYZ时，则其转换码为ABCXYZ不变。当N=2时，其转换码为BCDYZA，其它的非字母字符不变。为使编码较于破译，将转换码的信息自左而右两两交换，若最后仅剩单个字符则不换。然后，将一开始表示转换关系的N根据ascii表序号化成大写字母放在最前面。 如：abcABCxyzXYZ-/,1.n=3 cdeCDEzabZAB-/,1.{根据N的值转换}dcCeEDazZbBA/-1,.{两两交换}CdcCeEDazZbBA/-1,.{最后编码}解码过程为编码的逆过程。4、计算器的改良【第三届全国青少年信息学奥林匹克分区联赛复赛试题普及组题一】〖问题描述〗 NCL是一家专门从事计算器改良与升级的实验室。最近该实验室收到了某公司所委托的一个任务：需要在该公司某型号的计算器上加上解一元一次方程的功能。实验室将这个任务交组了一个刚进入的新手ZL先生。为了很好的完成这个任务，ZL先生首先研究了一些一元一次方程的实例： 4+3X=86a-5+1=2-2-5+12Y=0 ZL先生被告知：在计算器上键入的一个一元一次方程中，只包含整数、小写字母入+、-、=这三个数学符号（当然，“-”既可当减号也可当负号）。方程中并没有括号，也没有除号，方程中的字母表示末知数。〖问题求解〗 编写程序，解输入的一元一次方程，将解方程的结果（精确到小数点后三位）输出至屏幕。 键入的一元一次方程均合法，且有唯一的实数解。〖样例〗 输入：6a-5+1=2-2a输出：a=0.750 5、求封闭区域面积 如下图：求图中被*围成的封闭区域的面积（方格的个数不包括*所在的方格，且*不在最外一层）。 *** * ***** * * * * * * * * * ** * * *** * ** * [输入数据]： 第一行：ＭＮ表示有Ｍ行Ｎ列 后面Ｍ行每行Ｎ个数字，０表示空，１表示该位置有*[输出数据]： 一行：面积大小[算法分析]：