数据结构-关键路径和拓扑排序.doc

数据结构课程设计

《数据结构》课程设计报告

设计题目：关键路径与拓扑排序
姓名：_____ __李崇远___ _____
学号：________211415059________
专业：_____ _物联网工程___ ___
院系: 计科学院_________
班级：____ __1406___ ____
指导教师：_____ _王江涛___ _______

2016年 1月 8日
摘要
关键路径是计划项目活动中用到的一种算数方法。对于有效的计划管理而言，关键路径是一种十分重要的工具。
关键路径通常是决定项目工期的进度活动序列，很小的浮动也可 能影响整个项目。
拓扑排序常用来确定一个依赖关系集中，事物发生的顺序，可用于计算项目的进行顺序，但顺序并不唯一。
关键字：关键路径 拓扑排序

Abstract
Critical Path is an arithmetic method used in project activities.For the purposes of effective program management, critical Path is a very important tool.
Critical path schedule activities usually sequence determines the duration of the project, small float can also affect the entire project.
Topological Order used to determine a dependency set, the order of things happen, the order can be used to calculate the project, but the order is not unique.
Keywords: Critical Path, Topological Order
目 录

目录
一、问题描述（内容格式参考下面的描述，以下类似） 4
二、需求分析 4
三、概要设计 4
四、数据结构设计 5
五、算法设计 5
1、算法分析（必须要用语言进行描述） 5
2、算法实现 5
六、程序测试与实现 6
1、函数之间的调用关系 6
2、主程序 6
3、测试数据 6
4、测试结果 6
七、调试分析 6
八、遇到的问题及解决办法 7
九、心得体会 7

一、问题描述
题目内容：通过邻接表完成AOE网的创建，并输出图的拓扑序列和关键路径。
基本要求：将图存入邻接表中，通过邻接表的储存特征创建AOE网，完成图的拓扑序列，已经关键路径和路径长度。
二、需求分析
1． 本程序的功能包括单通讯录链表的建立，通讯录的插入，通讯者的删除，通讯者的查询，通讯录表的输出，通讯者人数的统计以及按通讯者编号排序等。
2． 程序运行后显现提示信息，等候用户输入0—7以进入相应的操作功能。
3． 用户输入数据完毕，程序将输出运行结束。
4． 测试数据应为通讯者的编号、姓名、性别、联系电话、地址。
三、概要设计
1． 带头结点的单链表抽象数据类型定义为：
ADT hlink_list{
数据集合K：K={k1,k2,…,kn},n≥0，K中的元素是DataType类型；
数据关系R：R={r}
r={<ki,ki+1>|i=1,2,…,n-1}。
操作集合：
(1)LinkList CreateList(void) 建立一个带头结点的通讯录单链表；
(2)void InserNode(LinkList head ,ListNode *p) 在带头结点的通讯录链表中插入结点；
(3)ListNode *ListFind(LinkList head) 在带头结点的通讯录链表中查找结点；
(4)void DelNode(LinkList head) 在带头结点的通讯录链表中删除结点；
(5)void PrintList(LinkList head) 输出带头结点的通讯录链表中各个结点的值；
(6)void Bubblesort(LinkList head) 将带头结点的通讯录链表中各个结点按通讯者编号排序。
}ADT hlink_list；

四、数据结构设计
1． 元素类型，结点类型，指针类型
typedef struct{ //通讯录结点类型
int num; //编号
char name[9]; //姓名
char sex[3]; //性别
char phone[13]; //电话
char addr[31]; //地址
}DataType;
typedef struct node{ //结点类型定义
DataType data; //结点数据域
struct node *next; //结点指针域
}ListNode;
typedef ListNode *LinkList;
LinkList head; //定义指向单链表的头指针
ListNode *p; //定义一个指向结点的指针变量
int n=0;
int person[10];
五、算法设计
1、算法分析（必须要用语言进行描述）
2、算法实现
LinkList CreateList(void) //
{ //尾插法建立带头结点的通讯录链表算法
LinkList head=new ListNode; //申请头结点
ListNode *p,*rear;
int flag=0; //结束标志置0
rear=head; //尾指针初始指向头结点
while(flag==0)
{ p=(ListNode *)malloc(sizeof(ListNode)); //申请新结点
printf("编号 姓名(8) 性别(2) 电话(11) 地址(31)\n");
printf("--------------------------------------\n");
scanf("%d%s%s%s%s",&(p->data.num),p->data.name,p->data.sex,p->data.
phone,p->data.addr);
n++;
rear->next=p; //新结点连接到尾结点之后
rear=p; //尾指针指向新结点
printf("结束建表吗？(1/0):");
scanf("%d",&flag); //读入一个标志数据
}
rear->next=NULL; //终端结点指针域置空
return head; //返回链表头指针
}
3、算法流程图
六、程序测试与实现
1、函数之间的调用关系

2、主程序
void main() //
{

}
3、测试数据
4、测试结果
七、调试分析
1．链表中的结点变量是通过指针变量来访问的。因为在C语言中是用P—>来表示P所指的变量，又由于结点类型是一个结构类型，因此可用P—> data和P—>next分别表示结点的数据域变量和指针域变量。指针变量的值要么为空(NULL)，不指向任何结点；要么其值为非空，即它的值是一个结点的存储地址。注意，当P为空值时，则它不指向任何结点，此时不能通过P 来访问结点，否则会引起程序错误。
2．算法的时空分析：
(1)对于本程序的通讯录单链表，其操作运算主要有建立单链表(尾插法)CreateList,查询(按编号和按姓名)ListFind,插入运算InsertNode,删除运算DelNode等。以上各操作运算的平均时间复杂度为O(n)，其主要时间是耗费在查找操作上。
(2)分析冒泡排序算法Bubblesort的时间和空间效率。冒泡排序的时间复杂度为O(n )。冒泡排序的过程中也只需要一个辅助空间，故空间复杂度为O(1)。
八、遇到的问题及解决办法
九、心得体会