十字链表_

更方便查询出入度#include stdio.h #include stdlib.h #include string.h #define inf 10001 int n,p; typedef struct ENode{ int tail_i; int head_i; struct ENode* tnext; struct ENode* hnext; }ENode; struct Graph{ char data; ENode* firstout; ENode* firstin; }g[105]; int find(char x){ int i; for(i 1; i n; i){ if(g[i].datax){ break; } } return i; } int main(){ scanf(%d %d,n,p); getchar(); for(int i 1; i n; i){ scanf(%c,g[i].data); g[i].firstout g[i].firstin NULL; } char x, y; int xi, yi; // 边起点和终点对应的下标 for(int i 1; i p; i){ getchar(); scanf(%c %c,x,y); xi find(x); yi find(y); ENode* e (ENode*)malloc(sizeof(ENode)); e-tnext g[xi].firstout; g[xi].firstout e; e-hnext g[yi].firstin; g[yi].firstin e; } // 读入待查询的顶点字符 getchar(); scanf(%c, x); xi find(x); // 获取该顶点的下标 int od 0, id 0; // 出度、入度 // 遍历出边链表统计出度 ENode* p g[xi].firstout; while (p ! NULL) { od; p p-tnext; // 移动到下一条同起点的边 } // 遍历入边链表统计入度 p g[xi].firstin; while (p ! NULL) { id; p p-hnext; // 移动到下一条同终点的边 } // 输出出度和入度 printf(%d %d\n, od, id); return 0; } /* 示例输入 4 6 ABCD B A A B B D D A A C C D 假设查询顶点为某个字符程序会输出其出度和入度。 */