[데이터 구조 (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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
데이터 구조 학습 - 단일 체인 테이블 ADT(순서화)텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
