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

}

} }

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

先序线索化二叉树

void preorder_Threading(BiThrNode *T) { BiThrNode *stack[MAX_NODE]; BiThrNode *last=NULL, *p ; int top=0 ; if (T!=NULL)

{ stack[++top]=T; while (top>0)

{ p=stack[top--] ;

if (p->Lchild!=NULL) p->Ltag=0 ;

else { p->Ltag=1 ; p->Lchild!=last ; } if (last!=NULL)

if (last->Rchild!=NULL) last->Rtag=0 ; else

{ last->Rtag=1 ; last->Rchild!=p ; } last=p ;

if (p->Rchild!=NULL)

stack[++top]=p->Rchild ; if (p->Lchild!=NULL)

stack[++top]=p->Lchild ; }

Last->Rtag=1; /* 最后一个结点是叶子结点 */ }

}

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

中序线索化二叉树

void inorder_Threading(BiThrNode *T) { BiThrNode *stack[MAX_NODE]; BiThrNode *last=NULL, *p=T ; int top=0 ;

while (p!=NULL||top>0)

if (p!=NULL) { stack[++top]=p; p=p->Lchild; } else

{ p=stack[top--] ;

if (p->Lchild!=NULL) p->Ltag=0 ;

else { p->Ltag=1 ; p->Lchild!=last ; } if (last!=NULL)

if (last->Rchild!=NULL) last->Rtag=0 ;

else { last->Rtag=1 ; last->Rchild!=p ; }

last=p ;

P=p->Rchild; }

last->Rtag=1; /* 最后一个结点是叶子结点 */ } }

===============================================================================Huffman树的生成 算法实现

void Create_Huffman(unsigned n, HTNode HT[ ], unsigned m) /* 创建一棵叶子结点数为n的Huffman树 */ { unsigned int w ; int k , j ; for (k=1 ; k

{ printf(“\\n Please Input Weight : w=?”); scanf(“%d”, &w) ;HT[k].weight=w ;

} /* 输入时，所有叶子结点都有权值 */

else HT[k].weight=0; /* 非叶子结点没有权值 */ HT[k].Parent=HT[k].Lchild=HT[k].Rchild=0 ;

} /* 初始化向量HT */ for (k=n+1; k

{ unsigned w1=32767 , w2=w1 ; /* w1 , w2分别保存权值最小的两个权值 */

int p1=0 , p2=0 ; /* p1 , p2保存两个最小权值的下标 */

for (j=1 ; j<=k-1 ; j++)

{ if (HT[k].Parent==0) /* 尚未合并 */ { if (HT[j].Weight

{ w2=w1 ; p2=p1 ;

w1=HT[j].Weight ; p1=j ; }

for ( ; fp!=0 ;p=fp , fp=HT[p].parent)

/* 从叶子结点到根逆向求编码 */ if (HT[fp].parent==p) cd[--sp]=‘0’ ; else cd[--sp]=‘1’ ;

HC[k]=(char *)malloc((n-sp)*sizeof(char)) ;

/* 为第k个字符分配保存编码的空间 */ trcpy(HC[k] , &cd[sp]) ; }

free(cd) ; }

===============================================================================void DFS(ALGraph *G , int v) { LinkNode *p ;

Visited[v]=TRUE ;

Visit[v] ; /* 置访问标志，访问顶点v */ p=G->AdjList[v].firstarc; /* 链表的第一个结点 */ while (p!=NULL)

{ if (!Visited[p->adjvex]) DFS(G, p->adjvex) ;

/* 从v的未访问过的邻接顶点出发深度优先搜索 */

p=p->nextarc ; } }

void DFS_traverse_Grapg(ALGraph *G) { int v ;

for (v=0 ; vvexnum ; v++)

Visited[v]=FALSE ; /* 访问标志初始化 */ p=G->AdjList[v].firstarc ;

for (v=0 ; vvexnum ; v++) if (!Visited[v]) DFS(G , v); }

==============================================================================typedef emnu {FALSE , TRUE} BOOLEAN ; BOOLEAN Visited[MAX_VEX] ; typedef struct Queue

{ int elem[MAX_VEX] ; int front , rear ;

}Queue ; /* 定义一个队列保存将要访问顶点 */

void BFS_traverse_Grapg(ALGraph *G) { int k ,v , w ;

LinkNode *p ; Queue *Q ;

Q=(Queue *)malloc(sizeof(Queue)) ;

Q->front=Q->rear=0 ; /* 建立空队列并初始化 */ for (k=0 ; kvexnum ; k++)

Visited[k]=FALSE ; /* 访问标志初始化 */ for (k=0 ; kvexnum ; k++)

{ v=G->AdjList[k].data ; /* 单链表的头顶点 */ if (!Visited[v]) /* v尚未访问 */

{ Q->elem[++Q->rear]=v ; /* v入对 */ while (Q->front!=Q->rear) { w=Q->elem[++Q->front] ;

Visited[w]=TRUE ; /* 置访问标志 */ Visit(w) ; /* 访问队首元素 */ p=G->AdjList[w].firstarc ; while (p!=NULL)

{ if (!Visited[p->adjvex])

Q->elem[++Q->rear]=p->adjvex ;

p=p->nextarc ; }

} /* end while */

} /* end if */ } /* end for */ }

===============================================================================求最小生成树的Prime算法 typedef struct MSTEdge

{ int vex1, vex2 ; /* 边所依附的图中两个顶点 */ WeightType weight ; /* 边的权值 */ }MSTEdge ;

算法实现

#define INFINITY MAX_VAL /* 最大值 */ MSTEdge *Prim_MST(AdjGraph *G , int u)

/* 从第u个顶点开始构造图G的最小生成树 */ { MSTEdge TE[] ; // 存放最小生成树n-1条边的数组指针 int j , k , v , min ;

for (j=0; jvexnum; j++) { closedge[j].adjvex=u ;

closedge[j].lowcost=G->adj[j][u] ; } /* 初始化数组closedge[n] */

closedge[u].lowcost=0 ; /* 初始时置U={u} */ TE=(MSTEdge *)malloc((G->vexnum-1)*sizeof(MSTEdge)) ; for (j=0; jvexnum-1; j++) { min= INFINITY ;

for (v=0; vvexnum; v++)

if (closedge[v].lowcost!=0&& closedge[v].Lowcost

TE[j].weight=closedge[k].lowcost ;

closedge[k].lowcost=0 ; /* 将顶点k并入U中 */ for (v=0; vvexnum; v++)

if (G->adj[v][k]adj[v][k] ; closedge[v].adjvex=k ;

} /* 修改数组closedge[n]的各个元素的值 */ }

return(TE) ;

} /* 求最小生成树的Prime算法 */

=============================================================================== 用Kruskal算法构造图G的最小生成树 MSTEdge *Kruskal_MST(ELGraph *G)

/* 用Kruskal算法构造图G的最小生成树 */ { MSTEdge TE[] ;

int j, k, v, s1, s2, Vset[] ; WeightType w ;

Vset=(int *)malloc(G->vexnum*sizeof(int)) ; for (j=0; jvexnum; j++)

Vset[j]=j ; /* 初始化数组Vset[n] */

sort(G->edgelist) ; /* 对表按权值从小到大排序 */ j=0 ; k=0 ;

while (kvexnum-1&&j< G->edgenum) { s1=Vset[G->edgelist[j].vex1] ; s2=Vset[G->edgelist[j].vex2] ;

/* 若边的两个顶点的连通分量编号不同, 边加入到TE中 */ if (s1!=s2)

{ TE[k].vex1=G->edgelist[j].vex1 ; TE[k].vex2=G->edgelist[j].vex2 ;

TE[k].weight=G->edgelist[j].weight ; k++ ;

for (v=0; vvexnum; v++)

if (Vset[v]==s2) Vset[v]=s1 ; } j++ ; }

free(Vset) ; return(TE) ;

} /* 求最小生成树的Kruskal算法 */

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

统计各顶点入度的函数

void count_indegree(ALGraph *G) { int k ; LinkNode *p ;

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

G->adjlist[k].indegree=0 ; /* 顶点入度初始化 */ for (k=0; kvexnum; k++) { p=G->adjlist[k].firstarc ;

while (p!=NULL) /* 顶点入度统计 */ { G->adjlist[p->adjvex].indegree++ ; p=p->nextarc ; } } }

===============================================================================拓扑排序算法

int Topologic_Sort(ALGraph *G, int topol[])

/* 顶点的拓扑序列保存在一维数组topol中 */