数据结构实验六.doc

实验难度： A □ B □ B-C √□ C □ 序号 学号 姓名 成绩 20 指导教师 （签名） 学　　期：　　2014秋季学期 任课教师: 　　 　 实验题目: 实验六 图及其应用Conceive）】(10%) （本部分） 为了实现校园导游系统，默认用户只认识目前所在位置。图的生成及实现对校园内各个地点的地名及简介，并通过迪杰斯特拉算法给出任意起点其他地点的最短路径并将路径信息一并输出出来 对于图的操作，是基于数组和实现的，完成对图这一抽象数据结构的存储，队列用于调整存储的顺序。 ，分支结构链式结构，队列等 Design)】(20%) （本部分） typedef char VertexData; typedef struct ArcNode1//边节点的辅助存储{ int adj; } ArcNode1; typedef struct//邻接矩阵的结构体 { VertexData vexs[N]; ArcNode1 arcs[N][N]; int vexnum1,arcnum1; }AdjMatrix; typedef struct VertexNode//图节点的结构体 { VertexData data; ArcNode2 *firstarc; }VertexNode; typedef struct//辅助存储的结构体 { VertexNode vertex[N]; int vexnum2,arcnum2; }AdjList; typedef struct Node队列节点的结构体 { int data; struct Node *next; }LinkQueueNode; typedef struct//队列的结构体 { LinkQueue Node *front; LinkQueue Node *rear; }LinkQueue; 各模块 从主函数来看，调用无向图生成，无向图遍历，迪杰斯特拉算法，四个函数。，无向图生成中嵌套了定位访问。 Implement）】(30%) （本部分 队列抽象数据类型的实现： { Q-front=(LinkQueueNode*)malloc(sizeof(LinkQueueNode)); if(Q-front!=NULL) { Q-rear=Q-front; Q-front-next=NULL; return(True); } else return(False); } int EnQueue(LinkQueue *Q,int x)//入队函数 { LinkQueueNode *NewNode; NewNode=(LinkQueueNode*)malloc(sizeof(LinkQueueNode)); if(NewNode!=NULL) { NewNode-data=x; NewNode-next=NULL; Q-rear-next=NewNode; Q-rear=NewNode; return(True); } else return(False); } int DeleteQueue(LinkQueue *Q,int *x)//出队函数 { LinkQueueNode *p; if(Q-front==Q-rear) return(False); p=Q-front-next; Q-front-next=p-next; if(Q-rear==p) Q-rear=Q-front; *x=p-data; free(p); return(True); } int IsEmpty(LinkQueue *Q)//队列判空函数 { if(Q-front==Q-rear) return(True); else return(False); } Dijkstra函数的实现： void Dijkstra( pathtype path[],int dist[],int v) { int A[11][11]={{0,2,99,99,99,4,1,99,99,99,99},{2,0,6,99,99,3,99,3,99,99,99},{99,6,0,3,99,8,99,99,99,2,99},{99,99,3,0,99,10,99,99,1,4,99},{99,99,1,99,0,99,99,2,99,2,99},{4,3,8,10,99,0,99,99,99,99,99},{1,99,99,99,