데이터 구조 도의 기본 조작 실현
9329 단어 데이터 구조 전문 지식
실험 환경: Visual C++ 6.0
실험 목적: 그림 의 인접 행렬 과 인접 표 두 개의 저장 구조 와 표 시 를 파악 한다.
그림 의 DFS 와 BFS 두 가지 스 트 리밍 알고리즘 을 파악 합 니 다.
다음 의 전체 알고리즘 의 기본 사상 과 알고리즘 실현 방법 을 이해 하고 파악 한다. 최소 생 성 트 리 알고리즘, 최 단 경로 알고리즘, 토폴로지 정렬 알고리즘 과 관건 적 인 경로 알고리즘 이다.
실험 내용: 1. 무 방향 도 를 만 들 고 DFS 와 BFS 를 각각 진행 합 니 다.
2. 최 단 경로, 최소 생 성 트 리, 토폴로지 정렬 세 가지 알고리즘 을 실현 합 니 다.
#include
#include
#include
#include
#include
#include
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MaxInt 32767
#define MVNum 100
using namespace std;
typedef int Status;
bool visited[MVNum];
typedef struct
{
int vexs[MVNum];//
int arcs[MVNum][MVNum];//
int vexnum,arcnum; //
}AMGraph;
Status CreateUDN(AMGraph &G)//
{
int i,j,k,w;
int v1,v2;
printf("
");
cin>>G.vexnum>>G.arcnum;// ，
for(i=0;i>v1>>v2>>w;
G.arcs[v1][v2]=w;
G.arcs[v2][v1]=w;
}
return OK;
}
Status CreateDirUDN(AMGraph &G)//
{
int i,j,k,w;
int v1,v2;
printf("
");
cin>>G.vexnum>>G.arcnum;// ，
for(i=0;i>v1>>v2>>w;
G.arcs[v1][v2]=w;
}
return OK;
}
typedef struct ArcNode//
{
int adjvex;//
struct ArcNode * nextarc;//
//OtherInfo info;//
}ArcNode;
typedef struct VNode//
{
int data;
ArcNode *firstarc;//
}VNode,AdjList[MVNum];
typedef struct
{
AdjList vertices;
int visited[MVNum];
int vexnum,arcnum;//
}ALGraph;
Status CreateUDG(ALGraph &G)//
{
ArcNode *p1,*p2;
int v1,v2,i,j,k;
printf("
");
cin>>G.vexnum>>G.arcnum;
for(i=0;i>i>>j;
p1=(ArcNode *)malloc(sizeof(ArcNode));
p1->adjvex=j;
p1->nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=p1;// *P1 Vi
p2=(ArcNode *)malloc(sizeof(ArcNode));
p2->adjvex=i;
p2->nextarc=G.vertices[j].firstarc;
G.vertices[j].firstarc=p2;
}
return OK;
}
Status CreateDirUDG(ALGraph &G)//
{
ArcNode *p1,*p2;
int v1,v2,i,j,k;
printf("
");
cin>>G.vexnum>>G.arcnum;
for(i=0;i>i>>j;
p1=(ArcNode *)malloc(sizeof(ArcNode));
p1->adjvex=j;
p1->nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=p1;// *P1 Vi
}
return OK;
}
void DFS_AL(ALGraph G,int v)
{// G ， V G
ArcNode *p;
int w;
cout<adjvex;//w V
if(!visited[w])// W ， DFS__AL
DFS_AL(G,w);
p=p->nextarc;//p
}
}
typedef struct//
{
int *base;
int front;
int rear;
}SqQueue;
Status InitQueue(SqQueue &Q)
{//
Q.base=(int*)malloc(sizeof(int)*MVNum) ;
if(!Q.base)
exit(OVERFLOW);
Q.front=Q.rear=0;
return OK;
}
Status EnQueue(SqQueue &Q,int v)
{// v Q
if((Q.rear+1)%MVNum==Q.front)
return ERROR;
Q.base[Q.rear]=v;//
Q.rear=(Q.rear+1)%MVNum;//
return OK;
}
Status DeQueue(SqQueue &Q,int &v)
{// Q ， V
if(Q.front==Q.rear)
return ERROR;
v=Q.base[Q.front];//
Q.front=(Q.front+1)%MVNum;//
return OK;
}
Status QueueEmpty(SqQueue &Q)//
{
if(Q.front==Q.rear)
return 1;
return 0;
}
void Visit(ALGraph &G,int i)
{
printf(" %d",G.vertices[i].data) ;
G.visited[i]=1; // 1
}
void BFS_AL(ALGraph G,int v)
{// G
SqQueue Q;
ArcNode *w;
int u;
cout<nextarc)
{// u w
if(!G.visited[w->adjvex] )
{
Visit(G,w->adjvex);
EnQueue(Q,w->adjvex);
}
}
}
printf("
");
}
struct node
{
int adjvex;// U
int lowcost;//
}closedge[MVNum];
void MiniSpanTree_Prim(AMGraph G,int k)
{// G ， u G T, T
//k=LocateVex(G,u);//k u
int i,j,u0,v0,minn;
for(j=0;j0)
{
if(closedge[j].lowcostadjvex]++;
G.vertices[i].firstarc=G.vertices[i].firstarc->nextarc;
}
}
}
Status TopologicalSort(ALGraph &G)//
{
SqStack S;
int i,m,k,v;
int indegree[1100];
ArcNode *p;
InitStack(S);
Findindegree(G,indegree);
printf(" ：
");
for(i=0;inextarc)
{
k=p->adjvex;
if(!(--indegree[k]))
Push(S,k);
}
}
printf("
");
printf("
");
}
int main()
{
AMGraph G,T;
ALGraph M,N,R;
int v,k;
printf("************************
");
printf("1.DFS
");
printf("2.BFS
");
printf("3.
");
printf("4.
");
printf("5.
");
printf("0.
");
printf("************************
");
int choose=-1;
while(choose)
{
printf(" :
");
scanf("%d",&choose);
switch(choose)
{
case 1:
{
printf("
:");
CreateUDG(M);
printf("
");
printf("
");
scanf("%d",&v);
DFS_AL(M,v);
break;
}
case 2:
{
printf("
");
CreateUDG(N);
printf("
");
printf("
");
scanf("%d",&v);
BFS_AL(N,v);
break;
}
case 3:
{
printf("
");
CreateUDN(G);
printf("
");
printf("
");
scanf("%d",&k);
MiniSpanTree_Prim(G,k);
break;
}
case 4:
{
printf("
");
CreateDirUDN(T);
printf("
");
printf("
");
scanf("%d",&k);
ShortestPath_DIJ(T,k);
break;
}
case 5:
{
printf("
");
CreateDirUDG(R);
printf("
");
TopologicalSort(R);
break;
}
}
}
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
데이터 구조 도의 기본 조작 실현실험 제목: 그림 의 기본 조작 실현 실험 환경: Visual C++ 6.0 실험 목적: 그림 의 인접 행렬 과 인접 표 두 개의 저장 구조 와 표 시 를 파악 한다. 그림 의 DFS 와 BFS 두 가지 스 트 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
