7. 자료구조 - 배열과 연결리스트

(173)

배열

1차원 배열	- 주소계산: 첨자가 0인 주소를 기본주소 base라 함 - A[f]의 주소 = base + (i * 데이터형의 크기)
2차원 배열	- 주소계산: 전체 배열의 크기가 A[m][n], 시작위치가 A[a][b] = base이며 한 주소의 크기를 1바이트로 함 - 행우선: A[i][j]의 주소 = base + (i-a)*n + (j-b) - 열우선: A[i][j]의 주소 = base + (j-b)*m + (i-a)
3차원 배열	- 주소계산: 전체 배열의 크기가 A[c][m][n], 시작위치 A[a][b][c] - base이며 한 원소의 크기는 1바이트로 함 - 행우선: A[k][i][j]의 주소 = base + (k-a)mn + (i-b)n + (j-c) * (k-a)mn: 변, (i-b)n: 행, (j-c): 열 - 열우선: A[k][i][j]의 주소 = base + (k-a)mn + (j-c)m + (i-b)

 

희소행렬

- 전체 원소수에 비해 극소수의 원소만 0이 아닌 행렬

- 기억 공간 낭비 초래할 수 있음

- 배열 또는 연결리스트로 표현 시 기억공간 절약 가능, 연산 복잡해짐

- 0이 아닌 원소들을 3원소 쌍을 열어 3인 2차원 배열로 표현

* 3원소 쌍: <행, 열, 값>

 

삼각행렬

- 상부삼각행렬(upper triangular matrix) = 상삼각행렬: 주대각선보다 아래에 있는 모든 성분이 0인 정사각행렬

- 하부삼각행렬(lower triangular matrix): 주대각선보다 위에 있는 모든 성분이 0인 정사각행렬

- 0이 아닌 항의 총계는 n(n+1)/2

- 상부삼각행렬 예시

1	1	1	1
0	1	1	1
0	0	1	1
0	0	0	1

 

포인터 변수

- 포인터가 가르키는 변수의 주소 저장, 주소만이 저장됨 - 기억공간의 주소값을 갖는 변수를 말함 - *를 사용해 포인터를 선언

int a,b; //int 형 변수 a.b 선언  int *p; //포인터 변수 p 선언  a = 7; //변수 a에 값 7 입력  p = &a; //포인터 변수 p가 가르키는 변수 a의 주소값 저장

 

구조체(struct)

- 여러 개의 변수를 하나의 자료형으로 묶어서 취급 - 서로 다른 자료형을 갖는 자료들의 모임을 하나의 자료형으로 정의해 사용하는 자료형 - 구조체를 구성하는 멤버 단위를 치급할 수도 있고, 구조체 변수를 이용해 구조체를 하나의 자료형으로 취급할 수 있음 - 구조체 멤버를 개별적으로 다룰 때: Dot연산자(.) 이용 * 구조체 변수가 포인터일 경우 Arrow연산자(->)이용해 각 멤버를 취급할 수 있음 - 장점: 배열이나 포인터가 함께 기존의 변수처럼 사용될 수 있어 다양한 형태의 자료를 간결한 형식으로 표현할 수 있음, 사용자가 새로운 형식으로 정의해 사용할 수 있음

struct 태그명{ 구조체 멤버 나열 } 구조체 변수 ;

 

자기 참조 구조체

- 구성 요소 중에 자기 자신을 가리키는 포인터가 한 개 이상 존재하는 구조체 - struct의 멤버는 같은 타입의 또 다른 struct를 지시하는 포인터도 될 수 있음

struct char_list_node {     char letter;     struct char_list_node *next;     }; struct char_list_node *p;

 

typedef 키워드

- 리스트 처리를 위해 노드와 포인터를 정의할 때 typedef 이용시 더욱 간결해짐

typedef struct char_list_node *list_pointer struct char_list_node{     char letter;     list_pointer next;     };     list_pointer p = NULL

 

메모리 동적할당

- 프로그램이 실행 도중 동적으로 메모리를 할당받는 것

- 프로그램에서 필요한 만큼의 메모리를 시스템으로부터 할당받아 사용하고 사용이 끝나면 반납함

- 프로그램 작성 당시에는 얼마나 많은 공간이 필요한지 알 수 없고 필요없이 낭비되거나 필요한 공간이 모자라는 상황을 막기 위해 미모리를 동적 할당할 필요가 있음

- malloc( ): 컴파일 시간에 확장된 크기의 메모리를 할당하지 않고 필요한 때에 필요한 만큼의 공간을 동적으로 운영체제에 요구하게 됨

*사용 가능한 기억장소 있으면 요구한 크기의 메모리 영역에 대한 시작 주소를 포인터에 반환

- free( ): malloc( )으로 할당한 메모리 영역을 시스템에 반환 (delete ( )와 유사)

 

원소값이 x인 노드를 p가 가리키는 노드 다음에 삽입

insertNode(1,p,x) //리스트 L에 p 노드 다음에 원소값 x 삽입     newNode <- getNode(); //공백 노드를 newNode가 지시     newNodedata <- x; //원소값 x 저장     if(L = null) then { //L이 공백 리스트일 경우         L <- newNode;         newNodelink <- null;     }     else if (p=null) then { //p가 공백이면 L의 첫 번째 노드로 삽입         newNodelink <- L;         L <- newNode;     }     else { //p가 가리키는 노드의 다음 노드로 삽입         newNodelink <- p.link;         p.link <- newNode;     } end insertNode(0

 

리스트 L에서 p가 가리키는 노드의 다음 노드를 삭제

deleteNext(L, p) //p가 가리키는 노드의 다음 노드를 삭제     if(L = null) then error;     if(p = null) then L <- L.link; //첫 번째 노드 삭제     else{         q <- p.link; //q는 삭제할 노드         if(q = null) then return; //삭제할 노드가 없는 경우         p.link = q.link;     }     returnNode(q); //삭제한 노드를 자유 공간 리스트에 반환 end deleteNext()

 

이중 연결리스트

- 노드가 3개의 필드(data, lnext, renxt)로 구성 - 노드의 왼쪽과 오른쪽에 포인터가 다 있음 -> 정방향, 역방향 탐색 둘 다 가능	- 이중 연결리스트의 삽입 insertD(D,p,q) //D는 이중 연결리스트, 노드 q를 p다음에 삽입     q.llink <-p;     q.rlink <- p.rlink;     p.rlink.llink <-q;     p.rlink <-q; end insertD()
	- 이중 연결리스트의 삭제 deleteD(D,p) //D는 공백이 아닌 이중 연결리스트, p는 삭제할 노드     if (p = null) then return;     p.llink.rlink <- p.rlink;     p.rlink.llink <- p.llink; end deleteD()

 

첫 21/30