자료구조 (Data Structure)
자료구조의 정의 프로그램이란 데이터를 표현하고 그렇게 표현된 데이터를 처리하는 것 의미 데이터를 표현 자료구조 데이터를 처리 알고리즘 의미 자료를 변수로 국한하면 (책 한권) 자료구조란 변수들의 메모리상의 배치 상태를 의미 (책 장의 구조, 모양 및 책의 배치)
자료구조의 종류 선형 구조 비선형 구조 프로그램에 최적화된 자료구조 선택 자료가 일렬로 연결되어있는 구조 예: 배열, 연결리스트, 스택 (LIFO), 큐 (FIFO) 비선형 구조 자료들의 구성이 일렬이 아닌 특별한 모양으로 연결되어 있는 구조 예: 트리, 그래프 프로그램에 최적화된 자료구조 선택 선택 기준 : 자료의 양, 활용빈도, 갱신 정도나 기억용량 등
연결리스트 연결리스트란? 더미 노드 방식 논리적 순서만 유지하고, 기억장소는 임의 위치 cf. 배열 : 물리적으로 순차적인 기억장소에 저장 레코드의 추가,삽입,삭제가 잦은 곳에 유리하고, 조회가 드문 곳에 유리하다. 더미 노드 방식 Head만 있고, Tail은 없다. cf. Tail도 있는 경우, Head와 Tail사이에 노드를 추가하는 방법
연결 리스트의 구조 Node = Data + Link Link : 다음 노드의 위치정보 포인터로 지시
배열과 비교
배열과 비교2 저장장치가 아래와 같이 빈 공간이 3개씩 밖에 존재하지 않는 경우, 아래의 입력자료가 4개이므로 배열은 연속된 4개의 공간이 필요하여 저장이 불가하나 연결리스트를 이용하여 저장하는 것은 가능하다.
장단점 장점: 단점: 링크에 의해 노드가 논리적으로 연결되어 있어 물리적 이동이 필요 없으므로 추가, 삽입, 삭제 등이 빠르다 탐색 속도가 느리다 링크로 계속 접근 임의 접근이 어렵다. : 그래서 qsort, bsearch 등 표준함수에서는 일반 배열만 지원 포인터 구문이 많아 복잡하고 어렵다. 스트림 입출력, 네트워크 전송 불편 저장 시 링크 제외, 불러올 때 링크 복원
노드 (Node) 구현 노드는 구조체로 구현한다. Node는 Data와 Link를 멤버로 가진다. Link는 다음 Node를 지시할 수 있도록 포인터로 구현한다. 노드는 자기참조구조체가 된다. struct _Node { int nData; // Data struct _Node *pNode; // Link : 다음 노드에 대한 링크 };
노드 삽입
노드 삽입 코드 // 새로운 노드를 생성 pNode = (Node*) malloc ( sizeof(Node) ) ; Node *pNode; pNode = (Node*) malloc ( sizeof(Node) ) ; if( !pNode ) exit(1); pNodenData = 25 ; // 이전 노드의 링크를 저장 pNodepNext = pPrevpNext ; // 이전 노드의 링크에 새로운 노드 주소 저장 pPrevpNext = pNode;
노드 삭제
노드 삭제 코드 // 삭제할 노드 Node *pDelNode = pPrevNext ; // 삭제할 노드의 링크 정보를 저장 pPrevpNext = pDelNodepNext ; // 노드를 삭제 free( pDelNode ) ;
형의 재정의 unsigned char와 같이 형의 이름이 긴 것을 typedef를 사용하여 임의의 이름을 붙일 수 있다. 예: typedef unsigned char u_char; 구조체 템플릿명의 변경 예: typedef struct employee { int id; … } s_emp; // 새 이름 s_emp kim; // struct employee보다 간결.
과제 구조체 배열 연결리스트 성적 처리 프로그램의 자료구조를 구조체 배열로 구현한다. 성적 처리 프로그램의 자료구조를 연결리스트로 구현한다.
End