[데이터 구조 (C 언어)] 도 론

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<time.h>
#define ERROR 0
#define OK 1
#define Overflow 2      //  
#define Underflow 3     //  
#define NotPresent 4    //     
#define Duplicate 5     //     
#define INFTY 10000     //        
typedef int Status;
typedef int ElemType;
/***********************************************************************       ****************************************************************/
/*      */
typedef struct mGraph
{
     
	ElemType **a;       //    
	int n;              //       
	int e;              //      
	int noEdge;         //         
}MGraph;
/*   */
Status Init(MGraph *mg, int nSize, ElemType noEdgeValue)
{
     
	mg->n = nSize;
	mg->noEdge = noEdgeValue;
	mg->e = 0;
	mg->a = (ElemType**)malloc(nSize * sizeof(ElemType*));
	if (!(mg->a))  return ERROR;
	for (int i = 0; i < nSize; i++)                 //       
	{
     
		mg->a[i] = (ElemType*)malloc(nSize * sizeof(ElemType));
		for (int j = 0; j < mg->n; mg->a[i][j++] = mg->noEdge);        
		mg->a[i][i] = 0;
	}
	return OK;
}
/*  */
void Destory(MGraph *mg)
{
     
	for (int i = 0; i < mg->n; free(mg->a[i++]));    //  n          
	free(mg->a);                                     //             
}
/* */
Status Exist(MGraph *mg, int u, int v)
{
     
	if (u<0 || v<0 || u>mg->n - 1 || v>mg->n - 1 || u == v || mg->a[u][v] == mg->noEdge) return ERROR;
	return OK;
}
/* */
Status Insert(MGraph *mg, int u, int v, ElemType w)
{
     
	if (u<0 || v<0 || u>mg->n - 1 || v>mg->n - 1 || u == v ) return ERROR;   //      
	if (mg->a[u][v] != mg->noEdge) return Duplicate;                         //          
	mg->a[u][v] = w;                                                         //    
	mg->e++;                                                                 //    1
	return OK;
}
/* */
Status Remove(MGraph *mg,int u,int v)
{
     
	if (u<0 || v<0 || u>mg->n - 1 || v>mg->n - 1 || u == v) return ERROR;     //      
	if (mg->a[u][v] == mg->noEdge) return NotPresent;                         //         
	mg->a[u][v] = mg->noEdge;                                                 //   
	mg->e--;                                                                  //    1
	return OK;
}
/*DFS      */
void DFS(int v, int visited[], MGraph *mg)
{
     
	printf("%d ", v);
	visited[v] = 1;                          //          
	for (int i = 0; i < (mg->n); i++)
		if (Exist(mg, v, i) && visited[i] == 0)
			DFS(i, visited, mg);            //    
}
void DFSGraph(MGraph *mg)
{
     
	int *visited = (int *)malloc((mg->n) * sizeof(int));//           
	for (int i = 0; i < mg->n; visited[i++] = 0);   //       
	for (int i = 0; i < mg->n; i++)
		if (!visited[i])
			DFS(i, visited, mg);                    //         
	free(visited);                                  //      
	printf("
"
); } /*BFS */ typedef struct queue // { int front; // int rear; // int maxSize; // ElemType *element; // }Queue; void Create(Queue *Q, int mSize)// { Q->maxSize = mSize; Q->front = Q->rear = 0; Q->element = (ElemType *)malloc(sizeof(ElemType)*mSize); } void DestoryQueue(Queue *Q)// { Q->maxSize = 0; free(Q->element); Q->rear = Q->front = 0; } int IsEmpty(Queue *Q)// { return Q->front == Q->rear; } int IsFULL(Queue *Q)// { return (Q->rear + 1) % Q->maxSize == Q->front; } Status EnQueue(Queue *Q, ElemType *x)// { if (IsFULL(Q)) return ERROR; // Q->rear = (Q->rear + 1) % Q->maxSize; // Q->element[Q->rear] = x; // return OK; } Status DeQueue(Queue *Q)// { if (IsEmpty(Q)) return ERROR; Q->front = (Q->front + 1) % Q->maxSize; // return OK; } Status Front(Queue *Q, ElemType *x)// { if (IsEmpty(Q)) return ERROR; *x = Q->element[(Q->front + 1) % Q->maxSize]; return OK; } void BFS(int v, int visited[], MGraph *mg) { Queue q; Create(&q, mg->n); printf("%d ", v); visited[v] = 1; EnQueue(&q, v); while (!IsEmpty(&q)) { Front(&q, &v); DeQueue(&q); for (int i = 0; Exist(mg, v, i); i++) // v { if (!visited[i]) // , { visited[i] = 1; printf("%d ", i); EnQueue(&q, i); } } } } void BFSGraph(MGraph *mg) { int *visited = (int *)malloc((mg->n) * sizeof(int));// for (int i = 0; i < mg->n; visited[i++] = 0); // for (int i = 0; i < mg->n; i++) if (!visited[i]) BFS(i, visited, mg); free(visited); } /*********************************************************************** *****************************************************************/ /* */ typedef struct eNode { int adjVex; // u ElemType w; // struct eNode* nextArc; // }ENode; /* */ typedef struct lGraph { int n; // int e; // ENode **a; }LGraph; /* */ Status Init1(LGraph *lg, int nSize) { lg->n = nSize; lg->e = 0; lg->a = (ENode**)malloc(sizeof(ENode*)*nSize); if (!lg->a) return ERROR; else { for (int i = 0; i < lg->n; i++) lg->a[i] = NULL; return OK; } } /* */ void Destory1(LGraph *lg) { ENode *p, *q; for (int i = 0; i < lg->n; i++) { p = lg->a[i]; //p i q = p; while (p) // i { p = p->nextArc; free(p); q = p; } } free(lg->a); // } /* */ Status Exist1(LGraph *lg, int u, int v) { ENode *p; if (u<0 || v<0 || u>lg->n - 1 || v>lg->n - 1 || u == v) return ERROR; p = lg->a[u]; while (p&&p->adjVex != v) p = p->nextArc; if (!p) return ERROR; return OK; } /* u( ),v( ) w */ Status Insert1(LGraph *lg,int u,int v,ElemType w) { ENode *p; if(u<0 || v<0 || u>lg->n - 1 || v>lg->n - 1 || u == v) return ERROR; if (Exist(lg, u, v)) return Duplicate; p = (ENode *)malloc(sizeof(ENode)); /* */ p->adjVex = v; p->w = w; /* */ p->nextArc = lg->a[u]; // lg->a[u] = p; /* */ lg->e++; return OK; } /* */ Status Remove1(LGraph *lg, int u, int v) { ENode *p, *q; if (u<0 || v<0 || u>lg->n - 1 || v>lg->n - 1 || u == v) return ERROR; p = lg->a[u], q = NULL; while (p&&p->adjVex != v) // { q = p; p = p->nextArc; } if (!p) return NotPresent; //p if (q) q->nextArc = p->nextArc; // else lg->a[u] = p->nextArc; free(p); lg->e--; return OK; } /*DFS */ void DFS1(int v, int visited[], LGraph *lg) { ENode *w; printf("%d ", v); visited[v] = 1; // for (w = lg->a[v]; w; w = w->nextArc) if (!visited[w->adjVex]) DFS(w->adjVex, visited, lg); } void DFSGraph1(LGraph *lg) { int *visited = (int *)malloc((lg->n) * sizeof(int));// for (int i = 0; i < lg->n; visited[i++] = 0); // for (int i = 0; i < lg->n; i++) if (!visited[i]) DFS(i, visited, lg); // free(visited); // } /*BFS */ void BFS1(int v, int visited[], LGraph *lg) { ENode *w; Queue q; Create(&q, lg->n); printf("%d ", v); visited[v] = 1; EnQueue(&q, v); while (!IsEmpty(&q)) { Front(&q, &v); DeQueue(&q); for (w = lg->a[v]; w;w=w->nextArc) // v { if (!visited[w->adjVex]) // , { visited[w->adjVex] = 1; printf("%d ", w->adjVex); EnQueue(&q, w->adjVex); } } } } void BFSGraph1(LGraph *lg) { int *visited = (int *)malloc((lg->n) * sizeof(int));// for (int i = 0; i < lg->n; visited[i++] = 0); // for (int i = 0; i < lg->n; i++) if (!visited[i]) BFS(i, visited, lg); free(visited); } /*********************************************************************** *********************************************************************/ int Choose(int *d, int *s, int n) { ElemType min=INFTY; // INITY int minpos=-1; // -1 for (int i = 0; i < n; i++) // d[i] if (d[i] < min && !s[i]) { min = d[i]; minpos = i; } return minpos; // } Status Dijkstra(int v,int u,MGraph *mg) { int k, *s = (int*)malloc((mg->n) * sizeof(int)),*path= (int*)malloc((mg->n) * sizeof(int)); ElemType *d = (ElemType*)malloc((mg->n) * sizeof(ElemType)), pass[20] = { 0}; if (v<0 || v>mg->n - 1) return ERROR; for (int i = 0; i < mg->n; i++) // { s[i] = 0; //s d[i] = mg->a[v][i]; //d v , d[i] v i //printf("%d ", d[i]); if (i != v && d[i] < INFTY) path[i] = v; // else path[i] = -1; // -1 } s[v] = -1; d[v] = 0; //v v 0 for (int i = 1; i < mg->n-1; i++) { k = Choose(d, s, mg->n); // d[i], if (k == -1) continue; s[k] = 1; for(int j=0;j<mg->n;j++) // d path if (!s[j] && d[k] + mg->a[k][j] < d[j]) { d[j] = d[k] + mg->a[k][j]; path[j] = k; } } k = 0; printf(">>> %d %d :", v, u); // for (int i = u; i != v; i = path[i]) pass[k++]=i; for(;k>0;k--) printf("%d -> ", pass[k]); printf("%d", u); printf("
>>> :%d
"
, d[u]); // free(s); // free(path); free(d); return OK; } int main() { MGraph *mg = (MGraph*)malloc(sizeof(MGraph)); LGraph *lg = (LGraph*)malloc(sizeof(LGraph)); int nSize = 0, noEdgeValue = 0, u, v, w, operation = 0; char judge,tmpbuf[] = { 0 }; _tzset(); // _strdate(tmpbuf); printf(" : %s
"
, tmpbuf); system("title MADE BY YQC"); label: printf("*1.
*2.
*3.
—— :"
); scanf("%d", &operation); switch (operation) { case 1: system("CLS"); while (1) { u = 0; v = 0; printf("### (1. 2. 3. 4. 5. 6. 7.DFS 8.BFS 9. ):"); scanf("%d", &operation); switch (operation) { case 1: printf(" :"); scanf("%d", &nSize); if (Init(mg, nSize, noEdgeValue)) printf(" ……
"
); else printf("WARNING:
"
); break; case 2: printf(" :"); scanf("%d", &u); printf(" :"); scanf("%d", &v); if (Exist(mg, u, v) == 1) printf(" %d %d
"
, u, v); else if (Exist(mg, u, v) == 4) printf(" "); else printf("
"
); break; case 3: printf(" :"); scanf("%d", &u); printf(" :"); scanf("%d", &v); printf(" :"); scanf("%d", &w); if (Insert(mg, u, v, w) == OK) printf("
"
); else if (Insert(mg, u, v, w) == Duplicate) printf("
"
); else printf("WARNING:
"
); break; case 4: printf(" :"); scanf("%d", &u); printf(" :"); scanf("%d", &v); if (Remove(mg, u, v)==OK) printf("
"
); else if (Remove(mg, u, v) == NotPresent) printf("
"
); else printf("WARNING:
"
); break; case 5: Destory(mg); break; case 6: exit(0); case 7: printf(" :
"
); DFSGraph(mg); break; case 8: printf(" :
"
); BFSGraph(mg); printf("
"
); break; case 9: while (1) { printf(" , (Y/N):
"
); scanf("%c", &judge); if (judge == 'y' || judge == 'Y') { system("CLS"); if(mg->n) Destory(mg); goto label; } if (judge == 'n' || judge == 'N') break; } break; label1: break; default: printf("WARNING: !!!
"
); break; } } case 2: system("CLS"); while (1) { u = 0; v = 0; printf("### (1. 2. 3. 4. 5. 6. 7.DFS 8.BFS 9. ):"); scanf("%d", &operation); switch (operation) { case 1: printf(" :"); scanf("%d", &nSize); if (Init1(lg, nSize)) printf(" ……
"
); else printf("WARNING:
"
); break; case 2: printf(" :"); scanf("%d", &u); printf(" :"); scanf("%d", &v); if (Exist1(lg, u, v) == 1) printf(" %d %d
"
, u, v); else printf("
"
); break; case 3: printf(" :"); scanf("%d", &u); printf(" :"); scanf("%d", &v); printf(" :"); scanf("%d", &w); if (Insert1(lg, u, v, w)==OK) printf("
"
); else if (Insert1(lg, u, v, w) == Duplicate) printf("
"
); else printf("WARNING:
"
); break; case 4: printf(" :"); scanf("%d", &u); printf(" :"); scanf("%d", &v); if (Remove1(lg, u, v) == OK) printf("
"
); else if (Remove1(lg, u, v) == NotPresent) printf("
"
); else printf("WARNING:
"
); break; case 5: Destory1(lg); break; case 6: exit(0); case 7: printf(" :
"
); DFSGraph1(lg); break; case 8: printf(" :
"
); BFSGraph1(lg); printf("
"
); break; case 9: while (1) { printf(" , (Y/N):
"
); scanf("%c", &judge); if (judge == 'y' || judge == 'Y') { system("CLS"); if (lg->a) Destory1(lg); goto label; } if (judge == 'n' || judge == 'N') break; } break; default: printf("WARNING: !!!
"
); break; } } case 3: system("CLS"); label3: printf("> ~~~
"
); printf("> :"); scanf("%d", &nSize); if (Init(mg, nSize, INFTY)) printf("> ……
"
); else printf(">WARNING:
"
); while (1) { printf(" 1.
2.
3.
4.
>> :"
); scanf("%d", &operation); switch (operation) { case 1: system("CLS"); printf(">>> :"); scanf("%d", &u); printf(">>> :"); scanf("%d", &v); printf(">>> (km):"); scanf("%d", &w); if (Insert(mg, u, v, w) == OK) printf("—— %d %d
"
,u,v); else if (Insert(mg, u, v, w) == Duplicate) printf("——
"
); else printf("——WARNING:
"
); break; case 2: system("CLS"); printf(" :"); scanf("%d", &v); printf(" :"); scanf("%d", &u); Dijkstra(v, u, mg); break; case 3: system("CLS"); printf(" :
"
); DFSGraph(mg); break; case 4: system("CLS"); while (1) { printf(" , (Y/N):
"
); scanf("%c", &judge); if (judge == 'y' || judge == 'Y') { system("CLS"); Destory(mg); goto label3; } if (judge == 'n' || judge == 'N') break; } break; default: system("CLS"); printf("WARNING: !!!
"
); break; } } default: printf("WARNING: !!!
"
); break; } return 0; }

좋은 웹페이지 즐겨찾기