öλÔÓéÀֵǼÈë¿ÚÏÂÔØ

Ô­ÎÄÄÚÈÝÀ´×ÔÃâ·ÑöλÔÓéÀÖ¹Ù·½appÏÂÔØÂÛ̳£¬Çëµã»÷²é¿´È«ÎÄ
http://bbs.freekaoyan.com/viewthread.php?tid=159294
»ªÖпƼ¼´óѧ¼ÆËã»úѧԺ
˶ʿÑо¿ÉúÈëѧ¡¶Êý¾Ý½á¹¹¡·öλÔÓéÀֵǼÈë¿ÚÏÂÔØ´ó¸Ù

µÚÒ»²¿·Ö öλÔÓéÀֵǼÈë¿ÚÏÂÔØ˵Ã÷
Ò»¡¢öλÔÓéÀֵǼÈë¿ÚÏÂÔØÐÔÖÊ
Êý¾Ý½á¹¹ÊǼÆËã»ú¸÷öλÔÓéÀֵǼÈë¿ÚÏÂÔصÄöλÔÓéÀֵǼÈë¿ÚÏÂÔØ»ù´¡¿Î¡£ËüµÄÆÀ¼Û±ê×¼ÊǸߵÈѧУ¼ÆËã»ú¿ÆѧÓë¼¼Êõ¸÷öλÔÓéÀֵǼÈë¿ÚÏÂÔر¾¿Æ±ÏÒµÉúÄÜ´ïµ½µÄ¼°¸ñ»ò¼°¸ñÒÔÉÏˮƽ,ÒÔ±£Ö¤±»Â¼È¡Õß¾ßÓлù±¾µÄöλÔÓéÀֵǼÈë¿ÚÏÂÔØÀíÂÛ»ù´¡¼°³ÌÐòÉè¼ÆÄÜÁ¦,ÒÔÀûÓÚ¼ÆËã»ú¿ÆѧÓë¼¼Êõ¸÷öλÔÓéÀֵǼÈë¿ÚÏÂÔصĵ¼Ê¦ÔñÓÅÑ¡°Î˶ʿÑо¿Éú¡£
öλÔÓéÀֵǼÈë¿ÚÏÂÔضÔÏóΪ²Î¼ÓÈ«¹ú˶ʿÑо¿ÉúÈëѧöλÔÓéÀֵǼÈë¿ÚÏÂÔصı¾¿Æ±ÏÒµÉúºÍ¾ßÓÐͬµÈѧÁ¦µÄÔÚÖ°ÈËÔ±¡£

¶þ¡¢öλÔÓéÀֵǼÈë¿ÚÏÂÔØ·¶Î§
¸÷ÖÖ»ù±¾ÀàÐ͵ÄÊý¾Ý½á¹¹µÄ¸ÅÄî¡¢ÌØÕ÷¡¢²Ù×÷¡¢´æ´¢±íʾºÍ»ù±¾Ó¦Ó㻸÷ÖÖ»ù±¾²éÕÒ±íµÄ¸ÅÄî¡¢ÌØÕ÷¼°Æä²éÕÒ·½·¨£¬»ù±¾µÄÄÚÅÅÐòºÍÍâÅÅÐò·½·¨£»ÎļþÔÚÍâ´æ´¢Æ÷ÖеĻù±¾±íʾ·½·¨£»ÓÃCÓïÑÔ(»òC )ÃèÊöËã·¨ºÍ³ÌÐòÉè¼Æ,Ëã·¨·ÖÎö¡£

Èý¡¢ÆÀ¼ÛÄ¿±ê
ÔÚ¿¼²é»ù±¾¸ÅÄî¡¢»ù±¾ÖªÊ¶¡¢»ù±¾·½·¨µÄ»ù´¡ÉÏ£¬×¢ÖØ¿¼²éѧÉúÔËÓûù±¾ÖªÊ¶À´·ÖÎöºÍ½â¾öʵ¼ÊÎÊÌâµÄÄÜÁ¦,×¢ÖØ¿¼²éËã·¨ºÍ³ÌÐòÉè¼ÆµÄÄÜÁ¦¡£
¾ßÌåÒªÇó¼û±¾öλÔÓéÀֵǼÈë¿ÚÏÂÔØ´ó¸ÙµÚ¶þ²¿·ÖµÄ¡°¿¼²éÒªµã¡±¡£

ËÄ¡¢öλÔÓéÀֵǼÈë¿ÚÏÂÔØÐÎʽÓëÊÔ¾í½á¹¹
1.´ð¾í·½Ê½:±Õ¾í,±ÊÊÔ¡£
2.´ðÌâʱ¼ä:180 ·ÖÖÓ¡£
3.¿¼²éÄÚÈݼ°Æ俼²é±ÈÀý
»ù±¾¸ÅÄî¡¢»ù±¾ÖªÊ¶¡¢»ù±¾·½·¨Ô¼Õ¼40%¡«50%£»×ÛºÏÓ¦Óá¢Ëã·¨ºÍ³ÌÐòÉè¼ÆÓëËã·¨·ÖÎöÔ¼Õ¼60%¡«50%¡£
4.ÊÔ¾í½á¹¹ÓëöλÔÓéÀֵǼÈë¿ÚÏÂÔØÌâÐÍ
ÊÔ¾í¹²150·Ö,»ù±¾µÄöλÔÓéÀֵǼÈë¿ÚÏÂÔØÌâÐÍÓУº
(1)µ¥ÏîÑ¡ÔñÌâºÍ¶àÏîÑ¡ÔñÌ⣻
(2)Ìî¿ÕÌâ(»ù±¾¸ÅÄî¡¢»ù±¾ÖªÊ¶¡¢»ù±¾·½·¨)£»
(3)»­Í¼Ì⣻
(4)¼ò´ðÌ⣻
(5)Ó¦ÓÃÌâ(Çó½âÎÊÌâ)£»
(6)Ëã·¨ºÍ³ÌÐòÉè¼ÆÌî¿ÕÌ⣻
(7)Ëã·¨ºÍ³ÌÐòÉè¼ÆÓë·ÖÎöÌ⣻
(8)ÆäËüÌâÐÍ¡£

Îå¡¢½Ì²ÄºÍ²Î¿¼Êé
½Ì²Ä: ¡¶Êý¾Ý½á¹¹¡·(CÓïÑÔ°æ)£¬ÑÏεÃô¡¢ÎâΰÃñ±àÖø,Ç廪´óѧ³ö°æÉç,1997.4

µÚ¶þ²¿·Ö ¿¼²éÒªµã
1.Êý¾Ý½á¹¹ºÍËã·¨
Êý¾Ý½á¹¹¡¢´æ´¢½á¹¹µÄ¸ÅÄÊý¾ÝÀàÐÍÓë³éÏóÊý¾ÝÀàÐÍ£»Ëã·¨µÄ¸ÅÄî,ÓÃC/C ÃèÊöËã·¨ºÍ³ÌÐòÉè¼Æ,Ëã·¨·ÖÎö³õ²½¡£
2.ÏßÐÔ±í
ÏßÐÔ±íµÄ¶¨ÒåºÍ»ù±¾²Ù×÷£»ÏßÐÔ±íµÄ³éÏóÊý¾ÝÀàÐÍ£»ÏßÐÔ±íµÄ˳Ðò´æ´¢½á¹¹£¬
Ó¦ÓþÙÀý£»ÏßÐÔ±íµÄÁ´Ê½´æ´¢½á¹¹(µ¥Á´±í,Ë«Á´±í,Ñ­»·Á´±í),Ó¦ÓþÙÀý¡£
3.Õ»
Õ»µÄ¶¨ÒåºÍ»ù±¾²Ù×÷£»Õ»µÄ³éÏóÊý¾ÝÀàÐÍ£»Ë³ÐòÕ»£¬Á´Ê½Õ»£»Õ»ºÍµÝ¹éËã·¨, ËãÊõ±í´ïʽÇóÖµ,ÆäËüÓ¦Óá£
4£®¶ÓÁÐ
¶ÓÁеĶ¨ÒåºÍ»ù±¾²Ù×÷£»¶ÓÁеijéÏóÊý¾ÝÀàÐÍ£»Ë³Ðò¶ÓÁУ¬Á´Ê½¶ÓÁУ»Ë«¶Ë
¶ÓÁеĶ¨ÒåºÍ»ù±¾²Ù×÷£»Ó¦ÓþÙÀý¡£
5.Êý×éºÍ¹ãÒå±í
(1)Êý×é
Êý×éµÄ¶¨ÒåºÍ»ù±¾²Ù×÷£»Êý×éµÄ˳Ðò´æ´¢½á¹¹£¬Ó¦ÓþÙÀý£»ÌØÊâ¾ØÕóºÍÏ¡Êè
¾ØÕóµÄѹËõ´æ´¢¡£
(2)¹ãÒå±í
¹ãÒå±íµÄ¶¨ÒåºÍ»ù±¾²Ù×÷,¹ãÒå±íµÄ³éÏóÊý¾ÝÀàÐÍ,¹ãÒå±íµÄ´æ´¢½á¹¹¡£
*¹ãÒå±íÔËËãµÄʵÏÖ¾ÙÀý¡£
6.×Ö·û´®
×Ö·û´®µÄ¶¨ÒåºÍ»ù±¾²Ù×÷,×Ö·û´®µÄ´æ´¢½á¹¹,×Ö·û´®²Ù×÷µÄʵÏÖ¾ÙÀý,×Ö·û´®ºÍģʽƥÅä¡£
7.Ê÷ºÍ¶þ²æÊ÷
(1)Ê÷µÄ»ù±¾¸ÅÄîºÍ»ù±¾²Ù×÷,Ê÷µÄ³éÏóÊý¾ÝÀàÐÍ¡£
(2)¶þ²æÊ÷µÄ¸ÅÄîºÍÐÔÖÊ,ÌØÊâ¶þ²æÊ÷£»¶þ²æÊ÷µÄ´æ´¢½á¹¹£»
(3)¶þ²æÊ÷µÄÉú³ÉÓ뽨Á¢¡£
(4)±éÀú¶þ²æÊ÷£ºÇ°Ðò±éÀú,ÖÐÐò±éÀú,ºóÐò±éÀú,²ã´Î±éÀú¡£
(5)¶þ²æÊ÷ÆäËü²Ù×÷ʵÏÖ¾ÙÀý¡£
(6)ÏßË÷¶þ²æÊ÷µÄ¸ÅÄîºÍ´æ´¢½á¹¹,¶þ²æÊ÷µÄÏßË÷»¯,ÏßË÷¶þ²æÊ÷µÄ±éÀú¡£
(7)Ê÷µÄ´æ´¢½á¹¹,Ê÷Óë¶þ²æÊ÷Ö®¼äµÄת»»,É­ÁÖÓë¶þ²æÊ÷Ö®¼äµÄת»»,Ê÷ºÍÉ­ÁֵıéÀú¡£
(8)Ê÷µÄ·¾¶³¤¶ÈºÍ´øȨ·¾¶³¤¶È,¹þ·òÂüÊ÷(Huffman)µÄ¸ÅÄî,¹þ·òÂüËã·¨, ¹þ·òÂü±àÂëÊ÷¡£
(9)¶þ²æÅÅÐòÊ÷µÄµÄ¸ÅÄîºÍ»ù±¾²Ù×÷,¶þ²æÅÅÐòÊ÷µÄ½¨Á¢,¶þ²æÅÅÐòÊ÷ÆäËü²Ù×÷ʵÏÖ¾ÙÀý¡£
8.ͼ
(1)ͼµÄ»ù±¾¸ÅÄîºÍ»ù±¾²Ù×÷£¬Í¼µÄ³éÏóÊý¾ÝÀàÐÍ¡£
(2)ͼµÄ´æ´¢½á¹¹£ºÊý×é±íʾ·¨(ÁÚ½Ó¾ØÕó)£»ÁÚ½Ó±í£¬ÄæÁÚ½Ó±í£¬Ê®×ÖÁ´±í£»ÁÚ½Ó¶àÖرí¡£
(3)ͼµÄ±éÀú£ºÉî¶ÈÓÅÏÈËÑË÷·¨, ¿í¶ÈÓÅÏÈËÑË÷·¨, ÇóͼµÄÁ¬Í¨·ÖÁ¿¡£
(4)Éú³ÉÊ÷¡¢×îСÉú³ÉÊ÷µÄ¸ÅÄ¿Ë³˹¿¨¶û(Kruskal)Ëã·¨,ÆÕÀïÄ·(Prim)
Ëã·¨¡£
*(5)´ÓÒ»¸ö¶¥µãµ½ÆäÓà¸÷¶¥µãµÄ×î¶Ì·¾¶,ÿ¶Ô¶¥µãÖ®¼äµÄ×î¶Ì·¾¶¡£
*(6)ÍØÆËÅÅÐòºÍ¹Ø¼ü·¾¶
9.²éÕÒ
(1)²éÕҵĸÅÄî,¹Ø¼ü×ֱȽϴÎÊý,ƽ¾ù²éÕÒ³¤¶È¡£
(2)˳Ðò±íµÄ²éÕÒ:˳Ðò²éÕÒ,ÕÛ°ë²éÕÒ,·Ö¿é²éÕÒ¡£
(3)Ê÷±íµÄ²éÕÒ:¶þ²æÅÅÐòÊ÷,ƽºâ¶þ²æÊ÷¡£
(4)¹þÏ£(Hash)±íµÄ²éÕÒ:¹þÏ£±íµÄ¸ÅÄî,¹þÏ£º¯Êý¹¹Ôì·½·¨,¹þÏ£±íµÄ½¨Á¢ºÍ²éÕÒ,³åÍ»´¦Àí·½·¨¡£
10.ÅÅÐò
(1)ÅÅÐòµÄ¸ÅÄÅÅÐòµÄÎȶ¨ÐÔ£»±È½Ï¹Ø¼ü×Ö´ÎÊý,Òƶ¯¼Ç¼´ÎÊý£»Ë³Ðò±íµÄÅÅÐò,Á´½Ó±í(µ¥Á´±í)µÄÅÅÐò¡£
(2)ÄÚÅÅÐò·½·¨ÓëËã·¨
(a)½»»»ÅÅÐò:ðÅÝÅÅÐò,¿ìËÙÅÅÐò¡£
(b)²åÈëÅÅÐò:Ö±½Ó²åÈëÅÅÐò,2·²åÈëÅÅÐò,ÕÛ°ë²åÈëÅÅÐò,Ï£¶ûÅÅÐò¡£
(c)Ñ¡ÔñÅÅÐò:Ö±½ÓÑ¡ÔñÅÅÐò,½õ±êÈüÅÅÐò,¶ÑÅÅÐò¡£
(d)¹é²¢ÅÅÐò¡£
(e)»ùÊýÅÅÐò¡£
(3)¸÷ÖÖÅÅÐòËã·¨µÄÆÀ¼ÛºÍÓ¦Óá£
11.Îļþ
(1)ÎļþµÄ»ù±¾¸ÅÄî, ÎļþµÄ»ù±¾²Ù×÷¡£
(2)ÎļþµÄÎïÀí½á¹¹£ºË³ÐòÎļþ, Ë÷ÒýÎļþÓëË÷Òý˳ÐòÎļþ, Ö±½Ó´æÈ¡Îļþ£¬
Á´½ÓÎļþºÍ¶àÖØÁ´±íÎļþ£¬µ¹ÅÅÎļþ¡£
*12.ÍâÅÅÐò
ÍâÅÅÐòµÄ»ù±¾¹ý³Ì, ³õʼ¹é²¢¶ÎµÄÉú³É,¶à·ƽºâ¹é²¢ÅÅÐò,×î¼Ñ¹é²¢Ê÷¡£
˵Ã÷:´ø¡°*¡±ºÅµÄÕ½ÚΪһ°ã¿¼²éÄÚÈÝ,ÆäÓàΪÖص㿼²éÄÚÈÝ¡£