今天刚做完的作业，希望大家能提出更好的建议（比如单独打印出树）
#include "Stdio.h"
#include "Conio.h"

#define MAX 30
#define MAX_VERTEX_NUM 20
#define INT_MAX 20000

int visited[MAX]={
0,0,0,0,0,0,
0,0,0,0,0,0,
0,0,0,0,0,0,
0,0,0,0,0,0,
0,0,0,0,0,0
};

/*------------------------------队列----------------------------*/
struct QNode
{
int data;
struct QNode *next;
};
struct Queue
{
struct QNode *rear;
};

/*------------------------------图----------------------------*/
typedef struct
{
char vex[MAX];
int arc[MAX][MAX];
int vexnum,arcnum;
}MGraphy; /*邻接矩阵*/

/*------------------------------树----------------------------*/
typedef struct Node
{
char data;
struct Node *lchild,*rchild; /*左右孩子指针*/

}Node,*BiTree;

/*------------------------------队列----------------------------*/

InitQueue(struct Queue *Q)
{ /*初始化链表队列*/
Q->rear=(struct QNode *)malloc(sizeof(struct QNode));
if (!Q->rear) printf("Application failed!");
Q->rear->next=Q->rear;
}

int EmptyQueue(struct Queue *Q)
{ /*判断队列是否为空*/
if (Q->rear->next==Q->rear)
return 1;
return 0;
}

EnQueue(struct Queue *Q,int e)
{ /*入队操作*/
struct QNode *p;
p=(struct QNode *)malloc(sizeof(struct QNode));

p->data=e;
p->next=Q->rear->next;
Q->rear->next=p;
Q->rear=p;

}

int DeQueue(struct Queue *Q)
{ /*出队操作*/
int back;
struct QNode *head=Q->rear->next;
struct QNode *p;

if (Q->rear->next==Q->rear)
printf("The queue is empty!");

back=head->next->data;
p=head->next;
head->next=p->next;

if (head->next==head)
Q->rear=head;

free(p);

return back;
}

/*----------------邻接矩阵的创建-------------------*/
CreateMGraphy(MGraphy *G)
{
int i=0,j=0,k=0,m,n;
char v1,v2;

printf("Please input vexnum and arcnum:\n");
scanf("%d",&(G->vexnum));
scanf("%d",&(G->arcnum));
printf("Please input vex string:");
for (i=0;i<G->vexnum;i++)
{
scanf("\n%c",&(G->vex[i]));
printf("%c ",G->vex[i]);
}
printf("\n");
for (i=0;i<G->vexnum;i++)
for (j=0;j<G->vexnum;j++)
G->arc[i][j]=0; /*弧的初始化*/
for (k=0;k<G->arcnum;k++)
{
printf("input the edge to create the graphy:\n");
scanf("%d,%d",&i,&j);
G->arc[i][j]=1; /*给已确定的弧做标记*/
G->arc[j][i]=1; /*这句表示创建的是无向图*/
}
for (i=0;i<G->vexnum;i++)
{ /*打印出弧关系矩阵*/
for (j=0;j<G->vexnum;j++)
printf("%d ",G->arc[i][j]);
printf("\n");
}

}

int LocateVex(MGraphy *G,char *v)
{
int i;
for (i=0;i<G->vexnum;i++)
if (G->vex[i]==*v)
{
printf("^^%c,%d\n",G->vex[i],i);
return i;
}

}

void DFST(MGraphy *G,int locate)
{ /*邻接矩阵深度优先遍历*/
int n;
printf("%c(%d)==>",G->vex[locate],locate);
visited[locate]=1;
for (n=0;n<G->vexnum;n++)
if (G->arc[locate][n]==1 && !visited[n])
{
DFST(G,n);
}
}

void WST(MGraphy *G,int locate)
{ /*邻接矩阵广度优先遍历*/
struct Queue Q;
int i,j;
InitQueue(&Q);
printf("\n\n=========WSTraverse:=========\n");
for (j=0;j<G->vexnum;j++)
visited[j]=0;
printf("The order is:");
printf("%c(%d)==>",G->vex[locate],locate);
visited[locate]=1;
EnQueue(&Q,locate);
while (!EmptyQueue(&Q))
{
i=DeQueue(&Q);
for (j=0;j<G->vexnum;j++)
if (G->arc[i][j]==1 && !visited[j])
{
printf("%c(%d)==>",G->vex[j],j);
visited[j]=1;
EnQueue(&Q,j);
}
}
}

void CreateTree(MGraphy *G,int locate,BiTree T)
{ /*图广度生成树*/
int i,j;
struct Queue Q;
InitQueue(&Q);
T=(BiTree)malloc(sizeof(Node));
for (j=0;j<G->vexnum;j++)
visited[j]=0;
printf("\n\n=====Graphy change to tree:=====");
T->data=G->vex[locate];
printf("\nRoot:%c \n",T->data);
visited[locate]=1;
EnQueue(&Q,locate);
printf("Child:");
while (!EmptyQueue(&Q))
{
i=DeQueue(&Q);
for (j=0;j<G->vexnum;j++)
if (G->arc[i][j]==1 && !visited[j])
{
T->lchild=(BiTree)malloc(sizeof(Node));
T->lchild->data=G->vex[j];
printf("%c ",T->lchild->data);
visited[j]=1;
EnQueue(&Q,j);
}
}
}

int main(void)
{
int i;
MGraphy *G;
BiTree T;
G=(MGraphy *)malloc(sizeof(MGraphy));
CreateMGraphy(G);
printf("========DFSTraverse:========\n");
printf("The order is:");
DFST(G,1);
WST(G,1);
CreateTree(G,1,T);
getch();
return 0;
}

aWPwJzcX.txt (4.83 KB) [原创]图的深度和广度优先遍历及其生成树！

int LocateVex(MGraphy *G,char *v)
{
int i;
for (i=0;i<G->vexnum;i++)
if (G->vex[i]==*v)
{
printf("^^%c,%d\n",G->vex[i],i);
return i;
}

}

在这里用不上

能不能帮我做下这个啊~！用图的方法来做~！

题目：
全国个大城市（任选10个）为已知的，有公路连接的两个城市的距离是已
知的，求从一个城市到其他城市的最短路径及任意两个城市间的最短路径。

太强了
好郁闷你哦

Way.h
const int SIZE = 20;
const int INCREMENT = 10;
struct Car
{ int NO;
int time;
};

//队列
template <class T>
class Queue
{
private:
T *base;
int max_size;
int head,tail;
public:
Queue();
~Queue();
void InQue(T elem);
T* OutQue();
};

//栈
template <class U>
class Stack
{
private:
U *base;
int max_size;
int top;
public:
Stack(){;}
~Stack(){;}
void Set(int n);
void Pop();
void Push(U elem);
bool IsEmpty();
bool IsFull();
U* GetTop();
};

//Park
class Park
{
private:
Car car;
Stack<Car> ParkedCar;
Stack<Car> OutCar;
Queue<Car> Road;
int n,Mon;
public:
Park(){;}
bool Search();
void manage();
void PrintBill(Car &CurCar);
void Init();
void ParkIn();
};

Park.cpp
#include <iostream>
#include "Way.h"
using namespace std;
//Park
void Park::Init()
{
cout << "请输入车站最大停车数和每单位时间应收费：" <<endl;
cin >> n >> Mon;
ParkedCar.Set(n);
OutCar.Set(n);
}
void Park::manage()
{
cout << "请输入数据：" <<endl;
char Inf;
Car *temp;
do
{
cin >> Inf >> car.NO >> car.time;
switch (Inf)
{
case 'A' : ParkIn();
break;
case 'D' : if(!Search()) continue;
PrintBill(*ParkedCar.GetTop());
ParkedCar.Pop();
while(!ParkedCar.IsFull())
{
if(!OutCar.IsEmpty())
{
temp = OutCar.GetTop();
OutCar.Pop();
ParkedCar.Push(*temp);
}
else
{
temp = Road.OutQue();
ParkedCar.Push(*temp);
}
}
break;
case 'E' : cout << endl;
}
}while(Inf != 'E');
}
void Park::PrintBill(Car &CurCar)
{
int TimeDif,Money;
TimeDif = car.time-CurCar.time;
Money = Mon*TimeDif;
cout << "该车停留的时间和应付的费用为：" <<TimeDif << '\t' << Money << '\n';
}
void Park::ParkIn()
{
int Number;
if(!ParkedCar.IsFull())
{
ParkedCar.Push(car);
Number = car.NO;
cout << "该车停在车库的第" << Number << "位" <<endl;
}
else
{
Road.InQue(car);
Number = car.NO;
cout << "该车停在候车道的第" << Number <<"位" <<endl;
}
}
bool Park::Search()
{
Car *temp;
if(ParkedCar.IsEmpty())
{
cout << "车库已空" <<endl;
return false;
}
while(car.NO != ParkedCar.GetTop()->NO && !ParkedCar.IsEmpty())
{

temp = ParkedCar.GetTop();
ParkedCar.Pop();
OutCar.Push(*temp);
}
if(ParkedCar.IsEmpty())
{
cout << "此车不在车库。" <<endl;
while(!OutCar.IsEmpty())
{
temp = OutCar.GetTop();
OutCar.Pop();
ParkedCar.Push(*temp);
}
return false;
}
return true;
}
//Queue
template <class T>
Queue<T>::Queue()
{
base = new T [SIZE];
max_size = SIZE;
head=tail=0;
}
template <class T>
Queue<T>::~Queue()
{
delete []base;
}
template <class T>
void Queue<T>::InQue(T elem)
{
if(tail==max_size)
{
T *temp = new T [max_size];
int i;
for(i=0;i<max_size;i++)
temp[i] = base[i];
delete []base;
base = new T [max_size + INCREMENT];
for(i=0;i<max_size;i++)
base[i] = temp[i];
delete []temp;
max_size += INCREMENT;
}
base[tail++]=elem;
}
template <class T>
T *Queue<T>::OutQue()
{
T *temp = &base[head++];
return temp;
}
//Stack
template <class U>
void Stack<U>::Set(int n)
{
max_size = n;
base = new U[max_size+1];
top = 0;
}
template <class U>
void Stack<U>::Pop()
{
if(top>0)top--;
else cout<<"The Stack is Empty!"<<endl;
}
template <class U>
void Stack<U>::Push(U elem)
{
if(top==max_size)
cout<<"The Stack is Full!"<<endl;
else base[++top] = elem;
}
template <class U>
U *Stack<U>::GetTop()
{
U *temp = &base[top];
return temp;
}
template <class U>
bool Stack<U>::IsEmpty()
{
return top==0;

}
template <class U>
bool Stack<U>::IsFull()
{
return top==max_size;
}
//main
int main()
{
Park park;
park.Init();
park.manage();
return 0;
}