알고리즘 서론 코드 제2 1 장 교차 집합 하지 않 는 데이터 구조 에 사용 된다.
21.2 교차 하지 않 는 집단 링크 표시
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct set_type *set;
struct set_node {
void *key;
struct set_node *next;
struct set_node *representative; //
};
struct set_type {
struct set_node *head;
struct set_node *tail;
int num;
};
void set_node_ini(struct set_node *x, void *key)
{
x->key = key;
x->next = NULL;
x->representative = NULL;
}
set set_create(void *key)
{
set s = malloc(sizeof(struct set_type));
struct set_node *x = malloc(sizeof(struct set_node));
set_node_ini(x, key);
s->head = x;
s->tail = x;
s->num = 1;
x->representative = x;
return s;
}
struct set_node *find_set(set s)
{
return s->head->representative;
}
void update_representative(struct set_node *head,
struct set_node *representative)
{
struct set_node *p = head;
while (p != NULL) {
p->representative = representative;
p = p->next;
}
}
// ,
void set_union(set sa, set sb)
{
if (sa->num < sb->num) {
update_representative(sa->head, sb->head);
sb->tail->next = sa->head;
sa->head = sb->head;
} else {
update_representative(sb->head, sa->head);
sa->tail->next = sb->head;
sa->tail = sb->tail;
}
sa->num += sb->num;
}
void set_destroy(set s, void (*free_key) (void *))
{
free_key(s->head->key);
free(s->head);
free(s);
}
struct edge {
char u;
char v;
};
int main()
{
// 21-1
char vertex[] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j' };
set s[256] = { NULL };
struct edge edge_array[] = { {'b', 'd'}, {'e', 'g'}, {'a', 'c'},
{'h', 'i'}, {'a', 'b'}, {'e', 'f'}, {'b', 'c'}
};
int vertex_num = sizeof(vertex) / sizeof(vertex[0]);
for (int i = 0; i < vertex_num; i++) {
char *c = malloc(sizeof(char));
*c = vertex[i];
s[(int)vertex[i]] = set_create(c);
}
//
for (unsigned i = 0; i < sizeof(edge_array) / sizeof(edge_array[0]);
i++) {
set su = s[(int)edge_array[i].u];
set sv = s[(int)edge_array[i].v];
if (find_set(su) != find_set(sv)) {
set_union(su, sv);
}
}
//
char str_set[256][256] = { {0} };
for (int i = 0; i < vertex_num; i++) {
char *pc = find_set(s[(int)vertex[i]])->key;
int len = strlen(str_set[(int)*pc]);
str_set[(int)*pc][len] = vertex[i];
}
printf(" :
");
for (int i = 0; i < vertex_num; i++) {
if (strcmp(str_set[(int)vertex[i]], "") != 0) {
printf("%s
", str_set[(int)vertex[i]]);
}
}
for (int i = 0; i < vertex_num; i++) {
set sv = s[(int)vertex[i]];
set_destroy(sv, free);
}
return 0;
}
21.3 교차 하지 않 고 숲 을 모으다.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct set_type *set;
struct set_node {
void *key;
int rank;
struct set_node *parent;
};
void set_node_ini(struct set_node *x, void *key)
{
x->key = key;
x->rank = 0;
x->parent = NULL;
}
struct set_type {
struct set_node *root;
};
set set_create(void *key)
{
set s = malloc(sizeof(struct set_type));
s->root = malloc(sizeof(struct set_node));
set_node_ini(s->root, key);
s->root->parent = s->root;
s->root->rank = 0;
return s;
}
void link(struct set_node *x, struct set_node *y)
{
if (x->rank > y->rank) {
y->parent = x;
} else {
x->parent = y;
if (x->rank == y->rank) {
++y->rank;
}
}
}
struct set_node *find_set_path_compression(struct set_node *x)
{
if (x != x->parent) {
x->parent = find_set_path_compression(x->parent);
}
return x->parent;
}
struct set_node *find_set(set s)
{
return find_set_path_compression(s->root);
}
void set_destroy(set s, void (*free_key) (void *))
{
free_key(s->root->key);
free(s->root);
free(s);
}
void set_union(set sa, set sb)
{
link(find_set(sa), find_set(sb));
}
struct edge {
char u;
char v;
};
int main()
{
// 21-1
char vertex[] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j' };
set s[256] = { NULL };
struct edge edge_array[] = { {'b', 'd'}, {'e', 'g'}, {'a', 'c'},
{'h', 'i'}, {'a', 'b'}, {'e', 'f'}, {'b', 'c'}
};
int vertex_num = sizeof(vertex) / sizeof(vertex[0]);
for (int i = 0; i < vertex_num; i++) {
char *c = malloc(sizeof(char));
*c = vertex[i];
s[(int)vertex[i]] = set_create(c);
}
//
for (unsigned i = 0; i < sizeof(edge_array) / sizeof(edge_array[0]);
i++) {
set su = s[(int)edge_array[i].u];
set sv = s[(int)edge_array[i].v];
if (find_set(su) != find_set(sv)) {
set_union(su, sv);
}
}
//
char str_set[256][256] = { {0} };
for (int i = 0; i < vertex_num; i++) {
char *pc = find_set(s[(int)vertex[i]])->key;
int len = strlen(str_set[(int)*pc]);
str_set[(int)*pc][len] = vertex[i];
}
printf(" :
");
for (int i = 0; i < vertex_num; i++) {
if (strcmp(str_set[(int)vertex[i]], "") != 0) {
printf("%s
", str_set[(int)vertex[i]]);
}
}
for (int i = 0; i < vertex_num; i++) {
set sv = s[(int)vertex[i]];
set_destroy(sv, free);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.