Êý¾Ý½á¹¹ - CÓïÑÔÃèÊö¿Îºó´ð°¸

ʵÏÖ¡£

int visited[MAXSIZE]; //ָʾ¶¥µãÊÇ·ñÔÚµ±Ç°Â·¾¶ÉÏ

int exist_path_DFS(ALGraph G,int i,int j)//Éî¶ÈÓÅÏÈÅжÏÓÐÏòͼGÖж¥µãiµ½¶¥µãjÊÇ·ñÓз¾¶,ÊÇÔò·µ»Ø1,·ñÔò·µ»Ø0 {

if(i==j) return 1; //i¾ÍÊÇj else {

visited[i]=1;

for(p=G.vertices[i].firstarc;p;p=p->nextarc) {

k=p->adjvex;

if(!visited[k]&&exist_path(k,j)) return 1;//iÏÂÓεĶ¥µãµ½jÓз¾¶ }//for }//else

}//exist_path_DFS

7.9 ͬÉÏÌâÒªÇó¡£ÊÔ»ùÓÚͼµÄ¹ã¶ÈÓÅÏÈËÑË÷²ßÂÔдһËã·¨¡£

int exist_path_BFS(ALGraph G,int i,int j)//¹ã¶ÈÓÅÏÈÅжÏÓÐÏòͼGÖж¥µãiµ½¶¥µãjÊÇ·ñÓз¾¶,ÊÇÔò·µ»Ø1,·ñÔò·µ»Ø0 {

int visited[MAXSIZE]; InitQueue(Q); EnQueue(Q,i);

while(!QueueEmpty(Q)) {

DeQueue(Q,u); visited[u]=1;

for(p=G.vertices[i].firstarc;p;p=p->nextarc) {

k=p->adjvex; if(k==j) return 1;

if(!visited[k]) EnQueue(Q,k); }//for }//while return 0;

}//exist_path_BFS

7.10 ÊÔÀûÓÃÕ»µÄ»ù±¾²Ù×÷£¬±àд°´Éî¶ÈÓÅÏȲßÂÔ±éÀúÒ»¸öÇ¿Á¬Í¨Í¼µÄ¡¢·ÇµÝ¹éÐÎʽµÄËã·¨¡£Ëã·¨Öв»¹æ¶¨¾ßÌåµÄ´æ´¢½á¹¹£¬¶ø½«Í¼Graph¿´³ÉÊÇÒ»ÖÖ³éÏóÊý¾ÝÀàÐÍ¡£

void STraverse_Nonrecursive(Graph G)//·ÇµÝ¹é±éÀúÇ¿Á¬Í¨Í¼G

{

int visited[MAXSIZE]; InitStack(S);

Push(S,GetVex(S,1)); //½«µÚÒ»¸ö¶¥µãÈëÕ» visit(1); visited=1;

while(!StackEmpty(S)) {

while(Gettop(S,i)&&i) {

j=FirstAdjVex(G,i); if(j&&!visited[j]) {

visit(j); visited[j]=1;

Push(S,j); //Ïò×ó×ßµ½¾¡Í· } }//while

if(!StackEmpty(S)) {

Pop(S,j); Gettop(S,i);

k=NextAdjVex(G,i,j); //ÏòÓÒ×ßÒ»²½ if(k&&!visited[k]) {

visit(k); visited[k]=1; Push(S,k); } }//if }//while

}//Straverse_Nonrecursive

·ÖÎö:±¾Ëã·¨µÄ»ù±¾Ë¼ÏëÓë¶þ²æÊ÷µÄÏÈÐò±éÀú·ÇµÝ¹éËã·¨Ïàͬ,Çë²Î¿¼6.37.ÓÉÓÚÊÇÇ¿Á¬Í¨Í¼,ËùÒÔ´ÓµÚÒ»¸ö½áµã³ö·¢Ò»¶¨Äܹ»·ÃÎʵ½ËùÓнáµã.

7.11 ²ÉÓÃÁÚ½Ó±í´æ´¢½á¹¹£¬±àдһ¸öÅбðÎÞÏòͼÖÐÈÎÒâ¸ø¶¨µÄÁ½¸ö¶¥µãÖ®¼äÊÇ·ñ´æÔÚÒ»Ìõ³¤¶ÈΪkµÄ¼òµ¥Â·¾¶£¨Ö¸¶¥µãÐòÁÐÖв»º¬ÓÐÖØÏֵĶ¥µã£©µÄËã·¨¡£

[Ìáʾ]£ºÀûÓÃÉî¶ÈËÑË÷£¬ÔöÉèÒ»¸öÉî¶È²ÎÊý£¬Éî¶È³¬¹ýk ÔòÍ£Ö¹¶Ô¸Ã½áµãµÄËÑË÷¡£

int visited[MAXSIZE];

int exist_path_len(ALGraph G,int i,int j,int k)//ÅжÏÁÚ½Ó±í·½Ê½´æ´¢µÄÓÐÏòͼGµÄ¶¥µãiµ½jÊÇ·ñ´æÔÚ³¤¶ÈΪkµÄ¼òµ¥Â·¾¶ {

if(i==j&&k==0) return 1; //ÕÒµ½ÁËÒ»Ìõ·¾¶,ÇÒ³¤¶È·ûºÏÒªÇó

else if(k>0) {

visited[i]=1;

for(p=G.vertices[i].firstarc;p;p=p->nextarc) {

l=p->adjvex; if(!visited[l])

if(exist_path_len(G,l,j,k-1)) return 1; //Ê£Óà·¾¶³¤¶È¼õÒ» }//for

visited[i]=0; //±¾ÌâÔÊÐíÔø¾­±»·ÃÎʹýµÄ½áµã³öÏÖÔÚÁíÒ»Ìõ·¾¶ÖÐ }//else

return 0; //ûÕÒµ½ }//exist_path_len

7.12 ÏÂͼÊÇ´øÈ¨µÄÓÐÏòͼGµÄÁÚ½Ó±í±íʾ·¨¡£´Ó½áµãV1³ö·¢£¬Éî¶È±éÀúͼGËùµÃ½áµãÐòÁÐΪ£¨ A £©£¬¹ã¶È±éÀúͼGËùµÃ½áµãÐòÁÐΪ£¨ B £©£»GµÄÒ»¸öÍØÆËÐòÁÐÊÇ£¨ C £©£»´Ó½áµãV1µ½½áµãV8µÄ×î¶Ì·¾¶Îª£¨ D £©£»´Ó½áµãV1µ½½áµãV8µÄ¹Ø¼ü·¾¶Îª£¨ E £©¡£ ÆäÖÐA¡¢B¡¢CµÄÑ¡ÔñÓУº ¢Ù V1,V2,V3,V4,V5,V6,V7,V8 ¢Ú V1,V2,V4,V6,V5,V3,V7,V8 ¢Û V1,V2,V4,V6,V3,V5,V7,V8 ¢Ü V1,V2,V4,V6,V7,V3,V5,V8 ¢Ý V1,V2,V3,V8,V4,V5,V6,V7 ¢Þ V1,V2,V3,V8,V4,V5,V7,V6 ¢ß V1,V2,V3,V8,V5,V7,V4,V6 D¡¢EµÄÑ¡ÔñÓУº ¢Ù V1,V2,V4,V5,V3,V8 ¢Ú V1,V6,V5,V3,V8 ¢Û V1,V6,V7,V8 V1,V2,V5,V7,V8 ¢Ü

7.13 ÒÑÖªÒ»¿ÃÒÔ¶þ²æÁ´±í×÷´æ´¢½á¹¹µÄ¶þ²æÊ÷£¬ÊÔ±àд°´²ã´Î˳Ðò£¨Í¬Ò»²ã×Ô×óÖÁÓÒ£©±éÀú¶þ²æÊ÷µÄËã·¨¡£

void LayerOrder(Bitree T)//²ãÐò±éÀú¶þ²æÊ÷ {

InitQueue(Q); //½¨Á¢¹¤×÷¶ÓÁÐ EnQueue(Q,T);

while(!QueueEmpty(Q)) {

DeQueue(Q,p); visit(p);

if(p->lchild) EnQueue(Q,p->lchild); if(p->rchild) EnQueue(Q,p->rchild); }

}//LayerOrder µÚ°ËÕ ²éÕÒ

8.1 Èô¶Ô´óС¾ùΪnµÄÓÐÐòµÄ˳Ðò±íºÍÎÞÐòµÄ˳Ðò±í·Ö±ð½øÐвéÕÒ£¬ÊÔÔÚÏÂÁÐÈýÖÖÇé¿öÏ·ֱðÌÖÂÛÁ½ÕßÔڵȸÅÂÊʱµÄƽ¾ù²éÕÒ³¤¶ÈÊÇ·ñÏàͬ£¿

£¨1£© ²éÕÒ²»³É¹¦£¬¼´±íÖÐûÓйؼü×ÖµÈÓÚ¸ø¶¨ÖµKµÄ¼Ç¼¡£ £¨2£© ²éÕҳɹ¦£¬ÇÒ±íÖÐÖ»ÓÐÒ»¸ö¹Ø¼ü×ÖµÈÓÚ¸ø¶¨ÖµKµÄ¼Ç¼¡£

£¨3£© ²éÕҳɹ¦£¬ÇÒ±íÖÐÓÐÈô¸É¸ö¹Ø¼ü×ÖµÈÓÚ¸ø¶¨ÖµKµÄ¼Ç¼£¬Ò»´Î²éÕÒÒªÇóÕÒ³öËùÓмǼ¡£

[Ìáʾ]£º¾ùÓÃ˳Ðò²éÕÒ·¨¡£

8.2 »­³ö¶Ô³¤¶ÈΪ10µÄÓÐÐò±í½øÐÐÕÛ°ë²éÕÒµÄÅж¨Ê÷£¬²¢ÇóÆäµÈ¸ÅÂÊʱ²éÕҳɹ¦µÄƽ¾ù²éÕÒ³¤¶È¡£

[Ìáʾ]£º¸ù¾ÝP.191 ASL¶¨Ò弯ËãÆ½¾ù²éÕÒ³¤¶È¡£

8.3 ÊÔÍÆµ¼º¬12¸ö½áµãµÄƽºâ¶þ²æÊ÷µÄ×î´óÉî¶È²¢»­³öÒ»¿ÃÕâÑùµÄÊ÷¡£

[Ìáʾ]£ºÑØ×î×ó·ÖÖ§Éú³¤£¬Ç°ÌáÊÇ£ºÆäÈÎÒ»×æÏȵÄÓÒ·ÖÖ§Óë×ó·ÖÖ§µÈÉÈç²»µÈÉÔòÏÈÉú³¤ÓÒ·ÖÖ§£¬¶øÉú³¤ÓÒ·ÖÖ§µÄǰÌáÊÇ£ºÆäÈÎÒ»×æÏȵÄ×ó·ÖÖ§ÓëÓÒ·ÖÖ§µÈÉÈç²»µÈÉÔòÏÈÉú³¤×ó·ÖÖ§£¬Èç´Ë½»»¥¿¼ÂÇ£¬Öð²½Éú³¤£¬Ö±µ½12¸ö½áµã¡£

8.4 ÊÔ´Ó¿ÕÊ÷¿ªÊ¼£¬»­³ö°´ÒÔÏ´ÎÐòÏò2-3Ê÷£¬¼´3½×B-Ê÷ÖвåÈë¹Ø¼üÂëµÄ½¨Ê÷¹ý³Ì£º20£¬30£¬50£¬52£¬60£¬68£¬70¡£Èç¹û´Ëºóɾ³ý50ºÍ68£¬»­³öÿһ²½Ö´Ðкó2-3Ê÷µÄ״̬¡£

8.5 ѡȡ¹þÏ£º¯ÊýH(k)=(3k)£¬ÓÃÏßÐÔ̽²âÔÙÉ¢Áз¨´¦Àí³åÍ»¡£ÊÔÔÚ0¡«10µÄÉ¢ÁеØÖ·¿Õ¼äÖУ¬¶Ô¹Ø¼ü×ÖÐòÁУ¨22£¬41£¬53£¬46£¬30£¬13£¬01£¬67£©¹¹Ôì¹þÏ£±í£¬²¢ÇóµÈ¸ÅÂÊÇé¿öϲéÕҳɹ¦Óë²»³É¹¦Ê±µÄƽ¾ù²éÕÒ³¤¶È¡£ [Ìáʾ]£ºÆ½¾ù²éÕÒ³¤¶È²Î¿¼P.225¡£

0 1 2 3 4 5 6 7 8 9 10 22 41 30 01 53 46 13 67 1 1 2 2 1 1 2 6

ASLsucc = (1¡Á4 + 2¡Á3 + 6) / 8 = 2

ASLunsucc = ( 2 + 1 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 1 ) / 11 = 40 / 11

ÁªÏµ¿Í·þ£º779662525#qq.com(#Ìæ»»Îª@)