Erdos Numbers/조현태

느낀점 및 설명 ¶

끙..;; 처음에 문제를 보고 C++로 자료구조를 만들어서 해보자는 생각으로 했지만..
왠지 더 복잡해진듯 하다~! @.@
메모리를 좀 낭비하더라도 중복을 줄여서, 양이 많아질때의 연산을 줄여보자는 생각이었지만..
생각해보니 많아지면 그게 그거라는..후후후...
...난 뭐한거지..;;

어쨋든 책마다의 저자를 연결하는 자료구조 하나..
책 저자의 자료구조 하나..
이렇게 두개를 만들어서 나름대로는 연산이 쪼~~~끔 줄었다고 말하고 싶지만..
다만들고 나니 그것도 아닐지도..훗.. 괜한 고생이었나..;;

소스 ¶

main.cpp ¶

~cpp 
#include <iostream>
#include "class.h"

using namespace std;

char TARGET_NAME[]="Erdos, P.";

void main()
{
	int simulation;
	cout << "시뮬레이션 횟수를 입력하십시오.\n>>";
	cin >> simulation;
	for (;simulation>0;--simulation)
	{
		data_manager* datas=new data_manager();
		int number_books, number_writers;
		char temp[256];
		cout << "논문의 수와 탐색할 저자의 수를 입력하십시오.\n>>";
		cin >> number_books >> number_writers;
		cout << "논문의 저자와 제목을 입력하세요.\n";
		for (int i=0; i<number_books; ++i)
		{
			fflush(stdin);
			cin.getline(temp,256);
			datas->swallow(temp);
		}
		datas->process_erdos_number(TARGET_NAME);
		cout << "찾을 저자의 이름을 입력하세요.\n";
		for (int i=0; i<number_writers; ++i)
		{
			fflush(stdin);
			cin.getline(temp,256);
			int score=datas->get_score(temp);
			if (score!=0)
				cout << temp << " " << score << "\n";
			else if (-1!=score)
				cout << temp << " infinity\n";
			else
				cout << "저자를 찾을 수 없습니다.\n";
		}
		delete datas;
	}
}

class.h ¶

~cpp 
#define NULL 0

class human_data{
private:
	char* names;
	int score;
	int tuched;
	int number_line;
	int* line_numbers;
	void str_copy(char**, char*);
public:
	human_data(char* );
	~human_data();
	void input_line(int );
	void change_score(int );
	void get_passive();
	int get_score();
	char* get_name();
	int get_number_line();
	int get_line_number(int );
	int get_tuched();
};

class line_data{
private:
	human_data* include_data;
	line_data* prv;
	line_data* next;
public:
	line_data(human_data* , line_data* );
	~line_data();
	void link(line_data* );
	human_data* get_data();
	line_data* get_next();
};

class data_manager{
private:
	int number_mans, number_books;
	human_data** mans;
	line_data** books;
	void creat_book();
	void creat_man(char* );
	int str_cmp(char* , char* );
	int such_man(char* );
	void str_swallow(char* );
public:
	data_manager();
	~data_manager();
	void swallow(char* );
	void process_erdos_number(human_data* );
	void process_erdos_number(char* );
	int get_score(char* );
};

class.cpp ¶

~cpp 
#include "class.h"

void human_data::str_copy(char** target, char* original)
{
	register int i=0;
	while (0!=original[i])
		++i;
	*target=new char[i+1];
	for (register int j=0; j<=i; ++j)
		(*target)[j]=original[j];
}
human_data::human_data(char* input_names)
{
	str_copy(&names,input_names);
	score=0;
	tuched=0;
	number_line=0;
	line_numbers=NULL;
}
human_data::~human_data()
{
	if (NULL!=names)
		delete names;
	if (line_numbers!=NULL)
		delete line_numbers;
}
void human_data::input_line(int input_line_number)
{
	int* temp_numbers=new int[number_line+1]; 
	for (register int i=0; i<number_line; ++i) 
		temp_numbers[i]=line_numbers[i]; 
	temp_numbers[number_line]=input_line_number;
	if (NULL!=line_numbers)
		delete line_numbers;
	line_numbers=temp_numbers;
	++number_line; 
}
void human_data::change_score(int new_score)
{
	score=new_score;
	if (0==tuched)
		tuched=1;
}
void human_data::get_passive()
{
	tuched=-1;
}
int human_data::get_score()
{
	return score;
}
char* human_data::get_name()
{
	return names;
}
int human_data::get_number_line()
{
	return number_line;
}
int human_data::get_line_number(int where)
{
	if (0<=where && where<number_line)
		return line_numbers[where];
	return -1;
}
int human_data::get_tuched()
{
	return tuched;
}


line_data::line_data(human_data* input_data, line_data* input_prv)
{
	include_data=input_data;
	prv=input_prv;
	if (NULL!=prv)
		prv->link(this);
	next=NULL;
}
line_data::~line_data()
{
	if (NULL!=next)
		delete next;
	if (NULL!=prv)
		delete prv;
}
void line_data::link(line_data* input_next)
{
	next=input_next;
}
human_data* line_data::get_data()
{
	return include_data;
}
line_data* line_data::get_next()
{
	return next;
}


void data_manager::creat_book()
{
	line_data** temp_books=new line_data*[number_books+1]; 
	for (register int i=0; i<number_books; ++i) 
		temp_books[i]=books[i]; 
	temp_books[number_books]=NULL;
	if (NULL!=books)
		delete books;
	books=temp_books;
	++number_books; 
}
void data_manager::creat_man(char* input_name)
{
	human_data** temp_mans=new human_data*[number_mans+1]; 
	for (register int i=0; i<number_mans; ++i) 
		temp_mans[i]=mans[i]; 
	temp_mans[number_mans]=new human_data(input_name);
	if (NULL!=mans)
		delete mans;
	mans=temp_mans;
	++number_mans; 
}
int data_manager::str_cmp(char* target_a, char* target_b)
{
	for (register int i=0; 0!=target_b[i] ; ++i)
	{
		if (0==target_a[i])
			return -1;
		if (target_a[i]!=target_b[i])
			return -1;
	}
	return 0;
}
int data_manager::such_man(char* target_name)
{
	for (register int i=0; i<number_mans; ++i)
	{
		if (0==str_cmp(target_name,mans[i]->get_name()))
			return i;
	}
	return -1;
}
void data_manager::str_swallow(char* tagert_line)
{
	human_data* temp_human;
	int temp_man_number=such_man(tagert_line);
	if (-1==temp_man_number)
	{
		creat_man(tagert_line);
		temp_human=mans[number_mans-1];
	}
	else
		temp_human=mans[temp_man_number];
	temp_human->input_line(number_books-1);

	line_data* temp_book=books[number_books-1];
	if (NULL==temp_book)
	{
		books[number_books-1]=new line_data(temp_human,NULL);
	}
	else
	{
		while (NULL!=temp_book->get_next())
			temp_book=temp_book->get_next();
		new line_data(temp_human,temp_book);
	}
}

data_manager::data_manager()
{
	number_mans=0;
	number_books=0;
	mans=NULL;
	books=NULL;
}
data_manager::~data_manager()
{
	for (register int i=0; i<number_books; ++i)
		delete books[i];
	if (NULL!=books)
		delete books;
	for (register int i=0; i<number_mans; ++i)
		delete mans[i];		
	if (NULL!=mans)
		delete mans;
}
void data_manager::swallow(char* input_line)
{
	creat_book();
	int copy_start=-1,suched=0,such_point=0;
	while (0!=input_line[such_point])
	{
		if (0==suched && ' '!=input_line[such_point])
		{
			suched=1;
			copy_start=such_point;
		}
		else if ('.'==input_line[such_point] && (','==input_line[such_point+1] || ':'==input_line[such_point+1]))
		{
			suched=0;
			++such_point;
			input_line[such_point]=0;
			str_swallow(&input_line[copy_start]);
		}
		++such_point;
	}
}
void data_manager::process_erdos_number(human_data* target_man)
{
	int target_number_line=target_man->get_number_line();
	for (register int i=0; i<target_number_line; ++i)
	{
		line_data* temp_book=books[target_man->get_line_number(i)];
		while (NULL!=temp_book)
		{
			if (temp_book->get_data()->get_score()>target_man->get_score()+1 || 0==temp_book->get_data()->get_tuched())
			{
				temp_book->get_data()->change_score(target_man->get_score()+1);
				process_erdos_number(temp_book->get_data());
			}
			temp_book=temp_book->get_next();
		}
	}
}
void data_manager::process_erdos_number(char* target_name)
{
	int target_man_number=such_man(target_name);
	if (-1!=target_man_number)
	{
		mans[target_man_number]->get_passive();
		process_erdos_number(mans[target_man_number]);
	}
}
int data_manager::get_score(char* target_name)
{
	int temp_target_number=such_man(target_name);
	if (-1==temp_target_number)
		return -1;
	return mans[temp_target_number]->get_score();
}

저에게 할말 ¶

AOI ErdosNumbers