[SOLVED] 代写 data structure graph Êý¾Ý½á¹¹ÓëËã·¨

Êý¾Ý½á¹¹ÓëËã·¨
ʵÑéÖ¸µ¼Êé
ÖйúʯÓÍ´óѧ(±±¾©)¼ÆËã»ú¿ÆѧÓë¼¼Êõϵ

Ç°ÑÔ
¡¶Êý¾Ý½á¹¹¡·ÊǼÆËã»ú¼°Ïà¹ØרҵµÄÒ»ÃźËÐÄ»ù´¡¿Î³Ì£¬Ò²ÊǺܶà¸ßУ¿¼ÑÐרҵ¿ÎÖ®Ò»¡£ ËüÖ÷Òª½éÉÜÏßÐԽṹ¡¢Ê÷½á¹¹¡¢Í¼½á¹¹ÈýÖÖÂß¼­½á¹¹ÔªËصĴ洢ʵÏÖ£¬ÔÚ´Ë»ù´¡ÉϽéÉÜһЩ µäÐÍËã·¨¼°Ê±¡¢¿ÕЧÂÊ·ÖÎö¡£ÕâÃſγ̵ÄÖ÷ÒªÈÎÎñÊÇÅàÑøѧÉúµÄËã·¨Éè¼ÆÄÜÁ¦¼°Á¼ºÃµÄ³ÌÐò Éè¼ÆÏ°¹ß¡£Í¨¹ýѧϰ£¬ÒªÇóѧÉúÄܹ»ÕÆÎÕµäÐÍËã·¨µÄÉè¼Æ˼Ïë¼°³ÌÐòʵÏÖ£¬Äܹ»¸ù¾Ýʵ¼ÊÎÊ ÌâÑ¡È¡ºÏÊʵĴ洢·½°¸£¬Éè¼Æ³ö¼ò½à¡¢¸ßЧ¡¢ÊµÓõÄËã·¨£¬ÎªºóÐø¿Î³ÌµÄѧϰ¼°Èí¼þ¿ª·¢´ò ÏÂÁ¼ºÃµÄ»ù´¡¡£Ñ§Ï°ÕâÃſγ̣¬Ï°ÌâºÍʵÑéÊÇÁ½¸ö¹Ø¼ü»·½Ú¡£Ñ§ÉúÀí½âËã·¨£¬ÉÏ»úʵÑéÊÇ×î ¼ÑµÄ;¾¶Ö®Ò»¡£Òò´Ë£¬ÊµÑé»·½ÚµÄºÃ»µÊÇѧÉúÄÜ·ñѧºÃ¡¶Êý¾Ý½á¹¹¡·µÄ¹Ø¼ü¡£ÎªÁ˸üºÃµØÅä ºÏѧÉúʵÑ飬ÌرàдʵÑéÖ¸µ¼Êé¡£
Ò»¡¢ÊµÑéÄ¿µÄ
¸üºÃµÄÀí½âËã·¨µÄ˼Ïë¡¢ÅàÑø±à³ÌÄÜÁ¦¡£
¶þ¡¢ÊµÑéÒªÇó 1¡¢Ã¿´ÎʵÑéǰѧÉú±ØÐë¸ù¾ÝÊÔÑéÄÚÈÝÈÏÕæ×¼±¸ÊµÑé³ÌÐò¼°µ÷ÊÔʱËùÐèµÄÊäÈëÊý¾Ý¡£ 2¡¢ÔÚÖ¸µ¼½ÌʦµÄ°ïÖúÏÂÄܹ»Íê³ÉʵÑéÄÚÈÝ£¬µÃ³öÕýÈ·µÄʵÑé½á¹û¡£ 3¡¢ÊµÑé½áÊøºó×ܽáʵÑéÄÚÈÝ¡¢ÊéдʵÑ鱨¸æ¡£ 4¡¢×ñÊØʵÑéÊÒ¹æÕÂÖƶȡ¢²»È±Ï¯¡¢°´Ê±ÉÏ¡¢Ï»ú¡£ 5¡¢ÊµÑéѧʱÄÚ±ØÐë×öÊý¾Ý½á¹¹µÄÓйØÄÚÈÝ£¬²»ÔÊÐíÉÏÍøÁÄÌì»òÍæÓÎÏ·£¬Èç·¢ÏÖÉÏÊöÏÖ
Ïó£¬È¡Ïû±¾´ÎÉÏ»ú×ʸñ£¬Æ½Ê±³É¼¨¿Û 10 ·Ö¡£ 6¡¢ÊµÑ鱨¸æÓÐÒ»´Î²»ºÏ¸ñ£¬¿Û 5 ·Ö£¬Á½´ÎÒÔÉϲ»ºÏ¸ñÕߣ¬Æ½Ê±³É¼¨ÒÔÁã·Ö¼Ç¡£
Èý¡¢ÊµÑé»·¾³ VC++6.0 »òÕß VC2010 ËÄ¡¢ËµÃ÷
1¡¢±¾ÊµÑéµÄËùÓÐËã·¨ÖÐÔªËØÀàÐÍ¿ÉÒÔ¸ù¾Ýʵ¼ÊÐèҪѡÔñ¡£
2¡¢ÊµÑéÌâÄ¿Öдø*ÕßΪ½Ï¸ßÒªÇó£¬Ñ§Éú¿É×ÔÑ¡;ÆäÓಿ·ÖΪ»ù±¾ÄÚÈÝ£¬Ó¦¾¡Á¿Íê³É(ÖÁ ÉÙÍê³É 70%£¬·ñÔòʵÑé²»ºÏ¸ñ)¡£
3¡¢Êý¾Ý½á¹¹ÊǺܶà¸ßУµÄ˶ʿÑо¿ÉúÈëѧ¿¼ÊÔµÄרҵ¿ÎÖ®Ò»£¬Ï£ÍûÓÐÖ¾ÓÚ¿¼ÑеÄѧÉú Äܹ»ÔÚѧϰ¹ý³ÌÖÐ×¢Òâ¸÷ÖÖËã·¨µÄÀí½â£¬ÒÔ±ãΪ¿¼ÑÐ×öÒ»¶¨µÄ×¼±¸¡£ Î塢ʵÑ鱨¸æµÄÊéдҪÇó
1.Ã÷ȷʵÑéµÄÄ¿µÄ¼°ÒªÇó; 2.¼Ç¼ʵÑéµÄÊäÈëÊý¾ÝºÍÊä³ö½á¹û; 3.˵Ã÷ʵÑéÖгöÏÖµÄÎÊÌâºÍ½â¾ö¹ý³Ì; 4.д³öʵÑéµÄÌå»áºÍʵÑé¹ý³ÌÖÐûÄܽâ¾öµÄÎÊÌâ;
Áù¡¢²Î¿¼ÊéÄ¿
¡¶Êý¾Ý½á¹¹¡·(C++ÓïÑÔÃèÊö) Íõºì÷µÈ Ç廪´óѧ³ö°æÉç ¡¶DATA STRUCTURE WITH C++¡· William Ford,William Topp
Ç廪´óѧ³ö°æÉç(Ó°Ó¡°æ)

ʵÑéÀàÐÍ:ÑéÖ¤ÐÔ ÊµÑéÒªÇó:±ØÐÞ ÊµÑéѧʱ: 2 ѧʱ
//¶¨Ò嶥µã±í½áµã ArcNode *firstedge;
T vertex;
ʵÑéÎå ͼµÄÓйزÙ×÷
Ò»¡¢ÊµÑéÄ¿µÄ: ²ÎÕÕ¸ø¶¨µÄͼÀàµÄ³ÌÐòÑùÀý£¬ÑéÖ¤¸ø³öµÄÓйØͼµÄ³£¼ûËã·¨£¬²¢ÊµÏÖÓйصIJÙ×÷¡£
¶þ¡¢ÊµÑéÒªÇó:
1¡¢ÕÆÎÕͼµÄÌص㣬ÀûÓÃͼµÄÁÚ½Ó¾ØÕóºÍÁÚ½Ó±íµÄ´æ´¢½á¹¹ÊµÏÖͼµÄ³£¼ûËã·¨¡£
2¡¢ÌύʵÑ鱨¸æ£¬±¨¸æÄÚÈÝ°üÀ¨:Ä¿µÄ¡¢ÒªÇó¡¢Ëã·¨ÃèÊö¡¢³ÌÐò½á¹¹¡¢Ö÷Òª±äÁ¿ËµÃ÷¡¢ ³ÌÐòÇåµ¥¡¢µ÷ÊÔÇé¿ö¡¢Éè¼Æ¼¼ÇÉ¡¢ÐĵÃÌå»á¡£
Èý¡¢ÊµÑéÄÚÈÝ:
1. Éè¼ÆÁÚ½Ó¾ØÕóͼÀ࣬ʵÏÖÈçϲÙ×÷: (1)²âÊÔÀàÖеijÉÔ±º¯Êý; (2)ʵÏÖÍØÆËÅÅÐòËã·¨; (3)ʵÏÖ×îСÉú³ÉÊ÷Ëã·¨; (4)ʵÏÖ×î¶Ì·¾¶Ëã·¨; (5)Éè¼ÆÖ÷º¯Êý£¬ÊäÈëÊý¾Ý£¬²âÊÔ¸÷Ëã·¨¡£
2. Éè¼ÆÁÚ½Ó±íÀ࣬ʵÏÖÎÞÏòͼµÄÉî¶ÈÓÅÏȷǵݹé±éÀú¡¢ÎÞÏòͼµÄ¹ã¶ÈÓÅÏȱéÀú£¬²¢ Éè¼ÆÖ÷º¯ÊýÊäÈëÊý¾Ý½øÐвâÊÔ¡£
*3.¼ÙÉèͼ G ²ÉÓÃÁÚ½Ó±í´æ´¢£¬Éè¼ÆÒ»¸öËã·¨£¬Êä³öͼ G ÖдӶ¥µã u µ½¶¥µã v µÄ³¤¶ÈΪ
l µÄËùÓмòµ¥Â·¾¶¡£
ËÄ¡¢³ÌÐòÑùÀý:
1.ͼµÄÁÚ½Ó±íÀàµÄ¶¨Òå
struct ArcNode //¶¨Òå±ß±í½áµã {
int adjvex; //ÁÚ½ÓµãÓò
ArcNode *next; };
template struct VertexNode {
};
const int MaxSize=10; template class ALGraph
{
//ͼµÄ×î´ó¶¥µãÊý
public:
ALGraph(T a[ ], int n, int e); //¹¹Ô캯Êý£¬³õʼ»¯Ò»¸öÓÐ n ¸ö¶¥µã e Ìõ±ßµÄͼ ~ALGraph; //Îö¹¹º¯Êý£¬ÊÍ·ÅÁÚ½Ó±íÖи÷±ß±í½áµãµÄ´æ´¢¿Õ¼ä
T GetVex(int i); //ȡͼÖÐµÚ i ¸ö¶¥µãÊý¾ÝÐÅÏ¢
void PutVex(int i, T value); //½«Í¼ÖÐµÚ i ¸ö¶¥µãµÄÊý¾ÝÓòÖÃΪ value
void InsertVex(int i, T value); //ÔÚͼÖвåÈëÒ»¸ö¶¥µã£¬Æä±àºÅΪ i£¬ÖµÎª value

void DeleteVex(int i); void InsertArc(int i, int j); void DeleteArc(int i, int j); void DFSTraverse(int v); void BFSTraverse(int v);
private:
VertexNode adjlist[MaxSize]; int vertexNum, arcNum;
};
//ɾ³ýͼÖÐµÚ i ¸ö¶¥µã //ÔÚͼÖвåÈëÒ»Ìõ±ß£¬ÆäÒÀ¸½µÄÁ½¸ö¶¥µãµÄ±àºÅΪ i ºÍ j //ÔÚͼÖÐɾ³ýÒ»Ìõ±ß£¬ÆäÒÀ¸½µÄÁ½¸ö¶¥µãµÄ±àºÅΪ i ºÍ j
//Éî¶ÈÓÅÏȱéÀúͼ //¹ã¶ÈÓÅÏȱéÀúͼ
//´æ·Å¶¥µã±íµÄÊý×é //ͼµÄ¶¥µãÊýºÍ±ßÊý
template ALGraph::ALGraph(T a[ ], int n, int e)
{
vertexNum=n; arcNum=e; for (i=0; i >i>>j; //ÊäÈë±ßËùÒÀ¸½µÄÁ½¸ö¶¥µãµÄÐòºÅ
s=new ArcNode; s->adjvex=j; s->next=adjlist[i].firstedge; adjlist[i].firstedge=s;
} }
template
void ALGraph::DFSTraverse(int v) {
//Éú³ÉÒ»¸ö±ß±í½áµã s
//½«½áµã s ²åÈëµ½½áµã i µÄ±ß±íµÄ±íÍ·
cout< adjvex;
if (visited[j]==0) DFSTraverse(j); p=p->next;
} }
template
void ALGraph::BFSTraverse(int v) {
front=rear=-1; //³õʼ»¯¶ÓÁÐ, ¼ÙÉè¶ÓÁвÉÓÃ˳Ðò´æ´¢ÇÒ²»»á·¢ÉúÒç³ö
cout< adjvex;
visited[v]=1; Q[++rear]=v;
//±ß±íÖеŤ×÷Ö¸Õë p ³õʼ»¯
//±»·ÃÎʶ¥µãÈë¶Ó

if (visited[j]==0) {
cout< next; }
} }
2.ͼµÄÁÚ½Ó¾ØÕóÀàµÄ¶¨Òå
const int MaxSize=10; template class MGraph
{
public:
MGraph(T a[ ], int n, int e );
~MGraph( ) { } //Îö¹¹º¯Êý
T GetVex(int i); //ȡͼÖÐµÚ i ¸ö¶¥µãÊý¾ÝÐÅÏ¢
void PutVex(int i, T value); void InsertVex(int i, T value); void DeleteVex(int i);
void InsertArc(int i, int j); void DeleteArc(int i, int j); void DFSTraverse(int v); void BFSTraverse(int v);
private:
T vertex[MaxSize];
int arc[MaxSize][MaxSize]; int vertexNum, arcNum;
};
template
//½«Í¼ÖÐµÚ i ¸ö¶¥µãµÄÊý¾ÝÓòÖÃΪ value //ÔÚͼÖвåÈëÒ»¸ö¶¥µã£¬Æä±àºÅΪ i£¬ÖµÎª value
//ɾ³ýͼÖÐµÚ i ¸ö¶¥µã //ÔÚͼÖвåÈëÒ»Ìõ±ß£¬ÆäÒÀ¸½µÄÁ½¸ö¶¥µãµÄ±àºÅΪ i ºÍ j
//ÔÚͼÖÐɾ³ýÒ»Ìõ±ß£¬ÆäÒÀ¸½µÄÁ½¸ö¶¥µãµÄ±àºÅΪ i ºÍ j //Éî¶ÈÓÅÏȱéÀúͼ
//¹ã¶ÈÓÅÏȱéÀúͼ
//´æ·ÅͼÖж¥µãµÄÊý×é //´æ·ÅͼÖбߵÄÊý×é //ͼµÄ¶¥µãÊýºÍ±ßÊý
MGraph::MGraph(T a[ ], int n, int e) {
vertexNum=n; arcNum=e; for (i=0; i >i>>j; arc[i][j]=1; arc[j][i]=1;
//±ßÒÀ¸½µÄÁ½¸ö¶¥µãµÄÐòºÅ //ÖÃÓб߱êÖ¾
top= -1; count=0;
for (i=0; i adjvex;
adjlist[k].in–;
if (adjlist[k].in==0) p=p->next;
} }
//½«Èë¶È¼õ 1£¬Èç¹ûΪ 0£¬Ôò½«¸Ã¶¥µãÈëÕ» S[++top]=k;
if (count