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

댓글을 달아 주세요