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

void shortestpath(int v, int cost[][MAX_VERTICES],int* distance,int n,short int* found)
{
 int i,u,w;
 for(i=0; i<n; i++){
  found[i]=FALSE;
  distance[i]=cost[v][i];
  }
 found[v]=TRUE;
 distance[v]=0;
 for(i=0; i<n-2; i++){
  u=choose(distance,n,found);
  found[u]=TRUE;
  for(w=0; w<n; w++)
   if(!found[w])
    if(distance[u]+cost[u][w]<distance[w]){
     distance[w]=distance[u]+cost[u][w];
     }
    }
}

int choose(int* distance,int n,short int* found){
 int i,min,minpos;
 min=INT_MAX;
 minpos = -1;
 for(i=0; i<n; i++)
  if(distance[i]<min && !found[i]){
   min=distance[i];
   minpos = i;
  }
  return minpos;
}

#define MAX_VERTICES 50
#define TRUE 1
#define FALSE 0
short intvidited[MAX_VERTICES];

typedef struct node* node_pointer;
typedef struct node{
 int vertex;
 struct node* link;
};
typedef struct queue* queue_pointer;
typedef struct queue{
 int vertex;
 queue_pointer link;
};
void addq(queue_pointer*, queue_pointer*,int);
int deleteq(queue_pointer*);

void bfs(int v){
 node_pointer w;
 queue_pointer front,rear;
 front=rear=NULL;

 printf("%5d",v);
 visited[v]=TRUE;
 addq(&front,&rear,v);
 while(front){
  v=deleteq(&front);
  for(w=graph[v]; w; w=w->link)
   if(visited[w->vertex]){
    printf("%5d",w->vertex);
    addq(&front,&rear,w->vertex);
    visited[w->vertex]=TRUE;
   }
 }
}

#define MAX_VERTICES 50
#define TRUE 1
#define FALSE 0
short intvidited[MAX_VERTICES];

typedef struct node* node_pointer;
typedef struct node{
 int vertex;
 struct node* link;
};
node_pointer graph[MAX_VERTICES];
int n=0; //현재 사용중인 정점들

void dfs(int v){
 node_pointer w;
 visited[v]=TRUE;
 printf("%5d",v);
 for(w=graph[v]; w; w=w->link)
  if(!visited[W->vertex])
   dfs(w->vertex);
}

LSD기수정렬

#define MAX_DIGIT 3
#define RADIX_SIZE 10
typedef struct list_node* list_pointer;
typedef struct list_node{
 int key[MAX_DIGIT];
 list_pointer link;
};

list_point radix_sort(list_pointer ptr){
 list_point front[RADIX_SIZE],rear[RADIX_SIZE];
 int i,j,digit;
 for(i=MAX_DIGIT-1; i>=0; i--){
  for(j=0; j<RADIX_SIZE; j++)
   front[j]=rear[j]=NULL;
  while(ptr){
   digit=ptr->key[i];
   if(!front[digit])
    front[digit]=ptr;
   else
    rear[digit]->lik=ptr;
   rear[digit]=ptr;
   ptr=ptr->link;
  }
  prt=NULL;
  for(j=RADIX_SIZE-1; j>=0;j--)
   if(front[j]){
    rear[j]->link=ptr; ptr=front[j];
   }
 }
 return ptr;
}

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

void quick_sort(int* list,int left,int right){
 if(left<right){
  int q=partition(list,left,right);
  quick_sort(list,left,q-1);
  quick_sort(list,q+1,right);
 }
}

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

 SWAP(list[left],list[high],temp);
 return high;
}


-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------

typedef struct{
 int key;
}element;
element list[MAX];

#define SWAP(x,y,t) ((t)=(x),(x)=(y),(y)=(t))
#define MAX 100

void quicksort(element int* list,int left, int right){
 int pivot,i,j;
 element temp;
 if(left<right){
  i=left;
  j=right+1;
  pivot=list[left].key;
  do{
   do{
    i++;
   }while(list[i].key<pivot);
   do{
    j--;
   }while(list[j].key>pivot);
   if(i<j)
    SWAP(list[i],list[j],temp);
  }while(i<j);
  SWAP(list[left],list[j],temp);
  quicksort(list,left,j-1);
  quicksort(list,j+1,right);
 }
}

void merge(int* list,int left,int mid,int right);

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 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++)
   sorted[k++] = list[l];
 for(l=left; l<=right; l++)
  list[l] = sorted[l];
}