자료구조 (Data Structure).

Presentation on theme: "자료구조 (Data Structure)."— Presentation transcript:

1 자료구조 (Data Structure)

2 자료구조의 정의 프로그램이란 데이터를 표현하고 그렇게 표현된 데이터를 처리하는 것 의미 데이터를 표현  자료구조
데이터를 처리  알고리즘 의미 자료를 변수로 국한하면 (책 한권) 자료구조란 변수들의 메모리상의 배치 상태를 의미 (책 장의 구조, 모양 및 책의 배치)

3 자료구조의 종류 선형 구조 비선형 구조 프로그램에 최적화된 자료구조 선택 자료가 일렬로 연결되어있는 구조
예: 배열, 연결리스트, 스택 (LIFO), 큐 (FIFO) 비선형 구조 자료들의 구성이 일렬이 아닌 특별한 모양으로 연결되어 있는 구조 예: 트리, 그래프 프로그램에 최적화된 자료구조 선택 선택 기준 : 자료의 양, 활용빈도, 갱신 정도나 기억용량 등

4 연결리스트 연결리스트란? 더미 노드 방식 논리적 순서만 유지하고, 기억장소는 임의 위치
cf. 배열 : 물리적으로 순차적인 기억장소에 저장 레코드의 추가,삽입,삭제가 잦은 곳에 유리하고, 조회가 드문 곳에 유리하다. 더미 노드 방식 Head만 있고, Tail은 없다. cf. Tail도 있는 경우, Head와 Tail사이에 노드를 추가하는 방법

5 연결 리스트의 구조 Node = Data + Link Link : 다음 노드의 위치정보  포인터로 지시

6 배열과 비교

7 배열과 비교2 저장장치가 아래와 같이 빈 공간이 3개씩 밖에 존재하지 않는 경우, 아래의 입력자료가 4개이므로 배열은 연속된 4개의 공간이 필요하여 저장이 불가하나 연결리스트를 이용하여 저장하는 것은 가능하다.

8 장단점 장점: 단점: 링크에 의해 노드가 논리적으로 연결되어 있어 물리적 이동이 필요 없으므로 추가, 삽입, 삭제 등이 빠르다
탐색 속도가 느리다  링크로 계속 접근 임의 접근이 어렵다. : 그래서 qsort, bsearch 등 표준함수에서는 일반 배열만 지원 포인터 구문이 많아 복잡하고 어렵다. 스트림 입출력, 네트워크 전송 불편  저장 시 링크 제외, 불러올 때 링크 복원

9 노드 (Node) 구현 노드는 구조체로 구현한다. Node는 Data와 Link를 멤버로 가진다.
Link는 다음 Node를 지시할 수 있도록 포인터로 구현한다. 노드는 자기참조구조체가 된다. struct _Node { int nData; // Data struct _Node *pNode; // Link : 다음 노드에 대한 링크 };

10 노드 삽입

11 노드 삽입 코드 // 새로운 노드를 생성 pNode = (Node*) malloc ( sizeof(Node) ) ;
Node *pNode; pNode = (Node*) malloc ( sizeof(Node) ) ; if( !pNode ) exit(1); pNodenData = 25 ; // 이전 노드의 링크를 저장 pNodepNext = pPrevpNext ; // 이전 노드의 링크에 새로운 노드 주소 저장 pPrevpNext = pNode;

12 노드 삭제

13 노드 삭제 코드 // 삭제할 노드 Node *pDelNode = pPrevNext ; // 삭제할 노드의 링크 정보를 저장
pPrevpNext = pDelNodepNext ; // 노드를 삭제 free( pDelNode ) ;

14 형의 재정의 unsigned char와 같이 형의 이름이 긴 것을 typedef를 사용하여 임의의 이름을 붙일 수 있다.
예: typedef unsigned char u_char; 구조체 템플릿명의 변경 예: typedef struct employee { int id; … } s_emp; // 새 이름 s_emp kim; // struct employee보다 간결.

15 과제 구조체 배열 연결리스트 성적 처리 프로그램의 자료구조를 구조체 배열로 구현한다.
성적 처리 프로그램의 자료구조를 연결리스트로 구현한다.

16 End