'permutation'에 해당되는 글 2건

  1. 2008.03.20 문자열의 배열의 순열 만들기
  2. 2008.03.16 선택 정렬과 이진탐색, 순열

자료구조 2008. 3. 20. 실습

파일로부터 문자열들을 입력받아 순열을 출력한다.

/************************************************************************/
/* 파일명 : permutation.cpp                                             */
/* 과목명 : 자료구조론             */
/* 교수님 : 유 하 진 교수님            */
/* 작성자 : 박상현              */
/* 작성일 : 2008. 03. 20            */
/* 내  용 : 파일로부터 문자열을 n 개 입력받아 문자열들의 순열을 출력한다.*/
/************************************************************************/


/*
 * inclue header files
 */
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>

int cnt = 0;   // permutation 의 개수를 카운터하는 변수
void swap(char *a, char *b);
void perm(char** list, int i, int n);       // 문자열 n 개의 순열을 출력하는 함수

/************************************************************************/
/* 함수명 : main                                                     */
/* 파일로부터 문자열 n 개를 입력받아 순열을 출력한다.     */
/************************************************************************/
void main(int argc, char* argv[])
{
 FILE *fp; // file pointer
 char **p; // 문자열 배열 저장을 위한 더블 포인터
 char name[10];  // 문자열을 임시 저장하기 위한 배열
 int i, n;
 fp = fopen("input.txt", "r"); // 파일을 일기 전용으로 연다.
 
 // 파일이 열리지 않았다면 exit 한다.
 if(fp == 0)
 {
  printf("Can't open file");
  exit(0);
 }
 fscanf(fp, "%d\n", &n);    // 문자열의 개수를 저장

 p = (char**)calloc(n, sizeof(char*));  // 문자열 n 개를 저장하기 위한 메모리 공간 할당
 
 printf("The number of fruit is %d\n", n);  // 데이터의 개수 출력

 // 데이터의 개수만큼 루프를 돌며 p[i] 에 저장한다.
 for(i = 0 ; i < n ; i++)
 {
  fscanf(fp, "%s\n", name);        // 과일이름을 임시로 name 배열에 저장
  p[i] = (char*)calloc(strlen(name) + 1 , sizeof(char)); // 과일의 이름 길이만큼 p[i] 에 공간 할당
  strcpy(p[i], name);          // p[i] 에 과일의 이름을 copy 한다.
  printf("%s\n", p[i]);         // 입력받은 값을 출력한다.
 }
 perm(p, 0, n - 1);           // 0 부터 n - 1 개 까지의 순열을 출력한다.
 printf("\ncnt = %d\n", cnt);        // 순열의 개수를 출력한다.

}

/************************************************************************/
/* 함수명 : perm                                                        */
/* list 를 입력받아 모든 순열을 출력해준다.        */
/* i == n 이면 출력하고 그렇지 않으면 i, j 를 스왑한뒤 recursive call */
/* 을 한다. 그리고 다시 i, j 를 스왑하여 원상태로 만들어 준다.   */
/************************************************************************/
void perm(char** list, int i, int n)
{
 int j;
 char temp[10];
 if(i == n)
 {
  printf("%d 번째 순열 : ", cnt + 1);     // 순열의 카운트 출력
  for(j = 0 ; j <= n ; j++)
  {
   printf("%s ", list[j]);       // 하나의 순열 출력
  }
  cnt++;            // cnt 1 증가시킴
  printf("\n");
 }
 else
 {
  for(j = i ; j <= n ; j++)
  {
   strcpy(temp, list[i]);       ////////////////
   strcpy(list[i], list[j]);      // list[i], list[j] SWAP
   strcpy(list[j], temp);       ////////////////*/
   perm(list, i + 1, n);       // RECURSIVE CALL
   strcpy(temp, list[i]);       ////////////////
   strcpy(list[i], list[j]);      // list[i], list[j] 다시 SWAP 하여 원상태로 돌림
   strcpy(list[j], temp);       ///////////////
  }
 }
}

void swap(char *a, char *b)
{
 char temp[10];
 strcpy(temp, a);
 strcpy(a, b);
 strcpy(b, temp);
}

Posted by 행복한 프로그래머 궁금쟁이박

댓글을 달아 주세요

자료구조 1주차 시험이었다...

선택정렬 : 정렬되지 않은 정수들 중에서 가장 작은 값을 찾아서 정렬된 리스트 다음 자리에 놓는다.
이진탐색 : 이미 정렬되어있는 리스트를 가정한다. 찾는 숫자와 중간값을 비교하여 범위를 줄여나간다.
               recursion 으로 구현한 소스 코드도 있다.
순열 : 순열은 재귀적으로 구현되었는데 사실 이해를 잘 못하였다;


/************************************************************************/
/* 작성일 : 2008. 03. 11.            */
/* 작성자 : 박상현                                                      */
/* 내 용 : 1장 연습              */
/************************************************************************/

#include "stdio.h"

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

void selectionSort(int [], int);
int compare(int, int);
int binSearch(int [], int, int, int);
int binSearchRec(int [], int, int, int);
void perm(char*, int, int);

void main()
{
 int i;
 int list[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
 char clist[10] = { 'a', 'b', 'c', 'd' };

 selectionSort(list, 10);
 for(i = 0 ; i < 10 ; i++)
 {
  printf("%d\n", list[i]);
 }
 printf("%d\n", list[binSearch(list, 5, 0, 9)]);   // 5 를 이진 탐색
 printf("%d\n", list[binSearchRec(list, 5, 0, 9)]);  // 5 를 재귀적으로 이진 탐색
 
 perm(clist, 0, 3);

}

/************************************************************************/
/* 함수명 : selectionSort                                               */
/* 내 용 : 숫자로 된 n 크기의 a[] 배열을 선택정렬한다.     */
/************************************************************************/
void selectionSort(int a[], int n)
{
 int i, j, min, minIndex, tmp;

 for(i = 0 ; i < n - 1 ; i++)
 {
  minIndex = i;
  min = a[i];
  for(j = i + 1 ; j < n ; j++)
  {
   if(min > a[j])
   {
    min = a[j];
    minIndex = j;
    SWAP(a[minIndex], a[i], tmp);
   }
  }
 }
}

/************************************************************************/
/* 함수명 : compare                                                     */
/* 내 용 : 두 가지 수의 대소를 비교한다.        */
/*     C 언어의 라이브러리 함수가 취하고 있는 방법을 따른다.  */
/*         첫 번째 값이 작은 경우 -1 리턴,        */
/*         두 값이 같은 경우 0  리턴,         */
/*         두 번째 값이 작은 경우 1 리턴.        */
/************************************************************************/
int compare(int x, int y)
{
 if(x < y) return -1;
 else if(x == y) return 0;
 else return 1;
}

/************************************************************************/
/* 함수명 : binSearch                                                   */
/* 내 용 : 이미 정렬되어 있는 배열 리스트에서 값을 탐색한다.   */
/************************************************************************/
int binSearch(int list[], int searchNum, int left, int right)
{
 int middle;
 while(left <= right)
 {
  middle = (left + right) / 2;
  switch(compare(list[middle], searchNum))
  {
  case -1 : left = middle + 1;
      break;
  case 0 : return middle;
  case 1 : right = middle - 1;
  }
 }
 return -1;
}

/************************************************************************/
/* 함수명 : binSearchRec                                                */
/* 내 용 : recursive 방식의 이진탐색         */
/************************************************************************/
int binSearchRec(int list[], int searchNum, int left, int right)
{
 int middle;
 if(left <= right)
 {
  middle = (left + right) / 2;
  switch(compare(list[middle], searchNum))
  {
  case -1 : return binSearchRec(list, searchNum, middle + 1, right); // 오른쪽이 더 클 경우
  case 0 : return middle;            // ==
  case 1: return binSearchRec(list, searchNum, left, middle - 1);  // 왼쪽이 더 클 경구
  }
 }
 return -1;

}

/************************************************************************/
/* 함수명 : perm                                                        */
/* 내 용 : list[i] 에서 list[n] 까지의 모든 순열을 생성     */
/************************************************************************/
void perm(char *list, int i, int n)
{
 int j, temp;
 if(i == n)
 {
  for(j = 0 ; j <=n ; j++)
  {
   printf("%c, ", list[j]);
   
  }
  printf(" ");
 }
 else
 {
  for(j = i ; j <= n ; j++)
  {
   SWAP(list[i], list[j], temp);
   perm(list, i + 1, n);
   SWAP(list[i], list[j], temp);
  }
 }
}

Posted by 행복한 프로그래머 궁금쟁이박

댓글을 달아 주세요