#include#include #define OK 1 #define INFINITY 32767 #define MAX_VERTEX_NUM 30 #define MAXINFOLEN 30 #define ERROR 0 #define OVERFLOW -1 #define MAXVERTEXLEN 30 #define FALSE 0 #define TRUE 1 typedef int Status; typedef enum { DG, DN, UDG, UDN }GraphKind; typedef int VRType; typedef int InfoType; typedef char* VertexType; //十字链表图结构（适用于有向图） typedef struct ArcBox { int tailvex, headvex; struct ArcBox* hlink, * tlink; InfoType* info; }ArcBox; typedef struct VexNode { VertexType data; ArcBox* firstin, * firstout; }VexNode; typedef struct { VexNode xlist[MAX_VERTEX_NUM]; int vexnum, arcnum; }OLGraph; Status CreatDG_OL(OLGraph* G) { int info; printf("请依次输入邻接矩阵的节点数，弧数，弧上是否具有额外信息n"); scanf("%d%d%d", &(G->vexnum), &(G->arcnum), &info); getchar(); for (int i = 0; i < G->vexnum; i++) { printf("请输入第%d个节点的描述n", i + 1); G->xlist[i].data = (char*)malloc(sizeof(char) * MAXVERTEXLEN); if (!G->xlist) exit(OVERFLOW); gets(G->xlist[i].data); G->xlist[i].firstin = NULL; G->xlist[i].firstout = NULL; } char* ch; ch = (char*)malloc(sizeof(char) * MAXVERTEXLEN); if (!ch) exit(OVERFLOW); int tail = 1000, head = 1000; for (int i = 0; i < G->arcnum; i++) { ArcBox* p; p = (ArcBox*)malloc(sizeof(ArcBox)); if (!p) exit(OVERFLOW); printf("请输入弧尾的节点描述n"); gets(ch); for (int j = 0; j < G->vexnum; j++) { if (strcmp(ch, G->xlist[j].data) == 0) { tail = j; break; } } p->tailvex = tail; p->tlink = G->xlist[tail].firstout; G->xlist[tail].firstout = p; printf("请输入弧头的节点描述n"); gets(ch); for (int j = 0; j < G->vexnum; j++) { if (strcmp(ch, G->xlist[j].data) == 0) { head = j; break; } } p->headvex = head; p->hlink = G->xlist[i].firstin; G->xlist[head].firstin = p; if (info) { printf("请输入弧的描述信息n"); p->info = (int*)malloc(sizeof(int)); if (!p->info) exit(OVERFLOW); scanf("%d", p->info); getchar(); } else p->info = NULL; } return OK; } //孩子兄弟树的数据结构描述 typedef char* TElemType; typedef struct CSNode { TElemType data; struct CSNode* firstchild, * nextsibling; }CSNode, * CSTree; //队列函数 typedef CSTree QElemType; typedef struct QNode { QElemType data; struct QNode* next; }QNode, * QueuePtr; typedef struct { QueuePtr front, rear; }LinkQueue; Status InitQueue(LinkQueue* Q) { Q->front = (QNode*)malloc(sizeof(QNode)); if (!Q->front) exit(OVERFLOW); Q->rear = Q->front; return OK; } Status EnQueue(LinkQueue* Q, QElemType e) { QNode* p; p = (QNode*)malloc(sizeof(QNode)); if (!p) exit(OVERFLOW); p->data = e; Q->rear->next = p; Q->rear = p; p->next = NULL; return OK; } Status DeQueue(LinkQueue* Q, QElemType* e) { if (Q->front == Q->rear) return ERROR; *e = Q->front->next->data; if (Q->rear == Q->front->next) Q->rear = Q->front; QNode* p = Q->front->next; Q->front->next = p->next; free(p); return OK; } Status QueueEmpty(LinkQueue Q) { if (Q.front == Q.rear) return TRUE; else return FALSE; } void PrintQueue(LinkQueue Q) { QNode* p = Q.front->next; if (!p) printf("空n"); else { while (p) { printf("%dt", p->data + 1); p = p->next; } printf("n"); } } void PrintCSTree_LevelOrder(CSTree T) { printf("孩子兄弟树层序输入为n"); LinkQueue* Q; Q = (LinkQueue*)malloc(sizeof(LinkQueue)); if (!Q) exit(OVERFLOW); InitQueue(Q); EnQueue(Q, T); QElemType* p; p = (QElemType*)malloc(sizeof(QElemType)); if (!p) exit(OVERFLOW); while (!QueueEmpty(*Q)) { DeQueue(Q, p); puts((*p)->data); if ((*p)->firstchild) EnQueue(Q, (*p)->firstchild); if ((*p)->nextsibling) EnQueue(Q, (*p)->nextsibling); } } //栈的数据结构及函数 #define STACK_INIT_SIZE 100 #define STACK_INCREASMENT 10 typedef int SElemType; typedef struct { SElemType* base, * top; int stacksize; }SqStack; Status InitStack(SqStack* S) { S->base = (SElemType*)malloc(sizeof(SElemType) * STACK_INIT_SIZE); if (!S->base) exit(OVERFLOW); S->top = S->base; S->stacksize = STACK_INIT_SIZE; } Status Push(SqStack* S, SElemType e) { if (S->top - S->base > S->stacksize) { S->base = (SElemType*)realloc(S->base, sizeof(SElemType) * (S->stacksize + STACK_INCREASMENT)); if (!S->base) exit(OVERFLOW); S->stacksize += STACK_INCREASMENT; } *(S->top) = e; S->top++; return OK; } Status Pop(SqStack* S, SElemType* e) { if (S->base == S->top) return ERROR; S->top--; *e = *(S->top); return OK; } Status StackEmpty(SqStack S) { if (S.base == S.top) return TRUE; else return FALSE; } //求强连通分量辅助数据结构 typedef struct { char ch[MAXVERTEXLEN]; int i; }Help;
//找有向图中的强连通分量（十字链表表示有向图）
int visited[MAX_VERTEX_NUM];
Help finished[MAX_VERTEX_NUM];
void Convert(OLGraph G1, OLGraph* G2)
{
G2->arcnum = G1.arcnum;
G2->vexnum = G1.vexnum;
for (int i = 0; i < G2->vexnum; i++)
{
G2->xlist[i].firstin = NULL;
G2->xlist[i].firstout = NULL;
G2->xlist[i].data = (char*)malloc(sizeof(char) * MAXVERTEXLEN);
if (!G2->xlist[i].data) exit(OVERFLOW);
strcpy(G2->xlist[i].data, G1.xlist[i].data);
}
for (int i = 0; i < G2->vexnum; i++)
{
ArcBox* p = G1.xlist[i].firstout;
while (p)
{
ArcBox* q = (ArcBox*)malloc(sizeof(ArcBox));
if (!q) exit(OVERFLOW);
q->headvex = i;
q->tailvex = p->headvex;
q->hlink = G2->xlist[i].firstin;
G2->xlist[i].firstin = q;
q->tlink = G2->xlist[p->headvex].firstout;
G2->xlist[p->headvex].firstout = q;
if (p->info)
{
q->info = (char*)malloc(sizeof(char) * MAXINFOLEN);
if (!q->info) exit(OVERFLOW);
}
p = p->tlink;
}
}
}
void DFSTree_OL(OLGraph G, int m, CSTree T)
{
visited[m] = TRUE;
int first = 1;
ArcBox* r = G.xlist[m].firstout;
CSNode* q;
while (r)
{
if (!visited[r->headvex])
{
CSNode* p = (CSTree)malloc(sizeof(CSNode));
if (!p) exit(OVERFLOW);
p->data = (char*)malloc(sizeof(char) * MAXVERTEXLEN);
if (!p->data) exit(OVERFLOW);
strcpy(p->data, G.xlist[r->headvex].data);
if (first == 1)
{
T->firstchild = p;
q = p;
q->nextsibling = NULL;
first = 0;
}
else
{
q->nextsibling = p;
q = p;
q->nextsibling = NULL;
}
DFSTree_OL(G, r->headvex, q);
}
r = r->tlink;
}
if (first == 1)
T->firstchild = NULL;
}
void DFSForest_OL(OLGraph G1, CSTree* T)
{
int first = 1;
for (int i = 0; i < G1.vexnum; i++)
visited[i] = FALSE;
CSNode* q;
for (int i = 0; i < G1.vexnum; i++)
{
if (!visited[i])
{
CSTree p = (CSTree)malloc(sizeof(CSNode));
if (!p) exit(OVERFLOW);
p->data = (char*)malloc(sizeof(char) * MAXVERTEXLEN);
if (!p->data) exit(OVERFLOW);
strcpy(p->data, G1.xlist[i].data);
if (first == 1)
{
(*T) = p;
first = 0;
q = p;
(*T)->nextsibling = NULL;
}
else
{
q->nextsibling = p;
q = p;
q->nextsibling = NULL;
}
DFSTree_OL(G1, i, q);
}
}
}
void PostOrderTraverse_CS(CSTree T, SqStack* S)
{
if (T)
{
int i = 0;
CSNode* p = T->firstchild;
CSNode* q = p;
while (q)
{
PostOrderTraverse_CS(q, S);
q = q->nextsibling;
}
Push(S, T->data);
while (strcmp(finished[i].ch, T->data) != 0)
i++;
finished[i].i = 1;
}
}
void DFS_OL(OLGraph G, int m)
{
finished[m].i = 2;
printf("%st", G.xlist[m].data);
ArcBox* p = G.xlist[m].firstout;
while (p)
{
if (finished[p->headvex].i == 1)
DFS_OL(G, p->headvex);
p = p->tlink;
}
}
void DFS_OL_Verse(OLGraph G, SqStack* S)
{
char* ch = (char*)malloc(sizeof(char) * MAXINFOLEN);
if (!ch) exit(OVERFLOW);
while (!StackEmpty(*S))
{
Pop(S, &ch);
int i = 0;
while (strcmp(ch, G.xlist[i].data) != 0)
i++;
if (finished[i].i == 1)
{
printf("一个连通分量的所有节点描述为：n");
DFS_OL(G, i);
printf("n");
}
}
}
int main()
{
OLGraph* G1;
G1 = (OLGraph*)malloc(sizeof(OLGraph));
if (!G1) exit(OVERFLOW);
CreatDG_OL(G1);
printf("G1的指针指向n");
for (int i = 0; i < G1->vexnum; i++)
{
ArcBox* p = G1->xlist[i].firstout;
while (p)
{
printf("%s->%sn", G1->xlist[i].data, G1->xlist[p->headvex].data);
p = p->tlink;
}
}
OLGraph* G2;
G2 = (OLGraph*)malloc(sizeof(OLGraph));
if (!G2) exit(OVERFLOW);
Convert(*G1, G2);
printf("G2的指针指向n");
for (int i = 0; i < G2->vexnum; i++)
{
ArcBox* p = G2->xlist[i].firstout;
while (p)
{
printf("%s->%sn", G2->xlist[i].data, G2->xlist[p->headvex].data);
p = p->tlink;
}
}
CSTree T;
DFSForest_OL(*G2, &T);
PrintCSTree_LevelOrder(T);
SqStack S;
InitStack(&S);
CSNode* p = T;
for (int i = 0; i < G2->vexnum; i++)
{
strcpy(finished[i].ch, G2->xlist[i].data);
finished[i].i = 0;
}
while (p)
{
PostOrderTraverse_CS(p, &S);
DFS_OL_Verse(*G1, &S);
p = p->nextsibling;
}
return 0;
}
输入：
13 22 0 V0 V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 V11 V12 V0 V5 V0 V6 V0 V1 V2 V0 V2 V3 V3 V2 V3 V5 V4 V2 V4 V3 V5 V4 V6 V4 V7 V6 V6 V9 V4 V11 V7 V8 V8 V7 V8 V9 V9 V10 V9 V11 V11 V12 V10 V12 V12 V9
原图：
输出：
