'C++프로그래밍'에 해당되는 글 45건

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_SIZE 60000
#define SWAP(x,y,t) ((t)=(x),(x)=(y),(y)=(t))

int list[MAX_SIZE];
int n;

void bubble_sort(int list[],int n)
{
 int i,j,temp;
 for(i=n-1;i>0;i--){
  for(j=0;j<i;j++)
   if(list[j]>list[j+1])
   SWAP(list[j],list[j+1],temp);
 }
}
void main()
{
 int i;
 clock_t start , end;
 n=MAX_SIZE;
 for(i=0;i<n;i++)
  list[i]=rand()%n;

 start = clock();
 bubble_sort(list,n);
 end = clock();
  printf("%lfsec\n",(end - start)/(double)1000);
}

//insertion_sort

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

#define MAX_SIZE 60000
//#define SWAP(x,y,t) ((t)=(x),(x)=(y),(y)=(t))

int list[MAX_SIZE];
int n;

void insertion_sort(int list[],int n)
{
 int i,j,key;
 for(i=1;i<n;i++){
  key=list[i];
  for(j=i-1;j>=0 && list[j]>key;j--)
   list[j+1]=list[j];
  list[j+1]=key;
 }
}

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

 start = clock();
 insertion_sort(list,n);
 end = clock();
  printf("%lfsec\n",(end - start)/(double)1000);
}

//merge_sort

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_SIZE 60000

int sorted[MAX_SIZE];
int list[MAX_SIZE];
int n;

void merge(int list[],int left,int mid,int right)
{
 int i,j,k,l;
 i=left, j=mid+1; k=left;

 while(i<=mid && j<=right){
  if(list[i]<=list[j])
   sorted[k++]=list[i++];
  else
   sorted[k++]=list[j++];
 }
 if(i>mid)
  for(l=j;l<=right;l++)
   sorted[k++]=list[l];
 else
  for(l=i;l<=mid;l++);

 for(l=left;l<=right;l++)
  list[l]=sorted[l];
}

void merge_sort(int list[],int left,int right)
{
 int mid;
 if(left<right){
  mid=(left+right)/2;
  merge_sort(list,left,mid);
  merge_sort(list,mid+1,right);
  merge(list,left,mid,right);
 }
}

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

 start = clock();
 merge_sort(list,0,n);
 end = clock();
  printf("%lfsec\n",(end - start)/(double)1000);
}

//quick_sort

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

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

int list[MAX_SIZE];
int partition(int left,int right)
{
 int pivot,temp;
 int low,high;
 
 low=left;
 high=right+1;
 pivot=list[left];
 do{
  do
  low++;
  while(low <= right && list[low]<pivot);
  do
  high--;
  while(high >= left && list[high]>pivot);
  if(low<high) SWAP(list[low],list[high],temp);
 }while(low<high);

 SWAP(list[left],list[high],temp);
 return high;
}
void quick_sort(int left,int right)
{
 int q;
 if(left<right){
  q=partition(left,right);
  quick_sort(left,q-1);
  quick_sort(q+1,right);
 }
}

int main()
{
 int i , n;
 clock_t start , end;
 n = MAX_SIZE;
 srand((unsigned)time(NULL));
 for(i = 0 ; i < n ; i++)
  list[i] = rand() % n;
 start = clock();
 quick_sort(0 , n-1);
 end = clock();
 printf("%lfsec \n",(end - start) / (double)1000);
}

//select_sort

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_SIZE 60000
#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;
 clock_t start , end;
 n=MAX_SIZE;
 for(i=0;i<n;i++)
  list[i]=rand()%n;

 start = clock();
 selection_sort(list,n);
 end = clock();
  printf("%lfsec\n",(end - start)/(double)1000);
}

//shell_sort

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

#define SIZE 60000

int a[SIZE];

void ShellSort(int n)
{
    int i,j,h,v;
    for(h=1 ; h<n ; h = 3*h+1) ;
    for( ; h > 0 ; h /=3)                     
        for ( i = h+1 ; i<=n ;i++)                                        
        {
            v = a[i];                                      
            j = i;                           
   while (j > h && a[j-h] > v)       
            {
                a[j] = a[j-h];                                                                 
                j = j - h;                                                                
            }a[j] = v;
  }
}

 void main()
{
    int i , n;
    double start_time;
 n = SIZE;

    srand((unsigned)time(NULL));

    for(i = 0; i< n; i++) a[i] = rand() % n;

    start_time = clock();
    ShellSort(n);

 printf("%lfsec\n", (clock()-start_time)/(double)1000);
 }

//heap_sort

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

#define SIZE 60000
int a[SIZE];

typedef struct HeapType {
 int heap[SIZE+1];
 int heap_size;
}HeapType;

void init(HeapType *h)
{
 h->heap_size=0;
}

void insert_max_heap(HeapType *h,int item)
{
 int i;
 i= ++(h->heap_size);

 while((i!=1)&&(item > h->heap[i/2])){
  h->heap[i]=h->heap[i/2];
  i/=2;
 }
 h->heap[i]=item;
}

int delete_max_heap(HeapType *h)
{
 int parent, child;
 int item, temp;

 item=h->heap[1];
 temp=h->heap[(h->heap_size)--];
 parent=1;
 child=2;
 while(child<=h->heap_size){
  if((child<h->heap_size)&&
   (h->heap[child] < h->heap[child+1]))
   child++;
  if(temp >=h->heap[child]) break;
  h->heap[parent]=h->heap[child];
  parent=child;
  child*=2;
 }
 h->heap[parent]=temp;
 return item;
}
void heap_sort(int n)
{
 int i;
 HeapType h;

 init(&h);
 for(i=0;i<n;i++){
  insert_max_heap(&h,a[i]);
 }
 for(i=(n-1);i>=0;i--){
  a[i]=delete_max_heap(&h);
 }
}

void main()
{
 int i , n;
 HeapType h;
 clock_t start , end;
 n = SIZE;

 for(i = 1 ; i <= n ; i++)
  a[i] = rand() % n;
    init(&h);
 start = clock();
 heap_sort(n);
 end = clock();
 printf("%lfsec \n",(end - start)/(double)1000);
 
}

//radix_sort

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

#define BUCKETS 10
#define DIGITS 5
#define MAX_QUEUE_SIZE 20000
#define SIZE 60000

typedef int element;
typedef struct{
 element queue[MAX_QUEUE_SIZE];
 int front,rear;
}QueueType;

int list[SIZE];

void error(char* message)
{
 fprintf(stderr,"%s\n",message);
 exit(1);
}

void init(QueueType* q)
{
 q->front=q->rear=0;
}

int is_empty(QueueType* q)
{
 return (q->front == q->rear);
}

int is_Full(QueueType* q)
{
 return ((q->rear+1)%MAX_QUEUE_SIZE ==q->front);
}
void enqueue(QueueType* q,element item)
{
 if(is_Full(q))
  error("큐가 포화상태입니다");
 q->rear=(q->rear+1)%MAX_QUEUE_SIZE;
 q->queue[q->rear]=item;
}

element dequeue(QueueType* q)
{
 if(is_empty(q))
  error("큐가 공백상태입니다");
 q->front=(q->front+1)%MAX_QUEUE_SIZE;
 return q->queue[q->front];
}

void radix_sort(int n)
{
 int i,b,d,factor=1;
 QueueType queues[BUCKETS];

 for(b=0;b<BUCKETS;b++) init(&queues[b]);

 for(d=0;d<DIGITS;d++){
  for(i=0;i<n;i++)
   enqueue(&queues[(list[i]/factor)%10],list[i]);

  for(b=i=0;b<BUCKETS;b++)
   while(!is_empty(&queues[b]))
    list[i++]=dequeue(&queues[b]);
  factor *=10;
 }
}

void main()
{
 int i,n;
 clock_t start , end;
 n=SIZE;
 for(i=0;i<n;i++)
  list[i]=rand()%n;

 start = clock();
 radix_sort(n);
 end = clock();
  printf("%lfsec\n",(end - start)/(double)1000);
}

#include <iostream>

#define MAX_QUEUE_SIZE 100

using std::cout;
using std::endl;
using std::cin;

class queue{
 int rear;
 int front;
 int queues[MAX_QUEUE_SIZE];
public:
 void init();
 void addq(int item);
 void deleteq();
 void show();
};
void queue::init()
{
 rear=front=0;
 queues[rear]=0;
 queues[front]=0;
}
void queue::addq(int item)
{
 rear=(rear+1) % MAX_QUEUE_SIZE;
 if(front == rear){
  cout<<"queue is full";
  }
 queues[rear]=item;
}
void queue::deleteq()
{
 if(front == rear){
  cout<<"queue is empty";
 }
 front=(front+1) % MAX_QUEUE_SIZE;
 return;// queues[front];
}
void queue::show()
{
 cout<<"front : "<<queues[front]<<"  "<<"rear : "<<queues[rear]<<endl;
}

int main(void)
{
 queue q1;
 q1.init();
 q1.show();

 q1.addq(10);
 q1.show();
 q1.addq(20);
 q1.show();
 q1.addq(30);
 q1.show();
 q1.addq(40);
 q1.show();
 q1.addq(50);
 q1.show();
 return 0;
}

//정렬되지 않은 배열에서 탐색

//순차탐색
int seq_search(int key, int low, int high){
 int i;
 for(i=low; i<high; i++){
  if(list[i] == key)
   return i;
 }
 return -1;
}

//개선된 순차탐색
int seq_search2(int key, int low, int high){
 int i;
 list[high+1] = key;
 for(i=low; list[i] != key; i++)
  ;
 if(i == (high+1)) return -1;
 else
  return i;
}

//정렬된 배열에서 탐색

//개선된 순차탐색
int sorted_seq_search(int key, int low, int high){
 int i;
 if(key<list[low] || key>list[high])
  return -1;
 for(i=low; i<=high; i++){
  if(list[i] > key) return -1;
  if(list[i] == key) return i;
 }
}

//이진 탐색(recursion)
int search_binary(int key, int low. int high){
 int middle;
 if(low<high){
  middle=(low+high)/2;
  if(key == list[middle])
   return middle;
  else if(key <list[middle])
   return search_binary(key,low,middle-1);
  else
   return search_binary(key,middle+1,high);
 }
 return -1;
}

//이진 탐색(반복)
int search_binary2(int key, int low, int high){
 int middle;

 while(low<=high){
  middle=(low+high)/2;
  if(key == list[middle])
   return middle;
  else if(key > list[middle])
   low = middle+1;
  else
   high = middle-1;
 }
 return -1;
}
//정렬된 배열에서 색인 순차 탐색
typedef struct{
 int key;
 int index;
}itable;
itable index_list[index_size];
//n은 전체 데이터의 수
int search_index(int key){
 int i,low,high;

 if(key<list[0] || key>list[n-1])
  return -1;

 for(i=0; i<INDEX_SIZE; i++)
  if(index_list[i].key<=key && index_list[i+1].key>key)
   break;
 if( i ==INDEX_SIZE){
  low = index_list[i-1].index;
  high=n;
 }
 else{
  low = index_list[i].index;
  high= index_list[i+1].index;
 }

 return seq_search(key,low,high);
}

//보간 탐색
int search_interpolation(int key,int n){
 int low,high,j;
 low=0;
 high=n-1;
 while((list[high] >= key) && (key>list[low])){
  j=((float)(key-list[low])/(list[high]-list[low])*(high-low))+low;
  if(key>list[j]) low = j+1;
  else if (key < list[j]) high = j-1;
  else low = j;
 }
 if(list[low] == key)  return(low);
 else return -1;
}

#define KEY_SIZE 10
#define TABLE_SIZE 13
#define equal(e1,e2) (!strcmp(e1.key,e2.key))
typedef struct{
 char key[TABLE_SIZE];
}element;

typedef struct ListNode{
 element item;
 struct ListNode* link;
}ListNode;

ListNode* hash_table[TABLE_SIZE];

void hash_chain_add(element item, ListNode* ht){
 int hash_value = hash_function(item.key);
 ListNode* ptr;
 ListNode* node_before = NULL;
 ListNode* node = ht[hash_value];
 for(; node; node_before = node , node=node->link){
  if(equal(node->item,item)){
   fprintf(stderr,"이미 탐색 키가저장되어 있음\n");
   return;
  }
 }
 ptr=(ListNode*)malloc(sizeof(ListNode));
 ptr->item = item;
 ptr->link = NULL;
 if(node_before)
  node_before->link = ptr;
 else
  ht[hash_value] = ptr;
}

void hash_chain_find(element item, ListNode* ht){
 ListNode* node;

 int hash_value = hash_function(item.key);
 for(node=ht[hash_value];node;node=node->link){
  if(equal(node->item,item)){
   printf("키를 찾았음\n");
   return;
  }
 }
 printf("키를 찾지 못함\n");
}

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

#define KEY_SIZE 10
#define TABLE_SIZE 7

#define empty(e) (strlen(e.key)==0)
#define equal(e1,e2) (!strcmp(e1.key,e2.key))

typedef struct{
 char key[KEY_SIZE];
}element;

element hash_table[TABLE_SIZE];

//해시 테이블 초기화
void init_table(element* ht){
 int i;
 for(i=0; i<TABLE_SIZE; i++){
  ht[i].key[0]=NULL;
 }
}

//문자로 된 탐색키를 숫자로 변환
int transform(char *key){
 int number = 0;
 while(*key)
  number += *key++;
 return number;
}
//제산 함수를 사용한 해싱 함수
int hash_function(char* key){
 return transform(key) % TABLE_SIZE;
}
int hash_function2(char* key){
 return (5-(transform(key) % 5) % TABLE_SIZE);
}

//선형 조사법을 이용하여 테이블에 키를 삽입하고 테이블이 가득찬 경우에는 종료
void hash_lp_add(element item, element* ht){
 int i,hash_value;
 hash_value = i = hash_function(item.key);
 while(!empty(ht[i])){
  if(equal(item,ht[i])){
   fprintf(stderr,"탐색키가 중복 되었습니다\n");
   return;
  }
  i= (i+1) % TABLE_SIZE;
  if(i == hash_value){
   fprintf(stderr,"테이블이 가득 찼습니다\n");
   return;
  }
 }
 ht[i]=item;
}
//이차 조사
void hash_qp_add(element item, element* ht){
 int i,hash_value,inc=0;
 hash_value = i = hash_function(item.key);
 while(!empty(ht[i])){
  if(equal(item,ht[i])){
   fprintf(stderr,"탐색키가 중복 되었습니다\n");
   return;
  }
  i= (i+inc+1) % TABLE_SIZE;
  inc = inc+2;
  if(i == hash_value){
   fprintf(stderr,"테이블이 가득 찼습니다\n");
   return;
  }
 }
 ht[i]=item;
}
//이중 조사
void hash_dh_add(element item, element* ht){
 int i,hash_value,inc;
 hash_value = i = hash_function(item.key);
 inc = hash_function2(item.key);
 while(!empty(ht[i])){
  if(equal(item,ht[i])){
   fprintf(stderr,"탐색키가 중복 되었습니다\n");
   return;
  }
  i= (i+inc) % TABLE_SIZE;
  if(i == hash_value){
   fprintf(stderr,"테이블이 가득 찼습니다\n");
   return;
  }
 }
 ht[i]=item;
}
//선형 탐색
void hash_lp_search(element item, element* ht){
 int i,hash_value;
 hash_value = i = hash_function(item.key);
 while(!empty(ht[i])){
  if(equal(item,ht[i])){
   fprintf(stderr,"탐색성공 : 위치 = %d\n",i);
   return;
  }
  i= (i+1) % TABLE_SIZE;
  if(i == hash_value){
   fprintf(stderr,"찾는 값이 테이블에 없음\n");
   return;
  }
 }
 fprintf(stderr,"찾는 값이 테이블에 없음\n");
}
//이차 탐색
void hash_qp_search(element item, element* ht){
 int i,hash_value,inc=0;
 hash_value = i = hash_function(item.key);
 while(!empty(ht[i])){
  if(equal(item,ht[i])){
   fprintf(stderr,"탐색성공 : 위치 = %d\n",i);
   return;
  }
  i= (i+inc+1) % TABLE_SIZE;
  inc = inc+2;
  if(i == hash_value){
   fprintf(stderr,"찾는 값이 테이블에 없음\n");
   return;
  }
 }
 fprintf(stderr,"찾는 값이 테이블에 없음\n");
}
//이중 탐색
void hash_dh_search(element item, element* ht){
 int i,hash_value,inc;
 hash_value = i = hash_function(item.key);
 inc = hash_function2(item.key);
 while(!empty(ht[i])){
  if(equal(item,ht[i])){
   fprintf(stderr,"탐색성공 : 위치 = %d\n",i);
   return;
  }
  i= (i+inc) % TABLE_SIZE;
  if(i == hash_value){
   fprintf(stderr,"찾는 값이 테이블에 없음\n");
   return;
  }
 }
 fprintf(stderr,"찾는 값이 테이블에 없음\n");
}

//해싱 테이블의 내용을 출력
void hash_lp_print(element* ht){
 int i;
 for(i=0; i<TABLE_SIZE; i++)
  printf("[%d]= %s\n",i,ht[i].key);
}

main(){
 element tmp;
 int op;
 while(1){
  printf("원하는 연산을 입력(0=입력,1=탐색,2=종료)=");
  scanf("%d",&op);
  if( op == 2) break;
  printf("키를 입력하시오 : ");
  scanf("%s",tmp.key);
  if( op == 0 )
   hash_dh_add(tmp,hash_table);
  else if( op == 1)
   hash_dh_search(tmp,hash_table);
  hash_lp_print(hash_table);
 }
}

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

#define KEY_SIZE 10
#define TABLE_SIZE 13

#define empty(e) (strlen(e.key)==0)
#define equal(e1,e2) (!strcmp(e1.key,e2.key))

typedef struct{
 char key[KEY_SIZE];
}element;

element hash_table[TABLE_SIZE];

//해시 테이블 초기화
void init_table(element* ht){
 int i;
 for(i=0; i<TABLE_SIZE; i++){
  ht[i].key[0]=NULL;
 }
}

//문자로 된 탐색키를 숫자로 변환
int transform(char* key){
 int number = 0;
 while(*key)
  number += *key++;
 return number;
}
//제산 함수를 사용한 해싱 함수
int hash_function(char* key){
 return transform(key) % TABLE_SIZE;
}
//선형 조사법을 이용하여 테이블에 키를 삽입하고 테이블이 가득찬 경우는 종료
void hash_lp_add(element item,element* ht){
 int i,hash_value;
 hash_value = i =hash_function(item.key);
 while(!empty(ht[i])){
  if(equal(item,ht[i])){
   fprintf(stderr,"탐색키가 중복되었습니다\n");
   return;
  }
  i = (i+1) % TABLE_SIZE;
  if(i == hash_value){
   fprintf(stderr,"테이블이 가득 찼습니다\n");
   return;
  }
 }
 ht[i]=item;
}

//선형 조사법을 이용하여 테이블에 저장된 키를 탐색
void hash_lp_search(element item, element* ht){
 int i,hash_value;
 hash_value = i = hash_function(item.key);
 while(!empty(ht[i])){
  if(equal(item,ht[i])){
   fprintf(stderr,"탐색 성공 : 위치=%d\n",i);
   return;
  }
  i= (i+1) % TABLE_SIZE;
  if(i == hash_value){
   fprintf(stderr,"찾는 값이 테이블에 없음\n");
   return;
  }
 }
 fprintf(stderr,"찾는 값이 테이블에 없음\n");
}

//해싱 테이블의 내용을 출력
void hash_lp_print(element* ht){
 int i;
 for(i=0; i<TABLE_SIZE; i++)
  printf("[%d]   %s\n",i,ht[i].key);
}

main(){
 element tmp;
 int op;
 while(1){
  printf("원하는 연산을 입력(0=입력,1=탐색,2=종료)=");
  scanf("%d",&op);
  if( op == 2) break;
  printf("키를 입력하시오");
  scanf("%s",tmp.key);
  if( op == 0 )
   hash_lp_add(tmp,hash_table);
  else if(op == 1)
   hash_lp_search(tmp,hash_table);
  hash_lp_print(hash_table);
 }
}