首页 考试资料幻灯片工程技术公务员考试小学教学中学教学大学教学外语资料
数据结构实验书


二、AOV 网:用顶点表示活动,弧表示活动间的优先关系的有向图称为顶点表示活动的网(简称 AOV 网)。 研究 AOV 网的目的有:(1)判定工程的可行性;(2)确定各项活动在整个工程执行中的先后顺序。使 用的方法是对有向图进行拓扑排序。

【数据描述】 有向图 G 采用邻接表存储结构: #define MAX_VERTEX_NUM typedef struct ArcNode int struct }ArcNode; typedef struct Vnode int ArcNode { data; *firstarc; 20 { adjvex; ArcNode *nextarc;

}Vnode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList int }ALGraph; 【算法描述】 vertices; vexnum, arcnum;

Status // //

TopologicalSort(ALGraph

G)

{

有向图 G 采用邻接表存储结构, 若 G 无回路,则输出 G 的顶点的一个拓扑序列并返回 ok,否则 ERROR. indegree); // 对各顶点求入度 indegree[0..vernum-1]

FindInDegree(G, InitStack(S);

for(i=0;i<G.vexnum; if (!indegree[i]) 0 ;

++i) Push(S,i);

//

建零入度顶点栈 S // 入度为 0 者进栈

count =

while (! StackEmpty(s)) pop(S, i); //

{ ++count;

printf(i,G.vertices[i].data);

输入 i 号顶点并计数 p; p = p->nextarc) {

for (p=G.vertices[i].firstarc; k=p->adjvex; if (! } } if else } ( // for //

对 i 号顶点的每个邻接点的入度减 1 Push(S,k); //若入度减为 0,则入栈

- indegree[k]))

// while (count < G.vexnum) ok; return ERROR; //该有向图有回路

return

// TopologicalSort

【C 源程序】 void / topsort(AdjList adj, int n) )输出 /

adj 为邻接表,拓扑排序结果用 printf(

{ int m,i,j,ghead; struct ghead=0; 头指针 / m=0; for(i=1;i<=n;i++) if(adj[i]->data==0) { adj[i]->data=ghead; / / m 指示输出的顶点个数 / / vexnode q; / ghead 是入度为 0 的顶点链表的

建立入度为 0 的顶点链表

ghead=i; while(ghead!=0) {j=ghead; ghead=adj[j]->data; q=adj[j]->link; printf("%d",j); m++; while(q!=NULL) { k=q->adjvex; adj[k]->data=adj[k]->data-1; if (adj[k]->data==0) /*将新的入度为 0 的顶点插入链表 / 找下一条弧 / / /*以顶点 vk 为尾的弧头的入度减 1*/ / 输出顶点 vj 并计数 / /*在链表中删除入度为 0 的顶点,顶点序号为 j*/

{adj[k]->data=ghead; p=p->next; } } if } 【实验题】 (m<n) printf("网中有环!

n");

/

输出顶点数不足 n

/

1. 将上面的程序补充完整,以教科书 P181 的课程优先有向图为例子,建立其邻接表,调用上面的程序实 现拓扑排序。 2. 改进这个程序,使之能够找到图中所有的拓扑排序。 3. 如果以十字链表存储图,如何实现拓扑排序?

第五节 思考题
1. 已知在某并发处理系统的 Petri 网基础上建立的可达图如图 7-8 所示。图中每个顶点表示系统运行中 的一种状态,有向边(弧)表示事件(用 t 表示),例如有向边(Vi,Vj)表示系统在状态 Vi 时出现该事件将引 发系统由状态 Vi 转变到状态 Vj。 (1) 请分别给出该可达图的邻接表、邻接矩阵以及邻接矩阵的三元组表形式,要求每种存储结构能够表 达出该可达图的全部信息,并分别对这三种形式中每个部分的含义(物理意义)予以简要说明。 (2) 若假设每个域(包括指针域)的长度为一个字节,请分别计算出这三种结构所占用的空间大小。

图 7-8

可达图

(北京航空航天大学,1999 年,《数据结构》考研题) 【简要分析】这道题目没有多少技巧,但需要细心。邻接矩阵与邻接表都不难画,每一部分的物理意义从 概念上就能说清楚。在计算空间大小时,不要忘了计算指针所占用的空间。 2. 编程实现迪杰斯特拉(Dijkstra)算法,求图中某一点到其余各点的最短路径。 3. 图的 D—搜索类似于 BFS,不同之处在于使用栈代替 BFS 中的队列,入、出队列的操作改为入、出栈的 操作。即当一个顶点的所有邻接点被搜索之后,下一个搜索出发点应该是最近入栈(栈顶)的项点 (1)用邻接表作存储结构,写一个 D-搜索算法。 (2)用 D-搜索方法搜索图 7-9,设初始出发点为 1,写出顶点的访问次序和相应的生成树,当从某 顶点出发搜索它的邻接点时,请按邻接点序号递增顺序搜索,以使答案唯一。

图 7-9 (中国科学技术大学 1998 年,《数据结构》入学考试题) 【简要分析】这是一道将 BFS 和 DFS 相结合的题目,出得非常巧妙;需要注意的是:一定要等相邻结点全 部入栈(不是入队列)后,方可弹栈遍历。

第八章 查找算法的实现
【实验目的】 1. 熟练掌握各种静态查找表的查找方法(顺序查找法、折半查找法、索引顺序表查找) ; 2. 熟练掌握二叉排序树的构造方法和查找算法; 3. 熟练掌握哈希表的构造方法,深刻理解哈希表与其他结构表的实质性差别; 4. 掌握描述查找过程的判定树的构造方法,以及按照定义计算各种查找方法在等概率情况下查找成功时的 平均查找长度; 5. 了解二叉平衡树的建立和维护平衡的方法。

第一节 知识准备
一、 基本概念和术语 1. 查找:在数据集合中寻找满足给定条件的数据元素,若找到满足给定条件的元素,则查找成功,否则称 查找失败。 2. 关键字:数据元素(或记录)中某个数据项的值,用它可以标识一个数据元素(或记录) 。关键字有主 关键字和次关键字之分。 3. 查找表:由同一类型的数据元素(或记录)构成的集合。 4. 查找的基本操作有:(1)查询某个“特定”的数据元素是否出现在查找表中;(2)检索某个“特定”的数据元素的 各种属性;(3)在查找表中插入一个新的数据元素;(4)在查找表中删除已存在的某个数据元素。若在查找表中 只进行(1) (2)两种查找操作的查找表称为静态查找表;若在查找过程中同时进行插入查找表中不存在的 数据元素,或者删除已存在的某个数据元素,则称为动态查找表。 二、 静态查找表 1. 顺序查找 若以顺序表或线性链表表示静态查找表时,可采用顺序查找方法进行查找。 (1) 方法:从表中最后一个记录开始,逐个进行记录关键字与给定值的比较,若某个记录的关键字和给 定值相等,则查找成功,找到所查记录;反之,直到第一个记录,其关键字和给定值比较都不等,则表明 表中没有所查记录,查找不成功。该方法简单,适用于任何表结构,但查找效率较低。 (2) 性能分析: 对含有 n 个记录的线性表, 记录的查找在等概率的前提下, 查找成功的平均查找长度 ASL 成功= = ;查找不成功的比较次数为 n+1。 2. 折半查找(二分查找) 若查找表中元素按关键字有序,并采用顺序存储结构进行存储,可采用折半查找方法进行查找。

123456789101112131415161718192021222324252627282930

 


 

  【Top

最新搜索

 


 

热点推荐