清华大学出版社 TSINGHUA UNIVERSITY PRESS 6.2图的存储结构 图邻接表的构造 输入:图的结点数n;依次存放图中结点值的数组D(1:n)。 输出:邻接表顺序存储空间的首地址。 PROCEDURE CREATGP (D, n) 定义DATA(:n),LINK(1:n)[建立顺序存储空间 FoR k=0 to n do i DAtA (k=dk] LINK(k=0 INPUT m,ⅴ/*输入图中第k个结点的后件信息* WHILE(m>=0)D0/*输入后件信息未结束* NEW(p)/米分配单链表结点*/ NUM(p)=m; VAL (p)=V; NEXT (p)=LINK(k); LINK(k)=p INPUT m,v/*继续输入后件信息*/ RETURN
6.2 图的存储结构 图邻接表的构造 输入：图的结点数n；依次存放图中结点值的数组D(1：n)。 输出：邻接表顺序存储空间的首地址。 PROCEDURE CREATGP(D，n) 定义DATA(1：n)，LINK(1：n) [建立顺序存储空间] FOR k＝0 TO n DO { DATA(k)＝D[k]； LINK(k)＝0 INPUT m，v /*输入图中第k个结点的后件信息*/ WHILE (m＞＝0) DO /*输入后件信息未结束*/ { NEW(p) /*分配单链表结点*/ NUM(p)＝m； VAL(p)＝v；NEXT(p)＝LINK(k)；LINK(k)＝p INPUT m，v /*继续输入后件信息*/ } } RETURN
华大学出版 6.2 图的存储 84 44 2,63(回车)3,95(回车)4,84(回车)-1,-1(回车)(结点A的后件) 1,63(回车)3,49(回车)4,44(回车)5,37(回车)-1,-1(回车) (结点B的后件) 1,95(回车)2,49(回车)一1,-1(回车)(结点C的后件) 1,84(回车)2,44(回车)5,35(回车)-1,-1(回车)(结点D的后件) 2,37(回车)4,35(回车)-1,-1(回车)(结点E的后件)
6.2 图的存储结构 2，63（回车）3，95（回车）4，84（回车）－1，－1（回车）（结点A的后件） 1，63（回车）3，49（回车）4，44（回车）5，37（回车）－1，－1（回车） （结点B的后件） 1，95（回车）2，49（回车）－1，－1（回车）（结点C的后件） 1，84（回车）2，44（回车）5，35（回车）－1，－1（回车）（结点D的后件） 2，37（回车）4，35（回车）－1，－1（回车）（结点E的后件）
清华大学出版社 TSINGHUA UNIVERSITY PRESS 6.2图的存储结构 #includestdio. h #include stdlib. h struct node/米单链表中结点结构 i int num; /*图中结点编号*/ int val /*求值函数米 struct node*next;/*指针域*/ struct gpnode/*顺序存储空间中结点结构*/ i char data; /*结点值*/ struct node*link;/*指针域*/
6.2 图的存储结构 #include "stdio.h" #include "stdlib.h" struct node /*单链表中结点结构*/ { int num； /*图中结点编号*/ int val； /*求值函数*/ struct node *next； /*指针域*/ }； struct gpnode /*顺序存储空间中结点结构*/ { char data； /*结点值*/ struct node *link； /*指针域*/ }；
清华大学出版社 TSINGHUA UNIVERSITY PRESS 6.2图的存储结构 struct gpnode米 creator(d,n)/米该函数返回顺序存储空间的首地址* int n: char du i struct gpnode *head; struct node *p; int k, m, V: head=(struct gpnode *)malloc(n*sizeof (struct gpnode)) for (k=0; k<n: k++) /*依次对图中的每一个结点建立链接所有后件的单链表米/ (head+k)-data=d[k]:/*置顺序存储空间的结点值* (head+k)-link=NUL;/*置顺序存储空间结点指针域为空 printf( input linked list of %c: \n", dlk) scanf(%d%d,&m,&v);/*输入图中第k个结点的后件信息*/
6.2 图的存储结构 struct gpnode *creatgp(d，n)/*该函数返回顺序存储空间的首地址*/ int n； char d[]； { struct gpnode *head； struct node *p； int k，m，v； head＝(struct gpnode *)malloc(n*sizeof(struct gpnode))； for (k＝0；k＜n；k＋＋) /*依次对图中的每一个结点建立链接所有后件的单链表*/ { (head＋k)－>data＝d[k]； /*置顺序存储空间的结点值*/ (head＋k)－>link＝NULL；/*置顺序存储空间结点指针域为空*/ printf("input linked list of %c :\n"，d[k])； scanf(“%d%d” ，&m，&v)； /*输入图中第k个结点的后件信息*/