清华大学严蔚敏版数据结构考研要点（精华版）(6)

{ int k, no, vex_no, top=0, count=0, boolean=1 ; int stack[MAX_VEX] ; /* 用作堆栈 */ LinkNode *p ;

count_indegree(G) ; /* 统计各顶点的入度 */ for (k=0; kvexnum; k++) if (G->adjlist[k].indegree==0) stack[++top]=G->adjlist[k].data ; do

{ if (top==0) boolean=0 ; else

{ no=stack[top--] ; /* 栈顶元素出栈 */ topl[++count]=no ; /* 记录顶点序列 */ p=G->adjlist[no].firstarc ;

while (p!=NULL) /*删除以顶点为尾的弧*/ { vex_no=p->adjvex ;

G->adjlist[vex_no].indegree-- ;

if (G->adjlist[vex_no].indegree==0) stack[++top]=vex_no ; p=p->nextarc ; } }

}while(boolean==0) ;

if (countvexnum) return(-1) ; else return(1) ; }

=============================================================================== 从图G中的顶点v出发到其余各顶点的最短路径Dijkstra BOOLEAN final[MAX_VEX] ;

int pre[MAX_VEX] , dist[MAX_VEX] ; void Dijkstra_path (AdjGraph *G, int v)

/* 从图G中的顶点v出发到其余各顶点的最短路径 */ { int j, k, m, min ;

for ( j=0; jvexnum; j++) {pre[j]=v ; final[j]=FALSE ; dist[j]=G->adj[v][j] ; } /* 各数组的初始化 */

dist[v]=0 ; final[v]=TRUE ; /* 设置S={v} */ for ( j=0; jvexnum-1; j++) /* 其余n-1个顶点 */ { m=0 ;

while (final[m]) m++; /* 找不在S中的顶点vk */ min=INFINITY ;

for ( k=0; kvexnum; k++)

{ if (!final[k]&&dist[m]

} /* 求出当前最小的dist[k]值 */

final[m]=TRUE ; /* 将第k个顶点并入S中 */ for ( j=0; jvexnum; j++)

{ if (!final[j]&&(dist[m]+G->adj[m][j]adj[m][j] ; pre[j]=m ; }

} /* 修改dist和pre数组的值 */ } /* 找到最短路径 */ }

===============================================================================int A[MAX_VEX][MAX_VEX] ; int Path[MAX_VEX][MAX_VEX] ; void Floyd_path (AdjGraph *G) { int j, k, m ;

for ( j=0; jvexnum; j++) for ( k=0; kvexnum; k++)

{ A[j][k]=G->adj[j][k] ; Path[j][k]=-1 ; } /* 各数组的初始化 */ for ( m=0; mvexnum; m++)

for ( j=0; jvexnum; j++) for ( k=0; kvexnum; k++)

if ((A[j][m]+A[m][k])

} /* 修改数组A和Path的元素值 */

for ( j=0; jvexnum; j++) for ( k=0; kvexnum; k++) if (j!=k)

{ printf(“%d到%d的最短路径为:\\n”, j, k) ; printf(“%d ”,j) ; prn_pass(j, k) ; printf(“%d ”, k) ;

printf(“最短路径长度为: %d\\n”,A[j][k]) ; }

} /* end of Floyd */ void prn_pass(int j , int k) { if (Path[j][k]!=-1)

{ prn_pass(j, Path[j][k]) ; printf(“, %d” , Path[j][k]) ; prn_pass(Path[j][k], k) ; } }

===============================================================================

折半查找 当n很大 (n>50)时， ASL≈ ㏒2(n+1)-1。

查找思想

用Low、High和Mid表示待查找区间的下界、上界和中间位置指针，初值为Low=1，High=n。

⑴ 取中间位置Mid：Mid=?(Low+High)/2? ； ⑵ 比较中间位置记录的关键字与给定的K值： ① 相等： 查找成功；

② 大于：待查记录在区间的前半段，修改上界指针： High=Mid-1，转⑴ ； ③ 小于：待查记录在区间的后半段，修改下界指针：Low=Mid+1，转⑴ ； 直到越界(Low>High)，查找失败。

int Bin_Search(SSTable ST , KeyType key)

{ int Low=1，High=ST.length, Mid ; while (Low

{ Mid=(Low+High)/2 ;

if (EQ(ST. elem[Mid].key, key)) return(Mid) ;

else if (LT(ST. elem[Mid].key, key)) Low=Mid+1 ; else High=Mid-1 ; }

return(0) ; /* 查找失败 */ }

============================================================================== 递归算法

BSTNode *BST_Serach(BSTNode *T , KeyType key) { if (T==NULL) return(NULL) ; else

{ if (EQ(T->key, key) ) return(T) ; else if ( LT(key, T->key) )

return(BST_Serach(T->Lchild, key)) ; else return(BST_Serach(T->Rchild, key)) ; } }

⑵ 非递归算法

BSTNode *BST_Serach(BSTNode *T , KeyType key) { BSTNode p=T ;

while (p!=NULL&& !EQ(p->key, key) ) { if ( LT(key, p->key) ) p=p->Lchild ; else p=p->Rchild ; }

if (EQ(p->key, key) ) return(p) ; else return(NULL) ; }

===============================================================================