오늘은 이중 연결 리스트에 대해 다시한번 기억을 되살렸다.

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

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

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

 으허허~


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

댓글을 달아 주세요

자료구조 마지막 실습..

오늘로서 자료구조 수업 및 시험이 모두 끝났다.

C 언어 야매로 배웠더니 2학년 과목이었음에도 불구하고 힘들었던듯 ㅡㅡ;

마지막 실습은 해싱. 오버플로 처리도 없는 해싱이다.ㅋㅋ

/*
***********************************************************************/
/* 작성자 : 박상현                                                                     */
/* 작성일 : 2008. 06. 12
/* Hashing
/************************************************************************/
// 헤더파일 선언
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
#define FULL    1                       // FULL 플래그 정의
// slot 구조체 선언
typedef struct
{
        char key[11];
} slot;
// 해시 테이블 구조체 선언
typedef struct
{
        int fullFlag;                           // 버킷이 꽊 찼는지 표시하는 플래그
        int slotCnt;                            // 슬롯이 찬 개수를 표시
        slot s[2]; // 배열 선언할때는 그러네. 그럼 기본 데이터가 하나 있어야되냐
} element;

int collCnt = 0;                        // 콜리전 횟수
int overCnt = 0;                        // 오버플로 횟수
element hash_table[50];         // 50 크기의 해시 테이블 선언

void initTable();                                       // 해시테이블 초기화
int hash(char *key);                                                    // 해시함수
void linearInsert(slot item);           // 데이터 삽입


void main()
{
        FILE *fp;                                                                               // 파일 포인터
        fp = fopen("data.txt", "r");                                    // 읽기 전용으로 open
        int i = 0, cnt = 0;
        char temp[11];                                                                  // 임시 문자열
        slot item;                                                                              // 임시 슬롯
        int dataCnt = 0;                                                                // 총 데이터 갯수
        while(1)                                                                                // fin 이 나올 때까지 loop
        {
                fscanf(fp, "%s\n", temp);                                       // 파일로부터 문자를 읽어옴
                strcpy(item.key, temp);                                         // 임시 item 에 삽입
                if(strcmp(temp, "fin") == 0)                            // fin 을 만나면 종료    
                        break;
                linearInsert(item);                                                     // 해시테이블에 삽입
                dataCnt++;                                                                      // 데이터 갯수 증가
        }

        printf("\t\tslot1    |    slot2    \n");
        // 해시테이블 출력
        for(i = 0 ; i < 50 ; i++)
        {
                printf("hash value : %d ", i);
                printf("%s  %s\n", hash_table[i].s[0].key, hash_table[i].s[1].key);
        }
        // 각 카운트 변수들 출력
        printf("dataCnt : %d\noverflow : %d\ncollision : %d\n", dataCnt, overCnt, collCnt);

}

/************************************************************************/
/* 함수명 :linearInsert                                                                     */
/* item 을 인자로 받아 해시테이블에 삽입한다.                                           */
/************************************************************************/
void linearInsert(slot item)
{
        int hash_value;
        hash_value = hash(item.key);                    // 해시펑션을 이용하여 해시 값을 구한다.

        // 버킷에 공간이 있다면
        if(hash_table[hash_value].fullFlag != FULL)
        {
                // 슬롯이 하나도 안찼다면
                if(hash_table[hash_value].slotCnt == 0)
                {
                        hash_table[hash_value].slotCnt++;       // 슬롯 count 증가
                        strcpy(hash_table[hash_value].s[0].key, item.key);              // 데이터를 슬롯에 insert

                }
                // 두 개의 슬롯 중 하나만 찼다면
                else
                {
                        collCnt++;                      // Collision 변수 증가
                        hash_table[hash_value].fullFlag = FULL;                 // 슬롯이 꽉찼으므로 플래그를 FULL 로..
                        strcpy(hash_table[hash_value].s[1].key, item.key);              // 데이터를 슬롯에 insert

                }
        }
        // 버킷이 꽉 찼다면
        else
        {
                overCnt++;      // Overflow 변수 증가
                collCnt++; // Collision 변수 증가
        }
}

/************************************************************************/
/* 함수명 : hash                                                                  */
/* key 값을 인자로 받아 재산 잔여법을 사용하여 해싱한뒤 그 값을 리턴한다. */
/************************************************************************/
int hash(char *key)
{
        unsigned hash_value;
        for(hash_value = 0 ;  *key != '\0' ; key++)
            hash_value = *key + 51 * hash_value;

    return hash_value % 50;
}

/************************************************************************/
/* 함수명 : initTable                                                                     */
/* 해시테이블을 초기화 한다.
/************************************************************************/
void initTable()
{
        int i;
        for(i = 0 ; i < 50 ; i++)
        {
                hash_table[i].s[0].key[0] = NULL;
                hash_table[i].s[1].key[0] = NULL;

        }
}

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

댓글을 달아 주세요

희소행렬을 transpose 시키는 프로그램을 작성하였다.

transpose, fast_transpose 두 가지 방법이 있다.

#include "stdio.h"

#define  MAX_COL 50
// 희소행렬 구조체 정의 - ( 행, 열, 값 )
typedef struct
{
 int row;
 int col;
 int value;
} term;

void transpose(term a[], term b[]);
void fast_transpose(term a[], term b[]);
void init(term a[]);

/************************************************************************/
/* 함수명 : main                                                       */
/* transpose 와 fast_transpose 함수를 테스트 해본다.     */
/************************************************************************/
void main(int argc, char* argv[])
{
 term a[MAX_COL], b[MAX_COL];
 init(a);
 int i;

 for(i = 0 ; i < 9 ; i++)
 {
  printf("%d, %d, %d\n", a[i].row, a[i].col, a[i].value);
 }
 transpose(a, b);    // normal transpose
 fast_transpose(a, b);   // fast transpose
 printf("\n");
 for(i = 0 ; i < 9 ; i++)
 {
 
  printf("%d, %d, %d\n", b[i].row, b[i].col, b[i].value);
 }
}

/************************************************************************/
/* 함수명 : init                                                        */
/* sparse_matrix 를 초기화 한다.          */
/************************************************************************/
void init(term a[])
{
 a[0].row = 6;
 a[0].col = 6;
 a[0].value = 8;

 a[1].row = 0; a[1].col = 0; a[1].value = 15;
 a[2].row = 0; a[2].col = 3; a[2].value = 22;
 a[3].row = 0; a[3].col = 5; a[3].value = 15;
 a[4].row = 1; a[4].col = 1; a[4].value = 11;
 a[5].row = 1; a[5].col = 2; a[5].value = 3;
 a[6].row = 2; a[6].col = 3; a[6].value = 6;
 a[7].row = 4; a[7].col = 0; a[7].value = 91;
 a[8].row = 5; a[8].col = 2; a[8].value = 28;
 
}

/************************************************************************/
/* 함수명 : fast_transpose                                              */
/* normal transpose 함수의 연산 시간을 절약하기 위한 알고리즘이다.  */
/* 원래 행렬의 각 열에 대한 원소수를 먼저 구해서 전치 행렬에서 각 행에 */
/* 대한 원소수를 결정한다. 이 정보로부터 전치 행렬에서 각 행의 시작 위치*/
/* 를 구하고 원래 행렬에 있는 원소를 하나씩 전치 행렬의 올바른 위치로 */
/* 옮기는 것이다.              */
/* transpose 함수에서는 O( columns * elements ) 의 시간 복잡도가 나오는 */
/* 데 반하여 fast_transpose 의 시간 복잡도는 O( columns + elements ) 로 */
/* 원소의 수가 적은 경우에 훨씬 빠르다.
/************************************************************************/
void fast_transpose(term a[], term b[])
{
 int row_terms[MAX_COL], starting_pos[MAX_COL];
 int i, j, num_cols = a[0].col, num_terms = a[0].value;
 b[0].row = num_cols;
 b[0].col = a[0].row;
 b[0].value = num_terms;

 if(num_terms > 0)
 {
  for(i = 0 ; i < num_cols ; i++)   // 열의 갯수만큼 반복하며 row_terms 배열을 0 으로 초기화
  {
   row_terms[i] = 0;
  }
  for(i = 1 ; i <= num_terms ; i++)  // 원소가 있는 열의 인덱스에 해당하는 row_terms 의 값을 ++
  {          // ( 열에 존재하는 원소의 개수 )
   row_terms[a[i].col]++;
   
  }

  starting_pos[0] = 1;     //  첫번째 원소는 b[1] 에 저장
 
  for(i = 1 ; i < num_cols ; i++)   // starting_pos[i] 는 전치행렬의 행 i 에 대한 시작위치를 나타낸다.
  {
   starting_pos[i] = starting_pos[i - 1] + row_terms[i - 1]; // 바로 전 인덱스에 해당하는 row_terms 와 starting_pos
                   // 의 합이 starting_pos[i] 가 된다.
  }
  printf("\n");
  for(i = 0 ; i < num_cols ; i++)
  {
   printf("row_terms[%d] = %d\t", i, row_terms[i]);  // row_terms 출력
   printf("starting_pos[%d] = %d\n", i, starting_pos[i]); // starting_pos 출력
  }
  for(i = 1 ; i <= num_terms ; i++)    
  {
   j = starting_pos[a[i].col]++;    // 각 행의 시작 위치
   b[j].row = a[i].col;      // 구한 올바른 위치에 원소를 옮긴다.
   b[j].col = a[i].row;      //
   b[j].value = a[i].value;     //
  }
 }
}

/************************************************************************/
/* 함수명 ; transpose                                                 */
/* a 를 transpose 하여 b 를 생성한다.         */
/************************************************************************/
void transpose(term a[], term b[])
{
 int n, i, j, currentb;
 n = a[0].value;    // 총 원소수
 b[0].row = a[0].col;  // b 의 row = a 의 col
 b[0].col = a[0].row ;  // b 의 col = a 의 row
 b[0].value = n;

 if(n > 0)
 {
  currentb = 1;
  for(i = 0 ; i < a[0].col ; i++)
  { // a 에서의 열별로 transpose
   for(j = 1; j <= n ; j++)
   { // 현재의 열로부터 원소를 찾는다.
    if(a[j].col == i)
    {
     // 현재의 열에 있는 원소를 b 에 저장한다.
     b[currentb].row = a[j].col;
     b[currentb].col = a[j].row;
     b[currentb].value = a[j].value;
     currentb++;
    }
   }
  }
 }
}

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

댓글을 달아 주세요


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은 메모리 초기화를 시켜서 할당 합니다.


4학년 1학기 자료구조 재수강...ㄷㄷㄷ;

새로 배우는 기분으로 열심히^^

/***************************************************************************************************************
 *
 * 파일명 : test.cpp
 * 파일내용 : data.txt 의 파일 내용을 읽어와 구조체에 저장한 뒤 출력한다.
 * 작성자 : 박상현
 * 작성일 : 2008. 3. 6.
 * 과목명 : data structure
 * 교수님 : 유하진 교수님
 *
 *************************************************************************************************************/


#include "stdio.h"
#include "string.h"
#include "stdlib.h"

typedef struct
{
 char name[10];
 int id;
 float math;
 float english;
} student;

void main(int argc, char *argv[])
{
 student students[10];
 FILE *fp;
 int sNum, i;
 float totalMath = 0, totalEng = 0;

 fp = fopen("data.txt", "r");  // 파일을 읽기 전용으로 open
 fscanf(fp, "%d\n", &sNum);

 for(i = 0 ; i < sNum ; i++)
 {
  fscanf(fp, "%s\n", &students[i].name);
  fscanf(fp, "%d\n", &students[i].id);
  fscanf(fp, "%f\n", &students[i].math);
  fscnaf(fp, "%f\n", &students[i].english);
  printf("이름 : %s\n", students[i].name);
  printf("학번 : %d\n", students[i].id);
  printf("수학 : %.2f\n", students[i].math);
  printf("영어 : %.2f\n", students[i].english);
  totalMath += students[i].math; totalEng += students[i].english;
 }

 printf("\n수학 평균 : %.2f\n", totalMath / sNum);
 printf("영어 평균 : %.2f\n", totalEng / sNum);



}

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

댓글을 달아 주세요

/************************************************************************/
/* Stack.cpp : 배열을 사용한 스택                                       */
/* 푸시와 팝을 이용한 LIFO( Last In First Out ) 구조     */
/************************************************************************/

#include <STDIO.H>

#define MAX  10

int stack[MAX];
int top;

/************************************************************************/
/* 함수명 : init_stack                                                  */
/* 스택 초기화 top = -1 이다.           */
/************************************************************************/
void init_stack( void )
{
 top = -1;
}

/************************************************************************/
/* 함수명 : push                                                        */
/* t 를 스택에 넣는다.             */
/************************************************************************/
int push(int t)
{
 if(top >= MAX - 1)
 {
  printf("\n Stack overflow.");
  return -1;
 }
 stack[++top] = t;
 return t;
}


/************************************************************************/
/* 함수명 : pop                                                         */
/* 가장 위에 있는 데이터를 리턴한다.         */
/************************************************************************/
int pop( void )
{
 if(top < 0)
 {
  printf("\n Stack underflow.");
  return -1;
 }
 return stack[top--];
}

/************************************************************************/
/* 함수명 : print_stack                                                 */
/* 스택의 내용을 모두 출력한다.           */
/************************************************************************/
void print_stack( void )
{
 int i;
 printf("\n  Stack Contents : Top ----> Bottom\n");
 for(i = top ; i >= 0 ; i--)
  printf("%-6d", stack[i]);
}

/************************************************************************/
/* 함수명 : main                                                        */
/* main function              */
/************************************************************************/
void main( void )
{
 int i;
 init_stack();

 printf("\nPush 5, 4, 7, 8, 2, 1");
 push(5);
 push(4);
 push(7);
 push(8);
 push(2);
 push(1);
 print_stack();

 printf("\nPop");
 i = pop();
 print_stack();
 printf("\n popping value is %d", i);

 printf("\nPush 3, 2, 5, 7, 2");
 push(3);
 push(2);
 push(5);
 push(7);
 push(2);
 print_stack();

 printf("\nNow stack is full, push 3");
 push(3); // 오버플로 에러남
 print_stack();

 printf("\nInitialize stack");
 init_stack();
 print_stack();

 printf("\nNow stack is empty, pop");
 i = pop(); // 언더플로 에러
 print_stack();
 printf("\n popping value is %d", i);
}


 

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

댓글을 달아 주세요

이중 연결 리스트이다.

참고문헌 : C 로 배우는 알고리즘 1


/************************************************************************/
/* DoubledLinkedList.cpp : 이중 연결 리스트 구현                        */
/* 이 자료구조에서는 단순 연결 리스트와 비교할 때      */
/* 다음 노드뿐만 아니라 이전노드도 링크로 가지고      */
/* 접근할 수 있다는 것이 장점이다.          */
/* 하나의 링크를 더 사용하기 때문에 단순 연결 리스트보다는 노드당  */
/* 2 ~ 4 바이트 정도 더 소요된다.          */
/************************************************************************/

#include <STDIO.H>
#include <MALLOC.H>

typedef struct _dnode
{
 int key;  /* 정보 저장 */
 struct _dnode *prev; /* 바로 전의 노드를 가리키는 링크 */
 struct _dnode *next; /* 바로 뒤의 노드를 가리키는 링크 */
} dnode;

dnode *head, *tail;

/************************************************************************/
/* 함수명 : init_dlist                                                  */
/* 이중 연결 리스트를 초기화한다.          */
/************************************************************************/
void init_dlist( void )
{
 head = (dnode*)malloc(sizeof(dnode));
 tail = (dnode*)malloc(sizeof(dnode));
 head->next = tail;  
 head->prev = head;
 tail->next = tail;
 tail->prev = head;
}

/************************************************************************/
/* 함수명 : insert_dnode_ptr                                            */
/* 포인터 t 와 정수 k 를 입력받아 t 앞에 k 를 가지는 노드를 삽입한다. */
/************************************************************************/
dnode *insert_dnode_ptr(int k, dnode *t)
{
 dnode *i; // 삽입될 노드
 // head 앞에는 삽입할 수 없음
 if(t == head)
  return NULL;
 i = (dnode*)malloc(sizeof(dnode));
 i->key = k;
 t->prev->next = i; // t 앞 노드의 다음은 i 노드
 i->prev = t->prev; // i 의 앞은 t 의 앞 노드
 t->prev = i;  // t 의 앞은 i 노드
 i->next = t;  // i 의 다음은 t 노드
 return i;
}

/************************************************************************/
/* 함수명 : delete_dnode_ptr                                            */
/* 인자로 주어진 노드의 포인터 p 를 연결리스트에서 삭제한다.   */
/************************************************************************/
int delete_dnode_ptr(dnode *p)
{
 if(p == head || p == tail) // head, tail 은 삭제할 수 없음
  return 0;
 p->prev->next = p->next; // p 의 prev 의 next 는 p 의 next 노드
 p->next->prev = p->prev; // p 의 next 의 prev 는 p 의 prev 노드
 free(p);
 return 1;
}

/************************************************************************/
/* 함수명 : find_dnode                                                  */
/* 주어진 정수를 key 로 가지는 노드를 찾는다.       */
/************************************************************************/
dnode *find_dnode(int k)
{
 dnode *s;
 s = head->next;
 while(s->key != k && s != tail) // key 가 아니거나 tail 이 아닐동안 loop
  s = s->next;
 return s;
}

/************************************************************************/
/* 함수명 : delete_dnode                                                */
/* 인자를 key 로 가지는 노드를 삭제한다.        */
/************************************************************************/
int delete_dnode(int k)
{
 dnode *s;
 s = find_dnode(k); // k 를 key 로 갖는 노드를 찾는다.
 if(s != tail) // s 가 tail 이 아니면 찾은 것
 {
  s->prev->next = s->next;
  s->next->prev = s->prev;
  free(s);
  return 1;
 }
 return 0;
}

/************************************************************************/
/* 함수명 : insert_dnode                                                */
/* t 를 key 로 갖는 노드 앞에 k 를 key 로 갖는 노드를 삽입    */
/************************************************************************/
dnode *insert_dnode(int k, int t)
{
 dnode *s;
 dnode *i = NULL;
 s = find_dnode(t);
 if( s != tail) // 찾았다면
 {
  i = (dnode*)malloc(sizeof(dnode));
  i->key = k;
  s->prev->next = i; // s 의 prev 노드의 next 는 i 노드
  i->prev = s->prev; // i 의 prev 노드는 s 의 prev 노드
  s->prev = i;  // s 의 prev 노드는 i 노드
  i->next = s;  // i 의 next 노드는 s 노드
 }
 return i;
}

/************************************************************************/
/* 함수명 : ordered_insert                                              */
/* 임의의 순서로 입력되는 정수들을 오름차순으로 삽입     */
/************************************************************************/
dnode *ordered_insert(int k)
{
 dnode *s;
 dnode *i;
 s = head->next;
 while(s->key <= k && s != tail) // 삽입될 자리를 찾음
  s = s->next;
 i = (dnode*)malloc(sizeof(dnode));
 i->key = k;
 s->prev->next = i;
 i->prev = s->prev;
 s->prev = i;
 i->next = s;
 return i;
}

/************************************************************************/
/* 함수명 : print_dlist                                                 */
/* 리스트를 출력한다.             */
/************************************************************************/
void print_dlist(dnode *p)
{
 printf("\n");
 while(p != tail)
 {
  printf("%-8d", p->key);
  p = p->next;
 }
}

/************************************************************************/
/* 함수명 : delete_all                                                  */
/* 모든 노드를 삭제한다.            */
/************************************************************************/
void delete_all( void )
{
 dnode *p;
 dnode *s;
 p = head->next;
 while(p != tail)
 {
  s = p;
  p = p->next;
  free(s);
 }
 head->next = tail;
 tail->prev = head;
}

/************************************************************************/
/* 함수명 : main                                                        */
/* main function              */
/************************************************************************/
void main( void )
{
 dnode *t;
 init_dlist();
 
 ordered_insert(1);
 ordered_insert(2);
 ordered_insert(5);
 ordered_insert(6);
 
 ordered_insert(8);
 ordered_insert(9);
 ordered_insert(10);
 ordered_insert(11);
 ordered_insert(12);

 printf("\n Initial Linked list is ");
 print_dlist(head->next);

 printf("\n Finding 6 is %ssuccessful", find_dnode(6) == tail ? "un" : "");

 t = find_dnode(5);
 printf("\n Finding 5 is %ssuccessful", t == tail ? "un" : "");

 printf("\n Inserting 7 before 6");
 insert_dnode_ptr(7, t);
 print_dlist(head->next);

 t = find_dnode(3);
 printf("\n Deleting 10");
 delete_dnode_ptr(t);
 print_dlist(head->next);

 printf("\n Inserting node 2 before 5");
 insert_dnode(2, 10);
 print_dlist(head->next);

 printf("\n Deleting node 2");
 if(!delete_dnode(2))
  printf("\n deleting 2 is unsuccessful");
 print_dlist(head->next);

 printf("\n Deleting node 1");
 delete_dnode(1);
 print_dlist(head->next);

 printf("\n Inserting 15 at first");
 insert_dnode_ptr(15, head->next);
 print_dlist(head->next);
 
 printf("\n Deleting all node");
 delete_all();
 print_dlist(head->next);
 
}

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

댓글을 달아 주세요