자료구조 구현을 위한 C 프로그래밍 기법, 순차 자 료구조

다음 주 과제 5,6장 읽어오기 숙제 해서 제출하기

C 프로그래밍 기법 배열 포인터 구조체 재귀호출

자료구조를 C 프로그램으로 구현하기 위해 필요 한 프로그래밍 기법을 알아본다. 배열 자료형을 이해하고 배열의 구현 방법을 알아 본다. 포인터의 의미를 이해하고 구현 방법을 알아본다. 구조체 자료형을 이해하고 구조체의 구현 방법을 알아본다. 재귀호출의 의미를 이해하고 구현 방법을 알아본 다.

배열(array) 인덱스(index) 모든 자료형에 대해서 배열로 구성 가능 같은 자료형을 가진 자료들을 나열하여 메모리에 연속으로 저장하여 만든 자료들의 그룹 인덱스(index) 배열의 요소를 간단히 구별하기 위해 사용하는 번호 C에서 인덱스는 항상 0부터 시작 모든 자료형에 대해서 배열로 구성 가능 구성 형태에 따라 1차원 배열, 2차원 배열, 3차원 배열, …

1차원 배열 1차원 배열 선언 형식 ❶ 자료형 ❷ 배열이름 ❸ 배열요소의 개수 배열을 선언하면 메모리에 배열에 대한 공간 할당 배열의 자료형을 선언. 배열 요소들은 모두 같은 자료형이어야 하고, 그 자료형이 배열의 자료형이 된다. ❷ 배열이름 일반 변수와 같은 규칙으로 정한다. 배열이름 뒤에 대괄호([, ])를 사용하여 ❸ 배열요소의 개수 배열요소의 개수는 배열의 크기 배열을 선언하면 메모리에 배열에 대한 공간 할당 할당 크기 : (자료형에 대한 메모리 할당 크기✕배열요소의 개수)

[표 3-1] 여러 자료형의 배열 선언에 대한 형태와 의미 배열 선언에 따른 메모리 할당 크기 [표 3-1] 여러 자료형의 배열 선언에 대한 형태와 의미

자료형의 크기 확인 프로그램 01 #include <stdio.h> 02 /* 자료형의 크기 확인하기 */ 02 /* 자료형의 크기 확인하기 */ 03 void main( ) 04 { 05 char c, c_array[100]; 06 int i, i_array[100]; 07 short s, s_array[100]; 08 float f, f_array[100]; 09 long l, l_array[100]; 10 11 printf("\n char c의 size = %d \t: char c_array의 size = %4d", 12 sizeof(c), sizeof(c_array)); 13 printf("\n int i의 size = %d \t: int i_array의 size = %4d", 14 sizeof(i), sizeof(i_array)); 15 printf("\n short s의 size = %d \t: short s_array의 size = %4d", 16 sizeof(s), sizeof(s_array));

자료형의 크기 확인 프로그램 실행 결과 17 printf("\n float f의 size = %d \t: float f_array의 size = %4d", 18 sizeof(f), sizeof(f_array)); 19 printf("\n long l의 size = %d \t: long l_array의 size = %4d", 20 sizeof(l), sizeof(l_array)); 21 22 getchar( ); 23 }

1차원 배열의 초기화 배열의 선언과 함께 초기 값을 설정하는 작업 1차원 배열의 초기화 형식 초기화 형식과 의미

초기화 형식과 의미

학년별 취득 학점 입출력하는 프로그램 01 #include <stdio.h> 02 /* 1차원 배열의 초기화 */ 02 /* 1차원 배열의 초기화 */ 03 void main( ) 04 { 05 int i; 06 int score[3]={91, 86, 97}; 07 char grade[3]={'A','B','A'}; 08 09 printf("\n *** 학년별 취득 학점 *** \n\n"); 10 11 for(i=0; i<3; i++){ 12 printf("%3d 학년 : 총점= %d , 등급= %c\n", 13 i+1, score[i], grade[i]); 14 } 15 16 getchar( ); 17 }

입력한 숫자의 구구단을 출력하는 프로그램 실행 화면 01 #include <stdio.h> 02 03 void main( ) 04 { 05 int i, n, multiply[9]; 06 printf("\n1~9의 정수를 입력하세요! : "); 07 scanf("%d", &n); 08 09 if(n<1) 10 printf("\n 1~9의 정수를 입력하세요!!\n"); 11 else if(n>9) 12 printf("\n 1~9의 정수를 입력하세요!!\n"); 13 else{ 14 printf("\n"); 15 for(i=0; i<9; i++){ 16 multiply[i]=n*(i+1); 17 printf(" %d * %d = %d \n", n, (i+1), multiply[i]); 18 } 19 } 20 getchar( ); 21 }

문자 배열 문자배열의 초기화 문자의 나열. “, ”사이에 표시 문자열을 저장하기 위해서는 문자열을 구성하는 문자들을 연속적으로 저장해야 하기 때문에 배열 사용 배열의 자료 형은 문자 자료 형(char) 문자배열의 초기화 문자열을 그대로 지정하거나 초기값 문자리스트를 사용

문자배열을 문자열“String”으로 초기화하는 예 S1 : 문자열을 사용한 초기화char s1[10] = “String” ; S2 : 초기값 문자리스트를 사용한 초기화 char s2[10] = { ‘S’, ‘t’, ‘r’, ‘i’, ‘n’, ‘g’} ; [그림 3-2] s1의 초기화에 대한 메모리 구조 [그림 3-3] s2의 초기화에 대한 메모리 구조

문자 배열에 문자 입력하는 프로그램 실행 화면 01 #include <stdio.h> 02 /* 문자 배열 예제 */ 03 void main() 04 { 05 char str[20]="Data Structure!" ; 06 int i; 07 printf("\n문자 배열 str[] : "); 08 for(i=0; str[i]; i++){ 09 printf("%c", str[i]); 10 } 11 getchar(); 12 }

입력한 문자열의 길이 계산하는 프로그램 실행 화면 01 #include <stdio.h> 02 /* 문자 배열 예제-2 */ 03 void main() 04 { 05 int i, length=0; 06 char str[50]; 07 printf("\n 문자열을 입력하세요 : "); 08 gets(str); 09 printf("\n 입력된 문자열은 \n \""); 10 for(i=0; str[i]; i++){ 11 printf("%c", str[i]); 12 length+=1; 13 } 14 printf("\" \n입니다."); 15 printf("\n\n입력된 문자열의 길이 = %d \n",length); 16 17 getchar(); 18 }

[그림 3-4] i[2][3]의 논리적 구조 [그림 3-5] i[2][3]의 물리적 구조 2차원 배열 선언에 대한 논리적 구조와 물리적 구조 int i[2][3]; [그림 3-4] i[2][3]의 논리적 구조 [그림 3-5] i[2][3]의 물리적 구조

3차원 배열의 선언 형식 ❶ 배열 크기 : 면의 개수. 면 인덱스 크기 ❷ 배열 크기 : 행의 개수. 행 인덱스 크기 ❸ 배열 크기 : 열의 개수. 열 인덱스 크기

다차원 배열 다차원 배열의 선언 2차원 이상의 배열 배열의 차수 만큼 [배열크기] 항목을 추가 2차원 배열의 선언 형식 ❶ 배열 크기 : 행의 개수. 행 인덱스 크기 ❷ 배열 크기 : 열의 개수. 열 인덱스 크기

3차원 배열 선언에 대한 논리적 구조와 물리적 구조 int i[2][3][4]; [그림 3-6] i[2][3][4]의 논리적 구조 [그림 3-7] i[2][3][4]의 물리적 구조

다차원 배열의 초기화 int i[2][3] = {1,2,3,4,5,6} ; 2차원 배열의 초기화 초기값의 지정형태는 다차원 배열이 배열의 배열이라는 것을 생각하여 초기값을 구분하여 지정하거나, 1차원 배열처럼 초기값 리스트를 지정하여 순서대로 배열요소의 초기값으로 설정 2차원 배열의 초기화 예 int i[2][3] = {{1,2,3}, {4,5,6}} ; int i[2][3] = {1,2,3,4,5,6} ; int i[][3] = {{1,2,3}, {4,5,6}} ; [그림 3-8] 2차원 배열 i[2][3]의 논리적 구조

3차원 배열의 초기화 [그림 3-9] 3차원 배열 i[2][3][4]의 논리적 구조 int i[2][3][4] = { {1, 2, 3, 4}, {5, 6, 7, 8}, {9,10,11,12}, {13,14,15,16}, {17,18,19,20}, {21,22,23,24} }; [그림 3-9] 3차원 배열 i[2][3][4]의 논리적 구조

3차원 배열의 입출력 프로그램 실행 화면 01 #include <stdio.h> 02 /* 3차원 배열 예제 */ 3차원 배열의 입출력 프로그램 실행 화면 01 #include <stdio.h> 02 /* 3차원 배열 예제 */ 03 void main( ) 04 { 05 int array[2][3][4]; 06 int i, j, k, value=1; 07 for(i=0; i<2; i++){ 08 for(j=0; j<3; j++){ 09 for(k=0; k<4; k++){ 10 array[i][j][k]=value; 11 printf("\n array[%d][%d][%d] = %d", 12 i, j, k, array[i][j][k]); 13 value++; 14 } 15 } 16 } 17 getchar( ); 18 }

문자 다차원 배열 [그림 3-10] char c[3][20]의 논리적 구조 char c[3][20]= { "Hong Gil Dong",                   "Computer Department",                   "Seoul, Korea"  }; [그림 3-10] char c[3][20]의 논리적 구조

3차원 문자 배열의 입출력 프로그램 01 #include <stdio.h> 02 /* 3차원 문자 배열 예제 */ 03 void main() 04 { 05 int i, j, k; 06 char student[2][3][20]; 07 for(i=0; i<2; i++){ 08 printf("\n 학생 %d의 이름 : ", i+1); 09 gets(student[i][0]); 10 printf(" 학생 %d의 학과 : ", i+1); 11 gets(student[i][1]); 12 printf(" 학생 %d의 학번 : ", i+1); 13 gets(student[i][2]); 14 } 15 for(i=0; i<2; i++){ 16 printf("\n\n 학생%d", i+1); 17 for(j=0; j<3; j++){ 18 printf("\n\t"); 19 for(k=0; student[i][j][k]!='\0'; k++){ 20 printf("%c", student[i][j][k]); 21 } 22 } 23 } 24 getchar(); 25 }

실행 결과

포인터 포인터변수 변수의 메모리 주소 값 주소 값을 저장하는 특별한 변수 포인터 변수가 어떤 변수의 주소를 저장하고 있다는 것은 포인터 변수가 그 변수를 가리키고 있다(포인트하고 있다)는 의미 포인터변수를 간단히 포인터라고도 한다.

포인터 변수의 의미 [그림 3-11] 포인터 변수의 의미 편지봉투에 받는 사람의 집주소를 쓰면, 그 주소로 편지가 전달되어 집주인이 편지를 받게 된다. 편지봉투 ☞ 포인터변수편지봉투에 쓰는 받는 사람 주소 ☞ 포인터변수에 저장된 변수의 메모리 주소 주소에 해당하는 집주인이 편지를 받는 것 ☞ 포인터변수를 통한 변수의 액세스 [그림 3-11] 포인터 변수의 의미

포인터 사용 예 int *ptr = &i; …❷ [그림 3-12] 포인터 변수를 사용하여 일반 변수를 액세스하는 방법 int i; …………❶ int *ptr = &i; …❷ ❶에서 int형 변수i를 선언했을 때에 저장된 메모리 번지를 150번지라고 한다면, ❷에서 변수i의 주소를 포인터변수 ptr에 저장하면 ptr에는 메모리 주소 150이 저장되고 포인터변수 ptr은 변수i를 가리키게 된다. [그림 3-12] 포인터 변수를 사용하여 일반 변수를 액세스하는 방법

포인터 선언 포인터 선언 형식 ❶자료형 ❷포인터변수이름 포인터변수 자체의 자료 형이 아니라 포인터변수에 저장할 주소에 있는 일반변수의 자료 형 ❷포인터변수이름 일반변수이름과 구별하여 변수이름 앞에 ‘*’를 표시하여 포인터변수임을 나타낸다.

포인터 변수의 자료 형에 따른 메모리 액세스 범위 char *ptr; ……❶ short *ptr;……❷ int *ptr;  ……❸ [그림 3-13] 포인터 변수의 자료 형에 따른 메모리 액세스 범위

포인터 연산 주소 연산자 : & [그림 3-14] 변수 선언에 따른 메모리 할당 변수의 주소를 구하기 위해 사용 변수 앞에 &를 사용하여 그 변수의 주소를 사용 주소를 사용할 변수와 포인터변수는 같은 자료 형으로 선언 주소 연산자 사용 예 int i=10; int *ptr; ptr = &i; [그림 3-14] 변수 선언에 따른 메모리 할당 [그림 3-15] ptr = &i;의 실행 결과

참조 연산자 : * 저장된 주소에 있는 값(변수에 저장된 값)을 액세스하는 연산자 사용 방법1: 사용 방법2: 지정한 값을 포인터가 가리키고 있는 주소에 저장 사용 방법2: 포인터가 가리키는 주소에 있는 값을 변수에 저장

int *ptr; ptr = &i; ………❶ *ptr = 10; ………❷ j = *ptr; ………❸ 참조 연산자 사용 예 int i, j; int *ptr; ptr = &i;    ………❶ *ptr = 10;   ………❷ j = *ptr;    ………❸ [그림 3-16] ptr = &i;의 실행 [그림 3-17] *ptr = 10;의 실행 [그림 3-18] j = *ptr;의 실행

[그림 3-19] ptr=&i;의 실행 [그림 3-20] ptr=&j;의 실행 [그림 3-21] i=*ptr;의 실행

포인터 연산자로 변수에 액세스하는 프로그램 01 #include <stdio.h> 02 /* 포인터 연산자 예제 */ 03 void main() 04 { 05 int i=10, j=20; 06 int *ptr; 07 printf("\n i의 값 = %d \n j의 값 = %d", i, j); 08 printf("\n i의 메모리 주소(&i) = %u", &i); 09 printf("\n j의 메모리 주소(&j) = %u", &j); 10 11 ptr=&i; // ❶ 12 printf("\n\n << ptr=&i 실행 >>"); 13 printf("\n ptr의 메모리 주소(&ptr) = %u", &ptr); 14 printf("\n ptr의 값(ptr) = %u", ptr); 15 printf("\n ptr의 참조 값(*ptr) = %d", *ptr); 16

포인터 연산자로 변수에 액세스하는 프로그램 17 ptr=&j; // ❷ 18 printf("\n\n << ptr=&j 실행 >>"); 19 printf("\n ptr의 메모리 주소(&ptr) = %u", &ptr); 20 printf("\n ptr의 값(ptr) = %u", ptr); 21 printf("\n ptr의 참조 값(*ptr) = %d", *ptr); 22 23 i=*ptr; // ❸ 24 printf("\n\n << i=*ptr 실행 >>"); 25 printf("\n i의 값 = %d", i); 26 27 getchar(); 28 }

실행 결과

포인터 초기화 포인터의 초기값은 메모리 주소 포인터 초기화 방법 1 주소연산자를 사용하여 변수의 주소 지정 예) int i; int *ptr = &i;

포인터 초기화 방법 2 포인터 초기화 방법 3 포인터 초기화 방법 4 동적 메모리를 할당하고 그 시작주소를 포인터 값으로 지정 예) char *ptr = (char *)malloc(100); 포인터 초기화 방법 3 문자형 포인터에 문자열의 시작주소를 지정 예) char *ptr = "korea"; 포인터 초기화 방법 4 배열의 이름을 이용하여 배열시작주소를 지정 배열 이름은 문자열과 마찬가지로 그 시작주소를 전달할 수가 있다. 예) char A[100]; char *ptr = A;

포 인터 초기화 방법 5 배열요소의 주소를 사용하여 지정 예) char A[100]; char *ptr = &A[0]; 이런 경우에 인덱스로 표시하는 배열의 각 요소는 그 이름만으로 주소를 전달할 수 없기 때문에 주소연산자 &를 사용 예) char A[100]; char *ptr = &A[0];

포인터와 문자 배열 포 인터 초기화 방법 5 [그림 3-22] ptr1 = string1;의 실행 배열요소의 주소를 사용하여 지정 이런 경우에 인덱스로 표시하는 배열의 각 요소는 그 이름만으로 주소를 전달할 수 없기 때문에 주소연산자 &를 사용 예) char A[100]; char *ptr = &A[0]; 포인터와 문자 배열 포인터를 사용하여 문자열 연산 처리 예제 3-9 : 포인터를 이용한 문자열 처리 프로그램 ptr1 = string1; [그림 3-22] ptr1 = string1;의 실행

[그림 3-23] ptr1+7과 &string1[7]의 관계

for(i=16; i>=0; i--){ putchar(*(ptr1+i)); }     } for 반복문을 사용하여 문자열을 거꾸로 출력 [그림 3-25] for 반복 문을 사용하여 문자열을 거꾸로 출력

[그림 3-27] 포인터를 사용하여 string1의 문자열 변경 포인터를 사용한 문자열 복사 포인터를 사용하여 string1의 문자열 변경 [그림 3-26] 포인터를 사용한 문자열 복사 [그림 3-27] 포인터를 사용하여 string1의 문자열 변경

포인터로 문자열을 처리하는 프로그램 01 #include <stdio.h> 02 03 void main( ) 04 { 05 int i; 06 char string1[20]="Dreams come true!", string2[20], *ptr1, *ptr2; 07 08 ptr1 = string1; // ❶ 09 printf("\n string1의주소 = %u \t ptr1 = %u", string1, ptr1); // ❷ 10 printf("\n string1 = %s \n ptr1 = %s", string1, ptr1); 11 printf("\n\n %s",ptr1+7); // ❸ 12 ptr2 = &string1[7]; // ❹ 13 printf("\n %s \n\n ", ptr2); // ❺ 14 15 for(i=16; i>=0; i--){ // ❻ 16 putchar(*(ptr1+i)); 17 }

포인터로 문자열을 처리하는 프로그램 18 for(i=0; i<20; i++){ // ❼ 19 string2[i] = *(ptr1+i); 20 } 21 printf("\n\n string1 = %s", string1); 22 printf("\n string2 = %s", string2); 23 24 *ptr1 = 'P'; 25 *(ptr1+1) = 'e'; 26 *(ptr1+2) = 'a'; // ❽ 27 *(ptr1+3) = 'c'; 28 *(ptr1+4) = 'e'; 29 printf("\n\n string1 = %s\n", string1); 30 31 getchar( ); 32 }

실행 화면

포인터 배열 포인터 자료 형을 배열로 구성 포인터 배열의 선언형식 여러 개의 포인터를 하나의 배열로 구성한 배열의 특징과 포인터의 특징을 모두 활용할 수 있다. 포인터 배열의 선언형식 포인터 배열에서 각 배열요소는 포인터 2차원 문자배열을 1차원 포인터배열로 표현 2차원 배열의 행의 개수는 포인터배열의 크기 포인터배열의 각 배열요소는 각 문자열에 대한 시작주소를 가진 포인터

2차원 배열과 1차원 포인터배열 [그림 3-28] 2차원 문자 배열string[3][10]의 구조 char string[3][10] = {"Dreams", "come", "true!"}; char *ptr[3] = {{"Dreams"}, {"come"}, {"true!"}}; [그림 3-28] 2차원 문자 배열string[3][10]의 구조 [그림 3-29] 1차원 포인터 배열 *ptr[3]의 구조

포인터 배열로 문자열을 저장하는 프로그램 01 #include <stdio.h> 02 03 void main( ) 포인터 배열로 문자열을 저장하는 프로그램 01 #include <stdio.h> 02 03 void main( ) 04 { 05 int i; 06 char *ptrArray[4] = {{"Korea"},{"Seoul"},{"Mapo"}, {"152번지 2/3"}}; 07 for(i=0; i<4; i++) 08 printf("\n %s", ptrArray[i]); 09 10 ptrArray[2] = "Jongno"; 11 printf("\n\n"); 12 for(i=0; i<4; i++) 13 printf("\n %s", ptrArray[i]); 14 15 getchar( ); 16 }

실행 화면

포인터의 포인터 포인터의 포인터 선언 형식 [그림 3-30] char **ptr;의 논리적 구조 포인터를 가리키고 있는 포인터. 이중 포인터 포인터의 포인터 선언 형식 예) char **ptr; [그림 3-30] char **ptr;의 논리적 구조

ptrptr = ptrArray; ptrArray[0] 예제 3-11 : 포인터 배열과 포인터의 포인터 예제 프로그램 ptrptr = ptrArray; [그림 3-31] ptrptr = ptrArray; 실행 후의 구조 ptrArray[0] [그림 3-32] 1차원 포인터 배열 요소 ptrArray[0]

char *ptrArray[2]; char **ptrptr; ptrptr = ptrArray; 예제 3-11 : 포인터 배열과 포인터의 포인터 예제 프로그램 char *ptrArray[2]; char **ptrptr; [그림 3-33] 1차원 포인터 배열 요소 ptrArray[1] ptrptr = ptrArray; [그림 3-34] 포인터의 포인터 변수 ptrptr의 구조

[그림 3-35] 포인터 배열 변수를 사용한 문자열“Korea”액 포인터배열변수 ptrArray를 사용하여 문자열 “Korea” 액세스하기 [그림 3-35] 포인터 배열 변수를 사용한 문자열“Korea”액

[그림 3-36] 포인터의 포인터 변수를 사용한 자열“Korea”액세스 포인터의 포인터 변수 ptrptr을 사용하여 문자열 “Korea” 액세스하기 [그림 3-36] 포인터의 포인터 변수를 사용한 자열“Korea”액세스

[그림 3-37] 포인터 배열 변수를 사용한 문자열“Seoul”액세스 포인터배열변수 ptrArray를 사용하여 문자열 “Seoul” 액세스하기 [그림 3-37] 포인터 배열 변수를 사용한 문자열“Seoul”액세스

[그림 3-38] 포인터의 포인터 변수를 사용한 문자열“Seoul”액세스 포인터의 포인터 변수 ptrptr을 사용하여 문자열 “Seoul” 액세스하기 [그림 3-38] 포인터의 포인터 변수를 사용한 문자열“Seoul”액세스

[그림 3-39] [그림 3-38]에서 *(ptrptr+1)을 x로 치환

포인터 배열과 포인터의 포인터를 사용하는 프로그램 01 #include <stdio.h> 02 void main( ) 03 { 04 char *ptrArray[2]; 05 char **ptrptr; 06 int i; 07 08 ptrArray[0] = "Korea"; 09 ptrArray[1] = "Seoul"; 10 ptrptr = ptrArray; // ❶ 11 printf(\n ptrArray[0]의 주소 (&ptrArray[0]) = %u", &ptrArray[0]); 12 printf("\n ptrArray[0]의 값 ( ptrArray[0]) = %u", ptrArray[0]); // ❷ 13 printf("\n ptrArray[0]의 참조값 (*ptrArray[0]) = %c", *ptrArray[0]); 14 printf("\n ptrArray[0]의 참조문자열 (*ptrArray[0]) = %s \n", *ptrArray); 15 16 printf("\n ptrArray[1]의 주소 (&ptrArray[1]) = %u", &ptrArray[1]); 17 printf("\n ptrArray[1]의 값 ( ptrArray[1]) = %u", ptrArray[1]);

포인터 배열과 포인터의 포인터를 사용하는 프로그램 18 printf("\n ptrArray[1]의 참조값 (*ptrArray[1]) = %c", *ptrArray[1]); 19 printf("\n ptrArray[1]의 참조문자열(*ptrArray[1])= %s \n", *(ptrArray+1)); 20 21 printf("\n ptrptr의 주소 ( &ptrptr) = %u", &ptrptr); 22 printf("\n ptrptr의 값 ( ptrptr) = %u", ptrptr); 23 printf("\n ptrptr의 1차 참조값 ( *ptrptr) = %u", *ptrptr); // ❹ 24 printf("\n ptrptr의 2차 참조값 (**ptrptr) = %c", **ptrptr); 25 printf(“\n ptrptr의 2차 참조문자열 (**ptrptr) = %s",*ptrptr); 26 27 printf("\n\n *ptrArray[0] : "); 28 for(i=0; i<5; i++) 29 printf("%c", *(ptrArray[0]+i)); 30 printf("\n **ptrptr : "); // ❺ 31 for(i=0; i<5; i++) 32 printf("%c", *(*ptrptr+i)); 33

포인터 배열과 포인터의 포인터를 사용하는 프로그램 34 printf("\n\n *ptrArray[1] : "); 35 for(i=0; i<5; i++) 36 printf("%c", *(ptrArray[1]+i)); 37 printf("\n **(ptrptr+1) : "); 38 for(i=0; i<5; i++) 39 printf("%c", *(*(ptrptr+1)+i)); 40 41 getchar(); 42 }

실행 화면

구조체 레코드(record) 필드(field) 파일(file) 배열처럼 여러 개의 데이터를 그룹으로 묶어서 하나의 자료 형으로 정의하고 사용하는 자료형 배열은 같은 자료형 만을 그룹으로 묶을 수 있지만, 구조체는 서로 다른 자료 형을 그룹으로 묶을 수 있으므로 복잡한 자료 형태를 정의하는데 유용하게 사용 레코드(record) 자료를 체계적으로 관리하기 위해서 구성한 일정한 단위 형식으로 필드(field) 레코드를 구성하는 하위 항목 파일(file) 여러 레코드가 모여서 하나의 파일을 구성 여러 자료 형의 필드를 가지고 있는 레코드를 만들 때 구조체 사용

필드와 레코드, 파일의 관계 [그림 3-40] 필드와 레코드, 파일

구조체 선언 구조체이름, 자료 형, 데이터 항목으로 구성 여러 자료 형의 변수들을 그룹으로 묶어서 하나의 자료 형으로 선언 구조체의 이름 - 구조체로 정의하는 새로운 자료 형의 이름 항목 - 구조체를 구성하는 내부 변수들의 이름 구조체의 항목은 배열의 각 배열요소에 해당 배열요소는 모두 같은 자료 형으로 되어있으므로 배열요소에 대한 선언 없이 사용 가능 구조체에서는 각 항목이 다른 자료 형을 가질 수 있기 때문에 항목별로 자료 형과 항목이름(변수이름)을  선언해야 한다. 구조체 선언은 사용할 구조체의 모양을 정의한 것뿐이므로 사용할 구조체 변수를 다시 선언해야 한다. 선언된 구조체 변수는 일반변수와 똑같이 취급하고 사용

구조체 사용 예) 직원 관리 구조체 구조체 선언 구조체 employee의 구조 [그림 3-41] 구조체 employee의 구조

struct employee Lee, Kim, Park; 구조체 변수 선언 구조체 변수의 선언 유형 struct  employee  Lee, Kim, Park; [그림 3-42] 구조체 employee에 대한 구조체 변수의 구조 [표 3-2] 구조체 변수의 선언 방법

구조체의 초기화 [그림 3-43] 구조체 Lee의 초기화된 구조 구조체 변수 선언 시에 각 데이터 항목에 대한 값을 중괄호 안에 나열 [그림 3-43] 구조체 Lee의 초기화된 구조

데이터 항목의 참조 구조체 변수에 있는 각 데이터 항목을 참조하기 위해서 구조체 연산자 사용 [표 3-3] 구조체 연산자

점 연산자 : . [그림 3-44] 점 연산자를 이용한 데이터 항목 값 지정 구조체 변수에 있는 데이터 항목을 개별적으로 지정할 때 사용 예) [그림 3-44] 점 연산자를 이용한 데이터 항목 값 지정

점 연산자로 데이터 항목 조회하는 프로그램 01 #include <stdio.h> 19 02 #include <string.h> 03 04 struct employee{ 05 char name[10]; 06 int year; 07 int pay; 08 }; 09 10 void main( ) 11 { 12 int i; 13 struct employee Lee[4]={ 14 {"이민수", 2002, 3200}, 15 {"이상건", 2002, 3000}, 16 {"이진호", 2004, 2500}, 17 {"이한영", 2003, 2900} 18 }; 19 20 for(i=0; i<4; i++) { 21 printf("\n 이름 : %s", Lee[i].name); 22 printf("\n 입사 : %d", Lee[i].year); 23 printf("\n 연봉 : %d \n", Lee[i].pay); 24 } 25 getchar(); 26 }

실행 화면

화살표 연산자 : -> [그림 3-45] 구조체 포인터 변수의 데이터 항목값 지정 구조체 포인터 변수에서 포인터가 가리키는 구조체 변수의 데이터항목을 지정하기 위해서 화살표 연산자 사용 예) [그림 3-45] 구조체 포인터 변수의 데이터 항목값 지정

화살표 연산자로 데이터 항목을 참조하는 프로그램 01 #include <stdio.h> 02 #include <string.h> 03 04 struct employee{ 05 char name[10]; 06 int year; 07 int pay; 08 }; 09 10 void main() 11 { 12 struct employee Lee; 13 struct employee *Sptr = &Lee; 14 strcpy(Sptr->name, "이순신"); 15 Sptr->year = 2005; 16 Sptr->pay = 2900; 17 18 printf("\n 이름 : %s", Sptr->name); 19 printf("\n 입사 : %d", Sptr->year); 20 printf("\n 연봉 : %d", Sptr->pay); 21 22 getchar(); 23 }

실행 화면

재귀 호출로 factorial 값 구하는 프로그램 01 #include <stdio.h> 02 #include <string.h> 03 04 struct employee{ 05 char name[10]; 06 int year; 07 int pay; 08 }; 09 10 void main( ) 11 { 12 struct employee Lee; 13 struct employee *Sptr = &Lee; 14 strcpy(Sptr->name, "이순신"); 15 Sptr->year = 2005; 16 Sptr->pay = 2900; 17 18 printf("\n 이름 : %s", Sptr->name); 19 printf("\n 입사 : %d", Sptr->year); 20 printf("\n 연봉 : %d", Sptr->pay); 21 22 getchar( ); 23 }

실행 결과

구조체의 연산 데이터 항목 참조 연산 구조체 복사 연산 점 연산자와 화살표연산자를 이용하여 구조체의 데이터 항목을 개별적으로 참조 예) struct  employee  Lee; struct  employee  *Sptr; Sptr = &Lee; Lee.year = 2005; Sptr -> pay = 3000; Sptr -> name = “Ann”; 구조체 복사 연산 예) struct  employee  Lee, Kim, team[5]; Lee = Kim; Lee = team[2]; team[2] = team[3];

구조체 변수의 주소 구하기 연산 포인터의 주소연산자를 사용하여 구조체 변수의 주소를 구하거나, 구조체 변수가 배열인 경우에는 배열의 특성에 따라 구조체 배열 변수의 이름에서 주소를 구할 수 있다. 예) struct  employee  Lee, team[5]; struct  employee  *Sptr1, *Sptr2; Sptr1 = &Lee; Sptr2 = team;

재귀호출(순환호출) 재귀 호출의 예 - factorial 자기 자신을 호출하여 순환 수행되는 것 함수에서 실행해야 하는 작업의 특성에 따라 일반적인 호출방식보다 재귀호출방식을 사용하여 함수를 만들면 프로그램의 크기를 줄이고 간단하게 작성 재귀 호출의 예 -  factorial n에 대한 factorial : 1부터 n까지의 모든 자연수를 곱하여 구하는 연산 n! = n x (n-1)! (n-1)! = (n-1) x (n-2)! (n-2)! = (n-2) x (n-3)! … 2! = 2 x 1! 1! = 1 마지막에 구한 하위 값을 이용하여 상위 값을 구하는 작업을 반복

factorial 함수에서 n=4 인 경우의 실행

순차 자료구조 선형 리스트 선형 리스트의 구현 다항식의 순차 자료구조 표현 행렬의 순차 자료구조 표현

순차 자료구조의 의미와 특징을 알아본다. 선형 리스트의 구조와 연산을 알아본다. 선형 리스트의 C 프로그램 구현을 알아본다. 선형 리스트의 응용 방법을 알아본다.

리스트(List) 선형 리스트(Linear List) 자료를 나열한 목록 순서 리스트(Ordered List), 자료들 간에 순서를 갖는 리스트 [표 4-1] 리스트의 예 [표 4-2] 선형 리스트의 예

리스트의 표현 형식 리스트이름 = (원소1, 원소2, …, 원소n) 선형 리스트에서 원소를 나열한 순서는 원소들의 순서가 된다. [표4-2]의 동창이름 선형 리스트의 표현 동창 = (홍길동, 이순신, 윤봉길, 안중근) 공백 리스트 원소가 하나도 없는 리스트 빈괄호를 사용하여 표현 공백리스트이름 = ( )      리스트이름 = (원소1, 원소2, …, 원소n)

선형 리스트의 저장 원소들의 논리적 순서와 같은 순서로 메모리에 저장 순차 자료구조 원소들의 논리적 순서 = 원소들이 저장된 물리적 순서 [표 4-2]의 동창 선형 리스트가 메모리에 저장된 물리적 구조 [그림 4-1] 동창 선형 리스트의 메모리 저장 순서

순차 자료구조의 원소 위치 계산 프로토콜은 계층적 구조로 정의 선형 리스트가 저장된 시작 위치 : α 원소의 길이 : ℓ 원소의 길이 : ℓ i번째 원소의 위치 = α + (i-1)ⅹℓ 프로토콜의 개념과 필요성 프로토콜은 계층적 구조로 정의 [그림 4-2] 순차 자료구조에서 원소의 위치 확인

선형 리스트에서의 원소 삽입 선형리스트 중간에 원소가 삽입되면, 그 이후의 원소들은 한자리씩 자리를 뒤로 이동하여 물리적 순서를 논리적 순서와 일치시킨다. [그림 4-3] 새치기 전과 후의 위치와 순서 변화

원소 삽입 방법 원소를 삽입할 빈 자리 만들기 준비한 빈 자리에 원소 삽입하기 삽입할 자리 이후의 원소들을 한자리씩 뒤로 자리 이동 시키기 준비한 빈 자리에 원소 삽입하기 [그림 4-4] 선형 리스트에서의 원소 삽입

선형 리스트에서의 원소 삭제 삽입할 자리를 만들기 위한 자리이동 횟수 (n+1)개의 원소로 이루어진 선형 리스트에서 k번 자리에 원소를 삽입하는 경우 : k번 원소부터 마지막 n번 원소까지 (n-k+1)개의 원소를 이동 이동횟수 = n-k+1 = 마지막 원소의 인덱스 - 삽입할 자리의 인덱스 +1 선형 리스트에서의 원소 삭제 선형리스트 중간에서 원소가 삭제되면, 그 이후의 원소들은 한자리씩 자리를 앞으로 이동하여 물리적 순서를 논리적 순서와 일치시킨다. [그림 4-5] 줄에서 사람이 나간 후의 위치와 순서 변화

원소 삭제 방법 삭제 후, 빈 자리를 채우기 위한 자리이동 횟수 원소 삭제하기 삭제한 빈 자리 채우기 삭제한 자리 이후의 원소들을 한자리씩 앞으로 자리 이동 시키기 삭제 후, 빈 자리를 채우기 위한 자리이동 횟수 (n+1)개의 원소로 이루어진 선형 리스트에서 k번 자리의 원소를 삭제한 경우 : (k+1)번 원소부터 마지막 n번 원소까지 (n-(k+1)+1)개의 원소를 이동 이동횟수 = n-(k+1)+1 = n-k = 마지막 원소의 인덱스-삭제한 자리의 인덱스 [그림 4-6] 선형 리스트에서의 원소 삭제

1차원 배열을 이용한 선형 리스트의 구현 1차원 배열을 이용한 구현 int sale[4] = {157, 209, 251, 312}; 논리적 구조 물리적 구조 [표 4-3] 분기별 판매량 리스트 [그림 4-7] 분기별 판매량 선형 리스트의 논리 구조 [그림 4-8] 분기별 판매량 선형 리스트의 물리 구조

1차원 배열을 이용한 선형 리스트 C 프로그램 01 #include <stdio.h> 02 02  03  void main( ) 04  { 05     int i, sale[4]={157, 209, 251, 312}; 06  07     for(i=0; i<4; i++){ 08      printf("\n address:%u sale[%d]=%d", &sale[i], i, sale[i]); 09     } 10  11     getchar( ); 12  }

실행 결과 실행 결과 확인 = 1245036 + (2ⅹ4바이트) = 1245044 배열 sale의 시작 주소 : 1245036 논리적인 순서대로 메모리에 연속하여 저장된 순차구조임을 확인!

2차원 배열을 이용한 선형 리스트의 구현 2차원 배열을 이용한 구현 int sale[2][4] = {{63, 84, 140, 130}, {157, 209, 251, 312}}; 논리적 구조 [표 4-4] 2004~2005년 분기별 판매량 리스트 [그림 4-9] 2004~2005년 분기별 판매량 선형 리스트의 논리 구조

2차원 배열의 물리적 저장 방법 2차원의 논리적 순서를 1차원의 물리적 순서로 변환하는 방법 사용 행 우선 순서 방법(row major order) 2차원 배열의 첫 번째 인덱스인 행 번호를 기준으로 사용하는 방법 sale[0][0]=63, sale[0][1]=84, sale[0][2]=140, sale[0][3]=130, sale[1][0]=157, sale[1][1]=209, sale[1][2]=251, sale[1][3]=312 원소의 위치 계산 방법 : α + (iⅹnj + j)ⅹℓ 행의 개수가 ni이고 열의 개수가 nj인 2차원 배열 A[ni][nj]의 시작주소가 α이고 원소의 길이가 ℓ 일 때, i행 j열 원소 즉, A[i][j]의 위치 열 우선 순서 방법(column major order) 2차원 배열의 마지막 인덱스인 열 번호를 기준으로 사용하는 방법 sale[0][0]=63, sale[1][0]=157, sale[0][1]=84, sale[1][1]=209, sale[0][2]=140, sale[1][2]=251, sale[0][3]=130, sale[1][3]=312 원소의 위치 계산 방법 : α + (jⅹni + i)ⅹℓ

물리적 구조 [그림 4-10] 2차원 논리 순서에 대한 1차원 물리 순서 변환 방법

2차원 배열을 이용한 선형 리스트 C 프로그램 01 #include <stdio.h> 02 02  03  void main( ) 04  { 05      int i, n=0, *ptr; 06         int sale[2][4] ={{63, 84, 140, 130}, 07              {157, 209, 251, 312}}; 08      09      ptr=&sale[0][0]; 10      for(i=0; i<8; i++){        11          printf("\n address: %u sale %d = %d", ptr, i, *ptr); 12          ptr++; 13      } 14      getchar( ); 15  }

실행 결과 실행 결과 확인 시작주소α=1245016, ni=2, nj=4, i=1, j=1, ℓ=4 sale[1][1]=209의 위치 = α+ (iⅹnj+j)ⅹℓ = 1245016 + (1ⅹ4+1)ⅹ4 = 1245016 + 20 = 1245036 C 컴파일러가 행 우선 순서 방법으로 2차원 배열을 저장함을 확인!

3차원 배열을 이용한 선형 리스트의 구현 예) 2004~2005년, 1팀과 2팀의 분기별 노트북 판매량 [표 4-5] 1팀과 2팀의 분기별 판매량 리스트

3차원 배열의 순환 표현 int sale[2][2][4] = {{{63, 84, 140, 130},         {157, 209, 251, 312}},                    {{59, 80, 130, 135}, {149, 187, 239, 310}}                   }; 논리적 구조 [그림 4-11] 1팀과 2팀의 2004~2005년 분기별 판매량 선형 리스트의 논리 구조

3차원 배열의 물리적 저장 방법 3차원의 논리적 순서를 1차원의 물리적 순서로 변환하는 방법 사용 면 우선 순서 방법 3차원 배열의 첫 번째 인덱스인 면 번호를 기준으로 사용하는 방법 원소의 위치 계산 방법 : α + {(iⅹnjⅹnk) + (jⅹnk) + k}ⅹℓ 면의 개수가 ni이고 행의 개수가 nj이고, 열의 개수가 nk 인 3차원 배열 A[ni][nj][nk] 시작주소가 α이고 원소의 길이가 ℓ 일 때, i면 j행 k열 원소 즉, A[i][j][k]의 위치 열 우선 순서 방법 3차원 배열의 마지막 인덱스인 열 번호를 기준으로 사용하는 방법 원소의 위치 계산 방법 : α + {(kⅹnjⅹni) + (jⅹni) + i}ⅹℓ

물리적 구조 [그림 4-12] 3차원 논리 순서에 대한 1차원 물리 순서

3차원 배열을 이용한 선형 리스트 C 프로그램 01 #include <stdio.h> 02 02  03  void main( ) 04  { 05      int i, n=0, *ptr; 06      int sale[2][2][4] ={{{63, 84, 140, 130}, 07                    {157, 209, 251, 312}}, 08                    {{59, 80, 130, 135}, 09               {149, 187, 239, 310}} }; 10  11      ptr=&sale[0][0][0]; 12      for(i=0; i<16; i++){        13          printf("\n address: %u sale %2d = %3d", ptr, i, *ptr); 14          ptr++; 15      } 16      getchar( ); 17  }

실행 결과 실행 결과 확인 시작주소α=1244980, ni=2, nj=2, nk=4, i=1, j=1, k=2, ℓ=4 sale[1][1][2]=239의 위치 = α+{(iⅹnjⅹnk)+(jⅹnk)+k}ⅹℓ   = 1244980 + {(1ⅹ2ⅹ4)+(1ⅹ4)+2}ⅹ4 = 1244980 + 56 = 1245036 C 컴파일러가 면 우선 순서 방법으로 3차원 배열을 저장함을 확인! ㅍ

다항식 aXe 형식의 항들의 합으로 구성된 식 지수에 따라 내림차순으로 항을 나열 다항식의 차수 : 가장 큰 지수 a : 계수(coefficient) X : 변수(variable) e : 지수(exponent) 지수에 따라 내림차순으로 항을 나열 다항식의 차수 : 가장 큰 지수 다항식 항의 최대 개수 = (차수 +1)개

다항식의 추상 자료형 ADT Polynomial End Polynomial 데이터 : 지수(ei)-계수(ai)의 순서쌍 <ei, ai>의 집합으로 표현된         다항식 p(x) = a0xe0 + a1xe1 + … + anxen. (ei는 음이 아닌 정수) 연산 :  p,p1,p2 ∈ Polynomial; a ∈ Coefficient; e ∈ Exponent;         // p,p1,p2는 다항식이고, a는 계수, e는 지수를 나타낸다.     zeroP( ) ∷= return polynomial p⒳=0;         // 다항식p⒳를 0으로 만드는 연산     isZeroP(p) ∷= if (p) then false;                   else return true;         // 다항식p가 0인지 아닌지 검사하여 0이면 true를 반환하는 연산     coef(p,e) ∷= if (<e,a> ∈ p) then return a;                  else return 0;         // 다항식p에서 지수가 e인 항의 계수a를 구하는 연산     maxExp(p) ∷= return max(p.Exponent);         // 다항식p에서 최대 지수를 구하는 연산     addTerm(p,a,e) ∷= if (e ∈ p.Exponent) then return error;                       else return p after inserting the term <e,a>;         // 다항식p에 지수가 e인 항이 없는 경우에 새로운 항<e,a>를 추가하는 연산     delTerm(p,e) ∷= if (e ∈ p.Exponent) then return p after removing the term <e,a>;                     else return error;         // 다항식p에서 지수가 e인 항<e,a>를 삭제하는 연산     Mult(p,a,e) ∷= return (p * axe);         // 다항식p의 모든 항에 axe항을 곱하는 연산     Addpoly(p1,p2) ∷= return (p1 + p2);         // 두 다항식p1과 p2의 합을 구하는 연산     Multpoly(p1,p2) ∷= return (p1 * p2);         // 두 다항식p1과 p2의 곱을 구하는 연산 End Polynomial

다항식의 표현 각 항의 지수와 계수의 쌍에 대한 선형 리스트 1차원 배열을 이용한 순차 자료구조 표현 예) A(x)=4x3+3x2+2 ☞ p1= ((3,4), (2,3), (0,2)) 1차원 배열을 이용한 순차 자료구조 표현 차수가 n인 다항식을 (n+1)개의 원소를 가지는 1차원 배열로 표현 배열 인덱스 i = 지수(n-i) 배열 인덱스 i의 원소 : 지수(n-i)항의 계수 저장 다항식에 포함되지 않은 지수의 항에 대한 원소에 0 저장 [그림 4-13] n차 다항식 P(x)의순차 자료구조 표현

희소 다항식에 대한 1차원 배열 저장 예) A(x)=4x3+3x2+2 의 순차 자료구조 표현 예) B(x)=3x1000 + x + 4 차수가 1000이므로 크기가 1001인 배열을 사용하는데, 항이 3개 뿐이므로 배열의 원소 중에서 3개만 사용 998개의 배열 원소에 대한 메모리 공간 낭비! [그림 4-14] A(x)의 순차 자료구조 표현 [그림 4-15] B(x)의 순차 자료구조 표현

2차원 배열을 이용한 순차 자료구조 표현 다항식의 각 항에 대한 <지수, 계수>의 쌍을 2차원 배열에 저장 2차원 배열의 행의 개수 = 다항식의 항의 개수 2차원 배열의 열의 개수 = 2 예) B(x)=3x1000 + x + 4 의 2차원 배열 표현 1차원 배열을 사용하는 방법보다 메모리 사용 공간 량 감소 공간 복잡도 감소 ☞ 프로그램 성능 향상! [그림 4-16] 희소 다항식 B(x)의 순차 자료구조 표현

다항식의 덧셈 다항식의 덧셈 알고리즘 : A(x)+B(x) = C(x) Addpoly(A, B) // 주어진 두 다항식 A와 B를 더하여 결과 다항식 C를 반환하는 알고리즘   C ← zeroP( );   while (not isZeroP(A) and not isZeroP(B)) do {     case {         maxExp(A) < maxExp(B) :                 C ← addTerm(C, coef(B, maxExp(B)), maxExp(B));                 B ← delTerm(B, maxExp(B));         maxExp(A) = maxExp(B) :                 sum ← coef(A, maxExp(A)) + coef(B, maxExp(B));                 if (sum≠0) then C ← addTerm(C, sum, maxExp(A));                 A ← delTerm(A, maxExp(A));                 B ← delTerm(B, maxExp(B));         maxExp(A) > maxExp(B) :                 C ← addTerm(C, coef(A, maxExp(A)), maxExp(A));                 A ← delTerm(A, maxExp(A));          }   }   if (not isZeroP(A)) then A의 나머지 항들을 C에 복사;   else if (not isZeroP(B)) then B의 나머지 항들을 C에 복사;   return C; End  Addpoly( )

다항식의 덧셈 C 프로그램 25 B_degree--; 26 } 27 else{ 28              C.coef[C_index++] = B.coef[B_index++]; 29              B_degree--; 30          }    31      } 32      return C; 33  } 34  35  void printPoly(polynomial P) 36  { 37      int i, degree; 38      degree=P.degree; 39      40      for(i=0; i<=P.degree; i++) 41          printf("%3.0fx^%d", P.coef[i], degree--); 42      printf("\n"); 43  } 44  45  46  void main( ) 47  { 48      polynomial A={3, {4,3,5,0}}; 49      polynomial B={4, {3,1,0,2,1}}; 50  51      polynomial C; 52      C= addPoly(A,B); 53  54      printf("\n A(x)=");  printPoly(A); 55      printf("\n B(x)=");  printPoly(B); 56      printf("\n C(x)=");  printPoly(C); 57  58      getchar( ); 59  } 01  #include <stdio.h> 02  #define MAX(a,b) ((a>b)?a:b) 03  #define MAX_DEGREE 50 04  05  typedef struct{ 06      int degree; 07      float coef[MAX_DEGREE]; 08  } polynomial; 09  10  polynomial addPoly(polynomial A, polynomial B) 11  { 12      polynomial C; 13      int A_index=0, B_index=0, C_index=0; 14      int A_degree=A.degree, B_degree=B.degree; 15      C.degree=MAX(A.degree, B.degree); 16  17      while(A_index<=A.degree && B_index<=B.degree){ 18          if(A_degree > B_degree){ 19              C.coef[C_index++] = A.coef[A_index++]; 20              A_degree--; 21          } 22          else if(A_degree == B_degree){ 23              C.coef[C_index++] = A.coef[A_index++]+B.coef[B_index++]; 24              A_degree--; 25              B_degree--; 26          }

실행 결과 A(x) = 4x3 + 3x2 + 5x B(x) = 3x4 + x3 + 2x + 1 C(x) = A(x) + B(x) = 3x4 + 5x3 + 3x2 + 7x + 1

전치 행렬 행렬의 행과 열을 서로 교환하여 구성한 행렬 행렬 A의 모든 원소의 위치(i, j)를 (j, i)로 교환 m×n 행렬을 n×m 행렬로 변환한 행렬 A’는 행렬 A의 전치행렬 예)

행렬의 순차 자료구조 표현 2차원 배열 사용 m×n행렬을 m행 n열의 2차원 배열로 표현 예) [그림 4-17] 행렬에 대한 2차원 배열 표현

희소 행렬에 대한 2차원 배열 표현 [그림 4-17]의 희소 행렬 B는 배열의 원소 56개 중에서 실제 사용하는 것은 0이 아닌 원소를 저장하는 10개 뿐이므로 46개의메모리 공간 낭비 희소 행렬인 경우에는 0이 아닌 원소만 추출하여 <행번호, 열번호, 원소>쌍으로 배열에 저장 [그림 4-18] 희소행렬에서 <행번호, 열 번호, 값>의 쌍 구하기

추출한 순서쌍을 2차원 배열의 행으로 저장 원래의 행렬에 대한 정보를 순서쌍으로 작성하여 0번 행에 저장 <전체 행의 개수, 전체 열의 개수, 0이 아닌 원소의 개수 [그림 4-19] 희소 행렬에 대한 2차원 배열

희소 행렬의 추상 자료형 ADT Sparse_Matrix 데이터 : 3원소쌍 <행 인덱스, 열 인덱스, 원소 값>의 집합          연산 :  a,b∈Sparse_Matrix; c∈Matrix; u,v∈value; i∈Row;  j∈Column;         // a, b는 희소행렬, c는 행렬, u, v는 행렬의 원소값을 나타내며, i와 j는           행 인덱스와 열 인덱스를 나타낸다.     smCreate(m,n) ∷= return an empty sparse matrix with m× n;         // m× n의 공백 희소행렬을 만드는 연산      smTranspose(a) ∷= return c where c[i,j]=v when a[i,j]=v;         // 희소행렬 a[i,j]=v를 c[i,j]=v로 전치시킨 전치행렬 c를 구하는 연산     smAdd(a,b) ∷= if (a.dimension = b.dimension)                    then return c where c[i,j]=v+u where a[i,j]=v and b[i,j]=u;                   else return error;         // 차수가 같은 희소행렬 a와 b를 합한 행렬 c를 구하는 연산     smMulti(a,b) ∷= if (a.n = b.m) then return c where c[i,j]=a[i,k]× b[k,j];                     else return error;         // 희소행렬 a의 열의 개수(n)와 희소행렬 b의 행의 개수(m)가 같은 경우에            두 행렬의 곱을 구하는 연산 End Sparse_Matrix

희소행렬의 전치 연산 알고리즘 smTranspose(a[]) m ← a[0,0]; // 희소 행렬 a의 행 수    n ← a[0,1];    // 희소 행렬 a의 열 수    v ← a[0,2];    // 희소 행렬 a에서 0이 아닌 원소 수    b[0,0] ← n;    // 전치 행렬 b의 행 수 지정    b[0,1] ← m;    // 전치 행렬 b의 열 수 지정    b[0,2] ← t;    // 전치 행렬 b의 원소 수 지정   if (v > 0) then {     // 0이 아닌 원소가 있는 경우에만 전치 연산 수행      p ← 1;      for (i←0; i < n; i←i+1) do {    // 희소 행렬 a의 열별로 전치 반복 수행         for (j←1; j <= v; j←j+1) do {// 0이 아닌 원소 수에 대해서만 반복 수행            if (a[j,1]←i) then  {   // 현재의 열에 속하는 원소가 있으면 b[]에 삽입              b[p,0] ← a[j,1];              b[p,1] ← a[j,0];              b[p,2] ← a[j,2];              p ← p+1;             }          }       }    }    return b[]; End smTranspose( )

희소 행렬의 전치 연산에 대한 C 함수 01 typedef struct{ 02 int row; 03 int col 04 int value; 05 } term; 06 07 void smTranspose(term a[], term b[]) { 08 int m, n, v, i, j, p; 09 m = a[0].row; // 희소 행렬 a의 행 수 10 n = a[0].col; // 희소 행렬 a의 열 수 11 v = a[0].value; // 희소 행렬 a에서 0이 아닌 원소 수 12 b[0].row = n; // 전치 행렬 b의 행 수 13 b[0].col = m; // 전치 행렬 b의 열 수 14 b[0].value = t; // 전치 행렬 b의 원소 수 15 if (v > 0) { // 0이 아닌 원소가 있는 경우에만 전치 연산 수행 16 p = 1; 17 for (i = 0; i < n; i++) // 희소 행렬 a의 열 별로 전치 반복 수행 18 for (j = 1; j <= v; j++) //0이 아닌 원소 수에 대해서만 반복 수행 19 if (a[j].col == i) {// 현재의 열에 속하는 원소가 있으면 b[ ]에 삽입 20 b[p].row = a[j].col 21 b[p].col = a[j].row 22 b[p].value = a[j].value 23 p++; 24 } 25 } 26 }