英文版数据结构算法题.doc

《英文版数据结构算法题.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、1.Supposewehavealinkedlist.Eacknodehasthreeparts:onedatafieldandtwolinkedfields.Thelisthasbeenlinkedbythefirstlinkedfieldlink1,butthelistisdisorder.Tryyourbesttosortthelistwiththesecondlinkedfieldintoanincreasinglist.算法:intcreasort(structnode&head){if(head.link1==NULL)//没有结点r

2、eturnERROR;head.link2=head.link1;//设排列链表的第一个结点head.link2->link2=NULL;p=head.link1->link1;//p为链表的第二个结点q=head;//q代表p插入位置的前一个结点if(!p)//只有一个结点returnOK;while(p){while(q->link2&&(q->link2->datadata))//找查找入位置q=q->link2;if(!q->link2)//插在最后{q->link2=p;}else//插在队列中间{p->link2=q->lin

3、k2;q->link2=p;}p=p->link1;q=head;}returnOK;}1.Supposewehaveasequencewiththeterminalcharacter@.TheformatofthesequencecanbeS1&S2,S1andS2donotcontain‘&’,S2isthereversesequenceofS1.Trytowriteanalgorithmtocheckthesequenceiftheformatofthesequenceobeystheabovefulesthenthefunctionret

4、urnTRUEotherwiseFALSE.算法://s为待检查的字符串intcheckrules(char*s){len=strlen(s);//用string.h自带函数取字符串s的长度if(len%2==0)//字符串是偶数returnFALSE;i=0;//i指向字符串第一个字符n=len-1;//n指向字符串最后一个字符while(i

5、

6、s[n]!='&'))//对半劈{if(s[i]==s[n]){i++;n--;}elsebreak;}if(i==len/2&&s[i]=='&')//i指向中间元

7、素且必须是’&’returnTRUE;elsereturnFALSE;}1.Supposewehaveadouble-linkedciroularlistL.Eacknodehasfourfields:twolinkedfielspreandnext,onedatafielddataandonefrequencyfieldfreq.Atthebeginningtheinitialvalueoffreqis0andaftereachopeationLocate(L,x),thevalueinfrequencyfieldofxplus1,andthe

8、nsortthelistaccordingtofreqintoanon-increasinglist.Thenodewhichismostfrequentlyaccessedisthefirstnodeaftertheheadnode.算法:voidLocate(structdoulinL,intx){structdoulin*;//访问时用到的遍历指针if(x>L.data)//无效的访问return;p=&L;//定位，p指向已经访问的指针while(x--){p=p->next;}p->freq++;//因为形参L不在循环链表里，因此要用L

9、.pre->next表示循环链表的头结点while(p->pre->freqfreq&&p->pre!=L.pre->next){p->data<->p->pre->data;p->freq<->p->pre->freq;}}1.Supposewehaveadisorderedlistofintegers.Thelisthasbeenstoredinastack.Youaresupposedtosortthelistwithqueue.算法://表示将from队的元素倒到to中voidQueToQue(Queue*from,Queue*t

10、o,intns){tag=0;//用于标注要排列的数是否进栈while(!QueueEmpty(from)){DeQueue(from,