数据结构28-30

第二十八课

本课主题：图的存储结构

教学目的：掌握图的二种存储表示方法

教学重点：图的数组表示及邻接表表示法

教学难点：邻接表表示法

授课内容：

一、数组表示法

用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系 （边或弧）的信息。

// 图的数组（邻接矩阵）存储表示

#define INFINITY INT_MAX //最大值无穷大

#define MAX_VERTEX_NUM 20 //最大顶点个数

typedef enum{DG,DN,AG,AN} GraphKind;//有向图，有向网，无向图，无向网

typedef struct ArcCell{

VRType adj; //VRType是顶点关系类型。对无权图，用1或0表示相邻否，对带权图，则为权值类型

InfoType *info; //该弧相关停息的指针

}ArcCell,AdjMatrix[max_vertex_num][max_vertex_num];

tpyedef struct{

VertexType vexs[MAX_VERTEX_NUM]; //顶点向量

AdjMatrix arcs; //邻接矩阵

int vexnum,arcnum; //图的当前顶点数和弧数

GraphKind kind; //图的种类标志

}MGraph;

二、邻接表

邻接表是图的一种链式存储结构。

在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧）。每个结点由三个域组成，其中邻接点域 (adjvex)指示与顶点vi邻接的点在图中的位置，链域(nextarc)指示下一条边或弧的结点；数据域(info)存储和边或弧相关的信息，如权 值等。每个链表上附设一个表头结点，包含链域(firstarc)指向链表中第一个结点，还设有存储顶点vi的名或其它有关信息的数据域(data)。 如：

#define MAX_VERTEX_NUM 20

typedef struct ArcNode{

int adjvex; //该弧所指向的顶点的位置

struct ArcNode *nextarc; //指向下一条弧的指针

InfoType *info; //该弧相关信息的指针

}ArcNode;

typedef struct VNode{

VertexType data; //顶点信息

ArcNode *firstarc; //指向第一条依附该顶点的弧的指针

}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct {

AdjList vertices; //图的当前顶点数和弧数

int vexnum,arcnum; //图的种类标志

int kind;

}ALGraph;

三、总结

图的存储包括哪些要素？

回目录上一课下一课

第二十九课

本课主题：静态查找表（一）顺序表的查找

教学目的：掌握查找的基本概念，顺序表查找的性能分析

教学重点：查找的基本概念

教学难点：顺序表查找的性能分析

授课内容：

一、查找的基本概念

一些约定：

二、静态查找表

静态查找表的类型定义：

三、顺序表的查找

静态查找表的顺序存储结构

typedef struct {

ElemType *elem;

int length;

}SSTable;

顺序查找：从表中最后一个记录开始，逐个进行记录的关键字和给定 值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，查找不成功。

int Search_Seq(SSTable ST,KeyType key){

ST.elme[0].key=key;

for(i=ST.length; !EQ(ST.elem[i].key,key); --i);

return i;

}

查找操作的性能分析：

查找算法中的基本操作是将记录的关键字和给定值进行比较，，通常 以“其关键字和给定值进行过比较的记录个数的平均值”作为衡量依据。

平均查找长度：

为确定记录在查找表中的位置，需用和给定值进行比较的关键字个数 的期望值称为查找算法在查找成功时的平均查找长度。

四、总结

什么是查找表

顺序表的查找过程

回目录上一课下一课

第三十课

本课主题：静态查找表（二）有序表的查找

教学目的：掌握有序表的折半查找法

教学重点：折半查找

教学难点：折半查找

授课内容：

一、折半查找的查找过程

以有序表表示静态查找表时，Search函数可用 折半查找来实现。

先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。

二、折半查找的查找实现

int Search_Bin(SSTable ST,KeyType key){

low=1;high=ST.length;

while(low<=high){

mid=(low+high)/2;

if EQ(key,ST.elem[mid].key) return mid;

else if LT(key,ST.elem[mid].key) high=mid -1;

else low=mid +1 ;

}

return 0;

}//Search_Bin;

三、折半查找的性能分析

折半查找在查找成功时和给定值进行比较的关键字个数至多为

回目录上一课下一课