《数据结构》课程设计_网_邻接表.doc

课 程 设 计 课程：数据结构 题目：网12（邻接表） 设计时间：2010年01月10日——2010年05月20日 成绩： 指导教师：楼建华  一、题目 题目 网12 结构 邻接表 表示 顶点链的头指针 回传方式 引用 操作 创建边链表、创建顶点链、增删边、增删结点、深度优先遍历、广度优先遍历等 二、概要设计 1.存储结构 typedef char DataType; // 定义顶点值为字符型 typedef double WeightType; //边的权值类型 struct NodeVertex{ DataType Vertex; // 顶点数据 NodeEdge * FEW; // 边集结点 NodeVertex * Vnext; // 顶点结点 char ch; }; struct NodeEdge{ NodeVertex * Edge; // 顶点结点 WeightType Weight; // 权值 NodeEdge * Enext; // 边集结点 }; struct Edge{ // 定义边集存储结构 DataType FVertex; // 边的起点 DataType EVertex; // 边的终点 WeightType Weight; // 边的权值 }; 网的邻接表存储(顶点链的头指针)： 8 ∧  6 ∧ G→ a — → b — → c — → d ∧ 8 — → 7 ∧ 5 ∧ a d 8 7 5 b C 6 2.基本操作(声明函数) ⑴void CreateVertexChain(Auxiliary * _Au); // 创建顶点链 ⑵void CreateEdgeChain(Auxiliary * _Au); // 创建边链表 ⑶void DeleteEdge(DataType Vertex1,DataType Vertex2);// 删除边 ⑷void AddEdge(DataType Vertex1,DataType Vertex2,WeightType Weight); // 增加边 ⑸void DeleteVertex(DataType Vertex); // 删除顶点 ⑹void AddVeretex(DataType Vertex); // 添加结点 ⑺void Depth_first(); //深度优先遍历 ⑻void Breadth_first(); //广度优先遍历 三、设计要点(给出主要操作的算法，包括：框图、程序实现、核心步骤图) ⑴存储要点 定义两个结点，即顶点结点和边结点，定义指针分别用来指向下一个结点及其后继的地址。 ⑵删除边要点 首先定义两个顶点结点指针和两个边结点指针分别用来查找要删除边的前后两个结点位置，并判断该边集是否为空，若不为空就删除。 ⑶增加边要点 首先定义两个顶点结点指针和两个边结点指针分别用来查找要增加边的前后两个结点位置，查找到以后为其申请空间，并把权值赋给所增加的边，然后再用定义的指针处理好它的位置。 核心步骤为： if(NA-FEW == NULL){ NodeEdge * P=new NodeEdge; P-Weight=Weight; P-Enext=NULL; P-Edge=NB; NA-FEW=P; } ⑷深度遍历要点 访问指定或任意起始顶点以各出端为新的起始顶点做深度优先遍历。 核心步骤为： while(H != NULL){ H-ch=0; H=H-Vnext; } for(H=this-GRAPH;H != NULL;H=H-Vnext){ if(H-ch==0) this-Traversal(H-Vertex); } ⑸广度遍历要点 访问指定或任意起始顶点（第一层），然后再访问前一层的顶点的所有出端。 核心步骤为： while(H != NULL){ H-ch=0; H=H-Vnext; } H=this-GRAPH; while(H != NULL){ if(H-ch == 0) this-BFSM(H); H=H-Vnext; } ⑹删除结点要点 从G查找目标接点，然后有哪些信誉好的足球投注网站目标接点的邻接点，并且删除对应的邻接边。最后删除目标节点