Chapter 2 배열과 구조 (Arrays and Structures) 2009. 3. 23

포인터 포인터 C언어에서는 모든 타입에 대해 그것의 포인터 타입이 존재 포인터 변수의 값은 메모리 상의 주소(address) 포인터 관련 연산 주소/참조 (address/reference) 연산자: & 역참조/간접참조 (dereferencing/indirection) 연산자: * 예 int i, *pi pi = &i; // pi는 i의 주소값을 가짐. 즉, i를 가리킴 // i에 10을 저장하기 i = 10; *pi = 10;

포인터 동적 메모리 할당(dynamic storage allocation) 프로그램을 작성 시 얼마나 많은 메모리 공간이 필요한지 알 수 없을 때 실행-시간 메모리 할당을 위해 heap 이용 새로운 메모리 공간이 필요할 때마다 함수 malloc을 호출해서 필요한 양의공간을 할당 받음 int i, *pi; float f, *pf; pi = (int *)malloc(sizeof(int)); pf = (float *)malloc(sizeof(float)); *pi = 1024; *pf = 3.14; printf(“an integer=%d, a float=%f\n”,*pi,*pf); free(pi); free(pf);

ADT로서의 배열 배열(array) 일련의 연속적인 메모리 위치 구현 중심의 이해 추상 데이터 타입 <index, value> 쌍의 집합 값들은 동일한 타입 인덱스와 값 사이의 대응 또는 사상(mappings) array : i → ai 수행 가능한 연산 정의 Array Create(j-dimension, j-range list) Item Retrieve(array, index) Array Store(array, index, item)

ADT로서의 배열 Structure Array    Objects : index의 각 값에 대하여 집합 item에 속한 한 값이 존재하는 <index, value>쌍의 집합. index는 일차원 또는 다차원의 유한 순서 집합이다. 예를 들면, 일차원의 경우 {0,‥, n-1}과 이차원 배열 {(0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2)}, 등이다.   Functions : 모든 A ∈ Array, i ∈ index, x ∈ item, j, size ∈ integer       Array Create(j, list)  ::= return j차원의 배열.                                여기서 list는 j-tuple(i번째 원소는 i번째 차원의                                크기를 나타냄)이며, item들은 정의되지 않았음.       Item Retrieve(A, i)   ::= if (i ∈ index)                                return 배열 A의 인덱스 i값과 관련된 항목.                                else return 에러.       Array Store(A, i, x)    ::= if (i ∈ index)                               return 새로운 쌍<i, x>가 삽입된 배열 A. end Array

C언어에서의 구현 C의 일차원 배열 int list[5], *plist[5]; 배열 이름 = 포인터 상수(첫번째 원소의 주소) 정수의 집합 : { list[0], list[1], list[2], list[3], list[4] } 정수 포인터의 집합 : { plist[0], plist[1], plist[2], plist[3], plist[4] }                  배열 이름 = 포인터 상수(첫번째 원소의 주소) int list2[5]; list2: list2[0]를 가리키는 포인터 (즉, list2[0]의 주소) list2+i: list2[i]를 가리키는 포인터 (즉, list2[i]의 주소) (list2+i) == &list2[i],  *(list2+i) == list2[i] 변 수 메모리 주소 list[0] 기본주소 = a list[1] a + sizeof(int) list[2] a + 2 ·sizeof(int) list[3] a + 3 ·sizeof(int) list[4] a + 4 ·sizeof(int)

C언어에서의 구현 배열 프로그램의 예 #define MAX_SIZE 100 float sum(float [], int); float input[MAX_SIZE], answer; int i; void main(void) {     for (i = 0; i < MAX_SIZE; i++)        input[i] = i;     answer = sum(input, MAX_SIZE);     printf("The sum is: %f\n", answer); } float sum(float list[], int n) // float list[] == float *list     int i;     float tempsum = 0;     for (i = 0; i < n; i++)        tempsum += list[i]; // list[i] == *(list+i)    return tempsum;

C언어에서의 구현 호출시 input(=&input[0])은 형식 매개 변수 list에 복사됨 역참조(dereference) 즉, list[i] == input[i] 역참조(dereference) list[i]가 “=”기호 우측  (list + i)가 가리키는 값 반환 list[i]가 “=”기호 좌측  값을 (list + i) 위치에 저장 ※ C언어의 매개변수 전달방식 : call-by-value  실 매개변수가 배열 이름인의 경우 배열의 주소를 형식매개변수에 복사함  배열 자체는 복사되지 않음

C언어에서의 구현 예제[일차원 배열의 주소 계산] short one[] = {0, 1, 2, 3, 4}; printf1(&one[0], 5) // == print1(one, 5) void print1 (short *ptr, int rows) { /* print out an one-dimensional array using a pointer */ int i; printf (“Address Contents\n”); for (i=0; i<rows; i++) printf(“%8u%5d\n”, ptr + i, *(ptr + i)); // &ptr[i], ptr[i]와 동일 printf(“\n”); } 주소 1228 1230 1232 1234 1236 내용 1 2 3 4

동적 할당 배열 #define MALLOC(p, s)\ if(!((p) = malloc(s))) {\ fprintf(stderr, “Insufficient memory”):\ exit(EXIT_FAILURE):\ } #define CALLOC(p, n, s)\ if(!((p) = calloc(n, s))) {\ 메모리를 할당하고 0으로 초기화함 fprintf(stderr, “Insufficient memory”):\ exit(EXIT_FAILURE):\ } #define REALLOC(p, s)\ if(!((p) = realloc(n, s))) {\ 메모리를 재할당 (크기 변경) fprintf(stderr, “Insufficient memory”):\ exit(EXIT_FAILURE):\ }

동적 할당 배열 1차원 배열 동적 생성 예 int i, n, *list; printf(“Enter the number of number to generate: ”); scanf(“%d”, &n”); if (n < 1) { fprintf(stderr, “Improper value of n \n”); exit (EXIT_FAILURE); } MALLOC(list, n * sizeof(int)); ※ n < 1이거나 정렬할 수의 리스트를 저장할 메모리가 충분치 않을 때 실패

동적 할당 배열 2차원 배열 동적 생성 예 int ** make2dArray(int rows, int cols) int x[3][5] [0] [1] [2] [3] [4] x x[0] x[1] x[2] int ** make2dArray(int rows, int cols) { /* create a two dimensional rows  cols array */ int **x, i; /* get memory for row pointers */ MALLOC (x, rows * sizeof(int*));; /* get memory for each row */ for (i = 0; i < rows; i++) MALLOC (x[i], cols * sizeof(int)); return x; }

동적 할당 배열 사용 예 int **myArray; myArray = make2dArray(5, 10); 510 2차원 정수 배열에 대한 메모리 할당 이 배열의 [2][4]원소에 정수 6을 지정 int **myArray; myArray = make2dArray(5, 10); myArray[2][4] = 6

구조체(Structure) 및 공용체(Union) 구조(structure) : struct 타입이 다른 데이터들을 그룹화 함 데이터 항목들의 집단 - 각 항목은 타입과 이름으로 식별                 멤버(member) 연산자 . strcpy(person.name, "james"); person.age =10; person.salary = 35000; struct { char name[10]; int age; float salary; } person;

구조체(Structure) 및 공용체(Union) typedef 문장을 사용한 구조체 데이터 타입 생성 전체 구조의 동등성 검사 :  if (person1 == person2) 구조 치환 :  person1 = person2 (ANSI C) strcpy(person1.name, person2.name); person1.age = person2.age; person1.salary = person2.salary; typedef struct human_being {        char name[10];      int age;                             float salary;                          };                             /* 변수 선언 */ human_being person1, person2; typedef struct {       char name[10];                int age;                      float salary;       } human_being;                     /* 변수 선언 */ human_being person1, person2;

구조체(Structure) 및 공용체(Union) 구조체 속에 또 다른 구조체 정의 예        typedef struct {                    int month;                  int day;                    int year;     } date ;      typedef struct human_being {                          char name[10];               int age;               float salary;               date dob; } ;                  person1.dob.month = 2; person1.dob.day = 11; person1.dob.year = 1944;

구조체(Structure) 및 공용체(Union) 공용체에 속한 각 필드들은 메모리 공간을 공유함 어느 한 시점에 한 필드만 활동적이 되어 사용 가능 C에서는 공용체 필드의 올바른 사용 여부를 검사하지 않음 typedef struct gender_type {     enum tag_field {female, male} gender;     union {         int children;         int beard;     } u ; }; typedef struct human_being {     char name[10];     int age;     float salary;     date dob;     gender_type g_info; human_being person1, person2; person1.g_info.gender = male; person1.g_info.u.beard = FALSE; person2.g_info.gender = female; person2.g_info.u.children = 4;

구조체(Structure) 및 공용체(Union) 자체참조 구조체 (self-referential structure) 구성요소중 자신을 가리키는 포인터가 존재하는 구조체 typedef struct list {                       char data;              list *link;    };                             list item1, item2, item3;          item1.data = 'a';                 item2.data = 'b';          item3.data = 'c';          item1.link = item2.link = item3.link = NULL;          item1.link = &item2;    구조들을 서로 연결          item2.link = &item3;     (item1→ item2→ item3)

순서 리스트 순서 리스트, 선형 리스트(Ordered list, Linear list) 순서가 있는 원소들의 집합 예 한 주일의 요일: (일,월,화,수, .., 토) 카드 한 벌의 값: (Ace, 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King) 건물 층: (지하, 로비, 1층, 2층) 미국의 WWII 참전년도: (1941, 1942, 1943, 1944, 1945) 스위스의 2차 세계대전 참전 년도: () 리스트 형태: (a0, a1, ... , an-1) 공백 리스트: () -> 포함된 항목이 없음

순서 리스트 리스트에 대한 연산 순서 리스트의 일반적인 구현 (기억장소 표현) 리스트 길이 n의 계산 리스트의 항목을 왼쪽에서 오른쪽 (오른쪽에서 왼쪽) 으로 읽기 i 번째 항목을 검색, 0  i < n i 번째 항목을 대체, 0  i < n i 번째 위치에 새 항목 삽입, 0  i <n i 번째 항목을 삭제, 0  i < n 순서 리스트의 일반적인 구현 (기억장소 표현) 순차 사상 (sequential mapping) 배열 이용 물리적 인접성 이용 장점: 상수 시간내에 항목 검색/변경 가능 문제점: 삽입, 삭제시 오버헤드 비순차 사상(non-sequential mapping) 비연속적 기억장소 위치 연결 리스트로 표현 : pointer(즉, link)를 가지는 노드들의 집합

다항식 추상 데이터 타입 다항식 (polynomial) 차수(degree): 가장 큰 지수 다항식의 합과 곱 A(x) = aiXei = anxn+an-1xn-1+...+a1x1+a0x0 ai : 계수(coefficient), ai 0 ei : 지수(exponent), unique, 0 x : 변수(variable) 예 A(x) = 3x20 + 2x5 + 4 , B(x) = x4 + 10x3 + 3x2 + 1 차수(degree): 가장 큰 지수 다항식의 합과 곱 A(x) =  aixi, B(x) =  bixi 일 때, A(x) + B(x) = (ai + bi) xi A(x) · B(x) = (aixi · (bjxj))

polynomial 추상 데이터 타입 Structure Polynomial Objects : P(x) = +・・・+ : <ei, ai>의 순서쌍 집합. 여기서 ai는 Coefficient, ei는 Exponents. ei (≥ 0)는 정수. Function : 모든 poly, poly1, poly2 ∈ polynomial,             coef ∈ Coefficients, expon ∈ Exponents에 대해   Polynomial Zero()                           ::= return 다항식, p(x) = 0   Boolean IsZero(poly)                       ::= if (poly) return FALSE                                             else return TRUE   Coefficient Coef(poly, expon)       ::= if (expon ∈ poly) return 계수                                                     else return 0   Exponent Lead_Exp(poly)             ::= return poly에서 제일 큰 지수   Polynomial Attach(poly, coef, expon)   ::= if (expon ∈ poly) return 오류                                                     else return <coef, exp>항이 삽입된 다항식 poly    Polynomial Remove(poly, expon)   ::= if (expon ∈ poly)                                                    return 지수가 expon인 항이 삭제된 다항식 poly                                                      else return 오류          Polynomial SingleMult(poly, coef, expon) ::= return 다항식 poly‧coef‧xexpon   Polynomial Add(poly1, poly2)             ::= return 다항식 poly1 + poly2   Polynomial Mult(poly1, poly2)            ::= return 다항식 poly1‧poly2 end polynomial

Add 연산 /* d = a + b, 여기서 a, b, d는 다항식이다. */ d = Zero(); while (! IsZero(a) && ! IsZero(b)) do {     switch COMPARE(Lead_Exp(a), Lead_Exp(b)) {         case -1:             d = Attach (d, Coef(b, Lead_Exp(b)), Lead_Exp(b));             b = Remove(b, Lead_Exp(b));             break;         case 0:             sum = Coef(a, Lead_Exp(a)) + Coef(b, Lead_Exp(b));             if (sum) {                      Attach(d, sum, Lead_Exp(a));                              a = Remove(a, Lead_Exp(a));                      b = Remove(b, Lead_Exp(b));             }         case 1:             d = Attach(d, Coef(a, Lead_Exp(a)), Lead_Exp(a));             a = Remove(a, Lead_Exp(a));     } } a 또는 b의 나머지 항을 d에 삽입한다.

다항식의 표현 1 가정: 서로 다른 지수들을 내림차순으로 정렬 [표현 1] 모든 차수에 대한 계수 저장 계수 배열 크기는 기정의된 값(최대값)으로 a: polynomial, n < MAX_DEGREE a.degree = n a.coef[i] = an-i, 0 ≤ i ≤ n 예 A(x) = x4+10x3+3x2+1   : n = 4 A = (4, 1, 10, 3, 0, 1)     장점: 다항식에 대한 연산 알고리즘이 간단 단점: 저장 공간 낭비 a.degree << MaxDegree 또는 Sparse polynomial의 경우 #define MAX_DEGREE 101 /* 다항식의 최대 차수 + 1 */ typedef struct        int degree;              float coef[MAX_DEGREE];        } polynomial;

다항식의 표현 2 [표현 2] 0이 아닌 계수-지수 쌍 만 저장 희소 다항식의 경우 a.coef[MAX_DEGREE]의 대부분이 필요없음 A(x) = x1000 + 1         : n = 1000 A = (1000, 1, 0,..., 0, 1)   : 1002 elements                                   ↳ 999 A(x) = bm-1xe_m-1 + bm-2xe_m-2 +  ...  + boxe_0      where bi ≠ 0 (0≤i≤m-1), em-1>em-2>...>eo≥0 A = (m, em-1, bm-1, em-2, bm-2, ... , e0, b0) 예 A(x) = x4+10x3+3x2+1 : A = (4, 4, 1, 3, 10, 2, 3, 0, 1) A(x) = x1000 +1 : A = (2, 1000, 1, 0, 1)

다항식의 표현 2 여러 개의 다항식 표현: 모든 다항식을 하나의 전역 배열에 저장 A(x)=2x1000+1       B(x)=x4+10x3+3x2+1             starta   finisha   startb          finishb  avail  coef   exp        A(x) : <starta, finisha>              finisha = starta + n - 1 장점: 많은 항이 0인 경우 우수 단점: 모든 항이 0이 아닌 경우 표현 1보다 두 배의 저장 장소 필요 MAX_TERMS 100 /* 항 배열의 크기 */                  typedef struct {                   float coef;                                   int expon;           } Polynomial;           Polynomial terms[MAX_TERMS];           int avail = 0; 2 1 10 3 1000 4

다항식의 표현 2: Add 연산의 구현 void padd(int starta, int finisha, int startb, int finishb, int *startd, int *finishd); {   /* A(x) 와 B(x)를 더하여 D(x)를 생성한다 */     float coefficient;     *startd = avail;     while (starta <= finisha && startb <= finishb)         switch (COMPARE(terms[starta].expon, terms[startb].expon)) {              case -1: /* a의 expon이 b의 expon보다 작은 경우 */                      attach(terms[startb].coef, terms[startb].expon);                      startb++;  break;              case 0: /* 지수가 같은 경우 */                     coefficient = terms[starta].coef + terms[startb].coef;                     if (coefficient) attach(coefficient, terms[starta].expon);                     starta++;  startb++; break;              case 1: /*  a의 expon이 b의 expon보다 큰 경우 */                     attach(terms[starta].coef, terms[starta].expon);                     starta++;     }     for( ; starta <= finisha; starta++ )   /* A(x)의 나머지 항들을 첨가한다 */         attach(terms[starta].coef, terms[starta].expon);     for( ; startb <= finishb; startb++ )   /* B(x)의 나머지 항들을 첨가한다 */         attach(terms[startb].coef, terms[startb].expon);           *finishd = avail-1; }

다항식의 표현 2: Add 연산의 구현 void attach(float coefficient, int exponent) {    /* 새 항을 다항식에 첨가한다. */     if (avail >= MAX_TERMS) {         fprintf(stderr, "다항식에 항이 너무 많다.");         exit(1);      }     terms[avail].coef = coefficient;     terms[avail++].expon = exponent; }

다항식의 표현 2: Add 연산의 구현 알고리즘 분석 문제점 m, n (>0) : 각각 A와 B의 0이 아닌 항의 수 while 루프 : O(n+m) 각 반복마다 starta나 startb 또는 둘 다 값이 증가 반복 종료 조건: starta > finisha || startb > finishb (즉, 어느 한쪽이 모두 검사될 때까지 반복) 반복 횟수 ≤ m+n-1 -> O(n+m) m+n-1인 경우: A(x) = x2i  , B(x) = x2i+1  일 때 for 루프 :  O(m), O(n) ∴ 총 연산시간 =  O(n+m) 문제점 avail = MAX_TERMS 일 때 불필요한 다항식 제거 후 배열 끝에 연속적인 가용공간 생성 필요 데이터 이동 및 각 다항식의 starti, finishi 변경 필요

희소 행렬(Sparse Matrix) A[m][n]: m  n 행렬 A 희소 행렬(sparse matrix) m = n : 정방 행렬(square matrix) 각 원소 A[i][j]에 대한 접근: O(1) 2차원 배열로 구현 시 공간 복잡도: O(m·n) 희소 행렬(sparse matrix) 0이 아닌 원소 개수 / 전체 원소 개수 << small 메모리를 효율적으로 사용하기 위해서는 0이 아닌 원소만 저장해야 함 행렬에 대한 연산 creation addition multiplication transpose

밀집 행렬과 희소 행렬의 예 1 2 3 4 5 1 2 1 1 2 2 3 3 4 4 5 밀집 행렬 희소 행렬

희소 행렬 추상 데이터 타입(ADT) Structure SparseMatrix Objects : 3 원소쌍 <행, 열, 값>의 집합. 행, 열, 값은 정수이고, 행과 열의 각 조합은 유일 Function : SparseMatrix Create(int MaxRow, int MaxCol); // MaxRow x MaxCol (=MaxItems)을 저장할 수 있는 SparseMatrix를 생성함 SparseMatrix Transpose(SparseMatrix a); // a의 모든 3원소 쌍의 행과 열의 값을 서로 교환하여 얻은 행렬을 반환함 SparseMatrix Add(SparseMatrix a, SparseMatrix b); // if a와 b의 차원이 같으면 대응 항들, 즉, 같은 행과 열의 값을 // 가진 항들을 더해서 만들어진 행렬을 반환 // else 오류를 발생 SparseMatrix Multiply(SparseMatrix a, SparseMatrix b); // if a의 열의 수와 b의 행의 수가 같으면 d(i,j)= (a[i][k]  b[k][j])인 // 행렬 d를 반환 end SparseMatrix

희소 행렬의 효율적인 표현 표현 방법 (필요한 정보들) i. 0이 아닌 값을 갖는 <행, 열, 값> 3원소 쌍(triple) ii. 행의 수 iii. 열의 수 iv. non-zero 원소의 수 v. 순서: 행우선 순서 또는 열우선 순서 #define MAX_TERMS 101 typedef struct { int row; int col; int value; } term; term a[MAX_TERMS]; - a[0].row: the number of rows - a[0].col: the number of columns - a[0].value: the total number of non-zeros - We choose row-major order => term들의 순서 리스트로 표현

희소 행렬의 효율적인 표현 행 열 값 a [0] 6 6 8 1 2 3 4 5 [1] 15 1 [2] 3 22 2 [3] 5 1 2 3 4 5 [1] 15 1 [2] 3 22 2 [3] 5 -15 3 [4] 1 1 11 [5] 1 2 3 4 [6] 2 3 -6 5 [7] 4 91 [8] 5 2 28 예제 희소 행렬 순서 리스트 표현

예제 희소 행렬 및 전치 행렬 1 2 3 4 5 1 2 3 4 5 A의 전치 행렬 AT 1 2 3 4 5 희소 행렬 A

순서 리스트 표현 행 열 값 8 행 열 값 15 4 91 1 11 2 3 5 28 22 -6 -15 [1] [2] [3] 15 4 91 1 11 2 3 5 28 22 -6 -15 [1] [2] [3] [4] [5] [6] [7] [8] A의 전치 행렬 AT 6 [0] a a [0] 6 6 8 [1] 15 [2] 3 22 [3] 5 -15 [4] 1 1 11 [5] 1 2 3 [6] 2 3 -6 [7] 4 91 [8] 5 2 28 희소 행렬 A

희소 행렬의 전치(transpose) 단순 알고리즘 for (각 행 i 에 대해) 원소 <i, j, 값>을 가져와서 전치행렬의 원소 <j, i, 값>으로 저장 (예) (0, 0, 15) → (0, 0, 15) (0, 3, 22) → (3, 0, 22) (0, 5, -15) → (5, 0, -15) (1, 1, 11) → (1, 1, 11) 문제점: 올바른 순서 유지 위해 기존 원소를 이동해야 함 알고리즘 1 for (각 열 j에 대해) 열 j 에 있는 모든 원소 <i, j, 값>을 원소 <j, i, 값>에 저장

희소 행렬의 전치 알고리즘 1 void transpose(term a[], term b[]) /* a를 전치시켜 b를 생성 */ {     int n, i, j, currentb;     n = a[0].value;     /* a 행렬에 포함된 0이 아닌 원소의 개수 */     b[0].row = a[0].col; /* b의 행 수 = a의 열 수 */      b[0].col = a[0].row; /* b의 열 수 = a의 행 수 */      b[0].value = n;    /* b의 원소 수 = a의 원소 수 */     if (n > 0) { /* 0이 아닌 행렬 */            currentb = 1;         for (i = 0; i < a[0].col; i++) /* a의 각 열에 대해 반복 */            for (j = 1; j <= n; j++) /* 모든 원소들을 검사하여 */            if (a[j].col == i) { /* i 열에 속한 원소들을 찾음 */                /* 발견된 원소를 b에 추가 */                   b[currentb].row = a[j].col;                   b[currentb].col = a[j].row;                   b[currentb].value = a[j].value;                   currentb++;               }     } }

희소 행렬의 전치 알고리즘 1 시간 복잡도: O(columns  elements) = O(rows  columns2) [Note] 희소 행렬을 단순한 2차원 배열로 표현할 경우 전치 방법 for (int j = 0; j < columns; j++) for (int i = 0; i < rows; i++) B[j][i] = A[i][j];  O(rows  columns) 공간 절약을 위해 시간을 희생한 결과

희소 행렬의 전치 알고리즘 2 메모리 공간을 조금 더 사용한 알고리즘: FastTranspose 즉, 전치 행렬 b의 각 행의 원소 수를 결정 이 정보로부터 전치 행렬 b의 각 행의 시작 위치를 구함 행렬 a에 있는 원소를 하나씩 전치 행렬 b의 올바른 위치로 옮김 구현 방법: 부가적인 배열 이용 row_terms[i]: the number of elements in the row i of the result matrix b starting_pos[i]: the starting point of the elements in the row i in the sparse matrix representation of b  결과 행렬에 row = i 인 원소를 저장할 때 마다 1 증가시켜, 다음 원소의 저장 위치를 가리키도록 함

희소 행렬의 전치 알고리즘 2 행 열 값 행 열 값 a [0] 6 6 8 b [0] 6 6 8 [1] 15 [1] 15 [2] 15 [1] 15 [2] 3 22 [2] 4 91 [3] 5 -15 [3] 1 1 11 [4] 1 1 11 [4] 2 1 3 [5] 1 2 3 [5] 2 5 28 [6] 2 3 -6 [6] 3 22 [7] 4 91 [7] 3 2 -6 [8] 5 2 28 [8] 5 -15 행: 0, 1, 2, 3, 4, 5 row_terms[] = {2, 1, 2, 2, 0, 1} starting_pos[] = {1, 3, 4, 6, 8, 8}

희소 행렬의 전치 알고리즘 2 void fast_transpose(term a[], term b[])     /* a를 전치시켜 b에 저장 */ {     int row_terms[MAX_COL], starting_pos[MAX_COL];     int i, j, num_col = a[0].col, num_terms = a[0].value;     b[0].row = a[0].col; b[0].col = a[0].row; b[0].value = a[0].value;     if (num_terms > 0) { /* 0이 아닌 행렬 */         for(i = 0; i < num_cols; i++) row_terms[i] = 0;         for(i = 1; i <= num_terms; i++)             row_terms[a[i].col]++;         starting_pos[0] = 1;         for(i = 1; i < num_cols; i++)             starting_pos[i] = starting_pos[i-1] + row_terms[i-1];          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;          }                     } }

희소 행렬의 전치 알고리즘 2 시간 복잡도: O(columns + elements) = O(rows  columns) 그러나, 희소 행렬에서 elements는 일반적으로 rows  columns 보다 훨씬 작으므로 2차원 배열 알고리즘 보다 빠름 (즉, 시간과 공간을 동시에 절약하는 효과를 거둘 수 있음)

행렬의 곱셈 Result A  B Result(mp)  A(mn)  B(np) [note] 통상적인 곱셈 알고리즘 for (int i = 0; i < A.Rows; i++) for (int j = 0; j < B.Cols; j++) { sum = 0; for (int k = 0; k < A.Cols; k++) sum += (a[i][k] * b[k][j]); c[i][j] = sum; }  O(A.Rows • A.Cols • B.Cols)

행렬의 곱셈 순서 리스트로 표현된 두 희소 행렬의 곱셈 결과 행렬(순서 리스트 표현)의 원소들을 행-우선 순서대로 계산 계산 및 저장된 원소들을 이동할 필요 없음 행렬 A에서 한 행을 선택하고, j = 0,1,..., cols_b-1에 대해 B의 j열에 있는 모든 원소를 찾아서 벡터 내적을 반복 계산해야 함 효율적인 계산을 위해 우선 행렬 B에 대한 전치 행렬을 구함 B의 j열의 원소들을 순서대로 찾을 수 있음 (B의 j열 = BT의 j행) A의 i행과 BT의 j행(= B의 j열)의 원소들이 정해지면 다항식 덧셈과 유사한 합병 연산 수행 알고리즘 및 시간 복잡도 계산 교재 참조 O(B.Cols • A.Terms + A.Rows • B.Terms) => 최악의 경우 O(A.Rows • A.Cols • B.Cols) 이나, A, B가 희소 행렬이면 일반적인 알고리즘보다 훨씬 빠름

다차원 배열의 표현 배열의 원소 수 : A[upper0][upper1]...[uppern-1] =       =     예: A[10][10][10] → 10・10・10 = 1000 개 행 우선 순서(row major order) A[upper0][upper1] A[0][0], A[0][1], ⋯ , A[0][upper1-1]    ⋯               row0              row1  row2   row_upper0-1 열 우선 순서(column major order) A[0][0], A[1][0], ⋯, A[upper0-1][0]    ⋯               col0                col1    col2       col_upper1-1

다차원 배열의 표현 원소의 메모리 주소 계산 (2차원 배열 – 행우선 표현) α = A[0][0]의 주소          A[i][0]의 주소 = α + i·upper1          A[i][j]의 주소 = α + i·upper1 + j 주소 계산 (3차원 배열 – 행우선 표현) A[upper0][upper1][upper2] 2차원 배열 upper1 × upper2 → upper0 개      A[i][0][0] 주소 = α + i·upper1·upper2      A[i][j][k] 주소 = α + i·upper1·upper2 + j ·upper2 + k

다차원 배열의 표현 주소 계산 (n차원 배열): A[upper0][upper1]...[uppern-1]   A[i0][0]...[0] 주소 = α + i0upper1upper2...uppern-1   A[i0][i1][0]...[0] 주소 =         α + i0upper1upper2...uppern-1 + i1upper2upper3...uppern-1   A[i0][i1]...[in-1] 주소 =         α + i0upper1upper2...uppern-1             + i1upper2upper3...uppern-1             + i2upper3upper4...uppern-1            ⋮            + in-2uppern-1            + in-1 = α +

문자열 추상 데이타 타입 문자열(string): S = s0, s1, …, sn-1의 형태, si : 문자 집합의 원소 연산 생성, 문자열의 읽기 또는 출력 두 문자열 접합(concatenation), 문자열 복사 문자열 비교 문자열에 일부 문자열 삽입 문자열로부터 일부 문자열 삭제 문자열에서 특정 패턴 식별

문자열 추상 데이타 타입 structure String objects : 0개 이상의 문자들의 유한 순서 집합 functions : String Null(int m); // 최대 길이가 m인 문자열 (Null로 초기화) int Compare(String s, String t); // if (s와 t가 동등하면) return 0 // else if (s가 t에 선행하면) return -1 else return 1 Boolean IsNull(String s); // if s가 Null 문자열이면 return TRUE // else return FALSE int Length(String s); // s의 문자수를 반환 String Concat(String s, String t); // s뒤에 t를 붙인 문자열을 반환 String Substr(String s, int i, int j); // s에서 i,i+1,...,i+j-1의 위치에 있는 j개의 문자열을 반환 // 이들이 유효한 위치가 아니면 공백 문자열을 반환 int nfind (String s, String pat); // s의 i에서 시작하는 부분문자열이 pat과 일치하는 경우 인덱스 i를 반환 // pat이 공백이거나 s의 부분문자열이 아닌 경우에는 -1을 반환

C 언어의 문자열 구현 내부적으로는 Null 문자(\0)로 끝나는 문자 배열로 표현 문자열 상수는 char* 타입의 변수에 지정 (예) char* str = "abc" 대부분의 C 컴파일러는 여러 가지 문자열 함수를 포함하는 라이브러리를 제공함 그림 2.8 참조 char s[] = “dog”; char t[] = “house”; s[0] s[1] s[2] s[3] t[0] t[1] t[2] t[3] t[4] t[5] d o g \0 h o u s e \0

문자열 삽입 함수 예 void strnins (char *s, char *t, int i) (Program 2.12) 초기 상태 s a m o b i l e \0 t u t o \0 temp \0 (a) 함수 strncpy(temp, s, i) 호출 후 temp a \0 (b) 함수 strcat(temp, t) 호출 후 temp a u t o \0 (c) 함수 strcat(temp, (s+i)) 호출 후 temp a u t o m o b i l e \0 (d) 함수 strcpy(s, temp) 호출

Homework #1 Chapter 1 Chapter 2 Due: 3.30(월) 수업시간에 제출