자기참조 구조체(1) 먼저 자신과 같은 형의 구조체를 포인트하는 포인터 멤버 필드를 갖는 구조체를 정의한다.

Presentation on theme: "자기참조 구조체(1) 먼저 자신과 같은 형의 구조체를 포인트하는 포인터 멤버 필드를 갖는 구조체를 정의한다."— Presentation transcript:

1 자기참조 구조체(1) 먼저 자신과 같은 형의 구조체를 포인트하는 포인터 멤버 필드를 갖는 구조체를 정의한다.
struct list { int data; struct list *next; } a; struct list 형으로 선언된 a는 메모리 두 워드에 저장된다.

2 자기참조 구조체(2) 한 워드에는 멤버 data가 저장되고 두번째 워드에는 멤버 next가 저장된다.
포인터 변수 next를 연결(link)라고 한다. 각 구조체는 멤버 next에 의해 연속적으로 연결된다. 이를 그림으로 표현하면 다음과 같다. data next

3 자기참조 구조체(3) 포인터변수 next는 다음 list 원소의 메모리 주소나 0으로 정의되는 특별한 NULL값을 가진다.
다음과 같이 선언되었을 때 어떻게 리스트 연산이 수행되는지 살펴보자. struct list a,b,c; 먼저 선언된 구조체에 다음과 같은 배정문을 수행하여 보자.

4 자기참조 구조체(4) a.data = 1; b.data =2; c.data = 3;
a.next = b.next = c.next = NULL; 그림으로 보면, 이코드의 결과는 다음과 같다. 1 NULL data next 2 NULL data next 3 NULL data next

5 자기참조 구조체(5) 노드들의 연결은 다음과 같이 할 수 있다. a.next = &b; b.next = &c;
이 포인트 배정문으로 a,b,c가 함께 연결된다. a.next->data 는 2의 값을 가진다. a.next->next->data 는 3의 값을 가진다. 1 data next 2 3 a b c NULL

6 선형 연결 리스트 선형 연결 리스트는 자료구조들이 순차적으로 매달려 있는 빨래줄과 같다.
헤드 포인터는 이 리스트상의 첫 번째 원소를 포인트하며 각 원소는 다음 원소를 포인트한다. 마지막 원소는 NULL값을 가진다. 구조체는 기억장소를 동적으로 할당하는 유틸리티 함수(malloc)를 사용한다.

7 기억장소 할당(1) malloc(size)
head = malloc(sizeof(ELEMENT)); 위 문장은 먼저 ELEMENT를 저장할 수 있는 기억장소를 할당하고, 그 주소를 포인터 head에 배정한다. sizeof() 연산자는 특정 자료구조를 저장하기 위해 필요한 바이트 수를 계산한다.

8 기억장소할당(2) head = malloc(sizeof(ELEMENT)); head -> d = ‘n’;
head -> next = NULL; 위의 코드는 리스트의 한 원소를 생성한다. n NULL data next head

9 기억장소할당(3) 두 번째 원소는 다음 배정문들로 추가된다.
head -> next = malloc(sizeof(ELEMENT)); head -> next -> d = ‘e’; head -> next -> next = NULL; n e NULL head

10 기억장소할당(4) 다음 코드로 마지막 원소를 추가한다.
head -> next -> next = malloc(sizeof(ELEMENT)); head -> next -> next -> d = ‘w’; head -> next -> next -> next = NULL; n e w NULL head

11 리스트 연산(1) 선형 리스트에 대한 기본 연산으로는 다음과 같은 것이 있다. 1. 리스트 생성 2. 원소 개수 세기
3. 원소 탐색 4. 두 리스트 결합 5. 원소 삽입 6. 원소 삭제

12 리스트 연산(2) 재귀적 리스트 생성 : p 반복적 리스트 생성 : p449

13 리스트 처리 함수(1) 리스트에 있는 원소의 수를 세는 함수 int count(LINK head) { }
if( head == NULL) return; else return ( 1 + count(head -> next)); } COUNT() 함수는 리스트가 공백이면 0을 리턴하고 그렇지 않으면 리스트의 원소의 수를 리턴한다.

14 리스트 처리 함수(2) 리스트의 원소를 출력하는 함수 void print_list(LINK head) {
if(head == NULL) printf(“NULL”); else { printf(“%c --> “, head -> d); print_list(head -> next); } 재귀적으로 리스트의 원소를 방문하면서 멤버 변수 d의 값을 출력한다.

15 리스트 삽입(1) 리스트의 가장 유용한 특성은 원소를 삽입할 경우 고정된 시간내에 수행될 수 있다는 것이다.
배열을 사용할 경우 새로운 삽입시 배열 길이에 비례하게 된다. 왜냐하면 새로 삽입된 값 다음에 오는 모든 원소 값을 한 위치씩 이동해야 되기 때문이다. 다음 그림은 p1과 p2가 인접한 원소를 포인트 하고 있고, 그 사이에 q가 포인트하고 있는 새로운 원소를 삽입하는 경우를 나타낸 것이다

16 리스트 삽입(2) 삽입전 B A C p1 p2 NULL q

17 리스트 삽입(3) 삽입후 p1 p2 void insert(LINK p1, LINK p2, LINK q) {
p1 -> next = q; q -> next = p2; } p1과 p2가 포인트하는 원소 사이에 q가 포인트하는 원소를 삽입하는 것이다. B A C p1 p2 q

18 리스트 삭제(1) 삭제될 원소의 후속자를 삭제될 원소의 선행자에 연결하면 된다. 삭제전(B를 삭제하려고 한다.)
다음 코드를 실행해 보자. p -> next = p -> next -> next A B C p

19 리스트 삭제(2) 삭제후 p void delete_list(LINK head) { if(head != NULL) {
delete_list(head -> next); free(head); } free() 함수는 할당받은 기억장소를 시스템에 반납하는 함수 이다. p A B C

20 스 택 스택은 서류함을 쌓아 놓은 것으로 볼 수 있다. 이 더미에서 서류함을 가져 갈 때는 항상 제일 위(top)에 있는 것을 가져 가고, 서류함을 쌓을 때도 항상 제일 위(top)에 올려 놓는다. top B A

21 스택에 삽입 push()루틴은 시스템에 기억장소를 리턴하기 위해 free()함수를 사용하였으며 리스트에서 삽입과 같다.
void push(data d, stack *stk) { elem *p; p = malloc(sizeof(elem)); p -> d = d; p -> next = stk -> top; stk -> top = p; stk -> cnt++; }

22 스택에서 삭제 pop()루틴은 새로운 스택 원소를 생성하기 위해 기억장소 할당자 malloc()을 사용하였고 리스트에서 삭제와 같다. data pop(stack *stk) { data d; elem *p; d = stk -> top -> d; p = stk -> top; stk -> top = stk -> top -> next; stk -> cnt--; free(p); return d; }