数据结构实验源代码（21）

包含二十一个数据结构实验的源代码 创建图的十字链表 #include<stdio.h> #include<malloc.h> #define NULL 0 struct node { int ltag,rtag; struct node *lchild,*rchild; }; struct vex { int tag; struct node *lchild,*rchild; }; struct graph { struct vex *vexpex; int vexnum,arcnum; }; struct graph insert(struct graph g,struct node *p,int m,int n) { struct node *q; if(g.vexpex[m].rchild==NULL) g.vexpex[m].rchild=p; else { q=g.vexpex[m].rchild; if(p->rtag<q->rtag) { g.vexpex[m].rchild=p; p->rchild=q; } else { while(q->rchild!=NULL&&((p->rtag)>(q->rchild->rtag))) q=q->rchild; if(q->rchild==NULL) { q->rchild=p; } else { p->rchild=q->rchild; q->rchild=p; } } } if(g.vexpex[n].lchild==NULL) { g.vexpex[n].lchild=p; return g; } else { q=g.vexpex[n].lchild; if(p->ltag<q->ltag) { g.vexpex[n].lchild=p; p->lchild=q; return g; } else { while(q->lchild!=NULL&&((p->ltag)>(q->lchild->ltag))) q=q->lchild; if(q->lchild==NULL) { q->lchild=p; return g; } else { p->lchild=q->lchild; q->lchild=p; return g; } } } } struct graph creatgraph() { struct graph g; int tag; printf("请输入顶点的标记:\n"); scanf("%d",&tag); if(tag==0) { g.arcnum=g.vexnum=0; g.vexpex=NULL; return g; } else { g.vexpex=(struct vex *)malloc(2*sizeof(struct vex)); g.vexpex[1].tag=tag; g.vexnum=1; g.arcnum=0; g.vexpex[1].rchild=g.vexpex[1].lchild=NULL; scanf("%d",&tag); while(tag!=0) { g.vexpex=(struct vex *)realloc(g.vexpex,((g.vexnum+2)*sizeof(struct vex))); g.vexpex[g.vexnum+1].tag=tag; g.vexpex[g.vexnum+1].rchild=g.vexpex[g.vexnum+1].lchild=NULL; g.vexnum++; scanf("%d",&tag); } } return g; } struct graph initgraph(struct graph g) { int m,n; int i=1; printf("请输入第%d条边的两个顶点标记:",i); scanf("%d,%d",&m,&n); while(m!=0&&n!=0) { struct node *p; p=(struct node *)malloc(sizeof(struct node )); p->ltag=m; p->rtag=n; p->rchild=p->lchild=NULL; g=insert(g,p,m,n); i++; g.arcnum++; printf("\n请输入第%d条边的两顶点标记:",i); scanf("%d,%d",&m,&n); } return g; } void print(struct graph g) { struct node *q; int i; if(g.vexnum==0) printf("这是一个空图！！！！\n"); else { for(i=1;i<g.vexnum+1;i++) { q=g.vexpex[i].rchild; printf("顶点标记为 %d 的邻接点为：",g.vexpex[i].tag); while(q) { printf("%5d",q->rtag); q=q->rchild; } printf("\n"); } } } void main() { struct graph g; g=creatgraph(); g=initgraph(g); print(g); }