p = g->vexs[i].edgelist; while (p) {
++inDegree[p->endvex]; p = p->nextedge; } } }
void makeNewAOV(EdgeList p, int* indegree, int* top) { int k;
while (p) { /* 删除以该顶点为起点的边 */ k = p->endvex; indegree[k]--;
if (indegree[k] == 0) { /* 将新的入度为零的边入栈 */ indegree[k] = *top; *top = k; }
p = p->nextedge; } }
int topoSort(GraphList * paov, Topo * ptopo) { EdgeList p;
int i, j, nodeno = 0, top = -1; int indegree[MAXVEX];
findInDegree(paov, indegree); /* 求出图中所有顶点的入度 */ for (i = 0; i < paov->n; i++)
if (indegree[i] == 0) { /* 将入度为零的顶点入栈 */ indegree[i] = top; top = i; }
while (top != -1) { /* 栈不为空 */ j = top;
top = indegree[top]; /* 取出当前栈顶元素 */
26
ptopo->vexs[nodeno]=paov->vexs[j].vertex; //将该元素输出到拓扑序
列中 ptopo->vexsno[nodeno++] = j;
p = paov->vexs[j].edgelist; /* 取该元素边表中的第一个边结点 */ /*删除该结点,构造新的AOV网*/ /*对indegree数组进行修改*/ makeNewAOV(p, indegree, &top); }
if (nodeno < paov->n) { /* AOV网中存在回路 */ printf(\ return FALSE; } return TRUE; }
void insert(GraphList* p,int a,int b){
*/ EdgeList pp; PEdgeNode temp;
temp = (PEdgeNode)malloc(sizeof(EdgeNode)); temp->endvex = b; temp->nextedge = NULL; pp = p->vexs[a].edgelist;
if (pp == NULL) p->vexs[a].edgelist = temp; else {
while (pp->nextedge != NULL) pp = pp->nextedge; pp->nextedge = temp; } }
/* 实例邻接表的构造 */
/* 边的插入算法
GraphList* makeList(){ GraphList* p;
27
int i;
p = (GraphList*)malloc(sizeof(GraphList)); p->n = 9;
for (i = 0; i < p->n; i++) p->vexs[i].edgelist = NULL; insert(p, 0, 2); insert(p, 0, 7); insert(p, 1, 2); insert(p, 1, 3); insert(p, 1, 4); insert(p, 2, 3); insert(p, 3, 5); insert(p, 3, 6); insert(p, 4, 5); insert(p, 7, 8); insert(p, 8, 6); return p; }
Topo topo; int main(){ GraphList* p; int i;
p = makeList();
if (topoSort(p, &topo) == TRUE) for (i = 0; i < p->n; i++)
printf(\ return 0; }
六、实验小结
通过这次实验学会了用邻接表构造图 ，然后进行拓扑排序，注意到今天调试时候出现了一个 以前没出现过的问题，就是 用* 与不用*的区别， 以前我不管有没有返回值我都用，但是没出现问题， 今天调试这个程序就是因为这个小
28
问题花费很长时间。以后一定要主要这一点，不要不管三七二十一 都用* ，有时候会造成原数据破坏，利用被破坏的值再进行运算，结果可想而知，所以 如果没返回值时一般不要用*， 不要因为图个方便一律用那样不好。
29
南昌大学实验报告
---（五）查找 排序
学生姓名： 学 号： 专业班级：
实验类型：□ 验证 □ 综合 ■ 设计 □ 创新 实验日期： 2010-6-7 实验成绩：
一、实验目的
深入了解各种内部排序方法及效率分析。
二、问题描述
各种内部排序算法的时间复杂度分析，试通过随机数据比较算法的关键字比较次数和关键字移动次数。
三、实验要求
1、对起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序这六种
常用排序算法进行比较。
2、待排序表的表长不超过100；其中数据用伪随机数产生程序产生。 1、 至少要用6组不同的输入数据做比较。 2、 要对实验结果做简单分析。
四、实验环境
PC微机
DOS操作系统或 Windows 操作系统
Turbo C 程序集成环境或 Visual C++ 程序集成环境
五、算法分析
A、直接插入排序
void InsertSort（SqList &L){ //对顺序表L作直接插入排序。
for（i=2；i<=L.length;++i)
if (LT(L.r[i].key,L.r[i-1].key)){
L.r[0]=L.r[i]; L.r[i]=L.r[i-1];
for ( j=i-2; LT(L.r[0].key,L.r[j].key);--j)
L.r[j+1]=L.r[j];
L.r[j+1]=L.r[0];
30