算术表达式的实现-数据结构课程设计|数据结构课程设计
#include
#include #define MAX_NAME 3 /* 顶点字符串的最大长度+1 */#define MAX_INFO 80 /* 相关信息字符串的最大长度+1 */#define MAX_VERTEX_NUM 20#define NULL 0/* 单链队列－－队列的链式存储结构 */ typedef struct QNode { int data; struct QNode *next; }QNode,*QueuePtr; typedef struct { QueuePtr front,rear; /* 队头、队尾指针 */ }LinkQueue; typedef char InfoType; typedef char VertexType[MAX_NAME]; /* 字符串类型 *//* c7-4.h 无向图的邻接多重表存储表示 */ typedef enum{unvisited,visited}VisitIf; typedef struct EBox { VisitIf mark; /* 访问标记 */ int ivex,jvex; /* 该边依附的两个顶点的位置 */ struct EBox *ilink,*jlink; /* 分别指向依附这两个顶点的下一条边 */ InfoType *info; /* 该边信息指针 */ }EBox; typedef struct { VertexType data; EBox *firstedge; /* 指向第一条依附该顶点的边 */ }VexBox; typedef struct { VexBox adjmulist[MAX_VERTEX_NUM]; int vexnum,edgenum; /* 无向图的当前顶点数和边数 */ }AMLGraph; /* 链队列的基本操作 */ InitQueue(LinkQueue *Q) { /* 构造一个空队列Q */ (*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode)); if(!(*Q).front) exit(0); (*Q).front->next=NULL; return 1; } QueueEmpty(LinkQueue Q) { /* 若Q为空队列,则返回TRUE,否则返回FALSE */ if(Q.front==Q.rear) return 1; else return -1; } EnQueue(LinkQueue *Q,int e) { /* 插入元素e为Q的新的队尾元素 */ QueuePtr p=(QueuePtr)malloc(sizeof(QNode)); if(!p) /* 存储分配失败 */ exit(0); p->data=e; p->next=NULL; (*Q).rear->next=p; (*Q).rear=p; return 1; } DeQueue(LinkQueue *Q,int *e) { /* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */ QueuePtr p; if((*Q).front==(*Q).rear) return -1; p=(*Q).front->next; *e=p->data; (*Q).front->next=p->next; if((*Q).rear==p) (*Q).rear=(*Q).front; free(p); return 1; } /* 无向图的邻接多重表存储 */ int LocateVex(AMLGraph G,VertexType u) { /* 初始条件: 无向图G存在,u和G中顶点有相同特征 */ /* 操作结果: 若G中存在顶点u,则返回该顶点在无向图中位置;否则返回-1 */ int i; for(i=0;imark=unvisited; /* 设初值 */ p->ivex=i; p->jvex=j; p->info=NULL; p->ilink=(*G).adjmulist[i].firstedge; /* 插在表头 */ (*G).adjmulist[i].firstedge=p; p->jlink=(*G).adjmulist[j].firstedge; /* 插在表头 */ (*G).adjmulist[j].firstedge=p; } return G; } VertexType* GetVex(AMLGraph G,int v) { /* 初始条件: 无向图G存在,v是G中某个顶点的序号。操作结果: 返回v的值 */ if(v>=G.vexnum||v<0) exit(0); return &G.adjmulist[v].data; }int visite[MAX_VERTEX_NUM]; /* 访问标志数组(全局量) */ int (*VisitFunc)(VertexType v); void DFS(AMLGraph G,int v) { int j; EBox *p; VisitFunc(G.adjmulist[v].data); visite[v]=1; p=G.adjmulist[v].firstedge; while(p) { j=p->ivex==v?p->jvex:p->ivex; if(!visite[j]) DFS(G,j); p=p->ivex==v?p->ilink:p->jlink; } } void DFSTraverse(AMLGraph G,int(*visit)(VertexType)) { /* 初始条件: 图G存在,Visit是顶点的应用函数。算法7.4 */ /* 操作结果: 从第1个顶点起,深度优先遍历图G,并对每个顶点调用函数Visit */ /* 一次且仅一次。一旦Visit()失败,则操作失败 */ int v; VisitFunc=visit; for(v=0;v
for(v=0;v=0;w=NextAdjVex(G,u1,strcpy(w1,*GetVex(G,w)))) if(!visite[w]) /* w为u的尚未访问的邻接顶点的序号 */ { visite[w]=1; Visit(G.adjmulist[w].data); EnQueue(&Q,w); } } } printf("\n"); } void MarkUnvizited(AMLGraph G) { /* 置边的访问标记为未被访问 */ int i; EBox *p; for(i=0;imark=unvisited; if(p->ivex==i) p=p->ilink; else p=p->jlink; } } } void Display(AMLGraph G) { /* 输出无向图的邻接多重表G */ int i; EBox *p; MarkUnvizited(G); /* 置边的访问标记为未被访问 */ printf("%d个顶点：\n",G.vexnum); for(i=0;iivex==i) /* 边的i端与该顶点有关 */ { if(!p->mark) /* 只输出一次 */ { printf("%s－%s ",G.adjmulist[i].data,G.adjmulist[p->jvex].data); p->mark=visited; if(p->info) /* 输出附带信息 */ printf("相关信息: %s ",p->info); } p=p->ilink; } else /* 边的j端与该顶点有关 */ { if(!p->mark) /* 只输出一次 */ { printf("%s－%s ",G.adjmulist[p->ivex].data,G.adjmulist[i].data); p->mark=visited; if(p->info) /* 输出附带信息 */ printf("相关信息: %s ",p->info); } p=p->jlink; } printf("\n"); } }/*主程序*/ visit(VertexType v) { printf("%s ",v); return 1; } void main() { int k,n; AMLGraph g; VertexType v1,v2; CreateGraph(&g); Display(g); printf("DFS:\n");/*深度优先搜索的结果*/ DFSTraverse(g,visit); printf("BFS:\n");/*广度优先搜索的结果*/ BFSTraverse(g,visit); DestroyGraph(&g); }
