计算机考研专业课复习科目包括数据结构、操作系统、计算机组成原理、计算机网络四门课程。其中数据结构这一科目兼具理论与实践，要求同学们在复习过程中不仅要对教材的基本概念进行记忆，同时还要结合知识点掌握相应的实际操作知识。为帮助同学们在计算机专业课复习上卓有成效，中公考研将为同学们整理全面的考点梳理，今天为大家带来的是数据结构的相关内容，请同学们适当参考，结合自身实际在全面复习的基础上进行重点理解记忆。
Status ToplogicalSort(ALGraph G)
{
FindIndegree(G,indegree);//求各点的入度放在Indegree[vnum];
InitStack(S);
for(i=0;i
if(Indegree[i]= =0)
push(S,i);
count=0;
while(!StackEmpty(S))
{ Pop(S,i); printf(i,G.vex[i].data); ++count;
for(p=G..vex[i].firstarc; p; p=p->nextarc)
{ k=p->adjvex;
Indegree[k]--;
if( Indegree[k]= =0) push(S,k);
}//for
}//while
if(count
return ERROR;
else
return OK
}
算法分析：求各顶点的入度的时间复杂度为O(e)，入度为零的点入栈O(n)，在循环中，每个顶点进一次栈，出栈一次，入度减1操作在while共执行了e次，所以总的时间复杂度为O(n+e).
当图中无环时，也可以利用深度优先遍历进行拓扑排序，因为图中无环，所以最先退出DFS函数的顶点即出度为零的点，是拓扑排序中最后一个顶点。由此，按DFS函数的先后记录下来的顶点序列即为逆向的拓扑有序序列。
Dijkstra算法
首先引进一个辅助向量, Dist[i]表示当前找到的从源点到vi的最短路径长度。
final[v]为true，即已经求得从v0到v的最短路径。p[v][w]为true，则w是从v0到v当前求得最短路径上的顶点。该算法弧上的权出现__负数__情况时，不能正确产生最短路径
void ShortestPath_DIJ( MGraph G, int v0, PathMatrix&p,ShortPathTable& Dist )
{ // 用 Dijkstra 算法求有向网G从源点 u 到其余顶点的最短路径
for (v=0; v
{
final[v] = FALSE; dist[v] = G.arcs[v0][v];
for(w=0;w
if(dist[v]
}
dist[v0] = 0; final[v0] = TRUE; // 初始化，顶点 v0 属于S集
for (i=1; i
{
min = INFINITY
for(w=0;w
if(!final[w]) //w在V-S中
if(D[w]
{v=w;min=D[w];}//w顶点离vo更近
final[v]=true; //离vo最近的v加入S集
for(w=0;w
if(!final[w]&&(min+G.arc[v][w]
{ D[w]=min+G.arc[v][w];
p[w]=p[v];p[w][w]=true;//p[w]=p[v]+[w];
}//if
}//for
} // ShortestPath_DIJ
Floyed算法:
void Floyd (mgraph G, int n) ∥求网G中任意两点间最短路径的Floyd算法∥
{ int i,j,k; int D[ ][n],path[ ][n];
∥最短路径长度及最短路径标志矩阵，
即path[i][j]存放路径(vi…vj)上vi之后继顶点的序号∥
for (i=0;i
for (j=0;j
{ if (G.A[i][j]
path[i][j]=j; ∥若∈R,vi当前后继为vj∥
else
path[i][j]=-1; //否则为-1//
D[i][j]=G.A[i][j];
}
for (k=0;k
for (i=0;i
for (j=0;j
if (D[i][j]>D[i][k]+D[k][j])
{ D[i][j]=D[i][k]+D[k][j]; ∥取小者∥
Path[i][j]=path[i][k]; ∥改vi的后继∥
}
for (i=0;i
for (j=0;j
{ printf (“\n %d”, D[i][j]); ∥输出vi到vj的最短路径长度∥
k=path[i][j]; ∥取路径上vi的后继vk∥
if (k==-1)
printf (“%d to %d no path \n”,i,j); ∥vi到vj路径不存在∥
else
{ printf (“(%d”,i); ∥输出vi的序号i∥
while (k!=j) ∥k不等于路径终点j时∥
{ printf (“,%d”,k); ∥输出k∥
k=path[k][j]; ∥求路径上下一顶点序号∥
}
printf (“%d) \n”,j); ∥输出路径终点序号∥
}
}
}
