배열과 ADT(1/2) 연속된 메모리 위치의 집합 <index, value>쌍의 집합

Slides:



Advertisements
Similar presentations
Ⅰ. 연산자 Ⅱ. 제어 구조. 연산자 : 할당 연산자 - 사용자가 정의한 변수에 임의의 값을 저장하는 기능 strvar = strVar1+ “ Hello ”
Advertisements

1. 2 차원 배열  배열은 동일한 데이터 유형으로 여러 개의 변수를 사용할 경우 같은 이 름으로 지정하여 간편하게 사용할 수 있도록 하는 것으로서 앞에서 1 차원 배열을 공부하였습니다.  2 차원 배열은 바둑판을 생각하면 되며, 1 차원 배열에서 사용하는 첨자를 2.
제 2 장 : 배열과 구조 이 형 원 강릉대학교 컴퓨터공학과
배열과 ADT(1/2) 연속된 메모리 위치의 집합 <index, value>쌍의 집합
Chapter 2 배열과 구조 (Arrays and Structures)
쉽게 풀어쓴 C언어 Express 제11장 포인터 C Express Slide 1 (of 27)
제14장 동적 메모리.
희소 행렬(sparse matrix) mn matrix A ≡ A[MAX_ROWS][MAX_COLS] 희소행렬
Report #5 - due: 4/13 다음 10*5의 희소 행렬 A, B를 고려하라.
제2장 배열과구조.
제2장 배열과구조.
9장. C 언어의 핵심! 함수. 9장. C 언어의 핵심! 함수 9-1 함수의 정의와 선언 main 함수 다시 보기 : 함수의 기본 형태 { } 그림 9-1.
5 순차 자료구조 방식.
C로 쉽게 풀어쓴 자료구조 © Copyright 생능출판사 2011
C로 쉽게 풀어쓴 자료구조 © Copyright 생능출판사 2005
연결리스트(linked list).
제 9 장 구조체와 공용체.
제2장 배열과구조.
시스템 생명 주기(System Life Cycle)(1/2)
-Part2- 제3장 포인터란 무엇인가.
Chapter 03 배열, 구조체, 포인터.
시스템 생명 주기(System Life Cycle)(1/2)
C로 쉽게 풀어쓴 자료구조 © Copyright 생능출판사 2005
자료 구조: Chapter 3 배열(1) 순천향대학교 컴퓨터공학과 하 상 호.
자료 구조: Chapter 3 배열(1) 순천향대학교 컴퓨터공학과 하 상 호.
자료 구조: Chapter 3 (2)구조체, 포인터
3장. 변수와 연산자. 3장. 변수와 연산자 3-1 연산자, 덧셈 연산자 연산자란 무엇인가? 연산을 요구할 때 사용되는 기호 ex : +, -, *, / 3-1 연산자, 덧셈 연산자 연산자란 무엇인가? 연산을 요구할 때 사용되는 기호 ex : +, -, *, /
개정판 누구나 즐기는 C언어 콘서트 제9장 포인터 출처: pixabay.
CHAP 3:배열, 구조체, 포인터.
제 3 장 선형 리스트 3.1 선형 리스트 3.2 연결 리스트 3.3 다항식.
쉽게 풀어쓴 C언어 Express 제17장 동적메모리와 연결리스트 C Express Slide 1 (of 13)
쉽게 풀어쓴 C언어 Express 제17장 동적 메모리와 연결 리스트 C Express.
동적메모리와 연결리스트 컴퓨터시뮬레이션학과 2016년 봄학기 담당교수 : 이형원 E304호,
5장. 참조 타입.
P150 문제를 프로그래밍 할 것 Source file (헤더파일포함), 실행화면 (학번_이름_1.txt)
Dynamic Memory and Linked List
11장. 포인터 01_ 포인터의 기본 02_ 포인터와 Const.
Chapter 2:: Array, Structure, and Pointer
SqlParameter 클래스 선문 비트 18기 발표자 : 박성한.
컴퓨터 프로그래밍 기초 #02 : printf(), scanf()
자료구조: CHAP 4 리스트 (1) 순천향대학교 컴퓨터공학과 하 상 호.
프로그래밍 랩 – 7주 리스트.
자료구조 구현을 위한 C 프로그래밍 기법, 순차 자 료구조
11장. 1차원 배열.
Introduction To Data Structures Using C
C#.
JA A V W. 03.
13. 포인터와 배열! 함께 이해하기 IT응용시스템공학과 김 형 진 교수.
3장 상수 변수 기본 자료형 키워드와 식별자 상수와 변수 기본 자료형 형변환 자료형의 재정의.
Report #3 - due: 4/6 100*100의 2개의 희소 행렬 A, B를 전달 받아서 이들의 덧셈을 구하고, 그 결과의 행렬 C를 반환하는 add_sparse_matrix(A, B, C)를 다음과 같이 작성하라. 희소 행렬은 sparse_matrix 타입으로 표현된다.
Quiz #7 다음 수들을 합병 정렬과 퀵 정렬 알고리즘을 이용하여 오름 차순으로 정렬하였을 때, 데이터 이동 회수를 각각 구하라. 여러분은 정렬 과정을 단계별로 보이면서 이동 회수를 추적해야 한다. 단, 퀵 정렬시에 피봇으로 배열의 왼쪽 첫 번째 원소를 선택한다. 5.
쉽게 풀어쓴 C언어 Express 제14장 포인터 활용 C Express Slide 1 (of 22)
3장. 변수와 연산자 교안 : 전자정보통신 홈페이지 / 커뮤니티/ 학술세미나
Chapter6 : JVM과 메모리 6.1 JVM의 구조와 메모리 모델 6.2 프로그램 실행과 메모리 6.3 객체생성과 메모리
컴퓨터 프로그래밍 기초 - 10th : 포인터 및 구조체 -
제 3 강.
처음으로 배우는 C 프로그래밍 제4부 복합 데이터 형 제 7 장 배열.
컴퓨터 프로그래밍 기초 - 8th : 함수와 변수 / 배열 -
8주차: Strings, Arrays and Pointers
데이터 동적 할당 Collection class.
4장. 데이터 표현 방식의 이해. 4장. 데이터 표현 방식의 이해 4-1 컴퓨터의 데이터 표현 진법에 대한 이해 n 진수 표현 방식 : n개의 문자를 이용해서 데이터를 표현 그림 4-1.
토론을 위한 질문 배열의 이름에는 무엇이 저장되는가? C언어에서 배열 추상데이터의 store는 어떻게 구현 되는가?
7주차: Functions and Arrays
컴퓨터 프로그래밍 기초 - 9th : 배열 / 포인터 -
Summary of Pointers and Arrays
Numerical Analysis Programming using NRs
제 4 장 Record.
13. 포인터와 배열! 함께 이해하기.
Pointers summary.
2019 2학기 9장 배열과 포인터 1. 주소, 주소연산자(&) 2. 포인터, 역참조연산자(*) 3. 배열과 포인터.
Presentation transcript:

배열과 ADT(1/2) 연속된 메모리 위치의 집합 <index, value>쌍의 집합 자료구조와 그 기억장소 구현의 혼동 <index, value>쌍의 집합 set of mappings (or correspondence) between index and values array : I  ai

배열과 ADT(2/2) ADT Array object : index의 각 값에 대하여 집합 item에 속한 한 값이 존재하는 <index, value>쌍의 집합. index는 일차원 또는 다차원 유한 순서 집합이다. 예를 들면, 1차원의 경우 {0, …., n-1}과 2차원 배열{(0,0), (0,1), (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는 i번째 원소가 i번째 차원의 크기인 j-tuple이며 item들은 정의 되지 않았음. item Retrieve(A, i) ::= if (i∈index) return 배열 A의 인덱스 i값과 관련된 항목. else return 에러. Array Store(A, i, x) ::= if (i ∈ index) end Array < Array 추상 데이터 타입 >

C언어에서의 배열(1/4) 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 *list1; int list2[5]; list2 = list2[0]를 가리키는 포인터 list2 + I = list[i]를 가리키는 포인터 (list2+i) = &list2[i], *(list+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언어에서의 배열(2/4) 배열 프로그램의 예 #define MAX_SIZE 100 float sum(float []), int; 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 tempsum = 0; for(i = 0; i<n; i++) tempsum += list[i]; return tempsum;

C언어에서의 배열(3/4) 호출시 input(=&input[0])은 임시 장소에 복사 역참조(dereference) 형식 매개 변수 list와 연관 역참조(dereference) list[i]가 “=”기호 우측  (list + i)가 가리키는 값 반환 list[i]가 “=”기호 좌측  값을 (list + i) 위치에 저장 ※ C언어의 매개변수 전달방식 : call-by-value  배열 매개변수는 그 값을 변경함

C언어에서의 배열(4/4) 예제[일차원 배열의 주소 계산] int one[] = {0, 1, 2, 3, 4}; printf1(&one[0], 5) void print1 (int *ptr, int rows) {/* print out a 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)); printf(“\n”); } 주소 1228 1230 1232 1234 1236 내용 1 2 3 4 < 1차원 배열의 주소 계산 >

동적 할당 배열(1/4) 1차원 배열 ※ N<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/4) 2차원 배열 int x[3][5] < 2차원 배열의 동적 생성 > [0] [1] [2] [4] 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 (*x));; /* get memory for each row */ for (i = 0; i < rows; i++) MALLOC(x[i], cols * sizeof(**x)); return x; } < 2차원 배열의 동적 생성 >

동적 할당 배열(3/4) Ex> Calloc / Realloc 함수 510 2차원 정수 배열에 대한 메모리 할당 이 배열의 [2][4]원소에 정수 6을 지정 Calloc / Realloc 함수 calloc : 사용자가 지정한 양의 메모리를 할당하고 할당된 메모리를 0으로 초기화 Realloc : malloc이나 calloc으로 이미 할당된 메모리 크기 재조정 int *myArray; myArray = make2dArray(5, 10); myArray[2][2] = 6 int *x; x = calloc(n, sizeof(int))

동적 할당 배열(4/4) #define CALLOC(p, n, s)\ if(!((p) = calloc(n, s))) {\ fprintf(stderr, “Insufficient memory”):\ exit(EXIT_FAILURE):\ } #define REALLOC(p, s)\ if(!((p) = realloc(n, s))) {\ fprintf(stderr, “Insufficient memory”):\ exit(EXIT_FAILURE):\ }

구조와 유니언(1/5) 구조(structure) : struct 타입이 다른 데이터를 그룹화 (레코드) 데이터 항목의 집단 – 각 항목은 타입과 이름으로 식별 구조의 멤버 연산자 struct { char name[10]; int age; float salary; } person; strcpy(person.name, “james”); person.age = 10; person.salary = 35000;

구조와 유니언(2/5) typedef 문장을 사용한 구조 데이터 타입 생성 변수선언 전체 구조의 동등성 검사 : if (person1 == person2) 구조 치환 : person1 = person2 strcpy(person1.name, person2.name); person1.age = person2.age; person1.salary = person2.salary; typedef struct human_being{ char name[10]; int age; float salary; }; typedef struct { char name[10]; int age; float salary; } human_being; or human_being person1, person2 ; if (strcmp(person1.name, person2.name)) printf(“두사람의 이름은 다르다.\n”); else printf(“두사람의 이름은 같다.”)

구조와 유니언(3/5) 구조의 동등성 검사 #define FALSE 0 #define TRUE 1 int humansEqual (humanBeing person1, humanBeing person 2) {/* 만일 personal과 person2가 동일인이면 TRUE를 반환하고 그렇지 않으면 FALSE를 반환한다. */ if (strcmp(person1.name, person2.name)) return FALSE; if (person1.age != person2.age) if (person1.salary != person2.salary) return TRUE; } < 구조의 동등성을 검사하는 함수 >

구조와 유니언(4/5) 유니언 Union의 필드들은 메모리 공간을 공용 한 필드 만 어느 한 시점에 활동적이 되어 사용 가능 typedef struct sex_type { enum tagField {female, male} sex; union { int children; int beard; } u; }; typedef struct human_being { char name[10]; int age; float salary; sex_type sex_info; human_being person1, person2;

구조와 유니언(5/5) 값 할당 구조의 내부 구현 struct {int i, j; float a, b;} or struct {int i; int j; float a; float b;} 오름차 주소의 위치를 이용하여 저장 구조 내 빈 공간을 두거나 채워넣기(padding)를 할수 있다. 구조는 같은 메모리 경계에서 시작하고 끝나야 함 짝수바이트거나 4, 8, 16등의 배수가 되는 메모리 경계 person1.sex_info.sex = male; person1.sex_info.u.beard = FALSE; person2.sex_info.sex = female; person2.sex_info.u.children = 4;

자기 참조 구조 구성요소중 자신을 가리키는 포인터가 존재하는 구조 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)

추상 데이터 타입(1/5) 순서 리스트(Ordered list, linear list) 원소들의 순서가 있는 모임 A = (a1, a2, …, an) ai : atom, n=0 : empty list 한주일의 요일들(일, 월, 화, 수, 목, 금, 토) 카드 한 벌의 값(ace, 2, 3, 4, 5, 6, 7, 8, 9, 10, j, q, k) 건물의 층(지하실, 로비, 일층, 이층) 미국의 2차 세계 대전 참전 연도(1941, 1942, 1943, 1944, 1945) 연산 리스트의 길이의 n의 계산 리스트의 항목을 왼쪽에서 오른쪽 (오른쪽에서 왼쪽)으로 읽기 리스트로부터 i번째 항목을 검색, 0≤i≤n 리스트의 i번째 항목을 대체, 0≤i≤n 리스트의 i번째 위치에 새로운 항목을 삽입(i번째 위치,0≤i≤n) 리스트의 i번째 항목을 제거(i번째 항목, 0≤i<n)

추상 데이터 타입(2/5) 순서리스트의 표현 메모리(기억장소) 표현 순차 사항 (sequential mapping) 물리적 인접성(arrays) 비순차 사항(non-sequential mapping) 비연속적 기억장소 위치 리스트 : pointer(links)를 가지는 노드 집합

추상 데이터 타입(3/5) 기호 다항식의 조작 A(x) = 3x20+2x5+4, B(x) = x4+10x3+3x2+1 A(x) = ∑aixi와 B(x) = ∑bixi A(x) + B(x) = ∑(ai+bi)xi A(x) · B(x) = ∑(aixi ·(∑bjxj)) A(x) = anxn + an-1xn-1 + … + a1x1 + a0x0 axe a : coefficient an ≠ 0 e : exponent – unique x : variable x - 차수(degree) : 다항식에서 가장 큰 지수

추상 데이터 타입(4/5) Polynomial 추상 데이터 타입 Structure Polynomial Objects : P(x) = a1xe1 + … + anxen : <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

추상 데이터 타입(5/5) 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

다항식의 표현(1/4) 다항식의 표현(I) 지수들의 내림차순으로 정돈 a : polynomial, n < MAX_DEGREE A(x) = ∑aixi a.degree = n, a.coef[i] = an-i, 0≤i≤n #define MAX_DEGREE 101 /* 다항식의 최대 차수 +1*/ typedef struct int degree; float coef[MAX_DEGREE]; } polynomial; ※ A = (n, an, an-1, … , a1, a0) degree of A n+1 coefficients 예) A(x) = x4+10x3+3x2+1 : n = 4 A = (4, 1, 10, 3, 0, 1) : 6 elements

다항식의 표현(2/4) 다항식의 표현(II) 함수 padd의 초기 버전 a.degree << MAX_DEGREE  a.coef[MAX_DEGREE]의 대부분이 필요없음 함수 padd의 초기 버전 /* 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;

다항식의 표현(3/4) 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)); } break; case 1; d = Attach(d, Coef(a, Lead_Exp(a)), Lead_Exp(a)); a 또는 b의 나머지 항을 d에 삽입한다.

다항식의 표현(4/4) A(x) = 2x1000+1 B(x) = x4+10x3+3x2+1 2 1 10 3 1000 4 MAX_TERMS 100 /* 항 배열의 크기*/ typedef struct { float coef; int expon; } polynomial; Polynomial terms[MAX_TERMS]; int avail = 0; startA finishA startB finishB avail coef 2 1 10 3 1000 4 exp 1 2 3 4 5 6 A(x) : <starta, finisha> finisha = starta + n - 1

다항식의 덧셈(D=A+B)(1/2) 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, term[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++;

다항식의 덧셈(2/2) < 두 다항식을 더하는 함수 > < 새로운 항을 첨가하는 함수 > /* A(x)의 나머지 항들을 첨가한다. */ for(; starta <= finisha; starta++) attach(terms[starta].coef, term[starta].expon); /* B(x)의 나머지 항들을 첨가한다. */ for(; starta <= finishb; startb++) attach(terms[startb].coef, terms[startb].expon); *finishd = avail – 1; < 두 다항식을 더하는 함수 > void attach(float coefficient, int exponent) { /* 새 항을 다항식에 첨가한다. */ if (avail >= MAX_TERMS) { fprintf(stderr, “다항식에 항이 너무 많다.”); exit(1); } terms[avail].coef = coefficient; terms[avail++].expon = exponent; } < 새로운 항을 첨가하는 함수 >

알고리즘 padd의 분석 m, n(>0) ; 각각 A와 B의 0이 아닌 항의 수 while 루프 각 반복마다 starta나 startb 또는 둘 다 값이 증가 반복 종료→ starta <= finisha && startb <= finishb 반복 횟수 ≤ m+n-1 for 루프 : O(m+n) ∴ 연산시간 = O(n+m) ※ 문제점 avail = MAX_TERMS ?  불필요한 다항식 제거후 배열 끝에 연속적인 가용공간 생성(압축 함수) - 데이터 이동시간, 각 다항식의 starti, finishi 변경

희소 행렬(sparse matrix)(1/3) mn matrix A ≡ A[MAX_ROWS][MAX_COLS] 희소행렬 no. of total elements no. of non-zero elements << small col0 col1 col2 row0 -27 3 4 row1 6 82 -2 row2 109 -64 11 row3 12 8 9 row4 48 27 47 col0 col1 col2 col3 col4 col5 row0 15 22 -15 row1 11 3 row2 -6 row3 row4 91 row5 28

희소 행렬(2/3) 희소 행렬의 추상데이터 타입 ADT sparseMatrix object: 3원소 쌍 <행, 열, 값>의 집합이다. 여기서, 행과 열은 정수이고 이 조합은 유일하며, 값은 item집합의 원소이다. functions : 모든 a, b∈sparseMatrix, x∈item, i, j, maxCol, maxRow∈index에 sparseMatrix Create(maxRow, maxCol) ::= return maxItems까지 저장할 수 있는 sparseMatrix 여기서 최대 행의 수는 maxRow이고 최대 열의 수는 maxCol이라 할때 maItems = maxRowmaxCol이다. sparseMatrix Transpose(a) ::= return 모든 3원소 쌍의 행과 열의 값을 교환하여 얻은 행렬 sparseMatrix Add(a,b) ::= if a와 b의 차원이 같으면 return 대응 항들 즉, 똑같은 행과 열의 값을 가진 항들을 더해서 만들어진 행렬 else return 에러

희소 행렬(3/3) 희소 행렬의 표현 3원소쌍<행(row), 열(col), 쌍(value)>으로 표현 전치연산을 효율적으로 표현하기 위해 오름차순으로 조직 열 인덱스가 오름차순으로 정렬되도록 조직 연산 종료를 보장하기 위해 행과 열의 수와 행렬 내에 있는 0이 아닌 항의 수를 알아야 함 sparseMatrix Multiply(a,b) ::= if a의 열의 수와 b의 행의 수가 같으면 return 다음 공식에 따라 a와 b를 곱해서 생성된 행렬 d : d(i, j) = ∑(a[i][k] b[k][j]) 여기서 d(i, j)는 (i, j)번째 원소이다. else return 에러

행렬의 전치(Matrix Transpose)(1/3) 원소 <i, j, 값>을 가져와서 전치 행렬의 원소 <j, i, 값>으로 저장 ex) (0, 0, 15) 는 (0, 0, 15) (0, 3, 22) 는 (3, 0, 22) (0, 5, -15) 는 (5, 0, -15) 행 열 값 a[0] 6 8 a[1] 15 a[2] 3 22 a[3] 5 -15 a[4] 1 11 a[5] 2 a[6] -6 a[7] 4 91 a[8] 28 행 열 값 b[0] 6 8 b[1] 15 b[2] 4 91 b[3] 1 11 b[4] 2 3 b[5] 5 28 b[6] 22 b[7] -6 b[8] -15

행렬의 전치(2/3) 희소 행렬의 전치 for (j = 0; j < colums; j++) for(i = 0; i < rows; i++) b[j][i] = a[i][j]; void transpose(term a[], term b[]) /* a를 전치시켜 b를 생성 */ { int n, i, j, currentb; n = a[0].value; /* 총 원소 수 */ b[0].row = a[0].col; /* b의 행 수 = a의 열 수 */ b[0].col = a[0].row; /* b의 열 수 = a의 행 수 */ b[0].value = n; 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 { /* 현재의 열에 있는 원소를 b에 첨가한다. */ b[currentb].row = a[j].col; b[currentb].col = a[j].row; b[currentb].value = a[j].value; currentb++; } }

행렬의 전치(3/3) 희소 행렬의 빠른전치 void fasttranspose(term a[], term b[]) /* a를 전치시켜 b를 생성 */ { int rowTerms[MAX_COL], startingPose[MAX_COL]; int i, j, numCol = a[0].col, numTerms = a[0].value; b[0].row = numCols; b[0].col = a[0].row; b[0].value = numTerms; if (numTerms >0) { /* 0이 아닌 행렬 */ for(i=0; i<numCols; i++) rowTerms[i] = 0; for(i=1; i<=numTerms; i++) rowTerms[a[i].col]++; startingPos[0]=1; for(i=1; i<num_cols; i++) startingPos[i] = startingPos[i=1] + rowTerms[i-1]; for(i=1; i<=numTerms; i++) { j=startingPos[s[i].col]++; b[j].row = a[i].col; b[j].col = a[i].row; b[i].value = a[i].value; } }

행렬 곱셈(1/3) 정의 mn행렬 A와 np행렬 B가 주어질 때 곱셈 결과 행렬인 D는 mp차원을 가지며, 0≤i≤m, 0≤j≤p에 대해 원소<i, j>는 다음과 같다. 1 0 0 1 1 1 1 1 1 1 0 0 0 0 0 = 1 1 1 1 0 0 0 0 0 1 1 1 < 두 희소 행렬의 곱셈 >  두 희소행렬의 곱셈 결과는 희소행렬이 아니다

행렬 곱셈(2/3) 희소 행렬의 곱셈 void mmult (term a[], term b[], term d[]) { /* 두 희소 행렬을 곱한다. */ int i, j, column, total B = b[0].value, totalD = 0; int rowsA = a[0].row, colsA = a[0].col; totalA = a[0].value; int colsB = b[0].col; int rowBegin = 1, row = a[1].row, sum=0; int rowB[MAX_TERMS][3]; If (colsA != b[0].row) { fprintf(stderr, “Incompatible matrices\n”); exit(1); } fastTranspose(b, newB); /* 경계 조건 설정 */ a[totalA+1].row = rowA; newB[totalB+1].row = colsB; newB[totalB+1].col = 0; column = newB[1].row; for (j=1; j<= totalB+1) { /* a의 행과 b의 열을 곱한다. */ if (a[i].row != row) { storeSum(d, &totalD, row, column, &sum); i = rowBegin; for (; newB[j].row = = column; j++) ; column = newB[j].row;

행렬 곱셈(3/3) } else if (newB[j].row != column) { storeSum(d, &totalD, row, column, &sum); i = rowBegin; column = newB[j].row; else switch (COMPARE(a[i].col, newB[j].col)) { case -1: /*a의 다음항으로 이동 */ i++; break; case 0: /*항을 더하고, a와 b를 다음 항으로 이동 */ sum += (a[i++].value * newb[j++].value); break; case 1 : /* b의 다음 항으로 이동 */ j++; } /* for j <= totalB + 1문의 끝 */ for (; a[i].row = = row; i++) ; rowBegin = i; row = a[i].row; } /* for i <= totalA문의 끝 */ d[0].row = rowsA; d[0].col = colsB; d[0].value = totalD;

다차원 배열의 표현(1/3) 배열의 원소 수 : a[upper0][upper1]….[uppern-1] = 다차원 배열 표현 방법 행 우선 순서(row major order) A[upper0][upper1] 열 우선 순위(column major order) A[0][0] A[0][1] ··· A[0][upper1-1] ···· row0 row1 row2 rowupper0-1 A[0][0] A[1][0] ··· A[upper0-1][0] ···· col0 col1 col2 colupper1-1

다차원 배열의 표현(2/3) 주소 계산 (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 A[upper0][upper1]…[uppern-1] α = A[0][0]…[0]의 주소 a[i0][0]…[0] 주소 = α + i0upper1upper2…uppern-1 a[i0][i1][0]…[0] 주소 = α + i0upper1upper2…uppern-1 + i1upper2upper3…uppern-1

다차원 배열의 표현(3/3) a[i0][i1]…[in-1] 주소 = α + i0upper1upper2…uppern-1 · + in-2uppern-1 + in-1 = α + 여기서 : 0≤ j < n-1

스트링(1/4) 추상 데이터 타입 ADT String object : 0개 이상의 문자들의 유한 집합 function : 모든 s, t ∈ string, i, j, m ∈ 음이 아닌 정수 string Null(m) ::= 최대 길이가 m인 스트링을 반환 초기는 NULL로 설정되며, NULL은 “”로 표현된다. integer Compare(s, t) ::= if (s와 t가 같으면) return 0 else if (s가 t에 선행하면) return -1 else return +1 Boolean IsNull(s) ::= if (Compare(s, NULL)) return FALSE else return TRUE Integer Length(s) ::= if (Compare(s, NULL)) s의 문자를 반환 else return 0 string Concat(s, t) ::= if (Compare(s, NULL)) s뒤에 t를 붙인 스트링을 반환 else return s string Substr(s, i, j) ::= if ((j>0) && (i+j-1)<Length(s)) s에서 i, i+1, i+j-1의 위치에 있는 스트링을 반환 else return NULL

 스트링(2/4) C언어에서 스트링 널 문자 \0으로 끝나는 문자 배열을 의미 d o g \0 h o u s e \0 #define MAX_SIZE 100 /* 스트링의 최대 크기 */ char s[MAX_SIZE]={“dog”}; char t[MAX_SIZE]={“house”};  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 < C언어에서 스트링 표현 >

스트링(3/4) 스트링 삽입의 예 a m o b i l e \0 u t o \0 \0 a \0 a u t o \0 a u t s a m o b i l e \0 t u t o \0 temp \0 initially temp a \0 (a) after strncpy (temp, s, i) temp a u t o \0 (b) after strcat (temp, t) temp a u t o m b i l e \0 (c) after strcat (temp, (s+i))

스트링(4/4) 스트링 삽입 함수 void strnins (char *s, char *t, int i) { /* 스트링 s의 i번째 위치에 스트링 t를 삽입 */ char string[MAX_SIZE], *temp = string; if (i < 0 && i > strlen(s) ) { fprintf(strerr, “Position is out of bounds \n”); exit(1); } if (!strlen(s)) strcpy(s, t); else if (strlen(t)) { strncpy (temp, s, i); strcat (temp, t); strcat (temp, (s + i)); strcpy (s, temp);