문제 풀이 기록

3610 단어
6 도 공간
초보 가 기록 을 만 들 었 을 뿐 코드 는 참고 성 이 없 으 니 대신 생략 하 세 요.
/ / 데이터 구조 학습 기록 PTA 링크
`
#include 
#include 

#define MAXN 10001			//      
#define INFINITY 65535        /* ∞              65535*/
#define ERROR 0 

int G[MAXN][MAXN], Nv, Ne;
int Visited[MAXN];/*   V    */
typedef int Vertex;

struct Node {
	int Data;
	struct Node *Next;
};
 
struct QNode {
	struct Node *rear;
	struct Node *front;
};
typedef struct QNode *Queue;

int IsEmpty(Queue Q);
Queue CreateQueue();
int DeleteQ(Queue PtrQ);
void InsertQ(int item, Queue PtrQ);

void BuildGraph ();
void SDS ();
bool IsEdge(Vertex V, Vertex W);
int BFS (Vertex V);
void Build ();

int main()
{
	//Build(); 
	BuildGraph();
	for (int i = 0; i < MAXN; i++) {
		Visited[i] = false; 
	}
	SDS();
	return 0;
}

void Build () //Build()    
{	//         
	int i, j, v1, v2; 
	//     
	//scanf("%d %d", &Nv, &Ne);
	Nv = 10; Ne = 9;
	G[0][0] = INFINITY;
	for (i=1; i<=Nv; i++) {
		for (j=1; j<=Nv; j++) {
			G[i][j] = INFINITY;
		}
	}
	//    
	G[1][2] = 1; G[2][1] = 1;
	G[2][3] = 1; G[3][2] = 1;
	G[3][4] = 1; G[4][3] = 1;
	G[4][5] = 1; G[5][4] = 1;
	G[5][6] = 1; G[6][5] = 1;
	G[6][7] = 1; G[7][6] = 1;
	G[7][8] = 1; G[8][7] = 1;
	G[8][9] = 1; G[9][8] = 1;
	G[9][10] = 1; G[10][9] = 1;

/*	for (i=1; i<=Ne; i++) {
		scanf("%d %d", &v1, &v2);
		G[v1][v2] = 1;
		G[v2][v1] = 1;
	} */
	//      
}
void BuildGraph ()
{	//         
	int i, j, v1, v2; 
	//     
	scanf("%d %d", &Nv, &Ne);
	G[0][0] = INFINITY;
	for (i=1; i<=Nv; i++) {
		for (j=1; j<=Nv; j++) {
			G[i][j] = INFINITY;
		}
	}
	//    
	for (i=1; i<=Ne; i++) {
		scanf("%d %d", &v1, &v2);
		G[v1][v2] = 1;
		G[v2][v1] = 1;
	} 
	//      
}

void SDS ()
{
	int V, count;
	double out;
	for (V=1; V<=Nv; V++) {
	for (int i = 0; i < MAXN; i++) {
		Visited[i] = false; 
	}
		count = BFS(V);
		double f=100.00*count/Nv;
		printf("%d: %.02f%%
", V, f); //printf("%d: %d
", V, count); out = count/Nv; //printf("%d: %.2lf
", V, out); //Output(count/Nv); } /* V=4; count = BFS(V); printf("%d %d
", V, count); */ } /* IsEdge(Graph, V, W) Graph , W V 。 */ bool IsEdge(Vertex V, Vertex W) { return G[V][W]front == NULL); }; Queue CreateQueue() { Queue PtrQ; PtrQ = (Queue)malloc(sizeof(struct QNode)); struct Node *rear; struct Node *front; rear = (Node*)malloc(sizeof(struct Node)); rear = NULL; front = (Node*)malloc(sizeof(struct Node)); front = NULL; PtrQ->front = front; PtrQ->rear = rear; return PtrQ; }; int DeleteQ(Queue PtrQ) { struct Node *FrontCell; int FrontElem; if (IsEmpty(PtrQ)) { printf(" "); return ERROR; } FrontCell = PtrQ->front; if (PtrQ->front == PtrQ->rear) PtrQ->front = PtrQ->rear = NULL; else { PtrQ->front = PtrQ->front->Next; } FrontElem = FrontCell->Data; free(FrontCell); return FrontElem; } void InsertQ(int item, Queue PtrQ) { struct Node *FrontCell; FrontCell = (Node*)malloc(sizeof(struct Node)); FrontCell->Data = item; FrontCell->Next = NULL; if (IsEmpty(PtrQ)) { PtrQ->front = FrontCell; PtrQ->rear = FrontCell; } else { PtrQ->rear->Next = FrontCell; PtrQ->rear = FrontCell; } };

좋은 웹페이지 즐겨찾기