（权值相同的边选取无顺序） 7．8 所选顶点 初态 3 2 6 4 f h 1 1 1
已选定点的集合 {1} {1，3} {1，3，2} {1，3，2，6} {1，3，2，6，4} 尚未被选顶点的集合 DIST [2] [3] [4] [5] [6] {2，3，4，5，6} {2，4，5，6} {4，5，6} {4，5} {5} 20 15 ∞ ∞ ∞ 19 ∞ ∞ 25 ∞ 29 25 29 29 29 {1，3，2，6，4，5} {} 5 注：选定点4和5时无优先顺序，二者最短路径均为29
7．9
0 8 ∞ A0= 3 0 ∞ 5 2 0
0 8 ∞ A1= 3 0 ∞
5 2 0
0 8 ∞ A2= 3 0 ∞
5 2 ∞
0 8 ∞ A3= 3 0 ∞ 5 2 0 7．10 V1
1 2 0
path0 = 1 2 0
1 2 3
0:1->1
1:1->2
∞:1到3没有直接通路
path1同path0,加入顶点1后无变化
path2同path1
本题不好，终态和初态无变化 V3 V6 V4 V2 V6 V5 V6 V2 V3 V4 V3 V4 V6 V4 V3 V2 V6 V1 V6 V2 V5 共七种
V3 V4 V3 V4 V6 V1 V2 V3 V4 用TOPOSORT算法求得第七种，即V5,V6,V1,V2,V3,V4.
用邻接表存储结构，邻接点逆序即编号大的排在前面。入度为0顶点用栈结构存储，初始时从顶点1到顶点N扫描，入度为0的顶点进栈，得V5在栈顶。 7．11
void toposort_dfs （graph g；vtptr v）
//从顶点v开始，利用深度优先遍历对图g进行拓扑排序。
//基本思想是利用栈s存放顶点，首先出栈的顶点是出度为0的顶点，是拓扑序列中最后一个顶//点。若出栈元素个数等于顶点数，则拓扑排序成功，输出的是逆拓扑排序序列。 { visited[1..n]=0;top=0;num=0;//初始化；top为栈顶指针，num记出栈元素数 s[++top]=v;//顶点入栈
while (top!=0)
{w=firstadj(g,v);//求顶点v的第一邻接点
while (w！=0) // w!=0的含义是w存在 { if ( !visited[w]) s[++top]=w;
w=nextadj(g,v,w);//求下一个邻接点
}
if (top!=0) {v=s[top--]; num++; printf(v);}//输出顶点 }
printf(“\\n”);
if (num V6 a12=4 顶点 Ve Vl V1 0 0 V2 5 9 V3 6 6 V4 12 12 V5 15 16 V6 16 20 V7 17 17 V8 19 20 V9 22 22 V10 24 24 a4 6 6 0 a5 6 13 7 a6 12 13 1 a7 12 12 4 a8 15 16 0 a9 12 16 4 a10 15 16 1 a11 17 17 0 a12 16 20 4 a13 19 20 1 a14 22 22 0 关键路径 V1->V3->V4->V7->V9->V10 长 22 关键活动 a3,a4,a7,a11,a14 顶点 Ve Vl V1 0 0 V2 5 9 V3 6 6 V4 12 12 V5 15 16 V6 16 20 V7 17 17 V8 19 20 V9 22 22 V10 24 24 活动 e l l-e a1 0 0 0 a2 5 9 4 a3 0 0 0 a4 6 6 0 a5 6 13 7 a6 12 13 1 a7 12 12 4 a8 15 16 0 a9 12 16 4 a10 15 16 1 a11 17 17 0 a12 16 20 4 a13 19 20 1 a14 22 22 0 关键路径 V1->V3->V4->V7->V9->V10 长 22 关键活动 a3,a4,a7,a11,a14 第八章 排序（参考答案） 本章所用数据结构 #define N 待排序记录的个数 typedef struct { int key; ElemType other; }rectype; rectype r[n+1]; // r为结构体数组 8.2 稳定排序有：直接插入排序、起泡排序、归并排序、基数排序 不稳定排序有：希尔排序、直接选择排序、堆排序 希尔排序例：49，38， 49，90，70，25 直接选择排序例：2， 2，1 堆排序例：1，2，2 8.3 void StlinkedInsertSort(s , n); // 对静态链表s[1..n]进行表插入排序， 并调整结果，使表物理上排序 { #define MAXINT 机器最大整数 typedef struct { int key; int next; }rec; rec s[n+1]; // s为结构体数组 s[0].key=maxint; s[1].next=0; //头结点和第一个记录组成循环链表 i=2; //从第2个元素开始，依次插入有序链表中 while (i<=n) {q=0; p=s[0].next; // p指向当前最小元素，q是p的前驱 while (p!=0 && s[p].key s[i].next=p; s[q].next=i; // 将第个元素链入 i++； } // while(i<=n) 静态链表的插入 // 以下是重排静态链表，使之物理有序 i=1; p=s[0].next; while (i<=n) {WHILE (p { s[i]??s[p]; s[i].next=p; p=q; i++; } } }//算法结束 8.4 void TwoWayBubbleSort( rectype r[n+1]; int n) // 对r[1..n]进行双向冒泡排序。即相邻两遍向两个相反方向起泡 { int i=1, exchange=1; // 设标记 while (exchange) { exchange=0; // 假定本趟无交换 for (j=n-i+1 j>=i+1;j--) // 向前起泡，一趟有一最小冒出 if (r[j] if (r[j]>r[j+1]) {r[j]?>r[j+1]; exchange=1;} // 有交换 i++; } // end of WHILE exchange }//算法结束 8.5 （1）在n=7时，最好情况下进行10次比较。6次比较完成第一趟快速排序，将序列分成 相等程度的序列（各3个元素），再各进行2次比较，完成全部排序。 （2）最好的初始排列：4，1，3，2，6，5，7 8.6 void QuickSort(rectype r[n+1]; int n) // 对r[1..n]进行快速排序的非递归算法 { typedef struct { int low,high; }node node s[n+1]； int top; int quickpass(rectype r[],int,int); // 函数声明 top=1; s[top].low=1; s[top].high=n; while (top>0) {ss=s[top].low; tt=s[top].high; top--; if (ss { k=quickpass(r,ss,tt); if (k-ss>1) {top++; s[top].low=ss; s[top].high=k-1;} if (tt-k>1) {top++; s[top].low=k+1; s[top].high=tt;} } } // 算法结束 int quickpass(rectype r[];int s,t) {i=s; j=t; rp=r[i]; x=r[i].key; while （i {while (i while (i } // 一次划分算法结束 8.7 void QuickSort(rectype r[n+1]; int n) // 对r[1..n]进行快速排序的非递归算法 对8.6算法的改进 { typedef struct