'Data Structure'에 해당되는 글 3건

  1. 2008.08.28 이중 연결 리스트
  2. 2008.03.20 문자열의 배열의 순열 만들기
  3. 2008.03.09 자료구조. malloc, calloc 사용법 (2)
 오늘은 이중 연결 리스트에 대해 다시한번 기억을 되살렸다.

자료구조의 기본 중의 기본이지만 구현해 볼 때마다 책 없이 혼자하라고 하면

시간이 꽤 걸린다. 나만그런가;ㅋ

어쨌든 오늘 중요한 자료구조를 또 한번 코딩해본 것은 의미있는 일이다.

 으허허~


      1 #include <stdio.h>
      2 #include <stdlib.h>
      3 #include <string.h>
      4
      5 struct A
      6 {
      7         char name[20];
      8         int age;
      9         int salary;
     10         struct A *before;
     11         struct A *next;
     12 } *head, *tail;
     13
     14 void input(void);
     15 void output(void);
     16
     17 int main()
     18 {
     19         head = tail = NULL;
     20         input();
     21         output();
     22         return 0;
     23 }
     24
     25 void input (void )
     26 {
     27         struct A *ptr;
     28
     29         while(1)
     30         {
     31                 if((ptr = (struct A *)malloc(sizeof(struct A))) == NULL)
     32                 {
     33                         printf("Memory Allocation Error\n");
     34                         exit(1);
     35                 }
     36
     37                 printf("\n성명 ? ");
     38                 gets(ptr -> name);
     39                 if(!strcmp(ptr -> name, "end"))
     40                         break;
     41                 printf("나이 ? ");
     42                 scanf("%d", &ptr -> age);
     43                 printf("월급 ? ");
     44                 scanf("%d%*c", &ptr -> salary);
     45                 ptr -> before = NULL;
     46                 ptr -> next = NULL;
     47
     48                 if(head == NULL)
     49                         head = tail = ptr;
     50                 else
     51                 {
     52                         ptr -> before = tail;
     53                         tail -> next = ptr;
     54                         tail = ptr;
     55                 }
     56         }
     57         free(ptr);
     58 }
     59
     60 void output(void)
     61 {
     62         struct A *ptr;
     63
     64         printf("\nNode List head -> tail \n");
     65         ptr = head;
     66         while(ptr)
     67         {
     68                 printf("name : %s, age : %d, salary : %d\n", ptr -> name, ptr -> age, ptr -> salary);
     69                 ptr = ptr -> next;
     70         }
     71         printf("\nNode List tail -> head \n");
     72         ptr = tail;
     73         while(ptr)
     74         {
     75                 printf("name : %s, age : %d, salary : %d\n", ptr -> name, ptr -> age, ptr -> salary);
     76                 ptr = ptr -> before;
     77         }
     78 }
     79
     80

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

댓글을 달아 주세요

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

댓글을 달아 주세요


malloc 과 calloc 는 기본적으로 힙에 메모리 영역을 할당하는 함수이다.

참고로 heap 이란 데이터 세크먼트의 끝과 스택의 상위부분 사이에 있는

당장 쓰이지 않는 영역을 말한다.

calloc 이 malloc 에 비해 다른점은 할당할 메모리의 양을 표시하는 방법이다.

calloc 은 구조체나 배열의 동적 메모리 할당을 위해 주로 사용되며

메모리 해제는 malloc 처럼 free 로 하면 된다.

calloc 은 다음과 같이 사용한다.

int *fi;

fi = (int *)calloc(5, sizeof(int));

malloc 은 다음과 같이 사용한다.

int *fi;

fi = (int *)malloc(sizeof(int) * 5));

이렇게 하면 결국 같은 뜻이 되는 것이다.

*fi = 1, *(fi + 1) = 2, *(fi + 2) = 2, ...

위처럼 사용하면 된다.

아 그리고 또 하나의 차이점은 calloc 으로 메모리를 할당하게 되면

모두 0으로 초기화 된다는 것이 malloc 과의 차이점이다.

참고로 다음처럼 매크로로 만들어서 사용해도 편리하겠다.

// malloc 매크로로 지정
#define MALLOC(p,t,s)  if(!((p) = (t*)malloc(s))) { fprintf(stderr, "Insufficient memory"); exit(EXIT_FAILURE); }

 // 매크로를 사용한 메모리 할당
 MALLOC(pi, int, sizeof(int));

마지막으로 잊지 말아야 할 것은

항상 메모리 공간이 필요없게 되면

free(fi); 해서 해제를 해주어야 한다는 것. 잊지말도록 하자.

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

댓글을 달아 주세요

  1. afewgoodman 2009.12.01 16:02  댓글주소  수정/삭제  댓글쓰기

    calloc과 malloc의 차이점 중 중요한 것이 빠졌네요. malloc은 메모리 초기화 없이 그냥 할당하고요... calloc은 메모리 초기화를 시켜서 할당 합니다.