《数据结构习题集（李冬梅 第2版）C语言版源程序习题源代码 习题集-算法6-1（邻接表）.docx》由会员分享，可在线阅读，更多相关《数据结构习题集（李冬梅 第2版）C语言版源程序习题源代码 习题集-算法6-1（邻接表）.docx（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1.2.I34.5.6.7.8.I9-10.1112I1314.15.16.17.18.19.邻接链表存储图 #include using namespace std;/定义最大顶点数#define MVNum 128定义状态类型#define Status int/函数结果状态代码#define OK 1#define ERROR 0#define INFEASIBLE 0#define EXISTED 2typedef struct ArcNode /定义边结点 int adjvex;struct ArcNode *nextarc;ArcNode;20. typedef struct Ve
2、xNode /定义顶点结点int data;21. struct ArcNode *firstarc;VexNode;|24.25. typedef struct ALGraph 定义图的结构体类型VexNode verticesMVNum + 1;26. int vexnum arcnum; 图当前的顶点数和边数ALGraph;27. 对于每个顶点，它的边采用头插法插入28. void insertArcNode(VexNode &vnode, int adjvex) /向邻接表顶点中插入一条边结点ArcNode *arcnode= new ArcNode;29. arcnode-adjve
3、x = adjvex;arcnode-nextarc= vnode.firstarc;30. vnode.firstarc =arcnode;31. /采用邻接矩阵表示法，创立无向图graph32. Status createUDN(ALGraph &graph, int vexnum int arcnum) graph, vexnum = vexnum;初始化图的总顶点数33. graph.arcnum = arcnum;初始化图的总边数for (int i = 0; i = graph.vexnum; i+) /初始图中的顶点信息34. graph.verticesi.data = i;g
4、raph.verticesi.firstarc = NULL;35. - int vex_one, vex_two;一条边依附的两个顶点 vex_one 和 vex_two36. for (int i = 0; i vex_one vex_two;37. insertArcNode(graph.verticesvex_onevex_two);50.50.insertArcNode(graph.verticesvex_two, vex_one);5152. return OK; 创立成功，返回成功代码53. .定义打印无向图函数54. void printUDN(ALGraph graph) f
5、or (int i = 1; i = graph .vexnum; i+) /输出边的信息(每行第一个数字为顶点)(注意0号顶点不输出)55. cout graph.verticesi.data nextarc) 开始输出每个顶点上所链接的边信息56. cout adjvex )57. cout endl;58. /输出结束59. /判断顶点v是否存在图G中60. int LocateVex(ALGraph G, int v) 169.for (int i = 0; i = 0)return EXISTED; /判断该顶点是否已存在 if (G.vexnum + 1) MVNum)return
6、 INFEASIBLE;84. G. vexnum+;增加图的顶点数量85. G.verticesG.vexnum.data = v;86. G.verticesG.vexnum.firstarc = NULL;87. return OK;添加成功，返回成功代码88. 89.90. /在以邻接表形式存储的无向图G上删除顶点v91. Status DeleteVex(ALGraph &G, int v) 92. int n;93. if (n = LocateVex(G v) nextarc;91. delete p;G.arcnum-; 每删除一条边，边数量减一，下列图中遍历邻接表删除边时那么
7、不用再自减92. /随后把v的顶点信息删除，后面顶点向前移动93. for (int i = n; i G.vexnum; i+) G.verticesi = G.verticesi + 1;99.100.101.1102.103.104.I105106.107.108.109.110111.112113.114.115.116.117.118.119.120.121.122.123.124.G.vexnum-; 顶点数量减一最后遍历所有顶点，将与顶点v关联的边结点删除for (int i = 1; i adjvex = v) 如果当前结点的第一条边关联的结点为v,那么直接删除该边 (ArcN
8、ode *temp = G.verticesi.firstarc-nextarc;delete G.verticesi.firstarc;G.verticesi.firstarc = temp;continue; q.firstarc = p.f irstarc-nextarc;继续比拟后面的边结点while (q.firstarc) if (q.firstarc-adjvex = v) /存在与v相关联的边，那么删除该边ArcNode *temp = q.firstarc;p.firstarc-nextarc = q.firstarc-nextarc;delete temp; break;)
9、 p.firstarc = q.firstarc;/没找到与v相关联的边，p和q指针均后移q.firstarc = q.firstarc-nextarc;)return OK;删除成功，返回成功代码125. 126.127. /在以邻接表形式存储的无向图G上插入边(v,w)128. Status InsertArc(ALGraph &G, int v, int w) |129.int i, j;130. i = LocateVex(GJ v);131. j = LocateVex(G_, w);132. if (i = 0) return ERROR;133. if (j adjvex = w
10、;136. pl-nextarc = G.verticesi.firstarc;137. G.verticesi.firstarc = pl;138. ArcNode *p2 = new ArcNode;139. p2-adjvex = v;140. p2-nextarc = G.verticesj.firstarc;141. G.verticesj.firstarc = p2;142. G.arcnum+;143. return OK;插入成功，返回插入成功代码144. )145. 146. 在以邻接表形式存储的无向图G上删除边147. Status DeleteArc(ALGraph &G
11、, int v, int w) /确定v和w在G中的位置/判断插入位置是否合法生成一个新的边结点*pl邻接点序号为j/将新结点*pl插入顶点v的边表头部生成一个新的边结点*pl邻接点序号为j将新结点*p2插入顶点w的边表头部148.149 15。151.152.153.154.155.156.157.158.159.160.161.162.163.164.165.166.167.168.169.170.171.172.173.174.175.176.1177.178.179.180181.182.183.184.185.186.187.188.189 190.191.192 193.194.1
12、95.196 int i, j;i = LocateVex(G_, v);/确定v和w在G中的位置j = LocateVex(G w);if (i = 0) return ERROR;/判断删除位置是否合法if (j adjvex = w) ArcNode *temp = G.verticesi.firstare-nextarc;delete G.verticesi.firstarc;G.verticesi.firstarc = temp;)else 第一个边结点不是(v,w),继续向后查找(v,w)ArcNode *pl = G.verticesi.firstarc *p2 = G.vert
13、icesi.firstarc; while (p2-nextarc) if (p2-adjvex = w) 在链表中找到边结点(v,w)pl-nextarc = p2-nextarc;delete p2; break;)Pl = P2；p2 = p2-nextarc; )/从顶点w所在的边链表遍历链表进行查找，第一个边结点是(w,v),直接删除if (G.verticesj.firstarc-adjvex = v) ArcNode *temp = G.verticesj.firstarc-nextarc;delete G.verticesj.firstarc;G.verticesj.first
14、arc = temp;)else 第一个边结点不是(v,w),继续向后查找(v,w)ArcNode *pl = G.verticesj.firstarc, *p2 = G.verticesj.firstarc; while (p2-nextarc) if (p2-adjvex =v) /在链表中找到边结点(v,w)pl-nextarc = p2-nextarc;delete p2; break;)Pl = P2;p2 = p2-nextarc;)G.arcnum-;/边的数目减1return OK;删除成功，返回成功代码)int main() int n, m; n个顶点和m条边cout n
15、m; /输入n和m的值197. ALGraph G;198. cout “请依次输入m条边所依附的两端顶点：n;199. createUDN(G_, n, m);200. 打印图的信息201. printUDN(G);202. int v, w;203. /开始添加新顶点测试204. cout ”请输入待添加新顶点编号：b v;206. 工nsertVex(G, v);插入顶点v207. 打印图的信息208. printUDN(G);209. 开始删除顶点测试210. cout ”请输入待删除新顶点编号：b v;212. DeleteVex(G, v);213. 打印图的信息214. prin
16、tUDN(G);215. /开始添加边的信息216. cout 请输入待添加新边两端顶点的编号：b v w;218. InsertArcCG v, w);219. /打印图的信息220. printUDN(G);221. 开始删除边的信息222. cout ”请输入待删除新边两端顶点的编号：b v w;224. DeleteArc(GJ v, w);225. /打印图的信息226. printUDN(G);227. system(pause);228. return 0; 程序运行结束229. 测试用例展示（以程序一次运行周期为例） 输入数据：4 321 31 4输出结果：14 23 12 21输入数据：7输出结果：14 23 12 2输入数据:3 输出结果:1 23 12 27输入数据:1 7输出结果:17 23 12 27 1输入数据2 3输出结果:17 22 137 1