수험적합 자료구조론 공무원/공사/교원임용대비 이론서 3장 연결리스트 주객관식 문제 포함

소개

 공무원⦁공사/공단⦁교원임용 및 각종 시험 대비
 다수 유명 대학 교재 활용한 기출 중심의 상세 이론 수록: 실전 고득점자 시각
 과년도 경간후보시험/중등교원임용/공무원 시험 등 주관식/객관식 상세 해설
- 주관식 7문, 객관식 11문

목차

1.THEME 3-1 선형 리스트(Linear list) 3
(1) 선형 리스트의 개요 3
(2) 선형 리스트의 구현: 순차적 사상과 비순차적 사상 4
(3) 순차적 사상에서의 원소의 삭제와 삽입 분석 6

2.THEME 3-2 단순 연결리스트 7
(1) 연결 리스트의 소개 7
(2) 단순 연결리스트의 개요 8
(3) 단순 연결 리스트의 기본 연산 (1) 9
(4) 단순 연결 리스트의 기본 연산 (2) 11

3.THEME 3-3 원형 연결리스트 15
(1) 원형 연결 리스트(Circular linked list)의 개요 15
(2) 원형 연결 리스트 상의 효율적인 삽입 16
(3) 가용공간리스트(Available space list)와 쓰레기 수집 17
(4) 원형 연결 리스트 연산 20

4.THEME 3-4 이중 연결 리스트 22
(1) 이중 연결 리스트(doubly linked list)의 개요 22
(2) 이중 연결 리스트의 기본 연산 23

5.THEME 3-5 연결 리스트의 응용: 체인 다항식 등 26
(1) 체인 다항식의 개요 26
(2) 체인 다항식의 덧셈 27
(3) 연결 리스트를 이용한 희소 행렬 30

6.THEME 3-6 일반 리스트 31
(1) 일반 리스트의 개요 31
(2) 일반 리스트 표기와 용어 32

7.THEME 3-7 주/객관식 문제 33

본문내용

THEME 3-1 선형 리스트(Linear list)
(1) 선형 리스트의 개요
1) 개념
① 선형 리스트(linear list, 리스트): 어떤 논리적 순서에 의해서 나열된 유한개의 데이터 항목의
모임
– 리스트는 원소들 간에 순서가 없는 집합(set)과는 다름
② 리스트 내의 원소들의 순서가 매우 중요한 의미를 가지므로 조밀 리스트(dense list), 순서 리
스트(ordered list), 순차 리스트(sequential list) 등으로도 불린다.
2) 선형 리스트의 표현
L = (a0, a1, a2, … , an)
단, L은 리스트의 이름, ai는 리스트의 원소
3) 용어
① 원소(element, 노드): 선형 리스트를 구성하는 순차적으로 나열되는 임의의 각 항목 ai(0≤i<n)
② 선형 리스트의 크기(길이): 선형 리스트를 구성하는 원소의 개수 n
③ 공백 리스트(empty list): 원소를 하나도 갖지 않는 리스트로 L = ()으로 표시한다.
◎ 예시 3-1 선형 리스트
- 한 주일 동안의 요일의 순서 리스트: 요일 = (일요일, 월요일, 화요일, 수요일, 목요일,
금요일, 토요일)
- 건물의 층의 리스트: 건물층 = (지하실, 로비, 1층, 2층, 3층)
4) 선형 리스트와 비선형 리스트의 유형
① 선형 리스트(선형 자료구조): 원소 간에 순서 개념을 가진 자료구조
② 비선형 리스트(비선형 자료구조): 원소 간에 순서 개념이 없는 자료구조

참고자료

· C로 쓴 자료구조론 (Fundamentals of Data Structures in C), 2판, Horowitz외 2인 교보문고
· 자료구조와 JAVA 이석호 저 정익사
· C언어로 쉽게 풀어쓴 자료구조 개정 3판 천인국 외 2인 생능출판사
· 예제로 배우는 자료구조론 주낙근 외 3인 정익사
· C, C++로 배우는 자료구조론 주우석 저 한빛미디어
· 쉽게 배우는 알고리즘 문병로 지음 한빛아카데미
· 인터넷 자료(네이버, 구글 등)