2012最全华为上机试题及部分答案

2011年华为软件校园招聘编程测验1、请上机编写程序，按题目要求提交文件。详见考试说明，点击进入考试说明3、评卷通过在给定用例输入下，严格按照试题要求比较考生实现函数的输出与预设输出。两者相同则得分，不同则不得分。1, 4、评卷人保证测试用例输入参数的合法性，考生不用考虑输入参数非法或异常的情况5、评卷人保证测试用例输入在被测函数正常合法情况下使用不会导致程序错误6、如果考生函数异常导致程序崩溃或死循环，则自动评卷可能会被人为终止，剩余用例不被执行，无法得分7、基于上述阅卷规则，请考生严格按照题目要求功能实现程序，尽量保证实现函数的稳健性，同时建议完成一道题并调试保证正确性后，再考虑并实现下一题目判断电话号码是否合法：/要注意情况包含，有可能会同时出现几种不好的情况，要按照顺序输出错误。不能同时输出好几种错误，应该是这样包含：先判断长度是否符合，再判断是否以86打头，再判断有无其他字符intfun(charnum)(char*p=num;intn=strlen(num);if(n=13)(if(*p='8'&&*(p+1)='6')while(*p!='0')(if(*p>='0'&&*p<='9')p+;elsereturn2;if(*p='0')return0;elsereturn3;elsereturn1;intmain()(charnum="87139a3887671"intk=fun(num);cout<<k<<endl;return0;1.数组比较(20分)?问题描述：比较两个数组，要求从数组最后一个元素开始逐个元素向前比较，如果2个数组长度不等，则只比较较短长度数组个数元素。请编程实现上述比较，并返回比较中发现的不相等元素的个数比如：数组1,3,5和数组77,21,1,3,5按题述要求比较，不相等元素个数为0数组1,3,5和数组77,21,1,3,5,7按题述要求比较，不相等兀素个数为3?要求实现函数：intarray_compare(intlen1,intarray1,intlen2,intarray2)?示例1)输入：intarray1=1,3,5,intlen1=3intarray2=77,21,1,3,5,intlen2=5函数返回：02)输入：intarray1=1,3,5,intlen1=3intarray2=77,21,1,3,5,7,intlen2=6函数返回:3函数如下：usingnamespacestd;intf(intlen1,intarry1,intlen2,intarry2)intk=0;for(inti=len1-1,j=len2-1;i>=0&&j>=0;i-,j-)if(arry1i!=arry2j)k+;returnk;intmain()intnum1=1,3,5;intnum2=77,21,1,3,5;intk=f(3,num1,5,num2);cout<<k<<endl;return0;约瑟夫问题?问题描述：输入一个由随机数组成的数列（数列中每个数均是大于0的整数，长度已知），和初始计数值作从数列首位置开始计数，计数到m佰，将数列该位置数值替换计数值m,并将数列该位置数值出列，然后从下一位置从新开始计数，直到数列所有数值出列为止。如果计数到达数列尾段，则返回数列首位置继续计数。请编程实现上述计数过程，同时输出数值出列的顺比如：输入的随机数列为：3,1,2,4，初始计数值m=7,从数列首位置开始计数（数值3所在位置）第一轮计数出列数字为2,计数值更新m=Z出列后数列为3,1,4,从数值4所在位置从新开始计数第二轮计数出列数字为3,计数值更新m=3,出列后数列为1,4，从数值1所在位置开始计数第三轮计数出列数字为1,计数值更新m=1，出列后数列为4,从数值4所在位置开始计数最后一轮计数出列数字为4,计数过程完成。输出数值出列顺序为：2,3,1,4。?要求实现函数：voidarray_iterate（intlen,intinput_array,intm,intoutput_array)【输入】intlen:输入数列的长度；intintput_array:输入的初始数列intm：初始计数值【输出】intoutput_array:输出的数值出列顺序?示例输入：intinput_array=3,1,2,4,intlen=4,m=7输出：output_array=2,3,1,4函数如下：voidfun(intlen,inta1,intlen2,inta2)intn=0,i=-1,k=1,m=len2;while(1)for(intj=0;j<m;)i=(i+1)%len;/注意这个是不要写成/if(a1i!=0)j+;m=a1i;a2n+=a1i;a1i=0;if(k=len)break;k+;简单四则运算?问题描述：输入一个只包含个位数字的简单四则运算表达式字符串，计算该表达式的值注：1、表达式只含+,-,*,/四则运算符，不含括号2、表达式数值只包含个位整数(0-9)，且不会出现0作为除数的情况3、要考虑加减乘除按通常四则运算规定的计算优先级4、除法用整数除法，即仅保留除法运算结果的整数部分。比如8/3=2。输入表达式保证无0作为除数情况发生5、输入字符串一定是符合题意合法的表达式，其中只包括数字字符和四则运算符字符，除此之外不含其它任何字符，不会出现计算溢出情况?要求实现函数：intcalculate(intlen,char*expStr)【输入】intlen:字符串长度；char*expStr:表达式字符串；【输出】无【返回】计算结果?示例输入：char*expStr="1+4*5-8/3”函数返回：19输入：char*expStr="8/3*3"函数返回：6简化版的四则运算：没有括号，只有加减乘除四种运算intfun(chara,intlen)/字符数组和字符数组的长度(intnum20;charstr20;intk1=0,k2=0;intdata=0;for(inti=0;i<len;i+)/主要运算(if(ai>='0'&&ai<='9')numk1+=ai-'0'if(ai='-'|ai='+')strk2+=ai;if(ai='*')numk1-1=numk1-1*(ai+1-'0');i+;/遇见*，就运算，结果保存在数组中if(ai='/')numk1-1=numk1-1/(ai+1-'0');i+;inttemp=num0;intj=0;/两个数组只剩下数组和加减运算符while(j<k2)/顺序运算if(strj='-')temp=temp-numj+1;elseif(strj='+')temp=temp+numj+1;j+;returntemp;intmain()hara="3*3+7+4/3"intk=fun(a,9);cout<<k<<endl;return0;函数实现2:中序表达式转换为后序表达式，使用算法实现intisp(charc)intp;switch(c)case'*':case'/':p=1;break;case'+':case'-':p=0;break;returnp;char*transf(intlen,chara,charb)(intk=0;stack<char>s1;for(inti=0;i<len;i+)(if(ai>='0'&&ai<='9')bk+=ai;else(if(s1.empty()s1.push(ai);elsewhile(isp(ai)<=isp(s1.top()bk+=s1.top();s1.pop();s1.push(ai);while(s1.empty()bk+=s1.top();s1.pop();bk='0'returnb;voidfun(charc,stacks2)charp1,p2;if(!s2.empty()p1=s2.top();s2.pop();elsepos=false;cout<<"kongzhan"<<endl;if(!s2.empty()p2=s2.top();s2.top();elsepos=false;cout<<"kongzhan"<<endl;if(pos=true)switch(c)case'+':s2.push(p1+p2);break;case'-':s2.push(p2-p1);break;case'*':s2.push(p1*p2);break;case'/':s2.push(p2/p1);break;voideval(chara)stack<char>s2;for(inti=len;i<len;i+)switch(ai)case'+':case'-':case'/':fun(ai,&s2);break;default:s2.push(ai-'0');break;intmain()chara="1+4*5-8/3”;intlen=strlen(a);charb20;char*q=transf(9,a,b);cout<<q<<endl;return0;第五题：一副牌中发五张扑克牌给你：让你判断数字的组成：有以下几种情况：1:四条：即四张一样数值的牌(牌均不论花色)2:三条带一对3:三条带两张不相同数值的牌4:两对5:顺子包括10,J,QKA6:什么都不是7:只有一对思路：将数组排序，统计相同的数字的个数，再分情况讨论voidsort(inta)inttemp;for(inti=0;i<5;i+)for(intj=0;j<5;j+)if(ai>aj)temp=ai;ai=aj;aj=temp;voidtest(inta)int*b=newint5;intk=1;for(inti=0;i<5;i+)bi=ai;for(intj=0;j<4;j+)if(aj=aj+1)k+;if(k=4)if(b1=b3)cout<<"四条"<<endl;elsecout<<"三条带一对"<<endl;if(k=3)if(b1!=b2|b2!=b3)cout<<”三条带两个不同的牌"<<endl;elsecout<<"两对"<<endl;if(k=2)cout<<"一对"<<endl;if(k=1)(if(b4-b0=4&&b4-b1=3&&b4-b2=2&&b4-b3=1)cout<<”顺子<<endl;elsecout<<"什么都不是"<<endl;intmain()(inta=1,2,4,4,4;test(a);return0;第二题：求两个数组的和差就是去掉两个数组中相同的元素然后将两个数组中的元素存放在一个新的数组中，按大小顺序排序思路：将数组A和数组B分别进行排序，然后将A与B进行比较，重复的跳过去，不重复的赋给数组C,依次输出。while(i<la&&j<lb)if(aai<bbj)csub=aai;+sub;+i;elseif(aai>bbj)csub=bbj;+sub;+j;elseif(aai=bbj)+i;+j;for(;i<la;+i)csub=aai;+sub;for(;j<lb;+j)csub=bbj;+sub;四：逆序单链表node*reverse(node*head)(node*p1,*p2,*p3;p1=head;p2=head->next;while(p2)(p3=p2->next;p2->next=p1;p1=p2;p2=p3;head->next=NULL;head=p1;returnhead;将一个字符串的元音字母复制到另一个字符串，并排序(30分)问题描述：有一字符串，里面可能包含英文字母(大写、小写)、数字、特殊字符，现在需要实现一函数，将此字符串中的元音字母挑选出来，存入另一个字符串中，并对字符串中的字母进行从小到大的排序(小写的元音字母在前，大写的元音字母在后，依次有序)。说明：1、元音字母是a,e,i,o,u,A,E,I,O,U。2、筛选出来的元音字母，不需要剔重；最终输出的字符串，小写元音字母排在前面，大写元音字母排在后面，依次有序。要求实现函数：voidsortVowel(char*input,char*output);usingnamespacestd;voidfun(chara,chars)/提取元音字母，放入数组(inti=0,n=0;while(ai!='0')(if(ai='a'|ai='e'|ai=T|ai='o'|ai='u')sn+=ai;elseif(ai='A'|ai='E'|ai='I'|ai='O'|ai='U')sn+=ai;i+;chartemp;/将数组排序for(inti=0;i<n-1;i+)for(intj=0;j<n-i-1;j+)if(sj>sj+1)(temp=sj;sj=sj+1;sj+1=temp;intk=0;/定位大写字母的最后位置while(sk>='A'&&sk<='Z')(k+;for(intj=0;j<n;j+)/输出原字符串cout<<sj<<''cout<<endl;char*p=newchar20;/将字符串变换位置，输出。char*q=p;for(inti=k;i<n;i+)*p=si;p+;for(intj=0;j<k;j+)*p=sj;p+;*p='0'cout<<q<<endl;intmain()charstr="HaJsdStOoAOeINaPQaWEiAIiO”;chars20;fun(str,s);return0;身份证号码合法性判断我国公民的身份证号码特点如下：1、长度为18位；2、第117位只能为数字；3、第18位可以是数字或者小写英文字母x。4、身份证号码的第714位表示持有人生日的年、月、日信息。例如：511002198808080111或51100219880808011x。请实现身份证号码合法性判断的函数。除满足以上要求外，需要对持有人生日的年、月、日信息进行校验。年份大于等于1900年，小于等于2100年。需要考虑闰年、大小月的情况。所谓闰年，能被4整除且不能被100整除或能被400整除的年份，闰年的2月份为29天,非闰年的2月份为28天。其他情况的合法性校验，考生不用考虑。函数返回值：如果身份证号合法，返回0；如果身份证号长度不合法，返回1；如果身份证号第117位含有非数字的字符，返回2;如果身份证号第18位既不是数字也不是英文小写字母x,返回3;如果身份证号的年信息非法，返回4;如果身份证号的月信息非法，返回5;如果身份证号的日信息非法，返回6(请注意闰年的情况)；要求实现函数：intverifyIDCard(char*input)示例1) 输入：”511002111222”，函数返回值：1;2) 输入：”511002abc123456789”，函数返回值2；3)输入：”51100219880808123a”，函数返回值3；4)输入：”511002188808081234”，函数返回值4；5)输入：”511002198813081234”，函数返回值5；6)输入：”511002198808321234”，函数返回值6；7)输入：”511002198902291234”，函数返回值：7;8)输入：”511002198808081234”，函数返回值0；intfun(char*str)(intyear=0,month=0,day=0;if(strlen(str)-1)<18)/1(for(inti=0;i<18;i+)(if(stri>='0'&&stri<='9')/2;elsereturn2;if(str17='x'|(str17>='0'&&str17<='9')/3(for(inti=6;i<10;i+)year=year*10+stri-'0'if(year>1900&&year<2100)/4(for(inti=10;i<12;i+)month=month*10+stri-'0'if(month>0&&month<=12)/5(for(inti=12;i<14;i+)day=day*10+stri-'0'if(day<=31)/6(if(year%4!=0&&month=2&&day<=28)return0;elseif(year%4=0&&month=2&&day<29)return0;elseif(year%4!=4&&month!=2&&day<31)return0;elsereturn6;elsereturn6;elsereturn5;elsereturn4;elsereturn3;elsereturn1;intmain()(chara="340621198608377817"intk=fun(a);cout<<k<<endl;return0;第二题：比较一个数组的元素是否为回文数组判断是否是回文数组：boolfun(chara)(intn=strlen(a);inti=0,j=n-1;while(i<j)(if(ai!=aj)returnfalse;i+;j-;returntrue;第三题：求两个数组的和差：就是去掉两个数组中相同的元素然后将两个数组中的元素存放在一个新的数组中且数组A中元素要在澈组元素之前思路：利用循环比较，将相同的数字的标记为0,再赋给数组Cintmain()(inta=1,3,5,7,9,12,13;ints=1,3,5,6,7,8,9;intlen1=sizeof(a)/sizeof(int);intlen2=sizeof(s)/sizeof(int);for(inti=0;i<len1;i+)for(intj=0;j<len2;j+)if(ai=sj)ai=0;sj=0;intt30;intk=0,i=0,j=0;while(i<len1)if(ai!=0)tk+=ai;i+;while(j<len2)if(sj!=0)tk+=sj;j+;for(inti=0;i<k;i+)cout<<ti<<''return0;字符串计算1、选秀节目打分，分为专家评委和大众评委，score数组里面存储每个评委打的分数，judge_type里存储与score数组对应的评委类别，judge_type=1,表示专家评委，judge_type=2,表示大众评委，n表示评委总数。打分规则如下：专家评委和大众评委的分数先分别取一个平均分(平均分取整)，然后，总分=专家评委平均分*0.6+大众评委*0.4,总分取整。如果没有大众评委，则总分=专家评委平均分，总分取整。函数最终返回选手得分。intcal_score(intscore,intjudge_type,intn)intsum1=0,sum2=0,avg1=0,avg2=0;intm=0,k=0;for(inti=0;i<n;i+)if(judge_typei=1)sum1=sum1+scorei;m+;if(judge_typei=2)sum2=sum2+scorei;k+;avg1=sum1/m;avg2=sum2/k;return(int)(avg1*0.6+avg2*0.4);intmain()intinput=3,6,1,9,7,8;intoutput=1,1,2,1,2,2;intn=sizeof(input)/sizeof(int);intp=cal_score(input,output,n);cout<<p<<endl;return0;2、给定一个数组input,如果数组长度n为奇数,则将数组中最大的元素放到output数组最中间的位置，如果数组长度n为偶数，则将数组中最大的元素放到output数组中间两个位置偏右的那个位置上，然后再按从大到小的顺序，依次在第一个位置的两边，按照一左一右的顺序，依次存放剩下的数。例如input=3,6,1,9,7output=3,7,9,6,1;input=3,6,1,9,7,8output=1,6,8,9,7,3函数接口voidsort(intinput,intn,intoutput)usingnamespacestd;voidsort(intinput,intn,intoutput)inti=0,j=n-1;inttemp;for(inti=0;i<n-1;i+)for(intj=0;j<n-i-1;j+)if(inputj>inputj+1)temp=inputj;inputj=inputj+1;inputj+1=temp;intk=0;i=0;j=n-1;while(i<j)(outputi+=inputk+;outputj-=inputk+;cout<<output3<<endl;intmain()(intinput=3,6,1,9,7,8;intoutput20;sort(input,6,output);return0;3、操作系统任务调度问题。操作系统任务分为系统任务和用户任务两种。其中，系统任务的优先级<50,用户任务的优先级>=50且<=255。优先级大于255的为非法任务,应予以剔除。现有一任务队列task，长度为n,task中的元素值表示任务的优先级，数值越小，优先级越高。函数scheduler实现如下功能，将task中的任务按照系统任务、用户任务依次存放到system_task数组和user_task数组中(数组中元素的值是任务在task数组中的下标)，并且优先级高的任务排在前面，数组元素为-1表示结束。task=0,30,155,1,80,300,170,40,99system_task=0,3,1,7,-1user_task=4,8,2,6,-1函数接口：voidscheduler(inttask,intn,intsystem_task,intuser_task)int*p=newintn;inti,j,temp;intk1=0,k2=0;for(i=0;i<n;i+)pi=i;for(i=0;i<n-1;i+)for(j=0;j<n-i-1;j+)if(*(task+pj)>*(task+pj+1)temp=pj;pj=pj+1;pj+1=temp;/此处是排下标for(j=0;j<n;j+)if(*(task+pj)<50)system_taskk1+=pj;if(*(task+pj)>=50&&*(task+pj)<=255)user_taskk2+=pj;system_taskk1=-1;user_taskk2=-1;地区2:单链表的操作：排序，插入，删除，逆序，创建。structnode(intdata;structnode*next;；node*creat()(node*head,*p,*s;head=newnode1;p=head;/p只是定义，并没有分配空间，intk;while(cin>>k)/创建单链表s=newnode1;s->data=k;p->next=s;p=s;head=head->next;/开始的的时候head是表头节点，现在是第一个节点p->next=NULL;returnhead;node*reverse(node*head)node*p1,*p2,*p3;p1=head;p2=head->next;while(p2)p3=p2->next;p2->next=p1;p1=p2;p2=p3;head->next=NULL;head=p1;returnhead;node*del(node*head,intnum)node*p,*s;p=head;while(p->data!=num&&p->next!=NULL)s=p;p=p->next;if(p->data=num)if(p=head)head=p->next;deletep;elses->next=p->next;deletep;elsecout<<"未找到要删除的节点"<<endl;returnhead;node*insert(node*head,intnum)/要插入和删除的时候要考虑判断特殊位置点(node*p,*s,*t;p=head;t=newnode1;t->data=num;while(p->data<num&&p->next!=NULL)s=p;p=p->next;if(num<=p->data)if(p=head)t->next=p;head=s;elset->next=p;s->next=t;else/把插入点定位在了链尾p->next=t;t->next=NULL;returnhead;node*sort(node*head)node*p;inttemp;intn=sizeof(head)/sizeof(node);if(head=NULL&&head->next=NULL)returnhead;p=head;for(inti=0;i<n;i+)p=head;for(intj=0;j<n-i;j+)if(p->data>p->next->data)temp=p->data;p->data=p->next->data;p->next->data=temp;returnhead;栈的基本操作：structlistintdata;structnode*next;*node;voidinitstack(node&top)top=NULL;voidpush(node&top,intnum)(node*p;p=newnode;p->data=num;p->next=top;top=p;voidpop(node&top)(node*p=top;intn=top->data;top=top->next;cout<<n<<endl;deletep;intIsempty(node&top)(returntop=NULL;改进后的冒泡排序：oidmaopao(int*s,intn)(inti=1,j,b=1;inttemp;while(b)(b=0;for(j=n-i-1;j>i;j-)if(sj<sj-1)(b=1;temp=sj;sj=sj-1;sj-1=temp;for(j=i;j<n-1;j+)if(sj>sj+1)(b=1;temp=sj;sj=sj+1;sj+1=temp;i+;扫描数组，求出最大的增量长度：intmain()(inta=7,2,3,4,5,6,8;intn=7;intmax=1,len=1;for(inti=1;i<n;i+)if(ai>=ai-1)len+;continue;/跳出本次循环，继续以下的部分if(max<len)max=len;len=1;cout<<max<<endl;return0;扫描整数序列，求出最大长度子序列：思路：定义两个游标ij分别在数组的左右，从两边收缩，计算ij之间数组的总和，然后比较，求出最大的记录，并将此时的ij记录下来。intmain()ints=1,20,-3,49,59,10,30,20,-41,90,-2,-30,60.-29;intn=sizeof(s)/sizeof(int);inti,k,j,a,b,num,max=0;for(i=0;i<n;i+)for(j=n-1;j>=i;j-)num=0;for(k=i;k<=j;k+)num=num+sk;if(max<num)max=num;a=i;b=j;for(intm=a;m<=b;m+)cout<<sm<<''return0;直接插入排序：voidinsertsort(inta,intn)intx,j;for(inti=1;i<n;i+)(x=ai;for(j=i-1;j>=0&&x>aj;j-)aj+1=aj;aj+1=x;提取字符串中的数字：在字符串”ab00cd+123fght456-253.005fgh”中提取的字符是0,123,456,253,5。voidfun(charstr,intoutArray)(char*p=str;intcount=0,value=0;while(*p!='0')(if(*p<='0'&&*p>='9')(value=0;while(*p<='0'&&*p>='9')(value=value*10+(*p-'0');p+；outArraycount+=value;p+;数字转换成字符串：intmain()(charstr20,temp20;inti=0,j=0;intnum=1234567;while(num>0)(stri=num%10+'0'num=num/10;i+;i-;while(i>=0)(tempj+=stri-;tempj='0'cout<<temp<<endl;return0;如下输入方法：第一行输入要输入字符的行数N,接下输入N亍字符，统计字符中特定字符的个数。方法如下：intmain()(charch;intN,num=0;cin>>N;/定义输入的行数getchar();/输入的N亍字符for(inti=0;i<N;i+)(while(1)(/记住控制方法ch=getchar();/这是单个字符if(ch='a')num+;if(ch='n')break;cout<<num<<endl;return0;大数的运算：voidfun(char*num1,char*num2,char*result)(inti=strlen(num1)-1,j=strlen(num2)-1;char*p=num1;char*q=num2;intn=0,k=0;if(p0!='-'&&q0!='-')(/两个正数相加，两个负数相加一样，就是在resultn中再加上一个-',再反序输出。while(i>=0&&j>=0)resultn+=(pi-'0')+(qj-'0')+k)%10+'0'k=(pi-'0')+(qj-'0')/10;i-;j-;while(i>=0)resultn+=(pi-'0')+k)%10+'0'k=(pi-'0')+k)/10;i-;while(j>0)resultn+=(q田-'0')+k)%10+'0'k=(qj-'0')+k)/10;i-;if(k=1)resultn+=1;/如果是两个负数相加，加上resultn+='-'resultn='0'求字符串中最大的回文长度:voidfun(chara)intlen=strlen(a);inti=0,j=len-1,len2=0;/len2是回文的一半长度char*p,*q;intmax=0,pos1=0,pos2=0;for(i=0;i<len;i+)for(j=len-1;j>i;j-)p=&ai;q=&aj;while(p<q)if(*p=*q)len2+;p+;q-;Else/上式中，如若不成立，保留下来的len的值可能很大，要将其变成0,以便继续使用。len=0,break;if(max<len2)max=len2;pos1=i;pos2=j;len2=0;while(pos1<=pos2)cout<<apos1+;intmain()chara="ddaffafFEaabbccccbbaabsgbsbgsbg”;fun(a);return0;求一串字符串中出现次数最多的单词：voidfun(chara)charstr100100;chartemp200;intvalue200;intk1=0,k2=0,k3=0;inti=0,j=0;while(ai!='0')if(i=0)while(ai!='')tempk3+=ai+;tempk3='0'k3=0;strcpy(strk1,temp);valuek1+=1;else(if(ai='')i+；while(ai!='0'&&ai!='')tempk3+=ai+;tempk3='0'k3=0;j=0;while(j<k1)(if(strcmp(strj,temp)=0)(valuej+=1;break;j+;if(j=k1)(strcpy(strk1,temp);valuek1=1;k1+;cout<<value7<<endl;cout<<str7<<endl;intmain()(chara="aaaaaaaaaaaaaaaaaaaaamededeamamamjnnkadfpcrpcwecrwcqaqaqaqaqaqaqaqaqa"fun(a);return0;一个字符申"aasbbsdsskkff”，求出重复的次数，并写到数组后面，输出为“a2s1b2s1d1s2k2f2”voidfun(char*a,char*s)(intn=1,k=0;char*p=a,*q=a;q+;sk+=*p;while(*p!='0')(if(*p=*q)(n+;p+;q+;else(sk+=n+'0'sk+=*q;p+;q+;n=1;cout<<s<<endl;单链表操作：structnode(intdata;node*next;；node*creat()(intnum;node*head,*p,*q;head=newnode1;q=head;while(cin>>num)p=newnode1;p->data=num;p->next=NULL;q->next=p;q=p;returnhead;voidreverse(node*head)node*p1,*p2,*p3;p1=*head;p2=p1->next;while(p2)p3=p2->next;p2->next=p1;p1=p2;p2=p3;(*head)->next=NULL;*head=p1;while(!(*head)->next=NULL)cout<<(*head)->data<<'-'*head=(*head)->next;voidinsert(node*head)node*p=head;while(p->data<=num)p+;intmain()(node*head;head=newnode1;head=creat();reverse(&head);return0;1.识别字符串中的整数并转换为数字形式（40分）问题描述：识别输入字符串中所有的整数，统计整数个数并将这些字符串形式的整数转换为数字形式整数。要求实现函数：voidtake_num（constchar*strIn,int*n,unsignedint*outArray）【输入】strIn:输入的字符串【输出】n:统计识别出来的整数个数outArray:识别出来的整数值，其中outArray0是输入字符串中从左到右第一个整数，outArray1是第二个整数，以此类推。数组地址已经分配，可以直接使用【返回】无注：I、不考虑字符串中出现的正负号（+,-）,即所有转换结果为非负整数（包括0和正整数）II、不考虑转换后整数超出范围情况，即测试用例中可能出现的最大整数不会超过unsignedint可处理的范围III、需要考虑'0'开始的数字字符串情况，比如”00035”,应转换为整数35;"000"应转换为整数0;"00.0035"应转换为整数0和35（忽略小数点：mmm.nnn当成两个数mmm和nnn来识别）IV、输入字符串不会超过100Bytes,请不用考虑超长字符串的情况。示例输入：strIn="ab00cd+123fght456-253.005fgh"输出：n=6outArray=（0,123,456,25,3,52.IP地址匹配（60分）问题描述：在路由器中，一般来说转发模块采用最大前缀匹配原则进行目的端口查找，具体如下：IP地址和子网地址匹配：IP地址和子网地址所带掩码做AND运算后，得到的值与子网地址相同，则该IP地址与该子网匹配。比如：IP地址：192.168.1.100子网：192.168.1.0/255.255.255.0，其中192.168.1.0是子网地址，255.255.255.0是子网掩码。192.168.1.100&255.255.255.0=192.168.1.0，则该IP和子网192.168.1.0匹配IP地址：192.168.1.100子网：192.168.1.128/255.255.255.192192.168.1.100&255.255.255.192=192.168.1.64,则该IP和子网192.168.1.128不匹配最大前缀匹配：任何一个IPv4地址都可以看作一个32bit的二进制数，比如192.168.1.100可以表示为：11000000.10101000.00000001.01100100,192.168.1.0可以表示为11000000.10101000.00000001.00000000最大前缀匹配要求IP地址同子网地址匹配的基础上，二进制位从左到右完全匹配的位数尽量多（从左到右子网地址最长）。比如：IP地址192.168.1.100，同时匹配子网192.168.1.0/255.255.255.0和子网192.168.1.64/255.255.255.192,但对于子网192.168.1.64/255.255.255.192，匹配位数达到26位，多于子网192.168.1.0/255.255.255.0的24位，因此192.168.1.100最大前缀匹配子网是192.168.1.64/255.255.255.192。请编程实现上述最大前缀匹配算法。要求实现函数：voidmax_prefix_match（constchar*ip_addr,constchar*net_addr_array,int*n）【输入】ip_addr:IP地址字符串，严格保证是合法IPv4地址形式的字符串net_addr_array:子网地址列表，每一个字符串代表一个子网，包括子网地址和掩码，表现形式如上述，子网地址和子网掩码用分开，严格保证是合法形式的字符串；如果读到空字符串，表示子网地址列表结束【输出】n：最大前缀匹配子网在*net_addr_array数组中对应的下标值。如果没有匹配返回-1示例输入：ip_addr="192.168.1.100"net_addr_array=("192.168.1.128/255.255.255.192","192.168.1.0/255.255.255.0","192.168.1.64/255.255.255.192","0.0.0.0/0.0.0.0",""输出：n=2#include<stdio.h>#include<assert.h>voidtake_num(constchar*strIn,int*n,unsignedint*outArray)(constchar*p=strIn;intnext=0;*n=0;outArray0=0;assert(p&&n&&outArray);for(p=strIn;*p;p+)(if('0'<=*p)&&(*p<='9')outArray*n=(outArray*n*10)+(*p)-'0');next=1;/*后面还有*/elseif(next=1)(*n)+;next=0;voidmax_prefix_match(constchar*ip_addr,char*net_addr_array,int*n)intip,tar_net,tar_mask;/*ip地址*/intip_it4,net_it4,mask_it4;char*p;intindex,max_index,cur_bits,max_bits=0,bit;*n=-1;sscanf(ip_addr,"%d.%d.%d.%d",&ip_it0,&ip_it1,&ip_it2,&ip_it3);ip=(ip_it0<<24)+(ip_it1<<16)+(ip_it2<<8)+ip_it3);for(index=0;net_addr_arrayindex0!='0'index+)/*获取网络号和掩码*/p=net_addr_arrayindex;sscanf(p,”%d.%d.%d.%d/%d.%d.%d.%d”,&net_it0,&net_it1,&net_it2,&net_it3,&mask_it0,&mask_it1,&mask_it2,&mask_it3);tar_mask=(mask_it0<<24)+(mask_it1<<16)+(mask_it2<<8)+mask_it3);tar_net=(net_it0<<24)+(net_it1<<16)+(net_it2<<8)+net_it3);if(tar_mask)&(ip)=(tar_net)cur_bits=0;/*计算1的个数*/for(bit=0;bit<sizeof(tar_mask)*8;bit+)cur_bits+=tar_mask&1;tar_mask>>=1;if(cur_bits>max_bits)max_bits=cur_bits;max_index=index;if(max_bits!=0)*n=max_index;intmain()inti,n;unsignedintarrayOut100=0;char*strIn="ab00cd+123fght456-253.005fgh”;char*ip_addr="192.168.1.100"char*net_addr_array1024="192.168.1.128/255.255.255.192","192.168.1.0/255.255.255.0","192.168.1.64/255.255.255.192","0.0.0.0/0.0.0.0",""take_num(strIn,&n,arrayOut);printf("<1>:input:%snoutput:%dn”,strIn,n);for(i=0;i<n;i+)printf("%dn”,arrayOuti);max_prefix_match(ip_addr,net_addr_array,&n);if(n!=-1)(printf("<2>max:%d%s”,n,net_addr_arrayn);getchar();return0;