2019 자료구조

IVIS wiki

Top

목차

강의 개요

  • 효율적이고 체계적인 프로그래밍 기법을 습득하는데 기본이 되는 자료구조를 익힌다.
  • 컴퓨터 프로그래밍을 통해 문제해결을 할 수 있는 능력을 익힌다
  • 강의 진행 :
    • 강사의 강의와 토론 그리고 프로그래밍 실습을 통하여 프로그래밍 기법을 익힌다
    • 주당 3시간의 강의이며 이론 강의와 프로그래밍 실습을 병행한다.
  • 강의실 : 51호관 310호실
    • 강의시간 : 매주 화요일 오후 3:00-4:15, 목요일 오후 4:30-5:45(75분 강의)

수강생

강의 내용

  • 기존에 학습한 프로그래밍 관련 교과목을 바탕으로 효율적인 프로그래밍을 위한 자료구조에 대하여 알아보도록 하자.

강의 교재

  • C언어로 쉽게 풀어쓴 자료구조[개정3판]
    • 최영규, 천인국, 공용해 공저
    • 생능출판사

2019 IT DS textbook.jpg

과제관련

  • 과제 제출 기간은 제출일로부터 일주일
  • 각 문제 마다 아래 채점 기준을 만족 못할 시 한 문제당 1점씩 감점

  • 과제 표지
    • 매 표지 마다 과제 번호를 기입한다. ex) #1, #2, ...
    • 스탠플러는 왼쪽 상단에 찍는다.
  • 이론 문제
    • 문제와 답을 적는다.
      • 문제를 적지 않을 시 감점
      • 타이핑 가능
      • 스캔 불허
  • 실습 문제
    • 문제와 소스코드을 적는다.
      • 문제를 적지 않을 시 감점
      • 타이핑 가능
      • 스캔 불허
    • 실행 결과를 캡쳐하여 삽입한다.
      • 배경은 흰색으로 한다.
    • 코드에는 주석을 달도록한다.
      • 주석 달지 않을 시 감점
    • 각 실습문제마다 느낀점이나 어려웠던 점을 2문장 이상 적어서 제출한다.
      • 느낀점을 적지 않을시 감점
      • 풀지 못한 문제나 어려운 문제도 반드시 느낀점을 적도록 한다.
  • 과제 샘플

2017 VP Reportform1.png 2017 VP Reportform2.png

1주차 강의(3월 5일, 7일)

  • 강의내용, 교재등에 대한 소개
  • 자료구조를 알아야 하는 이유
  • 컴퓨터를 이용한 문제해결에서 자료구조가 중요한 이유
  • 강의의 방향
  • 수강생이 알아야할 내용들
    • 수강생들은 C 혹은 C++ 프로그래밍을 학습하여야 함
    • 동적 자료구조에 대한 이해가 반드시 필요함

겨울방학 해외탐방 특강

강의 자료( 강의소개, 1장)

Lab(실습) #1

  • 다음의 코드는 1부터 n까지의 합을 구하는 프로그램과 그 수행시간을 구하는 코드이다.
  • 다음 코드를 입력하여 실행한 후 수행시간을 구해 보도록 하자.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 1에서 n까지의 합을 구하는 함수임
int sumto(int n)
{
    int sum = 0;   // sum을 초기화 함
    // for 반복문을 이용하여 반복계산
    for(int i=1; i<=n; i++)
    {
        sum += i;
    }
    return sum; // 결과를 반환함
}

int main( void )
{
    long  count = 100000;   // 조절가능한 값
    clock_t start, finish;
    double  duration;
    
    /* Measure the duration of an event. */
    printf("%li번의 루프를 수행하는 시간은  ", count);
    start = clock();
    //printf("sum to 100 = %d \n", sumto(100));
    for(int i=0; i<count; i++)
        sumto(100);
    finish = clock();
    duration = (double)(finish - start) / CLOCKS_PER_SEC;
    printf("%f 초입니다.\n", duration);
    
    return 0;
}

Lab(실습) #2

  • 다음의 코드는 순차탐색을 C로 구현한 프로그램이다
  • 다음의 코드를 보고 key값으로 10을 입력해셔 "10(은)는 배열에 없음"이 출력되도록 코드를 완성하라
//
//  main.c
//  sequential_search
//
//  Created by DongGyu Park on 2018. 3. 7..
//  Copyright © 2018년 ProfPark. All rights reserved.
//

#include <stdio.h>

// 순차 탐색(Sequential search) 알고리즘
int main()
{
    int arr[]={12,23,78,98,67,56,45,19,65,9},key,i,flag=0;
    
    printf("배열 arr의 멤버 \n");
    for(i=0;i<10;i++)
        printf("%4d",arr[i]);
    
    printf("\narr 배열에서 찾고자하는 수를 입력하세요 : ");
    scanf("%d",&key);
    
    for(i=0;i<10;i++) {
       // 이 부분에 코드를 완성하시오
    }

    if(flag==1)
        printf("\n %d(은)는 배열에 있음\n",key);
    else
        printf("\n %d(은)는 배열에 없음\n",key);
    
    return 0;
}

2018-DS seq search.png

2주차 강의(3월 12일, 14일)

  • 의사 코드와 추상자료형
  • 시간복잡도와 Big-Oh 개념
    • Microsoft Visual Studio 2013, 2015 설치하기
    • 시간복잡도 - Big-Oh의 개념
    • 순환(Recursion)의 개념
      • 순환을 이용한 문제 풀이

강의자료(2장 순환, 3장 배열구조체포인터)

과제 #1

  • 제목 : 1장 연습문제 풀이(전체)
  • 제출일 : 3월 19일
    • 교재 1장의 연습문제를 모두 풀어서 과제 보고서로 제출한다
      • 문제와 답을 적도록 한다
      • 풀이과정이 있을 경우 풀이 과정도 적도록 한다

과제 #2 : 동영상강의 수강(배열, 포인터, 포인터와 증가연산)

수강 : 홍길동
수강평 : 0000000 에 대해 알게되었으며, 0000라고 생각합니다.
궁금한점 : 0000000에 관한 부분이 잘 이해가 안됩니다. 0000000는 0000이 아닌가요? “등
형식으로 반드시 자기 이름을 달아주십시오.

Lab #2-1, #2-2 : 팩토리얼

#include <stdio.h>
#include <time.h>

// 순환문을 이용
int factorial(int n){
    if(n <= 1) return (1);
    else return (n*factorial(n-1));
}

// 반복문을 이용
int factorial_iter(int n){
    int k, v=1;
    for(k=n; k>0; k--){
        v = v*k;
    }
    return (v);
}

int main(int argc, const char * argv[]) {
    long  count = 1000;   // 조절가능한 값 - 반복횟수
    clock_t start, finish;
    double  duration;
    
    /* Measure the duration of an event. */
    start = clock();
    for(int i=0; i<count; i++)
        factorial(30);
    finish = clock();
    duration = (double)(finish - start) / CLOCKS_PER_SEC;
    printf("재귀적 방법으로 factorial(30)을 1000번 연산하면 %f 초입니다.\n", duration);
    
    /* Measure the duration of an event. */
    start = clock();
    for(int i=0; i<count; i++)
        factorial_iter(30);
    finish = clock();
    duration = (double)(finish - start) / CLOCKS_PER_SEC;
    printf("반복적 방법으로 factorial(30)을 1000번 연산하면 %f 초입니다.\n", duration);
    
    return 0;
}
  • factorial(30)을 재귀적 방법과 반복적 방법으로 각각 1000번 수행한 결과 - 수행시간

2019 DS factorial.png

Lab #2-3, #2-4 : 지수 구하기

#include <stdio.h>
#include <time.h>

// 순환문을 이용
double fast_power(double x, int n)
{
    if( n==0 ) return 1;
    else if ( (n%2)==0 ) {
        return fast_power(x*x, n/2);
    }
    else return x*fast_power(x*x, (n-1)/2);
}

// for 반복문을 이용
double slow_power(double x, int n)
{
    int i;
    double result = 1.0;
    
    for(i=0;i<n;i++)
        result = result * x;
    return result ;
}
//
int main()
{
    int i, count = 1000000;
    double r;
    clock_t start, end;
    start = clock();
    for(i=0;i<count;i++)
        r = slow_power(2,500);
    end =clock();
    printf("반복문을 사용한 지수계산의 소요시간 : ");
    printf("%f\n", (double)(end - start) / CLOCKS_PER_SEC);
    
    start = clock();
    for (i = 0; i<count; i++)
        r = fast_power(2, 500);
    end = clock();
    printf("재귀문을 사용한 지수계산의 소요시간 : ");
    printf("%f\n", (double)(end - start) / CLOCKS_PER_SEC);
    
    return 0;
}
  • 2의 500승을 1000000번 수행한 결과 - 수행시간

2019 DS exponent.png

Lab #2-5, #2-6 : 피보나치 수열

  • 피보나치 수열 계산의 빠른 버전과 느린 버전
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 재귀문을 이용한 피보나치 수 구현
int fib(int n)
{
    if (n==0) return 0;
    else if(n==1) return 1;
    else return (fib(n-1) + fib(n-2));
}

// 반복문을 이용한 피보나치 수 구현
int fib_iter(int n)
{
    if (n == 0) return 0;
    if (n == 1) return 1;
        
    int pp = 0;	
    int p = 1;
    int result = 0;
        
    for (int i = 2; i <= n; i++) {
        result = p + pp;
        pp = p;
        p = result;
    }
    return result;
}

int main( void )
{
    long  count = 1000;   // 조절가능한 값 - 반복횟수
    clock_t start, finish;
    double  duration;
    // 두가지 방법을 1000번 수행하여 시간을 비교해 보자
    /* Measure the duration of an event. */
    start = clock();
    for(int i=0; i<count; i++)
        fib(30);
    finish = clock();
    duration = (double)(finish - start) / CLOCKS_PER_SEC;
    printf("재귀적 방법으로 fib(30)을 1000번 연산하면 %f 초입니다.\n", duration);
    
    /* Measure the duration of an event. */
    start = clock();
    for(int i=0; i<count; i++)
        fib_iter(30);
    finish = clock();
    duration = (double)(finish - start) / CLOCKS_PER_SEC;
    printf("반복적 방법으로 fib_iter(30)을 1000번 연산하면%f 초입니다.\n", duration);
    
    return 0;
}
  • fib(30)을 재귀적 방법과 반복적 방법으로 각각 1000번 수행한 결과 - 수행시간

2017 DS fibonacci.png

Lab #2-8 : Tower of Hanoi

#include <stdio.h>

void hanoi_tower(int n, char from, char tmp, char to)
{
    // 원판이 1개이면 이것을 from에서 to로 옮기면 된다
    if( n==1 ) printf("원판 1을 %c 에서 %c으로 옮긴다.\n",from,to);
    else {
        // n-1개의 원판을 from에서 tmp로 이동시킨다.
        // 이를 위해 원래의 tmp를 to로 to를 tmp로 둔다
        hanoi_tower(n-1, from, to, tmp);
        printf("원판 %d을 %c에서 %c으로 옮긴다.\n",n, from, to);
        // 이제 tmp에 쌓여있는 원판을 원래의 from 위치를
        // 임시위치(tmp)로 두고 to로 이동시키면 된다
        hanoi_tower(n-1, tmp, from, to);
    }
}
int main(void)
{
    hanoi_tower(4, 'A', 'B', 'C');
    return 0;
}

3주차 강의(3월 19일, 21일)

  • 3월 21일은 개교기념일 휴일입니다
    • 배열과 구조체 데이터의 응용 : 다항식
    • 배열의 구조, 2차원 배열의 구조
    • 배열을 이용한 다항식의 표현 방법

Lab #3-1 : 구조체를 이용한 복소수 표현

#include <stdio.h>

typedef struct {
    double real;    // 복소수의 실수부
    double imag;    // 복소수의 허수부
} Complex;

void print_complex(Complex c) {
    printf("%4.1f + %4.1fi\n", c.real, c.imag);
}
void reset_complex(Complex c) {
    c.real = c.imag = 0.0;
}

int main() {
    Complex a = { 1.0, 2.0 };
    printf("초기화 이전: ");
    print_complex(a);        // 복소수 화면 출력
    reset_complex(a);        // 초기화가 되지 않음
    printf("초기화 이후: ");
    print_complex(a);        // 복소수 화면 출력
    
    return 0;
}

Lab #3-2 : 구조체를 이용한 학생정보 표현

#include <stdio.h>
#include <stdlib.h>

struct student{
    int student_id;
    char name[10];
    double grade;
};

int main(void) {
    struct student s = {20170001, "kim", 3.4}; // 초기화
    printf("학번: %d\n",s.student_id);
    printf("이름: %s\n",s.name);
    printf("학점: %f\n",s.grade);
    
    s.student_id = 20170001;
    strcpy(s.name,"홍길동");
    //s.name = "홍길동"; // 이렇게 하면 안됩니다
    s.grade = 4.3;
    
    printf("학번: %d\n",s.student_id);
    printf("이름: %s\n",s.name);
    printf("학점: %f\n",s.grade);
    return 0;
}

Lab #3-3 : 다항식 입력과 덧셈

#include <stdio.h>

#define MAX_DEGREE    101

typedef struct {
    int degree;
    float coef[MAX_DEGREE];
} Polynomial;

Polynomial read_poly()
{
    int i;
    Polynomial p;
    
    printf("다항식의 최고 차수를 입력하시오: ");
    scanf("%d", &p.degree);
    printf("각 항의 계수를 입력하시오 (총 %d개): ", p.degree + 1);
    for (i = 0; i <= p.degree; i++)
        scanf("%f", p.coef + i);
    return p;
}

void print_poly(Polynomial p, char str[])
{
    int i;
    printf("\t%s", str);
    for (i = 0; i<p.degree; i++)
        printf("%5.1f x^%d + ", p.coef[i], p.degree - i);
    printf("%4.1f\n", p.coef[p.degree]);
}

Polynomial add_poly(Polynomial a, Polynomial b)
{
    int i;
    Polynomial p;
    if (a.degree > b.degree) {
        p = a;
        for (i = 0; i <= b.degree; i++)
            p.coef[i + (p.degree - b.degree)] += b.coef[i];
    }
    else {
        p = b;
        for (i = 0; i <= a.degree; i++)
            p.coef[i + (p.degree - a.degree)] += a.coef[i];
    }
    return p;
}

int main()
{
    Polynomial a, b, c;
    a = read_poly();
    b = read_poly();
    c = add_poly(a, b);
    print_poly(a, " A = ");
    print_poly(b, " B = ");
    print_poly(c, "A+B= ");
    
    return 0;
}
  • 수행결과

2018 DS addPoly.png

Lab : 프로그램 3.2 다항식 덧셈

#include <stdio.h>

#define MAX(a,b) (((a)>(b))?(a):(b))
#define MAX_DEGREE 101
typedef struct {             // 다항식 구조체 타입 선언
    int degree;            // 다항식의 차수
    float coef[MAX_DEGREE];    // 다항식의 계수
} polynomial;

// C = A+B 여기서 A와 B는 다항식이다. 구조체가 반환된다.
polynomial poly_add1(polynomial A, polynomial B)
{
    polynomial C;                // 결과 다항식
    int Apos = 0, Bpos = 0, Cpos = 0;    // 배열 인덱스 변수
    int degree_a = A.degree;
    int degree_b = B.degree;
    C.degree = MAX(A.degree, B.degree); // 결과 다항식 차수
    
    while (Apos <= A.degree && Bpos <= B.degree) {
        if (degree_a > degree_b) {  // A항 > B항
            C.coef[Cpos++] = A.coef[Apos++];
            degree_a--;
        }
        else if (degree_a == degree_b) {  // A항 == B항
            C.coef[Cpos++] = A.coef[Apos++] + B.coef[Bpos++];
            degree_a--; degree_b--;
        }
        else {            // B항 > A항
            C.coef[Cpos++] = B.coef[Bpos++];
            degree_b--;
        }
    }
    return C;
}

void print_poly(polynomial p)
{
    for (int i = p.degree; i>0; i--)
        printf("%3.1fx^%d + ", p.coef[p.degree - i], i);
    printf("%3.1f \n", p.coef[p.degree]);
}

// 주함수
int main(void)
{
    polynomial a = { 5,{ 3, 6, 0, 0, 0, 10 } };
    polynomial b = { 4,{ 7, 0, 5, 0, 1 } };
    polynomial c;
    
    print_poly(a);
    print_poly(b);
    c = poly_add1(a, b);
    printf("--------------------------------------------------\n");
    print_poly(c);
    return 0;
}
  • 수행결과

2019 DS addPoly 3.2.png

도전 문제

  • 위의 다항식 덧셈 문제를 수정하여 보자
    • 이 프로그램은 최고차항이 각각 x^3, -x^3인 항에 대하여 다음과 같은 결과를 출력할 것이다

2019 DS addPoly 3.2 with wrong.png

  • 이 프로그램을 수정하여 다음과 같이 계수가 0인 항목이 나타나지 않도록 하자

2019 DS addPoly 3.2 with right.png

Lab #3-4 : 다항식의 덧셈

#include <stdio.h>
#include <stdlib.h>

#define MAX_TERMS 101

// 다항식의 계수와 차수를 저장하는 구조체
struct {
    float coef; // 항의 계수
    int expon;  // 항의 차수
} terms[MAX_TERMS] = {{8,3}, {7,1}, {1,0}, {10,3}, {3,2}, {1,0}};
int avail = 6;
//
char compare(int a, int b)
{
    if (a>b) return '>';
    else if (a == b) return '=';
    else return '<';
}

// 새로운 항을 다항식에 추가한다.
void attach(float coef, int expon)
{
    if (avail>MAX_TERMS){
        fprintf(stderr, "항의 개수가 너무 많음\n");
        exit(1);
    }
    terms[avail].coef = coef;
    terms[avail++].expon = expon;
}

void poly_print(int Cs, int Ce)
{
    for(int i=Cs;i<Ce;i++)
        printf("%4.1f X ^ %d + ", terms[i].coef, terms[i].expon);
    printf("%4.1f X ^ %d ", terms[Ce].coef, terms[Ce].expon);
    printf("\n");
}

// 두 다항식을 합하는 함수 C=A+B
void poly_add2(int As, int Ae, int Bs, int Be, int *Cs,int *Ce)
{
    float tempcoef;
    *Cs = avail;
    
    while (As <= Ae && Bs <= Be)
        switch (compare(terms[As].expon, terms[Bs].expon)){
            case '>': 	// A의 차수 > B의 차수
                attach(terms[As].coef, terms[As].expon);
                As++;			break;
            case '=': 	// A의 차수 == B의 차수
                tempcoef = terms[As].coef + terms[Bs].coef;
                if (tempcoef)
                    attach(tempcoef, terms[As].expon);
                As++; Bs++;		break;
            case '<': 	// A의 차수 < B의 차수
                attach(terms[Bs].coef, terms[Bs].expon);
                Bs++;			break;
        }
    // A의 나머지 항들을 이동함
    for (; As <= Ae; As++)
        attach(terms[As].coef, terms[As].expon);
    // B의 나머지 항들을 이동함
    for (; Bs <= Be; Bs++)
        attach(terms[Bs].coef, terms[Bs].expon);
    *Ce = avail - 1;
}
//
int main()
{
    int Cs, Ce;
    poly_add2(0, 2, 3, 5, &Cs, &Ce);
    printf("A = ");
    poly_print(0, 2);
    printf("B = ");
    poly_print(3, 5);
    printf("C = ");
    poly_print(Cs,Ce);
    
    return 0;
}

  • 수행결과

2017 DS Prog3 3.png

과제 #3 : 프로그램 구성요소, 수식, 조건문, 반복문등

수강 : 홍길동
수강평 : 0000000 에 대해 알게되었으며, 0000라고 생각합니다.
궁금한점 : 0000000에 관한 부분이 잘 이해가 안됩니다. 0000000는 0000이 아닌가요? “등
형식으로 반드시 자기 이름을 달아주십시오.

과제 #4

  • 제목 : 2장 연습문제 풀이
  • 제출일 : 3월 28일
    • 연습문제 1, 2, 3, 4, 5, 6, 7, 8, 13, 14번 문제
    • 문제와 답을 손으로 적어서 제출하세요
      • 프로그래밍 문제의 경우에는 소스코드, 수행결과 캡쳐화면을 제출할 것
      • 프로그램시 문제해결 과정의 어려웠던 점과 느낀 점을 적어서 제출

#TOP - 위로이동

4주차 강의(3월 26일, 28일)

  • 배열과 구조체를 이용한 다항식의 표현
  • 행렬의 배열 표현
    • 행렬의 전치행열 만들기

강의자료(good programmer)

Lab #3-4(matrix1.c) 행렬전치

#include <stdio.h>

#define ROWS 3
#define COLS 3
// 행렬 전치 함수
void matrix_transpose(int A[ROWS][COLS], int B[ROWS][COLS])
{
    for (int r = 0; r<ROWS; r++)
        for (int c = 0; c<COLS; c++)
            B[c][r] = A[r][c];
}
void matrix_print(int A[ROWS][COLS])
{
    printf("====================\n");
    for (int r = 0; r<ROWS; r++) {
        for (int c = 0; c<COLS; c++)
            printf("%d ", A[r][c]);
        printf("\n");
    }
    printf("====================\n");
}

int main(void)
{
    int array1[ROWS][COLS] = { { 2,3,0 },
        { 8,9,1 },
        { 7,0,5 } };
    int array2[ROWS][COLS];
    
    matrix_transpose(array1, array2);
    matrix_print(array1);
    matrix_print(array2);
    return 0;
}

과제 #5

  • 제목 : 3장 연습문제 풀이
  • 제출일 : 4월 2일
    • 연습문제 98-99쪽 풀이
    • 문제와 답을 손으로 적어서 제출하세요
      • 정답과 그 이유를 함께 설명하시오
    • 4, 5, 6, 7, 8, 10번 프로그래밍 문제에 대해서는 소스코드, 수행결과 캡쳐화면을 제출할 것
      • 문제해결시 어려웠던 점과 느낀 점을 적어서 제출

과제 #6 : while, for, break와 continue, 함수, 함수정의와 호출, 함수와 변수의 속성, 구조체등

수강 : 홍길동
수강평 : 0000000 에 대해 알게되었으며, 0000라고 생각합니다.
궁금한점 : 0000000에 관한 부분이 잘 이해가 안됩니다. 0000000는 0000이 아닌가요? “등
형식으로 반드시 자기 이름을 달아주십시오.

5주차 강의(4월 2일, 4일)

강의자료 (4장 스택)

Lab #4-1

  • 정수 배열 스택 프로그램
#include <stdio.h>
#include <stdlib.h>

//스택이 전역 변수로 구현된다. 

#define MAX_STACK_SIZE 100	// 스택의 최대 크기
typedef int element;		// 데이터의 자료형
element  stack[MAX_STACK_SIZE]; // 1차원 배열
int  top = -1;			

// 공백 상태 검출 함수
int is_empty()
{
	return (top == -1);
}
// 포화 상태 검출 함수
int is_full()
{
	return (top == (MAX_STACK_SIZE - 1));
}
// 삽입 함수
void push(element item)
{
	if (is_full()) {
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}
	else stack[++top] = item;
}
// 삭제 함수
element pop()
{
	if (is_empty()) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return stack[top--];
}
// 피크 함수
element peek()
{
	if (is_empty()) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return stack[top];
}

int main(void)
{
	push(1);
	push(2);
	push(3);
	printf("%d\n", pop());
	printf("%d\n", pop());
	printf("%d\n", pop());
	return 0;
}

Lab #4-2

  • 학생의 정보를 스택에 삽입하고 삭제함
    • 구조체를 스택에 삽입하고 삭제하는 기능
#include <stdio.h>
#include <stdlib.h>

#define MAX_STACK_SIZE 100
#define MAX_STRING 100

typedef struct {
    int student_no;
    char name[MAX_STRING];
    char address[MAX_STRING];
} element;
element  stack[MAX_STACK_SIZE];
int  top = -1;

// 공백 상태 검출 함수
int is_empty()
{
    return (top == -1);
}
// 포화 상태 검출 함수
int is_full()
{
    return (top == (MAX_STACK_SIZE - 1));
}
// 삽입 함수
void push(element item)
{
    if (is_full()) {
        fprintf(stderr, "스택 포화 에러\n");
        return;
    }
    else stack[++top] = item;
}
// 삭제 함수
element pop()
{
    if (is_empty()) {
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else return stack[top--];
}
// 피크함수
element peek()
{
    if (is_empty()) {
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else return stack[top];
}

int main(void)
{
    element ie = {     20190001,
        "Hong",
        "Seoul"    };
    element oe;
    
    push(ie);
    oe = pop();
    
    printf("학번: %d\n", oe.student_no);
    printf("이름: %s\n", oe.name);
    printf("주소: %s\n", oe.address);
    return 0;
}

2019 DS ex4.2.png

  • 위의 프로그램을 수정하여 다음과 같이 4명의 학생을 스택에 넣고 한명을 삭제하시오
    • 스택의 모든 내용을 삭제전과 삭제후에 대해서 다음과 같이 출력하시오.
    • 학번, 이름, 학과 정보가 들어가도록 프로그램을 수정하시오

2018 DS ex3.2.png

Lab #4-6 : 스택을 이용한 괄호쌍 검사

  • 스택을 이용하여 괄호의 쌍이 맞는지 검사하는 프로그램
//
#include <stdio.h>
#include <stdlib.h>

#define MAX_STACK_SIZE 100        // 스택 요소 저장을 위한 배열의 크기
typedef int Element;        // 스택 요소의 자료형 정의

Element data[MAX_STACK_SIZE];    // 실제 스택 요소의 배열
int    top;                // 실제 스택의 top

// 오류 상황 처리를 위한 함수. 메시지 출력 후 프로그램 종료.
void error(char str[])
{
    printf("%s\n", str);
    exit(1);
}

// 스택의 주요 연산: 공통
void init_stack() { top = -1; }
int is_empty() { return top == -1; }
int is_full() { return top == MAX_STACK_SIZE - 1; }
int size() { return top + 1; }

void push(Element e)
{
    if (is_full())
        error("스택 포화 에러");
    data[++top] = e;
}
Element pop()
{
    if (is_empty())
        error("스택 공백 에러");
    return data[top--];
}
Element peek()
{
    if (is_empty())
        error("스택 공백 에러");
    return data[top];
}

int check_matching(char expr[])
{
    int i = 0, prev;
    char ch;
    
    init_stack();
    while (expr[i] != '\0') {
        ch = expr[i++];
        if (ch == '[' || ch == '(' || ch == '{')
            push(ch);
        else if (ch == ']' || ch == ')' || ch == '}') {
            if (is_empty())
                return 2;    // 조건 2 위반
            prev = pop();
            if ((ch == ']' && prev != '[')
                || (ch == ')' && prev != '(')
                || (ch == '}' && prev != '{')) {
                return 3;    // 조건 3 위반
            }
        }
    }
    if (is_empty() == 0) return 1;        // 조건 1 위반
    return 0;                // 괄호 정상
}

int main()
{
    char expr[4][80] = { "{A[(i+1)]=0;}", "if((i==0) && (j==0)",
        "A[(i+1])=0;", "A[i] =f)(;" };
    int errCode, i;
    
    for (i = 0; i<4; i++) {
        errCode = check_matching(expr[i]);
        if (errCode == 0)
            printf(" 정상: %s\n", expr[i]);
        else
            printf(" 오류: %s (조건%d 위반)\n", expr[i], errCode);
    }
    
    return 0;
}

2018 DS ex3.3.png

Lab #4-9 : 스택을 이용한 미로 탐색

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_STACK_SIZE 100
#define MAZE_SIZE 6

typedef struct {		// 교체!
	short r;
	short c;
} element;

typedef struct {
	element data[MAX_STACK_SIZE];
	int top;
} StackType;

// 스택 초기화 함수
void init_stack(StackType *s)
{
	s->top = -1;
}

// 공백 상태 검출 함수
int is_empty(StackType *s)
{
	return (s->top == -1);
}
// 포화 상태 검출 함수
int is_full(StackType *s)
{
	return (s->top == (MAX_STACK_SIZE - 1));
}
// 삽입함수
void push(StackType *s, element item)
{
	if (is_full(s)) {
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}
	else s->data[++(s->top)] = item;
}
// 삭제함수
element pop(StackType *s)
{
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return s->data[(s->top)--];
}
// 피크함수
element peek(StackType *s)
{
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return s->data[s->top];
}
// ===== 스택 코드의 끝 ===== 


element here = { 1,0 }, entry = { 1,0 };

char maze[MAZE_SIZE][MAZE_SIZE] = {
	{ '1', '1', '1', '1', '1', '1' },
{ 'e', '0', '1', '0', '0', '1' },
{ '1', '0', '0', '0', '1', '1' },
{ '1', '0', '1', '0', '1', '1' },
{ '1', '0', '1', '0', '0', 'x' },
{ '1', '1', '1', '1', '1', '1' },
};
// 위치를 스택에 삽입
void push_loc(StackType *s, int r, int c)
{
	if (r < 0 || c < 0) return;
	if (maze[r][c] != '1' && maze[r][c] != '.') {
		element tmp;
		tmp.r = r;
		tmp.c = c;
		push(s, tmp);
	}
}
// 미로를 화면에 출력한다. 
void maze_print(char maze[MAZE_SIZE][MAZE_SIZE])
{
	printf("\n");
	for (int r = 0; r < MAZE_SIZE; r++) {
		for (int c = 0; c < MAZE_SIZE; c++) {
			printf("%c", maze[r][c]);
		}
		printf("\n");
	}
}

int main(void)
{
	int r, c;
	StackType s;

	init_stack(&s);
	here = entry;
	while (maze[here.r][here.c] != 'x') {
		r = here.r;
		c = here.c;
		maze[r][c] = '.';
		maze_print(maze);
		push_loc(&s, r - 1, c);
		push_loc(&s, r + 1, c);
		push_loc(&s, r, c - 1);
		push_loc(&s, r, c + 1);
		if (is_empty(&s)) {
			printf("실패\n");
			return -1;
		}
		else
			here = pop(&s);
	}
	printf("성공\n");
	return 0;
}

과제 #7

  • 교재 4장 스택 연습문제 풀이
    • 1 - 9번 문제와 정답 풀이과정을 각자의 방식대로 적으시오
    • 10-13번 문제와 프로그래밍 코드를 작성하여 제출하시오
    • 코드에는 반드시 3줄 이상의 주석문을 넣고 결과도 출력하여 제출하세요
  • 날짜 : 4월 11일까지

6주차 강의(4월 9일, 11일)

    • 큐의 정의와 활용
    • 배열을 이용한 큐
    • 원형큐의 구현
    • 덱이란
    • 큐의 응용
  • 포인터와 연결리스트

강의자료 (5장 큐)

Lab #5-1 선형 큐의 구현

  • 선형큐를 이용한 원소의 삽입과 삭제
#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 5

typedef int element;
typedef struct { 				// 큐 타입
	int  front;
	int rear;
	element  data[MAX_QUEUE_SIZE];
} QueueType;

// 오류 함수
void error(char *message)
{
	fprintf(stderr, "%s\n", message);
	exit(1);
}

void init_queue(QueueType *q)
{
	q->rear = -1;
	q->front = -1;
}
void queue_print(QueueType *q)
{
	for (int i = 0; i<MAX_QUEUE_SIZE; i++) {
		if (i <= q->front || i> q->rear)
			printf("   | ");
		else
			printf("%d | ", q->data[i]);
	}
	printf("\n");
}

int is_full(QueueType *q)
{
	if (q->rear == MAX_QUEUE_SIZE - 1)
		return 1;
	else
		return 0;
}

int is_empty(QueueType *q)
{
	if (q->front == q->rear)
		return 1;
	else
		return 0;
}

void enqueue(QueueType *q, int item)
{
	if (is_full(q)) {
		error("큐가 포화상태입니다.");
		return;
	}
	q->data[++(q->rear)] = item;
}

int dequeue(QueueType *q)
{
	if (is_empty(q)) {
		error("큐가 공백상태입니다.");
		return -1;
	}
	int item = q->data[++(q->front)];
	return item;
}

int main(void)
{
	int item = 0;
	QueueType q;

	init_queue(&q);

	enqueue(&q, 10); queue_print(&q);
	enqueue(&q, 20); queue_print(&q);
	enqueue(&q, 30); queue_print(&q);

	item = dequeue(&q); queue_print(&q);
	item = dequeue(&q); queue_print(&q);
	item = dequeue(&q); queue_print(&q);
	return 0;
}

Lab #5-2 : 원형 큐

#include <stdio.h>
#include <stdlib.h>

// ===== 원형큐 코드 시작 ======
#define MAX_QUEUE_SIZE 5
typedef int element;
typedef struct { // 큐 타입
	element  data[MAX_QUEUE_SIZE];
	int  front, rear;
} QueueType;

// 오류 함수
void error(char *message)
{
	fprintf(stderr, "%s\n", message);
	exit(1);
}

// 공백 상태 검출 함수
void init_queue(QueueType *q)
{
	q->front = q->rear = 0;
}

// 공백 상태 검출 함수
int is_empty(QueueType *q)
{
	return (q->front == q->rear);
}

// 포화 상태 검출 함수
int is_full(QueueType *q)
{
	return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}

// 원형큐 출력 함수
void queue_print(QueueType *q)
{
	printf("QUEUE(front=%d rear=%d) = ", q->front, q->rear);
	if (!is_empty(q)) {
			int i = q->front;
			do {
				i = (i + 1) % (MAX_QUEUE_SIZE);
				printf("%d | ", q->data[i]);
				if (i == q->rear)
					break;
			} while (i != q->front);
		}
	printf("\n");
}

// 삽입 함수
void enqueue(QueueType *q, element item)
{
	if (is_full(q))
		error("큐가 포화상태입니다");
	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
	q->data[q->rear] = item;
}

// 삭제 함수
element dequeue(QueueType *q)
{
	if (is_empty(q))
		error("큐가 공백상태입니다");
	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
	return q->data[q->front];
}

// 삭제 함수
element peek(QueueType *q)
{
	if (is_empty(q))
		error("큐가 공백상태입니다");
	return q->data[(q->front + 1) % MAX_QUEUE_SIZE];
}
// ===== 원형큐 코드 끝 ======

int main(void)
{
	QueueType queue;
	int element;

	init_queue(&queue);
	printf("--데이터 추가 단계--\n");
	while (!is_full(&queue))
	{
		printf("정수를 입력하시오: ");
		scanf("%d", &element);
		enqueue(&queue, element);
		queue_print(&queue);
	}
	printf("큐는 포화상태입니다.\n\n");

	printf("--데이터 삭제 단계--\n");
	while (!is_empty(&queue))
	{
		element = dequeue(&queue);
		printf("꺼내진 정수: %d \n", element);
		queue_print(&queue);
	}
	printf("큐는 공백상태입니다.\n");
	return 0;
}

과제 #8

강의자료 (slideshare 자료)

  • 배울 내용 : 포인터와 동적메모리 할당
    • 포인터 관련 연산자의 활용
    • 포인터를 이용한 연결리스트 프로그래밍

강의자료 (6장 연결리스트1)

  • 포인터와 동적 메모리, 연결리스트 강의자료 slideshare의 내용으로 진행할 예정
  • 강의자료 - 06.연결리스트1.pdf

참고자료(동영상강의)

코드( github.com 자료 )

2018-DS-github-down.png

Lab #6-1 : 배열을 이용하여 구현한 리스트

#include <stdio.h>
#include <stdlib.h>

#define MAX_LIST_SIZE 100 	// 리스트의 최대크기

typedef int element;			// 항목의 정의
typedef struct {
	element array[MAX_LIST_SIZE];	  // 배열 정의
	int size;		  // 현재 리스트에 저장된 항목들의 개수
} ArrayListType;
// 오류 처리 함수
void error(char *message)
{
	fprintf(stderr, "%s\n", message);
	exit(1);
}
// 리스트 초기화 함수
void init(ArrayListType *L)
{
	L->size = 0;
}
// 리스트가 비어 있으면 1을 반환
// 그렇지 않으면 0을 반환
int is_empty(ArrayListType *L)
{
	return L->size == 0;
}
// 리스트가 가득 차 있으면 1을 반환
// 그렇지 많으면 1을 반환
int is_full(ArrayListType *L)
{
	return L->size == MAX_LIST_SIZE;
}
element get_entry(ArrayListType *L, int pos)
{
	if (pos < 0 || pos >= L->size)
		error("위치 오류");
	return L->array[pos];
}
// 리스트 출력
void print_list(ArrayListType *L)
{
	int i;
	for (i = 0; i<L->size; i++)
		printf("%d->", L->array[i]);
	printf("\n");
}
void insert_last(ArrayListType *L, element item)
{
	if( L->size >= MAX_LIST_SIZE ) {
		error("리스트 오버플로우");
	}
	L->array[L->size++] = item;
}
void insert(ArrayListType *L, int pos, element item)
{
	if (!is_full(L) && (pos >= 0) && (pos <= L->size)) {
		for (int i = (L->size - 1); i >= pos; i--)
			L->array[i + 1] = L->array[i];
		L->array[pos] = item;
		L->size++;
	}
}
element delete(ArrayListType *L, int pos)
{
	element item;

	if (pos < 0 || pos >= L->size)
		error("위치 오류");
	item = L->array[pos];
	for (int i = pos; i<(L->size - 1); i++)
		L->array[i] = L->array[i + 1];
	L->size--;
	return item;
}
int main(void)
{
	// ArrayListType를 정적으로 생성하고 ArrayListType를 	
	// 가리키는 포인터를 함수의 매개변수로 전달한다.
	ArrayListType list;

	init(&list);		
	insert(&list, 0, 10);	print_list(&list);	// 0번째 위치에 10 추가
	insert(&list, 0, 20);	print_list(&list);	// 0번째 위치에 20 추가
	insert(&list, 0, 30);	print_list(&list);	// 0번째 위치에 30 추가
	insert_last(&list, 40);	print_list(&list);	// 맨 끝에 40 추가
	delete(&list, 0);		print_list(&list);	// 0번째 항목 삭제
	return 0;
}

Lab #6-2: 연결리스트의 구현

#include <stdio.h>
#include <stdlib.h>

typedef int element;
typedef struct ListNode { 	// 노드 타입
	element data;
	struct ListNode *link;
} ListNode;

// 오류 처리 함수
void error(char *message)
{
	fprintf(stderr, "%s\n", message);
	exit(1);
}
ListNode* insert_first(ListNode *head, int value)
{
	ListNode *p = (ListNode *)malloc(sizeof(ListNode));	//(1)
	p->data = value;					// (2)
	p->link = head;	// 헤드 포인터의 값을 복사	//(3)
	head = p;	// 헤드 포인터 변경		//(4)
	return head;	// 변경된 헤드 포인터 반환
}

// 노드 pre 뒤에 새로운 노드 삽입
ListNode*  insert(ListNode *head, ListNode *pre, element value)
{
	ListNode *p = (ListNode *)malloc(sizeof(ListNode));	//(1)
	p->data = value;		//(2)
	p->link = pre->link;	//(3)	
	pre->link = p;		//(4)	
	return head;		//(5)	
}

ListNode* delete_first(ListNode *head)
{
	ListNode *removed;
	if (head == NULL) return NULL;
	removed = head;	// (1)
	head = removed->link;	// (2)
	free(removed);		// (3)
	return head;		// (4)
}
// pre가 가리키는 노드의 다음 노드를 삭제한다. 
ListNode* delete(ListNode *head, ListNode *pre)
{
	ListNode *removed;
	removed = pre->link;
	pre->link = removed->link;		// (2)
	free(removed);			// (3)
	return head;			// (4)
}

void print_list(ListNode *head)
{
	for (ListNode *p = head; p != NULL; p = p->link)
		printf("%d->", p->data);
	printf("NULL \n");
}

// 테스트 프로그램
int main(void)
{
	ListNode *head = NULL;

	for (int i = 0; i < 5; i++) {
		head = insert_first(head, i);
		print_list(head);
	}
	for (int i = 0; i < 5; i++) {
		head = delete_first(head);
		print_list(head);
	}
	return 0;
}

7주차 강의(4월 16일, 18일)

  • 연결리스트, 재귀함수등
    • 연결리스트를 위한 노드의 정의
    • 동적 자료구조와 동적 객체의 생성
    • 단일 연결리스트, 이중 연결리스트

과제 #9

수강 : 홍길동
수강평 : 0000000 에 대해 알게되었으며, 0000라고 생각합니다.
궁금한점 : 0000000에 관한 부분이 잘 이해가 안됩니다. 0000000는 0000이 아닌가요? “등
형식으로 반드시 자기 이름을 달아주십시오.

#TOP - 위로이동

강의자료 (6장 연결리스트1)

Lab #6-9 : 연결리스트로 구현한 다항식 덧셈 프로그램

#include <stdio.h>
#include <stdlib.h>

typedef struct ListNode { // 노드 타입
	int coef;
	int expon;
	struct ListNode *link;
} ListNode;

// 연결 리스트 헤더
typedef struct ListType { // 리스트 헤더 타입
	int size;
	ListNode *head;
	ListNode *tail;
} ListType;

// 오류 함수
void error(char *message)
{
	fprintf(stderr, "%s\n", message);
	exit(1);
}

//  리스트 헤더 생성 함수
ListType* create()
{
	ListType *plist = (ListType *)malloc(sizeof(ListType));
	plist->size = 0;
	plist->head = plist->tail = NULL;
	return plist;
}

// plist는 연결 리스트의 헤더를 가리키는 포인터, coef는 계수, 
// expon는 지수
void insert_last(ListType* plist, int coef, int expon)
{
	ListNode* temp =
		(ListNode *)malloc(sizeof(ListNode));
	if (temp == NULL) error("메모리 할당 에러");
	temp->coef = coef;
	temp->expon = expon;
	temp->link = NULL;
	if (plist->tail == NULL) {
		plist->head = plist->tail = temp;
	}
	else {
		plist->tail->link = temp;
		plist->tail = temp;
	}
	plist->size++;
}

// list3 = list1 + list2
void poly_add(ListType* plist1, ListType* plist2, ListType* plist3)
{
	ListNode* a = plist1->head;
	ListNode* b = plist2->head;
	int sum;

	while (a && b) {
		if (a->expon == b->expon) {   // a의 차수 > b의 차수
			sum = a->coef + b->coef;
			if (sum != 0) insert_last(plist3, sum, a->expon);
			a = a->link; b = b->link;
		}
		else if (a->expon > b->expon) {  // a의 차수 == b의 차수 
			insert_last(plist3, a->coef, a->expon);
			a = a->link;
		}
		else {					// a의 차수 < b의 차수
			insert_last(plist3, b->coef, b->expon);
			b = b->link;
		}
	}

	// a나 b중의 하나가 먼저 끝나게 되면 남아있는 항들을 모두 
	// 결과 다항식으로 복사
	for (; a != NULL; a = a->link)
		insert_last(plist3, a->coef, a->expon);
	for (; b != NULL; b = b->link)
		insert_last(plist3, b->coef, b->expon);
}

//
//
void poly_print(ListType* plist)
{
	ListNode* p = plist->head;

	printf("polynomial = ");
	for (; p; p = p->link) {
		printf("%d^%d + ", p->coef, p->expon);
	}
	printf("\n");
}

//
int main(void)
{
	ListType *list1, *list2, *list3;

	// 연결 리스트 헤더 생성
	list1 = create();
	list2 = create();
	list3 = create();

	// 다항식 1을 생성 
	insert_last(list1, 3, 12);
	insert_last(list1, 2, 8);
	insert_last(list1, 1, 0);

	// 다항식 2를 생성 
	insert_last(list2, 8, 12);
	insert_last(list2, -3, 10);
	insert_last(list2, 10, 6);

	poly_print(list1);
	poly_print(list2);

	// 다항식 3 = 다항식 1 + 다항식 2
	poly_add(list1, list2, list3);
	poly_print(list3);

	free(list1); free(list2); free(list3);
}

8주차 강의(4월 23일,25일 ) : 중간고사

  • 연결리스트 이중 연결리스트 심화 및 실습

중간고사

  • 알립니다 - 중간고사
    • 날짜  : 2019년 4월 23일 화요일 오후 3시 310강의실
      • 범위 : 교재 7장 연결리스트 2의 학습내용까지
      • 문제유형 : 단답식 주관식문제와 서술식 문제 및 프로그램 코딩 문제
  • 힌트 1 : 교재 Exercise 문제를 많이 풀어보기 바랍니다
  • 힌트 2 : 널널한교수의 고급 C 강좌의 연결리스트 함수편을 자세히 보세요

Lab #6-13

  • 단순 연결리스트의 삽입과 삭제함수등
//
//  main.c
//  LinkedList
//

#include <stdio.h>
#include <stdlib.h>

typedef int Element;
typedef struct LinkedNode {
    Element data;
    struct LinkedNode* link;
} Node;

Node*    head = NULL;  // 초기화
// 초기화 함수
void init_list() { head = NULL; }
// 빈 리스트인지 검사하는 함수
int is_empty() { return head == NULL; }

// pos 번째 리스트 노드를 반환하는 함수
Node* get_entry(int pos)
{
    Node* p = head;
    int i;
    for (i = 0; i<pos; i++, p = p->link)
        if (p == NULL) return NULL;
    return p;
}

// 리스트의 크기를 반환
int size()
{
    Node* p;
    int count = 0;
    for (p = head; p != NULL; p = p->link)
        count++;
    return count;
}

void replace(int pos, Element val)
{
    Node* node = get_entry(pos);
    if (node != NULL)
        node->data = val;
}

Node* find(Element val)
{
    Node* p;
    for (p = head; p != NULL; p = p->link)
        if (p->data == val) return p;
    return NULL;
}

void insert_next(Node *before, Node *node)
{
    if (node != NULL) {
        node->link = before->link;
        before->link = node;
    }
}

void insert(int pos, Element val)
{
    Node *new_node, *prev;
    
    new_node = (Node*)malloc(sizeof(Node));
    new_node->data = val;
    new_node->link = NULL;
    
    if (pos == 0) {
        new_node->link = head;
        head = new_node;
    }
    else {
        prev = get_entry(pos - 1);
        if (prev != NULL)
            insert_next(prev, new_node);
        else free(new_node);
    }
}

Node* remove_next(Node *prev)
{
    Node* removed = prev->link;
    if (removed != NULL)
        prev->link = removed->link;
    return removed;
}

void delete(int pos)
{
    Node* prev, *removed;
    
    if (pos == 0 && is_empty() == 0) {
        removed = head;
        head = head->link;
        free(removed);
    }
    else {
        prev = get_entry(pos - 1);
        if (prev != NULL) {
            removed = remove_next(prev);
            free(removed);
        }
    }
}

void clear_list()
{
    while (is_empty() == 0)
        delete(0);
}

void print_list(char* msg)
{
    Node* p;
    printf("%s[%2d]: ", msg, size());
    for (p = head; p != NULL; p = p->link)
        printf("%2d ", p->data);
    printf("\n");
}

int main()
{
    init_list();
    insert(0, 10);
    insert(0, 20);
    insert(1, 30);
    insert(size(), 40);
    insert(2, 50);
    print_list("단순연결리스트로 구현한 List(삽입x5)");
    
    replace(2, 90);
    print_list("단순연결리스트로 구현한 List(교체x1)");
    
    delete(2);
    delete(size() - 1);
    delete(0);
    print_list("단순연결리스트로 구현한 List(삽입x3)");
    
    clear_list();
    print_list("단순연결리스트로 구현한 List(정리후)");
    
    return 0;
}
  • 수행결과

2018 DS linkedlist-result.png

Lab #6-16

  • 이중 연결리스트의 삽입과 삭제함수등
//
//  main.c
//  DbLinkedList
//

#include <stdio.h>
#include <stdlib.h>

typedef int Element;
typedef struct DLinkedNode {
    Element data;
    struct DLinkedNode* prev;
    struct DLinkedNode* next;
} Node;

Node org;    // 헤드 노드 (헤드 포인터가 아님)

void init_list() { org.next = NULL; }
Node* get_head() { return org.next; }
int is_empty() { return get_head() == NULL; }

Node* get_entry(int pos)
{
    Node* n = &org;
    int i = -1;
    for (i = -1; i<pos; i++, n = n->next)
        if (n == NULL) break;
    return n;
}

void replace(int pos, Element val)
{
    Node* node = get_entry(pos);
    if (node != NULL)
        node->data = val;
}

// 다음 세 함수는 for문에서 head 대신 get_head()를 사용하도록 수정해야 함.
// 나머지 코드는 이전 코드와 동일함
int size()
{
    Node* p;
    int count = 0;
    for (p = get_head(); p != NULL; p = p->next)
        count++;
    return count;
}

Node* find(Element val)
{
    Node* p;
    for (p = get_head(); p != NULL; p = p->next)
        if (p->data == val) return p;
    return NULL;
}

void print_list(char* msg)
{
    Node* p;
    printf("%s[%2d]: ", msg, size());
    for (p = get_head(); p != NULL; p = p->next)
        printf("%2d ", p->data);
    printf("\n");
}

void insert_next(Node *before, Node *n)
{
    n->prev = before;
    n->next = before->next;
    if (before->next != NULL) before->next->prev = n;
    before->next = n;
}

void insert(int pos, Element val)
{
    Node *new_node, *prev;
    
    prev = get_entry(pos - 1);
    if (prev != NULL) {
        new_node = (Node*)malloc(sizeof(Node));
        new_node->data = val;
        new_node->prev = NULL;
        new_node->next = NULL;
        
        insert_next(prev, new_node);
    }
}

void remove_curr(Node *n)
{
    if (n->prev != NULL) n->prev->next = n->next;
    if (n->next != NULL) n->next->prev = n->prev;
}

void delete(int pos)
{
    Node* n = get_entry(pos);
    if (n != NULL)
        remove_curr(n);
}

void clear_list()
{
    while (is_empty() == 0)
        delete(0);
}

int main()
{
    init_list();
    insert(0, 10);
    insert(0, 20);
    insert(1, 30);
    insert(size(), 40);
    insert(2, 50);
    print_list("이중연결리스트로 구현한 List(삽입x5)");
    
    replace(2, 90);
    print_list("이중연결리스트로 구현한 List(교체x1)");
    
    delete(2);
    delete(size() - 1);
    delete(0);
    print_list("이중연결리스트로 구현한 List(삽입x3)");
    
    clear_list();
    print_list("이중연결리스트로 구현한 List(정리후)");
    
    return 0;
}
  • 수행결과

2018 DS Dlist-result.png

#TOP - 위로이동

9주차 강의(4월 30일, 5월 2일)

  • 연결리스트 2
    • 순환 연결리스트와 이중 연결 리스트
    • 연결리스트를 이용한 스택과 큐의 구현
    • 이중 연결 리스트

강의자료 : 7장 연결리스트2

특강 안내 : 5월 2일

  • 특강제목 : " 창원에서 후쿠오카로 : 좌충우돌 해외취업 뚫기"
    • 부재 : 일본 FFG 금융그룹의 해외취업기
    • 강사 : 김덕구(창원대학교 정보통신공학과 졸업생)
    • 시간 : 오후 1: 30
    • 장소 : 328 강의실
    • 경품으로 상품, 도서 상품권, 기념품을 드립니다.

과제 #10 : 6장 연습문제

  • 교재 6장 연결리스트 연습문제 풀이
    • 1-8번 문제와 정답 풀이과정을 각자의 방식대로 적으시오
    • 9-14번 문제와 프로그래밍 코드를 작성하여 제출하시오
    • 20번 다항식을 연결리스트로 표현하고 합을 구하시오.
    • 코드에는 반드시 3줄 이상의 주석문을 넣고 결과도 출력하여 제출하세요
  • 날짜 : 5월 7일까지

Lab #7-7 : 이중 연결 리스트 ( 과제 # 11 )

#include <stdio.h>
#include <stdlib.h>

typedef int element;
typedef struct DListNode {    // 이중연결 노드 타입
    element data;
    struct DListNode* llink;
    struct DListNode* rlink;
} DListNode;

// 이중 연결 리스트를 초기화
void init(DListNode* phead)
{
    phead->llink = phead;
    phead->rlink = phead;
}

// 이중 연결 리스트의 노드를 출력
void print_dlist(DListNode* phead)
{
    DListNode* p;
    for (p = phead->rlink; p != phead; p = p->rlink) {
        printf("<-| |%d| |-> ", p->data);
    }
    printf("\n");
}
// 새로운 데이터를 노드 before의 오른쪽에 삽입한다.
void dinsert(DListNode *before, element data)
{
    DListNode *newnode = (DListNode *)malloc(sizeof(DListNode));
    newnode->data = data;
    newnode->llink = before;
    newnode->rlink = before->rlink;
    before->rlink->llink = newnode;
    before->rlink = newnode;
}
// 노드 removed를 삭제한다.
void ddelete(DListNode* head, DListNode* removed)
{
    if (removed == head) return;
    removed->llink->rlink = removed->rlink;
    removed->rlink->llink = removed->llink;
    free(removed);
}

// 이중 연결 리스트 테스트 프로그램
int main(void)
{
    DListNode* head = (DListNode *)malloc(sizeof(DListNode));
    init(head);
    printf("추가 단계\n");
    for (int i = 0; i < 5; i++) {
        // 헤드 노드의 오른쪽에 삽입
        dinsert(head, i);
        print_dlist(head);
    }
    printf("\n삭제 단계\n");
/*    for (int i = 0; i < 5; i++) {
        print_dlist(head);
        ddelete(head, head->rlink);
    }
    free(head);   */
    return 0;
}
  • Lab 1 : 이 연결리스트의 노드를 역으로 출력하는 rev_print_dlist() 함수를 구현하여

0 1 2 3 4 순으로 출력되도록 하시오

  • Lab 2 : 이 연결리스트의 모든 노드의 합과 평균을 구하는 sum(), avg(), len() 함수를 만들고 다음과 같이 출력하시오.
노드의 합 : 10, 평균 : 2, 노드의 갯수 : 5개
  • Lab 3 : 이중 연결 리스트에 다음과 같은 순서로 10개의 원소를 넣는다. 이 원소를 출력하라.
20 40 50 60 70 90 120 30 10 110
  • Lab 4 : Lab 3의 이중 연결리스트 노드 중 가장 큰 값, 작은 값을 구하는 함수 max(), min()를 만들고 다옴과 같이 출력하라.
가장 큰 값 : 120
가장 작은 값 : 10
  • 소스코드, 코드에 대한 설명, 주석문까지 추가해서 결과를 캡쳐하여 제출합니다.
  • 제출일 : 5월 9일 강의시간까지

10주차 강의(5월 7일, 9일)

  • 트리
    • 트리의 개념
    • 트리의 순회 알고리즘
    • 이진 트리의 탐색화 효율성

과제 #12 : 8장 연습문제

  • 교재 8장 트리 연습문제 풀이
    • 1 - 11번 문제와 정답 풀이과정을 각자의 방식대로 적으시오
    • 12 - 17번 문제와 프로그래밍 코드를 작성하여 제출하시오
    • 코드에는 반드시 3줄 이상의 주석문을 넣고 결과도 출력하여 제출하세요
  • 날짜 : 5월 14일까지

강의자료 : 8장 트리

Lab #8-3 : Tree 순회

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

typedef struct TreeNode {
    int data;
    struct TreeNode *left, *right;
} TreeNode;
//          15
//       4         20
//    1          16  25
TreeNode n1 = { 1,  NULL, NULL };
TreeNode n2 = { 4,  &n1,  NULL };
TreeNode n3 = { 16, NULL, NULL };
TreeNode n4 = { 25, NULL, NULL };
TreeNode n5 = { 20, &n3,  &n4 };
TreeNode n6 = { 15, &n2,  &n5 };
TreeNode *root = &n6;

void in_order(TreeNode *root);
void pre_order(TreeNode *root) ;
void post_order(TreeNode *root) ;

// 중위 순회
void in_order(TreeNode *root) {
    if (root != NULL) {
        in_order(root->left);// 왼쪽서브트리 순회
        printf("[%d] ", root->data);  // 노드 방문
        in_order(root->right);// 오른쪽서브트리 순회
    }
}

// 전위 순회
void pre_order(TreeNode *root) {
    if (root != NULL) {
        printf("[%d] ", root->data);  // 노드 방문
        pre_order(root->left);// 왼쪽서브트리 순회
        pre_order(root->right);// 오른쪽서브트리 순회
    }
}

// 후위 순회
void post_order(TreeNode *root) {
    if (root != NULL) {
        post_order(root->left);// 왼쪽서브트리 순회
        post_order(root->right);// 오른쪽서브트리순회
        printf("[%d] ", root->data);  // 노드 방문
    }
}
int main(void)
{
    printf("중위 순회=");
    in_order(root);
    printf("\n");
    
    printf("전위 순회=");
    pre_order(root);
    printf("\n");
    
    printf("후위 순회=");
    post_order(root);
    printf("\n");
    return 0;
}

Lab #8-4 : 레벨 순회

  • 스택을 이용한 레벨 순회프로그램
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

typedef struct TreeNode {
    int data;
    struct TreeNode *left, *right;
} TreeNode;

#define SIZE 100
int top = -1;
TreeNode *stack[SIZE];

void push(TreeNode *p)
{
    if (top < SIZE - 1)
        stack[++top] = p;
}

TreeNode *pop()
{
    TreeNode *p = NULL;
    if (top >= 0)
        p = stack[top--];
    return p;
}

void inorder_iter(TreeNode *root)
{
    while (1) {
        for (; root; root = root->left)
            push(root);
        root = pop();
        if (!root) break;
        printf("[%d] ", root->data);
        root = root->right;
    }
}
//          15
//       4         20
//    1          16  25
TreeNode n1 = { 1,  NULL, NULL };
TreeNode n2 = { 4,  &n1,  NULL };
TreeNode n3 = { 16, NULL, NULL };
TreeNode n4 = { 25, NULL, NULL };
TreeNode n5 = { 20, &n3,  &n4 };
TreeNode n6 = { 15, &n2,  &n5 };
TreeNode *root = &n6;

int main(void)
{
    printf("중위 순회 = ");
    inorder_iter(root);
    printf("\n");
    return 0;
}

Lab #8-6 : 수식트리 계산 프로그램

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int data;
    struct TreeNode *left, *right;
} TreeNode;
//             +
//         *         +
//    1       4   16  25
TreeNode n1 = { 1,  NULL, NULL };
TreeNode n2 = { 4,  NULL,  NULL };
TreeNode n3 = { '*',  &n1,  &n2 };
TreeNode n4 = { 16, NULL, NULL };
TreeNode n5 = { 25, NULL, NULL };
TreeNode n6 = { '+', &n4,  &n5 };
TreeNode n7 = { '+', &n3,  &n6 };
TreeNode *ex = &n7;

// 수식 계산 함수
int evaluate(TreeNode *root)
{
    if (root == NULL)
        return 0;
    if (root->left == NULL && root->right == NULL)
        return root->data;
    else {
        int op1 = evaluate(root->left);
        int op2 = evaluate(root->right);
        printf("%d %c %d을 계산합니다.\n", op1, root->data, op2);
        switch (root->data) {
            case '+':
                return op1 + op2;
            case '-':
                return op1 - op2;
            case '*':
                return op1 * op2;
            case '/':
                return op1 / op2;
        }
    }
    return 0;
}
//
int main(void)
{
    printf("수식의 값은 %d입니다. \n", evaluate(ex));
    return 0;
}

아이디 만들기와 이메일 보내기

11주차 강의(5월 14일, 16일 )

  • 우선순위 큐
    • 완전 이진 트리
    • upheap(), downheap() 의 구성

과제 #13

  • 제목 : 9장 우선순위 큐 연습문제 풀이
    • 연습문제  : 1번-10번까지 풀이하기
    • 프로그램 풀이 : 11번,16번,17번
    • 제출일 : 5월 23일 목요일까지입니다.

강의자료 : 9장 우선순위큐

Lab : 힙 트리 테스트

//
//  main.c
//  MaxHeap
//
//  Created by mac on 2018. 3. 16..

#include <stdio.h>
#include <stdlib.h>
#define MAX_HEAP_NODE    200

void error(char str[])
{
    printf("%s\n", str);
    exit(1);
}

typedef int HNode;
#define Key(n)   (n)

HNode heap[MAX_HEAP_NODE];
int heap_size;

#define Parent(i) (heap[i/2])        // i의 부모 노드
#define Left(i) (heap[i*2])        // i의 왼쪽 자식 노드
#define Right(i) (heap[i*2+1])    // i의 오른쪽 자식 노드

void init_heap() { heap_size = 0; }
int is_empty_heap() { return heap_size == 0; }
int is_full_heap() { return (heap_size == MAX_HEAP_NODE - 1); }
HNode find_heap() { return heap[1]; }

void insert_heap(HNode n)
{
    int i;
    if (is_full_heap()) return;
    i = ++(heap_size);
    while (i != 1 && Key(n) > Key(Parent(i))) {
        heap[i] = Parent(i);
        i /= 2;
    }
    heap[i] = n;
}

HNode delete_heap()
{
    HNode hroot, last;
    int parent = 1, child = 2;
    
    if (is_empty_heap() != 0)
        error("힙 트리 공백 에러");
    
    hroot = heap[1];
    last = heap[heap_size--];
    while (child <= heap_size) {
        if (child<heap_size && Key(Left(parent))<Key(Right(parent)))
            child++;
        if (Key(last) >= Key(heap[child]))
            break;
        heap[parent] = heap[child];
        parent = child;
        child *= 2;
    }
    heap[parent] = last;
    return hroot;
}

void print_heap()
{
    int i, level;
    for (i = 1, level = 1; i <= heap_size; i++) {
        if (i == level) {
            printf("\n");
            level *= 2;
        }
        printf("%2d ", Key(heap[i]));
    }
    printf("\n-----------");
}

int main()
{
    init_heap();
    insert_heap(2);        insert_heap(5);
    insert_heap(4);        insert_heap(8);
    insert_heap(9);        insert_heap(3);
    insert_heap(7);        insert_heap(3);
    print_heap();
    
    delete_heap();    print_heap();
    delete_heap();    print_heap();
    printf("\n");
    
    return 0;
}

12주차 강의( 5월 21일, 23일 )

  • 그래프의 정의
    • 그래프의 역사
    • 그래프의 종류와 용어
    • 인접 행렬을 이용한 그래프의 표현
    • 인접 리스트를 이용한 그래프의 표현
  • 가중치 그래프

강의자료 : 10장 그래프1

Lab( AdjMatrix.c )

  • 인접배열을 이용한 그래프 표현
#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 50
typedef struct GraphType {
    int n;    // 정점의 개수
    int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;

// 그래프 초기화
void init(GraphType* g)
{
    int r, c;
    g->n = 0;
    for (r = 0; r<MAX_VERTICES; r++)
        for (c = 0; c<MAX_VERTICES; c++)
            g->adj_mat[r][c] = 0;
}
// 정점 삽입 연산
void insert_vertex(GraphType* g, int v)
{
    if (((g->n) + 1) > MAX_VERTICES) {
        fprintf(stderr, "그래프: 정점의 개수 초과");
        return;
    }
    g->n++;
}
// 간선 삽입 연산
void insert_edge(GraphType* g, int start, int end)
{
    if (start >= g->n || end >= g->n) {
        fprintf(stderr, "그래프: 정점 번호 오류");
        return;
    }
    g->adj_mat[start][end] = 1;
    g->adj_mat[end][start] = 1;
}
// 인접 행렬 출력 함수
void print_adj_mat(GraphType* g)
{
    for (int i = 0; i < g->n; i++) {
        for (int j = 0; j < g->n; j++) {
            printf("%2d ", g->adj_mat[i][j]);
        }
        printf("\n");
    }
}

void main()
{
    GraphType *g;
    g = (GraphType *)malloc(sizeof(GraphType));
    init(g);
    for(int i=0;i<4;i++)
        insert_vertex(g, i);

    insert_edge(g, 0, 1);
    insert_edge(g, 0, 2);
    insert_edge(g, 0, 3);
    insert_edge(g, 1, 2);
    insert_edge(g, 2, 3);
    print_adj_mat(g);
    
    free(g);
}

Lab( AdjList.c )

  • 인접 리스트를 이용한 그래프 표현
#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 50
typedef struct GraphNode
{
    int vertex;
    struct GraphNode* link;
} GraphNode;

typedef struct GraphType {
    int n;    // 정점의 개수
    GraphNode* adj_list[MAX_VERTICES];
} GraphType;

// 그래프 초기화
void init(GraphType* g)
{
    int v;
    g->n = 0;
    for (v = 0; v<MAX_VERTICES; v++)
        g->adj_list[v] = NULL;
}

// 정점 삽입 연산
void insert_vertex(GraphType* g, int v)
{
    if (((g->n) + 1) > MAX_VERTICES) {
        fprintf(stderr, "그래프: 정점의 개수 초과");
        return;
    }
    g->n++;
}

// 간선 삽입 연산, v를 u의 인접 리스트에 삽입한다.
void insert_edge(GraphType* g, int u, int v)
{
    GraphNode* node;
    if (u >= g->n || v >= g->n) {
        fprintf(stderr, "그래프: 정점 번호 오류");
        return;
    }
    node = (GraphNode*)malloc(sizeof(GraphNode));
    node->vertex = v;
    node->link = g->adj_list[u];
    g->adj_list[u] = node;
}

void print_adj_list(GraphType* g)
{
    for (int i = 0; i<g->n; i++) {
        GraphNode* p = g->adj_list[i];
        printf("정점 %d의 인접 리스트 ", i);
        while (p!=NULL) {
            printf("-> %d ", p->vertex);
            p = p->link;
        }
        printf("\n");
    }
}

int main()
{
    GraphType *g;
    g = (GraphType *)malloc(sizeof(GraphType));
    init(g);
    for(int i=0;i<4;i++)
          insert_vertex(g, i);

    insert_edge(g, 0, 1);
    insert_edge(g, 1, 0);
    insert_edge(g, 0, 2);
    insert_edge(g, 2, 0);
    insert_edge(g, 0, 3);
    insert_edge(g, 3, 0);
    insert_edge(g, 1, 2);
    insert_edge(g, 2, 1);
    insert_edge(g, 2, 3);
    insert_edge(g, 3, 2);
    print_adj_list(g);
    free(g);
    return 0;
}

Lab( graph.txt 파일 )

  • 아래와 같은 내용을 가지는 텍스트 파일을 만들어 놓고 이 파일을 읽어서 깊이우선, 너비우선 탐색이 가능함
8
A   0 1 1 0 0 0 0 0
B   1 0 0 1 0 0 0 0
C   1 0 0 1 1 0 0 0
D   0 1 1 0 0 1 0 0
E   0 0 1 0 0 0 1 1
F   0 0 0 1 0 0 0 0
G   0 0 0 0 1 0 0 1
H   0 0 0 0 1 0 1 0

Lab( DFS.c )

//
//  main.c
//  DFS
//
//  Created by mac on 2019. 3. 16..
//  Copyright © 2019년 MobileX. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>
#define MAX_VTXS    256

void error(char str[])            // 오류 메시지 출력후 종료 함수: 공통
{
    printf("%s\n", str);
    exit(1);
}

typedef char VtxData;            // 그래프 정점에 저장할 데이터의 자료형
int adj[MAX_VTXS][MAX_VTXS];    // 인접 행렬
int vsize;                    // 전체 정점의 개수
VtxData vdata[MAX_VTXS];        // 정점에 저장할 데이터 배열

int is_empty_graph() { return (vsize == 0); }
int is_full_graph() { return (vsize >= MAX_VTXS); }
void init_graph()
{
    int i, j;
    vsize = 0;
    for (i = 0; i<MAX_VTXS; i++)
        for (j = 0; j<MAX_VTXS; j++)
            adj[i][j] = 0;
}
void insert_vertex(VtxData name)
{
    if (is_full_graph())
        error("Error: 그래프 정점의 개수 초과\n");
    else
        vdata[vsize++] = name;
}
void insert_edge(int u, int v, int val)
{
    adj[u][v] = val;
}
void insert_edge2(int u, int v, int val)
{
    adj[u][v] = adj[v][u] = val;
}

//---------------------------------------------------------------------------

void print_graph(char* msg)
{
    int i, j;
    printf("%s", msg);
    printf("%d\n", vsize);
    for (i = 0; i<vsize; i++) {
        printf("%c  ", vdata[i]);
        for (j = 0; j<vsize; j++)
            printf(" %3d", adj[i][j]);
        printf("\n");
    }
}
void load_graph(char *filename)
{
    int i, j, val, n;
    char    str[80];
    FILE *fp = fopen(filename, "r");
    if (fp != NULL) {
        init_graph();
        fscanf(fp, "%d", &n);
        for (i = 0; i<n; i++) {
            fscanf(fp, "%s", str);
            insert_vertex(str[0]);
            for (j = 0; j<n; j++) {
                fscanf(fp, "%d", &val);
                if (val != 0)
                    insert_edge(i, j, val);
            }
        }
        fclose(fp);
    }
}
int    visited[MAX_VTXS];
void reset_visited()
{
    int i;
    for (i = 0; i<vsize; i++)
        visited[i] = 0;
}
void DFS(int v)
{
    int w;
    visited[v] = 1;
    printf("%c ", vdata[v]);
    for (w = 0; w<vsize; w++)
        if (adj[v][w] != 0 && visited[w] == 0)
            DFS(w);
}
int main()
{
    load_graph("graph.txt"); // console에서 텍스트 파일내용이 보이지 않으면, 파일명 앞에 파일경로 추가
    reset_visited();
    printf("DFS ==> ");
    DFS(0);
    printf("\n");
    
    return 0;
}

2018 DS DFS.png

LAB : BFS(너비 우선 탐색)

  • 인접 배열을 이용한 계산(2차원 배열)
#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define MAX_QUEUE_SIZE 10

typedef int element;
typedef struct { // 큐 타입
	element  queue[MAX_QUEUE_SIZE];
	int  front, rear;
} QueueType;

// 오류 함수
void error(char *message)
{
	fprintf(stderr, "%s\n", message);
	exit(1);
}

// 공백 상태 검출 함수
void queue_init(QueueType *q)
{
	q->front = q->rear = 0;
}

// 공백 상태 검출 함수
int is_empty(QueueType *q)
{
	return (q->front == q->rear);
}

// 포화 상태 검출 함수
int is_full(QueueType *q)
{
	return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}

// 삽입 함수
void enqueue(QueueType *q, element item)
{
	if (is_full(q))
		error("큐가 포화상태입니다");
	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
	q->queue[q->rear] = item;
}

// 삭제 함수
element dequeue(QueueType *q)
{
	if (is_empty(q))
		error("큐가 공백상태입니다");
	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
	return q->queue[q->front];
}


#define MAX_VERTICES 50
typedef struct GraphType {
	int n;	// 정점의 개수
	int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;
int visited[MAX_VERTICES];

// 그래프 초기화 
void graph_init(GraphType* g)
{
	int r, c;
	g->n = 0;
	for (r = 0; r<MAX_VERTICES; r++)
		for (c = 0; c<MAX_VERTICES; c++)
			g->adj_mat[r][c] = 0;
}
// 정점 삽입 연산
void insert_vertex(GraphType* g, int v)
{
	if (((g->n) + 1) > MAX_VERTICES) {
		fprintf(stderr, "그래프: 정점의 개수 초과");
		return;
	}
	g->n++;
}
// 간선 삽입 연산
void insert_edge(GraphType* g, int start, int end)
{
	if (start >= g->n || end >= g->n) {
		fprintf(stderr, "그래프: 정점 번호 오류");
		return;
	}
	g->adj_mat[start][end] = 1;
	g->adj_mat[end][start] = 1;
}
void bfs_mat(GraphType* g, int v)
{
	int w;
	QueueType q;

	queue_init(&q);     // 큐 초기화 
	visited[v] = TRUE;          // 정점 v 방문 표시 
	printf("%d  방문 -> ", v);
	enqueue(&q, v);			// 시작 정점을 큐에 저장 
	while (!is_empty(&q)) {
		v = dequeue(&q);		// 큐에 정점 추출 
		for (w = 0; w<g->n; w++)	// 인접 정점 탐색 
			if (g->adj_mat[v][w] && !visited[w]) {
				visited[w] = TRUE;    // 방문 표시
				printf("%d 방문 -> ", w);
				enqueue(&q, w); 	// 방문한 정점을 큐에 저장
			}
	}
}

int main(void)
{
	GraphType *g;
	g = (GraphType *)malloc(sizeof(GraphType));
	graph_init(g);
	for (int i = 0; i<6; i++)
		insert_vertex(g, i);
	insert_edge(g, 0, 2);
	insert_edge(g, 2, 1);
	insert_edge(g, 2, 3);
	insert_edge(g, 0, 4);
	insert_edge(g, 4, 5);
	insert_edge(g, 1, 5);

	printf("너비 우선 탐색\n");
	bfs_mat(g, 0);
	printf("\n");

	free(g);
	return 0;
}

LAB : BFS(너비 우선 탐색)

  • 인접 리스트를 이용한 방법
void bfs_list(GraphType* g, int v)
{
	GraphNode* w;
	QueueType q;

	init(&q);    				// 큐 초기 화 
	visited[v] = TRUE;      // 정점 v 방문 표시 
	printf("%d 방문 -> ", v);
	enqueue(&q, v);			// 시작정점을 큐에 저장 
	while (!is_empty(&q)) {
		v = dequeue(&q);		// 큐에 저장된 정점 선택 
		for (w = g->adj_list[v]; w; w = w->link) //인접 정점 탐색
			if (!visited[w->vertex]) {	// 미방문 정점 탐색 
				visited[w->vertex] = TRUE;   // 방문 표시
				printf("%d 방문 -> ", w->vextex);
				enqueue(&q, w->vertex);	//정점을 큐에 삽입
			}
	}
}

과제 #14

  • 제목 : 교재 10장 연습문제 풀이
    • 제출일 : 5월 30일 목요일
    • 교재 10장 연습문제 1번 - 11번
    • 프로그래밍 문제 : 문제 12번 파일로 부터 그래프를 읽어서 13, 14번 문제 풀이하여 코드와 결과를 제출할 것

13주차 강의(5월 28일, 30일 )

  • 그래프와 정렬
  • 정렬
    • 정렬이란
    • 선택정렬, 삽입정렬, 버블정렬, 함수 푸인터를 사용한 정렬, 쉘정렬, 병합 정렬, 퀵정렬, 힙 정렬

과제 #15

  • 제목 : 교재 11장 연습문제 풀이
    • 제출일 : 6월 4일 화요일(학과 사무실 우편함에 제출하세요)
    • 교재 11장 연습문제 1번 - 5번

LAB : 최소 신장 트리 - Kruskal 알고리즘

#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0

#define MAX_VERTICES 100
#define INF 1000

int parent[MAX_VERTICES];		// 부모 노드
							// 초기화
void set_init(int n)
{
	for (int i = 0; i<n; i++) 
		parent[i] = -1;
}
// curr가 속하는 집합을 반환한다.
int set_find(int curr)
{
	if (parent[curr] == -1)
		return curr; 			// 루트 
	while (parent[curr] != -1) curr = parent[curr];
	return curr;
}

// 두개의 원소가 속한 집합을 합친다.
void set_union(int a, int b)
{
	int root1 = set_find(a);	// 노드 a의 루트를 찾는다. 
	int root2 = set_find(b);	// 노드 b의 루트를 찾는다. 
	if (root1 != root2) 	// 합한다. 
		parent[root1] = root2;
}

struct Edge {			// 간선을 나타내는 구조체
	int start, end, weight;
};

typedef struct GraphType {
	int n;	// 간선의 개수
	struct Edge edges[2 * MAX_VERTICES];
} GraphType;

// 그래프 초기화 
void graph_init(GraphType* g)
{
	g->n = 0;
	for (int i = 0; i < 2 * MAX_VERTICES; i++) {
		g->edges[i].start = 0;
		g->edges[i].end = 0;
		g->edges[i].weight = INF;
	}
}
// 간선 삽입 연산
void insert_edge(GraphType* g, int start, int end, int w)
{
	g->edges[g->n].start = start;
	g->edges[g->n].end = end;
	g->edges[g->n].weight = w;
	g->n++;
}
// qsort()에 사용되는 함수
int compare(const void* a, const void* b)
{
	struct Edge* x = (struct Edge*)a;
	struct Edge* y = (struct Edge*)b;
	return (x->weight - y->weight);
}

// kruskal의 최소 비용 신장 트리 프로그램
void kruskal(GraphType *g)
{
	int edge_accepted = 0;	// 현재까지 선택된 간선의 수	
	int uset, vset;			// 정점 u와 정점 v의 집합 번호
	struct Edge e;

	set_init(g->n);				// 집합 초기화
	qsort(g->edges, g->n, sizeof(struct Edge), compare);

	printf("크루스칼 최소 신장 트리 알고리즘 \n");
	int i = 0;
	while (edge_accepted < (g->n - 1))	// 간선의 수 < (n-1)
	{
		e = g->edges[i];
		uset = set_find(e.start);		// 정점 u의 집합 번호 
		vset = set_find(e.end);		// 정점 v의 집합 번호
		if (uset != vset) {			// 서로 속한 집합이 다르면
			printf("간선 (%d,%d) %d 선택\n", e.start, e.end, e.weight);
			edge_accepted++;
			set_union(uset, vset);	// 두개의 집합을 합친다.
		}
		i++;
	}
}

int main(void)
{
	GraphType *g;
	g = (GraphType *)malloc(sizeof(GraphType));
	graph_init(g);

	insert_edge(g, 0, 1, 29);
	insert_edge(g, 1, 2, 16);
	insert_edge(g, 2, 3, 12);
	insert_edge(g, 3, 4, 22);
	insert_edge(g, 4, 5, 27);
	insert_edge(g, 5, 0, 10);
	insert_edge(g, 6, 1, 15);
	insert_edge(g, 6, 3, 18);
	insert_edge(g, 6, 4, 25);

	kruskal(g);
	free(g);
	return 0;
}

강의자료 : 11장 그래프

강의자료 : 12장 정렬

14주차 강의(6월 4일, 6일 )

  • 정렬의 기능과 예제
    • 실습을 통해 정렬에 대해 살펴봅니다

과제 #16

  • 제목 : C언어 정렬 강의 수강평 남기기
    • 제출일 : 6월 11일(학과 사무실 우편함에 제출할 것)
  • 아래에 있는 널널한 교수의 고급 C언어 정렬 강의 동영상 수강할 것(널널한 박교수의 고급 C강의 23-30 까지)
  • 화면 skip하지말고 끝까지 정독해 주세요
  • https://www.youtube.com/watch?v=yV1gplHtXiM&list=PL2P1Vm9k53HMteZqIByxvSzH1MDXwvQBO
    • 수강 후 youtube 동영상에 수강평을 남기고 동영상에 대한 수강평을 캡쳐하여 1페이지에 모아서 제출할 것
    • 수강평에는
수강 : 홍길동
수강평 : 0000000 에 대해 알게되었으며, 0000라고 생각합니다.
궁금한점 : 0000000에 관한 부분이 잘 이해가 안됩니다. 0000000는 0000이 아닌가요? “등
형식으로 반드시 자기 이름을 달아주십시오.

과제 #17

  • 제목 : 교재 12장 연습문제 풀이
    • 1번부터 14번까지
    • 프로그램 문제 : 13, 14번 문제 코딩하기

15주차 강의(6월 11일, 13일 )

  • 보충강의주

강의자료 : 왜 자료구조를 배우나

16주차 기말시험안내(6월 18일)

  • 기말시험주
    • 학기말 시험 : 6월 18일 화요일 15:00 예정
    • 중간시험과 비슷한 형식의 문제로 출제
    • 시험 범위 : 교재 6장 연결리스트부터 12장까지
      • 주관식 문제 및 일부 객관식 문제
      • 의사코딩 작성하기등의 문제
      • 교재의 연습문제를 많이 풀어보시기 바랍니다.

15학번 김동욱 조교님의 코딩 교육

  • 장소 : 310강의실
  • 시간 : 매주 목요일 2학년 자료구조론 수업 이후
  • 학습 시간 : 30분 내외
  • 학습내용
    • 5/9(목)
      • 단순 연결리스트 다양한 함수들(삭제, 삽입 등)
#include <stdio.h>
#include <stdlib.h>
#define MAX_ELEMENT 200

typedef struct{
    int key;
}element;

typedef struct{
    element heap[MAX_ELEMENT];
    int heap_size;
}HeapType;

HeapType* create()
{
    return (HeapType*)malloc(sizeof(HeapType));
}

void init(HeapType* h)
{
    h->heap_size = 0;
}

void insert_max_heap(HeapType* h, element item)
{
    int i;
    i = ++(h->heap_size);
    
    while ((i != 1) && (item.key > h->heap[i/2].key)){
        h->heap[i] = h->heap[i/2];
        i /= 2;
    }
    h->heap[i] = item;
}

element delete_max_heap(HeapType* h)
{
    int parent, child;
    element item, temp;
    
    item = h->heap[1];
    temp = h->heap[(h->heap_size)--];
    parent = 1;
    child = 2;
    while(child <= h->heap_size){
        //현재 노드의 자식노드 중 더 큰 자식노드를 찾는다.
        if((child < h->heap_size) && (h->heap[child].key) < h->heap[child + 1].key)
            child++;
        if(temp.key >= h->heap[child].key) break;
        //한 단계 아래로 이동
        h->heap[parent] = h->heap[child];
        parent = child;
        child *=2;
    }
    h->heap[parent] = temp;
    return item;
}

void heap_sort(element a[], int n)
{
    int i;
    HeapType* h;
    
    h = create();
    init(h);
    for(i=0; i<n; i++){
        insert_max_heap(h, a[i]);
    }
    for(i=(n-1); i>=0; i--){
        a[i] = delete_max_heap(h);
    }
    free(h);
}
void max_input(HeapType* h)
{
    char a;
    char work[100];
    int im;
    
    while(1){
        printf("삽입(i), 삭제(d): ");
        scanf("%c", &a);
        if(a == 'i'){
            printf("할일: ");
            scanf("%s", work);
            printf("우선순위: ");
            scanf("%d", &im);
        }
        else if(a == 'd'){
            
        }
    }
}

int main(void)
{
    element e1 = {10}, e2 = {5}, e3 = {30};
    element e4, e5, e6;
    HeapType* heap;
    
    heap = create();
    init(heap);
    
    insert_max_heap(heap, e1);
    insert_max_heap(heap, e2);
    insert_max_heap(heap, e3);
    
    e4 = delete_max_heap(heap);
    printf("< %d >", e4.key);
    e5 = delete_max_heap(heap);
    printf("< %d >", e5.key);
    e6 = delete_max_heap(heap);
    printf("< %d >", e6.key);
    
}