考研真题数据结构

【2023年山西大学考研真题】

（1）这个问题可以使用Dijkstra算法来求解，它可以找到从起点到其他所有顶点的最短路径。
算法的基本思想是从源点开始，逐步扩展周围的顶点，通过比较选择最短路径来更新当前顶点到其他顶点的距离。具体步骤如下：

1.?初始化一个数组dist，用于存储源点到各个顶点的最短距离。
2.?将源点的最短距离初始化为0，其他顶点的最短距离初始化为无穷大。
3.?创建一个优先队列（优先级队列），将源点加入队列，并将源点的最短距离设为0。
4.?循环直到队列为空：
???a.?从队列中取出当前最短距离的顶点u。
???b.?遍历顶点u的所有邻接顶点v：
????????-?如果通过顶点u到达顶点v的路径长度更短，更新顶点v的最短距离为新的路径长度。
????????-?将顶点v加入队列。
5.?当队列为空时，dist数组中存储的就是源点到所有顶点的最短距离。

（2）以下是用C语言描述的算法：
typedef?struct?{
????int?vertex;
????int?weight;
}?Edge;

//?邻接链表节点
typedef?struct?Node?{
????int?vertex;
????int?weight;
????struct?Node*?next;
}?Node;

//?优先队列（最小堆）的节点
typedef?struct?MinHeapNode?{
????int?vertex;
????int?distance;
}?MinHeapNode;

//?图的结构
typedef?struct?{
????Node*?list[MAX_VERTICES];
????int?numVertices;
}?Graph;

//?交换两个最小堆节点
void?swapNodes(MinHeapNode**?a,?MinHeapNode**?b)?{
????MinHeapNode*?t?=?*a;
????*a?=?*b;
????*b?=?t;
}

//?最小堆化操作
void?minHeapify(MinHeapNode*?heapArray[],?int?size,?int?index)?{
????int?smallest?=?index;
????int?left?=?2?*?index;
????int?right?=?2?*?index?+?1;

????if?(left?<=?size?&&?heapArray[left]->distance?<?heapArray[smallest]->distance)
????????smallest?=?left;
????if?(right?<=?size?&&?heapArray[right]->distance?<?heapArray[smallest]->distance)
????????smallest?=?right;

????if?(smallest?!=?index)?{
????????swapNodes(&heapArray[index],?&heapArray[smallest]);
????????minHeapify(heapArray,?size,?smallest);
????}
}

//?检查最小堆是否为空
bool?isEmpty(int?heapSize)?{
????return?heapSize?==?0;
}

//?从最小堆中取出距离最小的节点
MinHeapNode*?extractMin(MinHeapNode*?heapArray[],?int*?heapSize)?{
????if?(isEmpty(*heapSize))
????????return?NULL;

????MinHeapNode*?min?=?heapArray[1];
????heapArray[1]?=?heapArray[*heapSize];
????(*heapSize)--;
????minHeapify(heapArray,?*heapSize,?1);

????return?min;
}

//?更新最小堆中的节点值
void?decreaseKey(MinHeapNode*?heapArray[],?int?vertex,?int?distance,?int*?heapPosition)?{
????int?i?=?heapPosition[vertex];
????heapArray[i]->distance?=?distance;

????while?(i?>?1?&&?heapArray[i]->distance?<?heapArray[i?/?2]->distance)?{
????????swapNodes(&heapArray[i],?&heapArray[i?/?2]);
????????i?/=?2;
????}
}

//?Dijkstra算法求最短路径
void?dijkstra(Graph*?graph,?int?numVertices)?{
????int?parent[MAX_VERTICES];?//?保存最短路径
????int?distance[MAX_VERTICES];?//?保存每个顶点到源点的距离
????int?heapSize?=?0;?//?优先队列的大小

????//?优先队列（最小堆）
????MinHeapNode*?heapArray[MAX_VERTICES];
????int?heapPosition[MAX_VERTICES];

????//?初始化
????for?(int?v?=?1;?v?<=?numVertices;?v++)?{
????????parent[v]?=?-1;
????????distance[v]?=?INT_MAX;
????????heapArray[v]?=?NULL;
????????heapPosition[v]?=?0;
????}
????printResult(distance,?numVertices,?parent);
}

（3）这个算法的时间复杂度是O((n+m)logn)，其中n是顶点数，m是边数。此算法需要遍历所有顶点和边，并且使用优先队列来选择当前最短距离的顶点，所以主要时间消耗在队列的操作上。

????????????????