2022-1
22-04-17 (데이터 구조)
오로시
2022. 4. 17. 16:40
데이터 구조
Binary tree
lemma -1 (일반트리)
n개의 node를 갖는 , k-degree tree에서 child를 가리키는 pointer n*k개 중 (n(k-1)+1) 개가 NULL이다. (NULL의 개수)
- Level 이 i 인 node는 최대 2^(i -1) 개 이다.
- Height 가 k인 binary tree의 최대 node 수(full binary tree의 노드 수)는 (2^k -1 )개 이다.
- Node 수가 n 인 full binary tree 의 height는 log2(n+1)이다. --> 꽉 채워진 height는 log 값으로 나타난다.
lemma -2 (바이너리트리)
어떤 binary tree 에서 degree가 0인 node(leaf)의 수는 dgree가 2인 node수 보다 1개 많다.
n0= n2+1
링크드 리스트 연습
#include <iostream>
using namespace std;
//linked list practice
class node {
public: // public에 안하면, 저 밑에서 cout 할때 사용 못함
string name;
double score;
node *link;
void set_data(string s , double n);
};
void node::set_data(string s , double n){
name = s;
score = n;
}
class my_list{ // 괄호 없다.
private:
node *head , *tail;
public:
my_list();//constructor
void add_to_head(node t);
void add_to_tail(node t);
node delete_from_head();
int num_nodes();
bool list_empty();
double score_sum();
double get_score(string name);
int remove_a_node(string name);
};
my_list::my_list(){
head = NULL;
tail = NULL;
}
void my_list::add_to_head(node t){
node *p;
p = new node;
(*p) = t;
p->link = head;
head = p;
if ( tail == NULL)
tail = p;
}
//head 랑 tail 이랑 좀 다르다.
//tail은 이전 상태가 empty였냐 아니엇냐가 중요하다.
//head는 어차피 이전 노드가 없으므로, 신경 안써도 되지만,
//tail != NULL이면 tail의 link를 추가되는 노드에 연결시켜 줘야 한다.
void my_list::add_to_tail(node t){
node *p;
p = new node;
(*p) = t;
p->link = NULL;
//만약 이전 상태가 empty 가 아니었다면
if (tail != NULL)
tail -> link = p;
else
head = p;
tail = p; // 이게 가장 마지막에 와야한다 그렇지 않으면
//tail 이 먼저 변경 되어 값이 망가질 것이다.
}
node my_list::delete_from_head(){
node tmp;
node *t;
tmp = (*head);
t = head;
head = head->link;
delete t;
//예외 상황 처리 하는 거 꼭 잊지 말자!!!
//삭제 후 empty가 되면, tail 값도 조정
if(head == NULL)
tail =NULL;
return tmp;
}
int my_list::num_nodes(){
int count=0;
node *t;
if(!list_empty()){
for(t=head ; t!=NULL ; t= t->link){
count++;
}
}
return count;
}
bool my_list::list_empty(){
if (head == NULL)
return true;
else
return false;
}
double my_list::score_sum(){
node *p;
double sum=0;
p = head;
while(p != NULL){
sum += p->score;
p = p->link;
}
return sum;
}
double my_list::get_score(string name){
node *p;
for(p=head; p != NULL ; p= p->link){
if ( p -> name == name){
return p->score;
}
}
return 0;
}
int my_list::remove_a_node(string name){
node *p ,*tmp;
p=head;
// empty면 종료
if(list_empty())
return 0;
// head의 값이 삭제 대상일 경우
if (p->name == name){
tmp = p;
head = p ->link;
delete tmp;
return 1;
}
// 중간값이나 tail 값이 삭제 대상일 경우
while ( p->link != NULL){
if ( p ->link->name == name){
tmp = p->link;
// 중간 값 일 때
if(tmp->link != NULL)
p->link = tmp->link;
//tail 일 때
else
p->link = NULL;
delete tmp;
return 1;
}
p = p->link;
}
return 0;
}
int main( )
{
my_list a;
node tmp;
// ryu- kim - park - choi
tmp.set_data("Kim", 20);
a.add_to_head(tmp);
tmp.set_data("Lee", 78.2);
a.add_to_head(tmp); // head 위치로 2개의 원소 추가
cout << a.num_nodes() << " : " << a.score_sum() << "\n"; // 1단계 점검
tmp.set_data("Park", 30);
a.add_to_tail(tmp); // tail 위치로 1개의 원소 추가
cout << a.num_nodes() << " : " << a.score_sum() << "\n"; //2단계 점검
tmp = a.delete_from_head();
cout << tmp.name << " is deleted.\n"; // 3단계 점검
tmp.set_data("Choi", 50);
a.add_to_tail(tmp);
tmp.set_data("Ryu", 10);
a.add_to_head(tmp); // 2개의 원소 추가
cout << a.num_nodes()<<" : " << a.score_sum() << "\n";
cout << "Park’s score : " << a.get_score("Park")<< "\n"; // 4단계 점검
if ( a.remove_a_node("Ryu") == 1)
cout << "choi is deleted from the list. \n"; // 5단계 점검
cout << a.num_nodes()<< " : " << a.score_sum() << "\n"; // 최종 점검
return 0;
}특정 이름 입력 받아서, 삭제하는 int remove_a_node(string name) 함수 수정함.
스택 연습
/* int array 말고 , elemnet로 작성함
#include <iostream>
using namespace std;
#define SIZE 100
class element{
string name;
double score;
void set_data(string n , double s);
};
void element::set_data(string n , double s){
name = n;
score = s;
}
class mystack{
private:
element s[SIZE];
int top;
public:
mystack();
void push(element n);
element pop ();
bool stack_full();
bool stack_empty();
};
mystack::mystack(){
top = 0;
}
void mystack::push(element n){
mystack sta;
if(stack_full())
return;
else{
sta.s[top] = n;
top ++;
}
}
element mystack::pop(){
element e;
if(stack_empty())
return e;
else{
top--;
return e[top];
}
}
bool mystack::stack_full(){
if (top >= SIZE )
return true;
else
return false;
}
bool mystack::stack_empty(){
if (top == 0)
return true;
else
return false;
}
큐 연습
#include <iostream>
using namespace std;
#define SIZE 5
class element {
public:
string name;
int score;
void set_data(string n , int s);
};
void element::set_data(string n , int s){
name = n;
score = s;
}
class queue{
private: //여기서 실수 발생 , array q 생성 안했음. front rear int형인데 생각 못함
element q[SIZE];
int front, rear;
public:
queue();
void add_to_rear(element e);
element delete_from_front();
bool queue_full();
bool queue_empty();
};
queue::queue(){
front = 0;
rear =0;
}
void queue::add_to_rear(element e){
if(!queue_full()){
q[rear] = e;
rear = (rear+1)%SIZE;
}
else{
cout<<"the queue is full\n";
return;
}
}
/* 실수 포인트임. return 다음에 문장을 쓰니 실행이 안 될게 뻔함
element queue::delete_from_front(){
if(!queue_empty()){
return q[front];
front = (front+1)%SIZE; // return 뒤에 있으므로 실행이 안된다.ㅜ
}
}
*/
element queue::delete_from_front(){
element tmp;
if(!queue_empty()){
tmp = q[front];
front = (front+1)%SIZE;
return tmp;
}
else{
cout<<"the queue is empty";
return tmp;
}
}
bool queue::queue_empty(){
if(front == rear)
return true;
else
return false;
}
bool queue::queue_full(){
if ((rear+1)%SIZE == front)
return true;
else
return false;
}
int main() {
queue a;
element tmp;
tmp = a.delete_from_front();
cout << tmp.name<<":"<<tmp.score<<"\n"; //sname과 score가 public인 이유
tmp.set_data("KIM",30);
a.add_to_rear(tmp);
tmp.set_data("Lee", 10);
a.add_to_rear(tmp);
tmp.set_data("Park", 50);
a.add_to_rear(tmp);
while(!a.queue_empty()){
tmp = a.delete_from_front();
cout << tmp.name<<":"<<tmp.score<<"\n"; //sname과 score가 public인 이유
}
return 0;
}
링크드 리스트를 이용한 스택
링크드 리스트를 이용한 큐
#include <iostream>
using namespace std;
//링크드 리스트를 이용한 스택
//node
class node {
public :
string name;
double score;
node *link;
void set_data(string s, double n);
};
void node::set_data(string s , double n){
name = s;
score =n;
}
class stack{
//array 도 필요 없게 되고, 오직 남은 건 포인터 노드 변수
private:
node *top;
public:
stack();
void push_top(node t);
node pop_top();
bool stack_empty();
};
stack::stack(){
top = NULL;
}
void stack::push_top(node t){
node *p;
p = new node; //dynamic memory 로부터 node 공간 확보
(*p) =t; // node에 데이터 값 저장
p->link = top; // p가 원래 top이 가리키는 곳을 가리키도록 함
top = p; //top의 내용을 바꿔준다.
}
node stack::pop_top(){
node tmp;
node *t;
if(!stack_empty()){
tmp = (*top);
t = top;
top = top->link;
delete t;
return tmp;
}
else
return tmp;
}
//linked list 를 이용한 queue 구현
class node1{
public:
string name1;
double score1;
node link1;
void set_data(string n1 , double s1);
};
void node1::set_data(string n1, double s1){
name1 = n1;
score1 = s1;
}
class queue{
private:
node *front, *rear;
public:
queue();
void add_to_rear(node t);
node de_from_front();
bool queue_empty();
};
queue::queue(){
front = NULL;
rear = NULL;
}
void queue::add_to_rear(node t){
//새로운 데이터 p가 저장
node *p;
p = new node;
(*p) = t;
//p는 rear이므로 NULL 을 가리키도록 함
p->link = NULL;
if(rear == NULL)
front = p;
else
rear->link = p;
rear = p;
}
node queue::de_from_front(){
node *p;
node tmp;
tmp = (*front);
p = front;
front = front->link;
delete p;
if (front ==NULL)
rear = NULL;
return tmp;
}
bool queue::queue_empty(){
if (rear == NULL)
return true;
else
return false;
}
int main() {
std::cout << "Hello World!\n";
}
바이너리 트리 연산
#include <iostream>
#include <string>
using namespace std;
//linked list 개념이 다 들어가 있어.
class node {
public:
string name;
double score;
node *left, *right;
void set_data(string n, double s);
};
void node :: set_data(string n , double s){
name = n;
score = s;
}
class my_tree{
public :
int node_count; // 현재 노드 수
node *root; // root를 가리키는 pointer
my_tree(); // constructor
int insert_root(node t); // root 로 node 내용 t 추가
int insert_left(string tname, node tnode); // tname 의 왼쪽에 t 추가
int insert_right(string tname, node tnode); // tname의 오른쪽에 t 추가
double score_sum(); // 모든 node의 score 합
double score_average(); //모든 node의 score 평균
void print_data_inorder(); // inorder 순서로 모든 node의 값 출력
void print_data_preorder(); //preorder 순서로 모든 node의 값 출력
void print_data_postorder(); //postorder 순서로 모든 node의 값 출력
};
// 초기 empty 상태 설정
my_tree::my_tree(){
node_count = 0;
root = NULL;
}
//성공하면 1, 실패하면 0 출력
int my_tree::insert_root(node t){
// root 가 비어있지 않다면 실패(0) return
if(root != NULL)
return 0;
node *p;
p = new node; //node 공간 생성
(*p) = t; //주어진 node 내용 copy
p->left = NULL; // left NULL 로 설정 왜냐하면 root가 비어있었으니까
p->right = NULL; // right NULL로 설정
root = p; // 생성한 node를 root로 -->root 가 p를 가리키는 포인터 노드 변수임. root자체에 데이터가 들어가는게 아니다.
node_count++; // count ++
return 1; // 성공(1) return
}
//p를 root로 하는 binary tree 에서 성명이 tname인 node를 찾고 그 node의 왼쪽에 t 추가
// algorithm
// p가 null이면 return 0 : 해당 node 없음
//root 가 찾는 node(name이 tname)이면
// root의 left가 null 아니면 return -1 (이미 왼쪽에 값이 있는 것임)
// root의 left가 null이면 왼쪽에 새로운 node 추가
// .node 공간확보 - data내용저장 - left,right 를 null 로 - root 의 왼쪽에 연결
// 성공(1)을 return
//root가 찾는 node(name이 tname)이 아니면
// left subtree에 해당 작업 수행
// return 0 이 아닌경우 (해당 노드를 아직 못찾은 경우가 아니면) 결과값을 그대로 return
// return 0 인 경우 right subtree에 해당 작업을 수행하고 그 결과를 return
int node_insert_left(node *p, string tname, node tnode){
if(p==NULL) return 0; //p가 null이면 0 출력. 아예 비워있으니 찾는게 불가능
if(p->name == tname){
if(p->left != NULL) // 이미 left에 뭔가 있으면 추가 못하도록 한다.
return -1;
node *t;
t = new node;
(*t) = tnode;
t->left = NULL;
t->right = NULL;
p->left = t;
return 1;
}
else{
int result = node_insert_left(p->left, tname, tnode);
if(result!=0)
return result;
return node_insert_left(p->right,tname,tnode);
}
}
int node_insert_right(node *p, string tname, node tnode){
if(p==NULL) return 0;
//p가 null이 아닐때 p->name == tname 인지 확인
if(p->name == tname){
// 찾았는데, 오른쪽에 뭔가 있으면 -1
if(p->right != NULL)
return -1;
//찾았는데, 오른쪽에 아무것도 없으면 추가
node *t;
t = new node;
(*t) = tnode;
t-> left = NULL;
t-> right = NULL;
p-> right = t;
return 1;
}
//p가 null이 아닌데, p->name == tname 이 아닌 경우 //한 단계 더 가야지
else{
//순서가 left 먼저니까 p->left먼저 하는게 맞지 않을까?--> 그림을 그려서 해본 결과 이게 맞는듯 , 왜냐하면 왼쪽먼저 오른쪽 나중이 binary tree 의 기본 순서임! 왼쪽이 children 이고 ,오른쪽이 sibling 이기 때문이다.!
int result = node_insert_right(p->left, tname, tnode);
if(result!=0)
return result;
return node_insert_right(p->right,tname, tnode);
}
}
//성명이 'tname' 인 node를 찾고 그 node의 왼쪽에 t 추가
// return value
// 1 : insert 과정 성공
// 0 : 'tname' 갖는 Node 없음
// -1: 'tname' 을 갖는 노드는 있으나 왼쪽이 NULL이 아닌 경우
// recursive 하게 코딩 ('root'를 root로 하는 tree 에 해당 내용을 수행하는 function 을 call 한다.
// 결과가 성공이면 node_count를 1 증가 시킴
int my_tree::insert_left(string tname, node tnode){
int result;
result = node_insert_left(root,tname,tnode); // member 함수가 아니다.
if(result ==1)
node_count ++;
return result;
}
int my_tree::insert_right(string tname , node tnode){
int result;
result = node_insert_right(root, tname, tnode); //member 함수가 아니다. 굳이 이렇게 하는 이유는 class 내부 자체에서 recursive 함수 만드는게 매우 어렵기 때문이다.
if(result == 1)
node_count++;
return result;
}
//recursive 함수의 특성 때문에, p 가 계속 subtree의 root 가 된다.
double sum_allnodes(node *p){
if (p==NULL)
return 0;
return sum_allnodes(p->left) + sum_allnodes(p->right)+p->score;
}
// 'root'를 root으로 하는 binary tree의 모든 node에 대한 score의 합을 계산 : recursive function 으로 구현
// root 가 null 이면 return 0 , 아니면 left subtree의 모든 node의 score 합 +
// right subtree의 모든 node의 score 합 + root 의 score 합 을 계산하여 return
double my_tree::score_sum(){
return sum_allnodes(root); // 이렇게 함수를 하나 더 만드는 이유는 clas member function으로 recursive 함수를 만들기 어렵기 때문이다. 파라미터의 인수들을 서로 공유할기 때문이다.(?)
}
// score_sum 으로 얻은 결과를 전부 node_count로 나눠준다.
double my_tree::score_average(){
return score_sum()/node_count;
}
void inorder_print(node *p)
{
if(p==NULL) return;
inorder_print(p->left);
cout <<p->name<<" : " << p->score << "\n";
inorder_print(p->right);
}
// 현재 tree 의 모든 node의 data값을 inorder 순서로 출력
// 'root'를 root로 하는 binary tree의 모든 node의 data 값을 Indoer 순서로 출력 : recursive function으로 구현
//root 가 null이면 그대로 return
//아니면
// left subtree 의 모든 node의 data 값을 inorder로 출력
// rooot node의 data 값을 출력
// right subtree의 모든 node의 data 값을 inorder로 출력
void my_tree::print_data_inorder(){
inorder_print(root);
}
void preorder_print(node *p)
{
if(p==NULL) return;
cout <<p->name<<" : " << p->score << "\n";
preorder_print(p->left);
preorder_print(p->right);
}
void my_tree::print_data_preorder(){
preorder_print(root);
}
void postorder_print(node *p)
{
if(p==NULL) return;
postorder_print(p->left);
postorder_print(p->right);
cout <<p->name<<" : " << p->score << "\n";
}
void my_tree::print_data_postorder(){
postorder_print(root);
}
int main(int argc, const char * argv[]) {
my_tree thetree;
node tmp;
tmp.set_data("Kim" , 8.1);
thetree.insert_root(tmp);
tmp.set_data("Lee", 6.5);
thetree.insert_left("Kim",tmp);
tmp.set_data("Park", 8.3);
thetree.insert_right("Kim", tmp);
tmp.set_data("Choi", 7.2);
thetree.insert_left("Lee", tmp);
tmp.set_data("Ryu", 9.0);
thetree.insert_right("Lee", tmp);
tmp.set_data("Cho", 7.7);
thetree.insert_right("Park", tmp);
cout<< "Score Sum : " << thetree.score_sum() << "\n";
cout<< "Score Average : " << thetree.score_average() << "\n";
cout <<"\n Inorder Traversal Result \n";
thetree.print_data_inorder();
cout << "\n Preorder Traversal Result \n";
thetree.print_data_preorder();
cout << "\n Postorder Traversal Result \n";
thetree.print_data_postorder();
return 0;
}
다음 3가지 문제는 서로 equivalent한 문제이다.
- n개의 node로 이루어진 binary tree의 형태는 총 몇가지 인가?
- n개의 원소로 이루어진 stack permutaition 문제
- n+1 개의 matrix를 곱하는 방법의 수
