图遍历应用_数据结构与算法_数据结构算法_c语言_c 语言之家.htm

严蔚民版的数据结构的完整课件

                      <TD>
                        <FORM action=Readnews.asp?newsid=1294&amp;id2=1294 
                        method=post name=form1>
                        <CENTER><!-- <input type=submit name=aa value="点击关闭浮动图标" width=20 title="点击广告支持本站">--></CENTER></FORM></TD></TR>
                    <TR>
                      <TD align=middle bgColor=#dddddd height=20 
                      style="FONT-SIZE: 18px" vAlign=bottom 
                        width="85%"><STRONG><FONT color=#003399 size=4><B>图遍历应用 
                        </B></FONT></STRONG></TD><BR></TR>
                    <TR>
                      <TD align=middle width="100%"><BR></TD></TR>
                    <TR>
                      <TD align=middle style="FONT-SIZE: 9pt" 
                        width="100%">发表日期：2003年6月9日&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;已经有3131位读者读过此文</TD></TR>
                    <TR>
                      <TD align=middle width="100%"><!--下面的这一句是设置阅读文本区的宽度-->
                        <TABLE align=center border=0 cellPadding=0 cellSpacing=0 
                        style="TABLE-LAYOUT: fixed" width="90%">
                          <TBODY>
                          <TR>
                            <TD align=middle width="100%"></TD></TR>
                          <TR>
                            <TD style="WORD-WRAP: break-word"><FONT 
                              class=news><BR>
                              <P>/* ======================================== 
                              */<BR>/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              图形的遍历&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>/* ======================================== 
                              */<BR>#include &lt;stdlib.h&gt;<BR>#define 
                              MAXQUEUE 
                              70&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              /* 伫列的最大容量&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              */</P>
                              <P>struct 
                              node&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              /* 图形顶点结构宣告&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>{<BR>&nbsp;&nbsp; int 
                              vertex;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              /* 
                              顶点资料&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>&nbsp;&nbsp; struct node 
                              *nextnode;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              /* 指下一顶点的指标&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>};<BR>typedef struct node 
                              *graph;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* 
                              图形的结构新型态&nbsp;&nbsp;&nbsp;&nbsp; */<BR>struct node 
                              head[61];&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              /* 图形顶点结构数组&nbsp;&nbsp;&nbsp;&nbsp; */<BR>int 
                              visited[61];&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              /* 
                              遍历记录数组&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              */</P>
                              <P>int 
                              queue[MAXQUEUE];&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              /* 伫列的数组宣告&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>int front = 
                              -1;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              /* 
                              伫列的前端&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>int rear = 
                              -1;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              /* 
                              伫列的后端&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              */</P>
                              <P>/* ---------------------------------------- 
                              */<BR>/*&nbsp; 
                              建立图形&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>/* ---------------------------------------- 
                              */<BR>void creategraph(int *node,int 
                              num)<BR>{<BR>&nbsp;&nbsp; graph 
                              newnode;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              /* 
                              新顶点指标&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>&nbsp;&nbsp; graph ptr;<BR>&nbsp;&nbsp; int 
                              from;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              /* 
                              边线的起点&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>&nbsp;&nbsp; int 
                              to;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              /* 
                              边线的终点&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>&nbsp;&nbsp; int i;</P>
                              <P>&nbsp;&nbsp; for ( i = 0; i &lt; num; i++ 
                              )&nbsp;&nbsp;&nbsp; /* 
                              读取边线的回路&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>&nbsp;&nbsp; 
                              {<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; from = 
                              node[i*2];&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              /* 
                              边线的起点&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; to = 
                              node[i*2+1];&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              /* 
                              边线的终点&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* 建立新顶点记忆体 
                              */<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; newnode = ( 
                              graph ) malloc(sizeof(struct 
                              node));<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              newnode-&gt;vertex = 
                              to;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* 
                              建立顶点内容&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              newnode-&gt;nextnode = NULL;&nbsp;&nbsp; /* 
                              设定指标初值&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ptr = 
                              &amp;(head[from]);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              /* 
                              顶点位置&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; while ( 
                              ptr-&gt;nextnode != NULL ) /* 
                              遍历至链表尾&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              ptr = 
                              ptr-&gt;nextnode;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              /* 下一个顶点&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              ptr-&gt;nextnode = 
                              newnode;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              /* 
                              插入结尾&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>&nbsp;&nbsp; }<BR>}</P>
                              <P>/* ---------------------------------------- 
                              */<BR>/*&nbsp; 
                              伫列资料的存入&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>/* ---------------------------------------- 
                              */<BR>int enqueue(int value)<BR>{<BR>&nbsp;&nbsp; 
                              if ( rear &gt;= MAXQUEUE 
                              )&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* 
                              检查伫列是否全满&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return 
                              -1;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              /* 
                              无法存入&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>&nbsp;&nbsp; 
                              rear++;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              /* 后端指标往前移&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>&nbsp;&nbsp; queue[rear] = 
                              value;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              /* 
                              存入伫列&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>}</P>
                              <P>/* ---------------------------------------- 
                              */<BR>/*&nbsp; 
                              伫列资料的取出&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>/* ---------------------------------------- 
                              */<BR>int dequeue()<BR>{<BR>&nbsp;&nbsp; if ( 
                              front&nbsp; == rear 
                              )&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              /* 检查伫列是否是空&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return 
                              -1;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              /* 
                              无法取出&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>&nbsp;&nbsp; 
                              front++;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              /* 前端指标往前移&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>&nbsp;&nbsp; return 
                              queue[front];&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              /* 
                              伫列取出&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>}</P>
                              <P>/* ---------------------------------------- 
                              */<BR>/*&nbsp; 
                              图形的广度优先搜寻法&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>/* ---------------------------------------- 
                              */<BR>void bfs(int current)<BR>{<BR>&nbsp;&nbsp; 
                              graph ptr;</P>
                              <P>&nbsp;&nbsp; /* 处理第一个顶点 */<BR>&nbsp;&nbsp; 
                              enqueue(current);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              /* 将顶点存入伫列&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>&nbsp;&nbsp; visited[current] = 
                              1;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              /* 
                              记录已遍历过&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>&nbsp;&nbsp; 
                              printf("[%d]&nbsp;&nbsp;&nbsp;&nbsp; 
                              ",current);&nbsp;&nbsp; /* 
                              印出遍历顶点值&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>&nbsp;&nbsp; while ( front != rear 
                              )&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* 
                              伫列是否是空的&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>&nbsp;&nbsp; 
                              {<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; current = 
                              dequeue();&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              /* 将顶点从伫列取出&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ptr = 
                              head[current].nextnode;&nbsp;&nbsp; /* 
                              顶点位置&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; while ( ptr 
                              != NULL 
                              )&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              /* 遍历至链表尾&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              {<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              if ( visited[ptr-&gt;vertex] == 0 ) /* 如过没遍历过 
                              */<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              {<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              enqueue(ptr-&gt;vertex);&nbsp;&nbsp;&nbsp;&nbsp; 
                              /* 递回遍历呼叫&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              visited[ptr-&gt;vertex] = 1; /* 
                              记录已遍历过&nbsp;&nbsp;&nbsp;&nbsp; 
                              */<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              /* 印出遍历顶点值 */<BR>&nbsp;&nbsp;&nbsp;&nbsp;