자료구조 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 행복한 프로그래머 궁금쟁이박

댓글을 달아 주세요

자료구조 과제..

이거... 알고리즘 보고 옮기긴 했지만... 이해하기 어렵다;

/************************************************************************/
/* 과목명 : Data structure            */
/* 교수님 : 유 하 진 교수님            */
/* 파일명 : Perm_hw.cpp                                                 */
/* 작성일 : 2008. 03. 18.            */
/* 작성자 : 박상현              */
/* 내 용  : recursive 하지 않은 permutation 을 구현한다.    */
/************************************************************************/

/*
 * Declare headers
 */
#include <stdio.h>
#include <string.h>
#include <malloc.h>

/*
 * Declare functions
 */
void init(int*, int, int);      //  각 variable 들을 초기화한다.
int factorial(int);        // 팩토리얼 함수
int numLeft;         // 남아있는 순열의 개수를 표시한다.
int* getNext(int*, int, int);     //

/************************************************************************/
/* 함수명 : main                                                        */
/* permutation 을 적용시킬 문자열을 입력받고, 문자열의 길이를 구해서    */
/* 순열을 만들어낸다.             */
/************************************************************************/
int main(char *argv[], int argc)
{
 int *indexes, *indexList;  // 인덱스의 순서를 가지는 배열 ( indexes = indexList )
 char *buf;      // 문자열을 담아둘 버퍼
 char elements[255];    // 입력받는 문자열의 저장소
 int total;      // 순열의 총 개수
 int i, len, cnt = 0;   // 문자열의 길이와 카운터

 printf("문자열을 입력하세요 : ");
 scanf("%s", elements);         // 문자열을 입력받는다.
 len = strlen(elements);         // 문자열의 길이를 구한다.
 total = factorial(len);         // 순열의 개수를 팩토리얼로 구한다.
 buf = (char *)malloc(sizeof(char) * len);    // 버퍼에 메모리를 할당한다.
 indexList = (int *)malloc(sizeof(int) * len);   // 인덱스 리스트에 메모리를 할당한다.
 init(indexList, len, total);       // 리스트를 초기화한다.
 
 
 // 남아있는 순열의 개수가 0 보다 클동안 loop
 while(numLeft > 0)
 {
  indexes = getNext(indexList, len, total);   // indexList 를 리턴받는다.
  for(i = 0 ; i < len ; i++)
  {
   buf[i] = elements[indexes[i]];     // indexes 의 순서대로 버퍼에 저장한다.
  }
  for(i = 0 ; i < len ; i++)
  {
   printf("%c", buf[i]);       // 버퍼의 내용을 출력한다.
  }
  printf("\t");

  cnt++;
 }
 printf("\n순열의 총 개수 = %d\n", cnt);
 
 
 
 return 0;
}

/************************************************************************/
/* 함수명 : getNext                                                     */
/* 실질적으로 순열을 만들어내는 함수이다.        */
/* 1. 먼저 입력받은 문자열을 한번 그대로 출력한다.      */
/* 2. j + 1 로 가장 큰 인덱스를 가리키는 j 를 찾아낸다.     */
/* 3. indexList[j] 보다 큰 가장 작은 인덱스를 가리키는 k 를 찾는다.  */
/* 4. j 와 k 를 SWAP 한다.            */
/* 5. r 을 마지막 인덱스, s 를 j + 1 로 둔다.       */
/* 6. r 이 s 보다 클동안 indexList[r] 과 indexList[s] 를 SWAP 하며 r */
/*    은 증가시키고 s 는 감소시킨다.         */
/************************************************************************/
int* getNext(int *indexList, int n, int total)
{
 int j, k, r, s;
 int temp;

 
 // 일단 입력받는 문자열을 그대로 한번 출력 ( numLeft == total )
 if(numLeft == total)
 {
  numLeft -= 1;
  return indexList;
 }

 // Find largest index j with a[j] < a[j+1]
 j = n - 2; // 끝에서 두번째 인덱스
 // 마지막 인덱스 두개를 비교해서 왼쪽 것이 더 클동안 왼쪽으로 한칸씩 시프트한다.
 // j 는 1 씩 줄여나간다. ( j + 1 이 가장 큰 인덱스가 된다. )
 while (indexList[j] > indexList[j + 1])  
 {
  j--;
 }

 // Find index k such that a[k] is smallest integer
 // greater than a[j] to the right of a[j]
 k = n - 1;
 // 가장 뒤부터 indexList[j] 보다 큰 가장 작은 인덱스를 가리키는 k 를 찾는다.
 while (indexList[j] > indexList[k])
 {
  k--;
 }

 // j 와 k 를 SWAP 한다.
 temp = indexList[k];
 indexList[k] = indexList[j];
 indexList[j] = temp;

  // Put tail end of permutation after jth position in increasing order
  r = n - 1;   // r = 마지막 인덱스
  s = j + 1;   // j 의 오른쪽 인덱스
 
  // r 이 s 보다 클동안 indexList[r] 와 indexList[s] 를 SWAP 한다.
  // r 은 1 씩 감소시키고, s 는 1 씩 증가시킨다.
  while (r > s)
  {
    temp = indexList[s];
    indexList[s] = indexList[r];
    indexList[r] = temp;
    r--;
    s++;
 }
 numLeft -= 1;  // 남아있는 순열의 개수가 하나 줄어든다.
 return indexList; // 결과 인덱스리스트를 리턴한다.
}

/************************************************************************/
/* 함수명 : init                                                        */
/* 문자열 : 길이가 n 인 문자열의 인덱스 리스트를 초기화한다.   */
/*   numLeft 를 total 로 초기화한다.        */
/************************************************************************/
void init(int *list, int n, int total)
{
 int i;
 for(i = 0 ; i < n ; i++)
 {
  *(list + i) = i;   // 인덱스를 순서대로 저장. 0, 1, 2,..
 }
 numLeft = total;    // 처음 남아있는 순열의 개수는 총 개수

 
}

/************************************************************************/
/* 함수명 : factorial                                                  */
/* 팩토리얼을 구해주는 함수            */
/************************************************************************/
int factorial(int n)
{
 int i, f = 1;

 for(i = n ; i > 0 ; i--)
 {
  f = f * i;
 }
 return f;
}


 

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 행복한 프로그래머 궁금쟁이박

댓글을 달아 주세요