16. 3181 : 족보 만들기

1. data node 생성

struct data {
	char name[13];
	data* parent, * next, * child;
	data() {
		parent = next = child = NULL;
	}
	data(char na[], data* pa, data* ne, data* ch) {
		strcpy(name, na), parent = pa, next = ne, child = ch;
	}
}*root, *cur;

2. strcmp 문자열 비교 함수

int strcmp(const char* s, const char* t) {
	while (*s && *s == *t) ++s, ++t;
	return *s - *t;
}

3. mystrcpy 문자열 복사 함수

/// 문자열 dest에 문자열 src를 복사
void mystrcpy(char* dest, const char* src) {
	while ((*dest++ = *src++));
}

4. init_user() : 초기화를 위해 구현

void init_user() {
	if (root != NULL) del_all(root);
	root = cur = new data("root", NULL, NULL, new data());
	root->parent = root;
}

5. Add_child(char name[]) : 노드 추가

void Add_child(char name[]) {
	data* p = cur->child;
	while (p->next != NULL && strcmp(p->next->name, name) < 0)
		p = p->next;
	if (p->next != NULL && strcmp(p->next->name, name) == 0)
		return;
	p->next = new data(name, cur, p->next, new data());
}

6. Delete(char name[]) : 노드 삭제

int Delete(char name[]) {
	if (strcmp(name, "ALL") == 0) return del_all(cur->child);
	return del_find(cur->child, name);
}

7. del_all : 자식 노드 모두 삭제

int del_all(data* p) {
	int cnt = 0;
	while (p->next != NULL) {
		cnt += del_all(p->next->child) + 1;
		delete p->next->child;
		data* tmp = p->next;
		p->next = tmp->next;
		delete tmp;
	}
	return cnt;
}

8. del_fine : 삭제할 대상을 찾는다

int del_find(data* p, char name[]) {
	int cnt = 0, len = strlen(name);
	if (p->next == NULL || strncmp(p->next->name, name, len) > 0)
		return 0;
	cnt += del_find(p->next, name);
	if (strncmp(p->next->name, name, len) == 0) {
		data* tmp = p->next;
		cnt += del_all(tmp->child) + 1;
		p->next = tmp->next;
		delete tmp->child;
		delete tmp;
	}
	return cnt;
}

9. Move(char name[]) : 
1) name[]이 "root"인 경우에는 최상위(root)로 이동한다.
2) name[]이 "parent"인 경우에는 부모 노드로 이동한다.

3) name[]이 "first"인 경우에는 사전순으로 가장 빠른 이름을 가진 자식 노드로 이동한다.

4) 그렇지 않은 경우 name[]으로 시작하는 사전순으로 가장 빠른 이름을 가진 자식 노드로 이동한다.

void Move(char name[]) {
	if (strcmp(name, "root") == 0) cur = root;
	else if (strcmp(name, "parent") == 0) cur = cur->parent;
	else if (cur->child->next != NULL) {
		data* p = cur->child->next;
		if (strcmp(name, "first") == 0) cur = p;
		else {
			int len = strlen(name);
			while (p->next != NULL && strcmp(p->name, name) < 0)
				p = p->next;
			if (strncmp(p->name, name, len) == 0) cur = p;
		}
	}
}

10. count(data* p, char name[])

int count(data* p, char name[]) {
	if (p == NULL) return 0;
	int len = strlen(name);
	int cnt = count(p->next, name) + count(p->child->next, name);
	if (strncmp(p->name, name, len) == 0) cnt++;
	return cnt;
}

11. Count(char name[])

int Count(char name[]) {
	if (strcmp(name, "ALL") == 0) name[0] = 0;
	return count(cur->child->next,name);
}