第三次数据结构实验报告

中国矿业大学数据结构课程实验报告

中国矿业大学计算机学院实验报告

中国矿业大学数据结构课程实验报告

BiTNode1[0].rchild BiTNode1[4].lchild BiTNode1[6].lchild BiTNode1[1].data = BiTNode1[2].data = BiTNode1[3].data = BiTNode1[4].data = BiTNode1[5].data = BiTNode1[6].data = BiTNode1[1].lchild BiTNode1[1].rchild BiTNode1[3].lchild BiTNode1[3].rchild BiTNode1[4].rchild int count=0;

= BiTNode1[2].lchild = BiTNode1[2].rchild = = BiTNode1[5].lchild = BiTNode1[5].rchild = = BiTNode1[6].rchild =NULL; 'B'; 'C'; 'D'; 'E'; 'F'; 'G'; = & BiTNode1[2]; = & BiTNode1[3]; = & BiTNode1[4]; = & BiTNode1[5]; = & BiTNode1[6];

cout<<"该树的节点数目为："<<node_count(root,count)<<endl; return 0; }

2、对图的邻接矩阵和邻接表表示分别进行深度优先搜索遍历算法的实现。#include <iostream> #include <malloc.h> using namespace std; #define int_max 10000 #define inf 9999 #define max 20 //…………………………………………邻接矩阵定义……………………

中国矿业大学数据结构课程实验报告

typedef struct ArcCell { int adj; char *info; }ArcCell,AdjMatrix[20][20]; typedef struct { char vexs[20]; AdjMatrix arcs; int vexnum,arcnum; }MGraph_L; //^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ int localvex(MGraph_L G,char v)//返回 V 的位置 { int i=0; while(G.vexs[i]!=v) { ++i; } return i; } int creatMGraph_L(MGraph_L &G)//创建图用邻接矩阵表示 { char v1,v2; int i,j,w; cout<<"…………创建无向图…………"<<endl<<"请输入图 G 顶点和弧的个数:(4 6)不包括 “()”"<<endl; cin>>G.vexnum>>G.arcnum; for(i=0;i!=G.vexnum;++i) { cout<<"输入顶点"<<i<<endl; cin>>G.vexs[i]; } for(i=0;i!=G

.vexnum;++i) for(j=0;j!=G.vexnum;++j) { G.arcs[i][j].adj=int_max; G.arcs[i][j].info=NULL; } for(int k=0;k!=G.arcnum;++k) { cout<<"输入一条边依附的顶点和权:(a b 3)不包括“()”"<<endl; cin>>v1>>v2>>w;//输入一条边依附的两点及权值 i=localvex(G,v1);//确定顶点 V1和 V2在图中的位置 j=localvex(G,v2);

中国矿业大学数据结构课程实验报告

G.arcs[i][j].adj=w; G.arcs[j][i].adj=w; } cout<<"图 G 邻接矩阵创建成功！"<<endl; return G.vexnum; } void ljjzprint(MGraph_L G) { int i,j; for(i=0;i!=G.vexnum;++i) { for(j=0;j!=G.vexnum;++j) cout<<G.arcs[i][j].adj<<" "; cout<<endl; } } int visited[max];//访问标记 int we; typedef struct arcnode//弧结点 { int adjvex;//该弧指向的顶点的位置 struct arcnode *nextarc;//弧尾相同的下一条弧 char *info;//该弧信息 }arcnode; typedef struct vnode//邻接链表顶点头接点 { char data;//结点信息 arcnode *firstarc;//指向第一条依附该结点的弧的指针 }vnode,adjlist; typedef struct//图的定义 { adjlist vertices[max]; int vexnum,arcnum; int kind; }algraph; //…………………………………………队列定义…………………… typedef struct qnode { int data; struct qnode *next; }qnode,*queueptr; typedef struct { queueptr front; queueptr rear;

中国矿业大学数据结构课程实验报告

}linkqueue; //……………………………………………………………………… typedef struct acr { int pre;//弧的一结点 int bak;//弧另一结点 int weight;//弧的权 }edg; int creatadj(algraph &gra,MGraph_L G)//用邻接表存储图 { int i=0,j=0; arcnode *arc,*tem,*p; for(i=0;i!=G.vexnum;++i) { gra.vertices[i].data=G.vexs[i]; gra.vertices[i].firstarc=NULL; } for(i=0;i!=G.vexnum;++i) { for(j=0;j!=G.vexnum;++j) { if(gra.vertices[i].firstarc==NULL) { if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum) { arc=(arcnode *)malloc(sizeof(arcnode)); arc->adjvex=j; gra.vertices[i].firstarc=arc; arc->nextarc=NULL; p=arc; ++j; while(G.arcs[i][j].adj!=int_max&&j!=G.vexnum) { tem=(arcnode *)malloc(sizeof(arcnode)); tem->adjvex=j; gra.vertices[i].firstarc=tem; tem->nextarc=arc; arc=tem; ++j; } --j; } } else

中国矿业大学数据结构课程实验报告

{ if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum) { arc=(arcnode *)malloc(sizeof(arcnode)); arc->adjvex=j; p->nextarc=arc; arc->nextarc=NULL; p=arc; } } } } gra.vexnum=G.vexnum; gra.arcnum=G.arcnum; /*for(i=0;i!=gra.vexnum;++i) { arcnode *p; cout<<i<<" "; p=gra.vertices[i].firstarc; while(p!=NULL) { cout<<p->adjvex; p=p->nextarc; } cout<<endl; }*/ cout<<"图 G 邻接表创建成功！"<<endl; return 1; } void adjprint(algraph gra) { int i; for(i=0;i!=gra.vexnum;++i) { arcnode *p; cout<<i<<" "; p=gra.vertices[i].firstarc; while(p!=NULL) { cout<<p->adjvex; p=p->nextarc; } cout<<endl;

中国矿业大学数据结构课程实验报告

} } int firstadjvex(algraph gra,vnode v)//返回依附顶点 V 的第一个点 //即以 V 为尾的第一个结点 { if(v.firstarc!=NULL) return v.firstarc->adjvex; } int nextadjvex(algraph gra,vnode v,int w)//返回依附顶点 V 的相对于 W 的下一个顶点 { arcnode *p; p=v.firstarc; while(p!=NULL&&p->adjvex!=w) { p=p->nextarc; }

if(p->adjvex==w&&p->nextarc!=NULL) { p=p->nextarc; return p->adjvex; } if(p->adjvex==w&&p->nextarc==NULL) return -10; } int initqueue(linkqueue &q)//初始化队列 { q.rear=(queueptr)malloc(sizeof(qnode)); q.front=q.rear; if(!q.front) return 0; q.front->next=NULL; return 1; } int enqueue(linkqueue &q,int e)//入队 { queueptr p; p=(queueptr)malloc(sizeof(qnode)); if(!p) return 0; p->data=e; p->next=NULL; q.rear->next=p; q.rear=p; return 1;

中国矿业大学数据结构课程实验报告

} int dequeue(linkqueue &q,int &e)//出队 { queueptr p; if(q.front==q.rear) return 0; 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 queueempty(linkqueue q)//判断队为空 { if(q.front==q.rear) return 1; return 0; } void bfstra(algraph gra)//广度优先遍历 { int i,e; linkqueue q; for(i=0;i!=gra.vexnum;++i) visited[i]=0; initqueue(q); for(i=0;i!=gra.vexnum;++ …… 此处隐藏：8376字，全部文档内容请下载后查看。喜欢就下载吧 ……