'C++프로그래밍/자료구조'에 해당되는 글 29건

void shell_sort(int* list, int n){
 int i,gap;
 for(gap=n/2;gap>0;gap=gap/2){
  if((gap%2) == 0 ) gap++;
  for(i=0;i<gap;i++)
   insertion_sort(list,i,n-1,gap);
 }
}
void insertion_sort(int* list,int first,int last,int gap)
{
 int i,j,key;
 for(i=first+gap;i<=last;i=i+gap){
  key=list[i];
  for(j=i-gap;j>=first && key<list[j];j=j-gap)
   list[j+gap]=list[j];
  list[j+gap]=key;
 }
}

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 10000
#define SWAP(x,y,t) ((t)=(x),(x)=(y),(y)=(t))

int list[MAX_SIZE];
int n;

void selection_sort(int* list,int n){
 int i,j,least,temp;
 for(i=0; i<n-1; i++){
  least = i;
  for(j=i+1; j<n; j++)
   if(list[j]<list[least]) least =j;
  SWAP(list[i],list[least],temp);
 }
}

void main(){
 int i;
 n = MAX_SIZE;
 for(i=0; i<n; i++)
  list[i] = rand()%n;

 selection_sort(list,n);
 for(i=0; i<n; i++)
  printf("%d\n",list[i]);
}

#define MAX_ELEMENT 200
#define HEAP_FULL(n) (n == MAX_ELEMENT-1)
#define HEAP_EMPTY(n) (!n)
typedef struct{
 int key;
}element;

element heap[MAX_ELEMENT];
int n=0;

//최대 히프에 삽입
void insert_max_heap(element item, int* n){
 int i;
 if(HEAP_FULL(*n)){
  fprintf(stderr,"the heap is FULL\n");
  exit(1);
 }
 i=++(*n);
 while((i != 1) && (item.key > heap[i/2].key)){
  heap[i] = heap[i/2];
  i/=2;
 }
 heap[i] =item;
}

element delete_max_heap(int* n){
 int parent,child;
 element item,temp;
 if(HEAP_EMPTY(*n)){
  fprintf(stderr,"the heap is EMPTY\n");
  exit(1);
 }

 item=heap[1];
 temp=heap[(*n)--];
 parent = 1;
 child = 2;
 while(child <= *n){
  if(child< *n) && (heap[child].key) < heap[child+1].key
   child++;
  if(temp.key >= heap[child.key) break;

  heap[parent] =heap[child];
  parent=child;
  child* = 2;
 }
 heap[parent] = temp;
 return item;
}

typedef struct TreeNode{
 int key;
 struct TreeNode *left,*right;
}TreeNode;

//삭제
void delete_node(TreeNode** root, int key){
 TreeNode *p,*child,*succ,*succ_p,*t;

 p = NULL;
 t= *root;

 while(t != NULL && t->key != key){
  p=t;
  t=(key < t->key) ? t->left : t->right;
 }
 if( t== NULL){
  printf("Key is not in the tree");
  return ;
 }
 // 단말노드인 경우
 if((t->left == NULL) && (t->right == NULL)){
  if(p != NULL){
   if(p->left == t)
    p-left = NULL;
  }
  else
   *root = NULL;
 }
 //하나의 자식만 가지는 경우
 else if((t->left == NULL) || (t->right == NULL)){
  child = (t->left != NULL) ? t->left : t->right;
  if(p != NULL){
   if(p->left == t)
    p->left = child;
   else p->right = child;
  }
  else
   *root = child;
 }
 else{
  succ_p = t;
  succ = t->right;
  while(succ->left != NULL){
   succ_p = succ;
   succ = succ->left;
  }
  if(succ_p-<left == succ)
   succ_p->left = succ->right;
  else succ_p->right = succ->right;

  t->key = succ->key;
  t=succ;
 }
 free(t);
}

typedef struct node* tree_pointer;
typedef struct node{
 int data;
 tree_pointer left_child,right_child;
};
//이진 탐색 트리의 순환적 탐색
tree_pointer search(tree_pointer root, int key){
 if(!root) return NULL;
 if(key == root->data) return root;
 if(key < root->data)
  return search(tree_pointer left_child,int key);
 return search(tree_pointer right_child,int key);
}
//이진 탐색 트리의 반복적 탐색
tree_pointer search(tree_pointer tree,int key){
 while(tree){
  if( key == tree->data) return tree;
  if( key < tree->data)
   tree=tree->lefe_child;
  else
   tree=tree->right_child;
 }
 return NULL;
}
//반복적 탐색의 변형
void modified_search(tree_pointer node2,int num){
 tree_pointer temp;
 if(!node2) return NULL;
 while(node2 !=NULL ){
  if(num == node2->data) return node2;
  temp=node2;
  if(num < temp->data)
   temp = temp->left;
  else temp=temp->right;
 }
}

//이진 탐색 트리에 원소를 삽입
void insert_node(tree_pointer* node,int num){
 tree_pointer ptr;
 temp=modified_search(*node,num);
 if( temp || !(*node)){
  ptr = (tree_pointer)malloc(sizeof(node));
  if(IS_FULL(ptr)){
   fprintf(stderr,"The memory is FULL\n");
   exit(1);
  }
  ptr->data = num;
  prt->left_child = prt->right_child = NULL;
  if(*node)
   if(num < temp->data)
    temp->left_child = ptr;
   else temp->right_child =ptr;
  else *node =ptr;
 }
}

typedef struct threaded_tree *threaded_pointer;
typedef struct threaded_tree{
 short int left_thread;
 threaded_pointer left_child;
 char data;
 threaded_pointer right_child;
 short int right_child;
};

//한노드의 중위 후속자를 찾는 함수
threaded_pointer insucc(threaded_pointer tree){
 threaded_pointer temp;
 temp=tree->right_child;
 if(!tree->right_thread)
  while(!temp->left_thread)
   temp=temp->left_child;
 return temp;
}
//스레드이진트리의 중위순회
void tinorder(threaded_pointer tree){
 threaded_pointer temp=tree;
 for( ; ; ){
  temp = insucc(temp);
  if(temp = tree) break;
  printf("%3c",temp->data);
 }
}
//스레드 이진 트리에서의 오른쪽삽입
void insert_right(threaded_pointer parent, threaded_pointer child){
 threaded_pointer temp;
 child->right_child=parent->right_child;
 child->right_thread=parent->right_thread;
 child->left_child=parent;
 child->left_thread=TRUE;
 parent->right_child = child;
 parent->right_thread = FALSE;
 if(!child->right_thread){
  temp=insucc(child);
  temp->left_child=child;
 }
}