DONGEUI UNIVERSITY Data structures 동의대학교 멀티미디어공학과 이광의교수 01.1: an Introduction

course schedule 1주: 기초지식 I ► 자료구조란 무엇인가 ? ►C++ 의 클래스 ►C++ 포인터 2주: 기초지식 II ► 재귀함수 ► 수학적 귀납법 3주~7주: 리스트 / 스택 / 큐 / 정렬 8주: 중간시험 9주~14주: 트리 / 우선순위큐 / 탐색 / 그래프 15주: 기말시험 Dept. of Multimedia Engineering, DongEui Univ.(2)

Today’s topic 자료구조의 정의 ► 정의 1: 자료구조는 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법이다. ► 정의 2: 자료구조는 추상자료형이다. ► 정의 3: 자료구조는 잘 알려지고 유용한 추상자료형이다. C++클래스: 추상자료형의 구현 ► 클래스 기초 ► 클래스 구현 예 1 ► 클래스 구현 예 2 포인터 ► 포인터 기초 ► 포인터 활용 예 1 Dept. of Multimedia Engineering, DongEui Univ.(3)

The 1 st Definition of data structure 자료구조란 무엇인가? ► 자료구조는 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법이다. [wiki] 시작하는 예제 ► 유선방송 시청에 꼭 필요한 것은 ? TV 리모트 컨트롤러 채널목록 Dept. of Multimedia Engineering, DongEui Univ.(4)

A Starting example: t.v. channel list 1 Dept. of Multimedia Engineering, DongEui Univ.(5) ch 채널이름 02 시네마 TV 13 금강방송 1 24 금강방송 2 35 금강방송 3 46JTV 57CJ 홈쇼핑 68KBS1 79KBS2 810GS 홈쇼핑 911MBC 1012 현대 홈쇼핑 1113EBS 1214MGM 1315 농수산 TV 1416inet(iTV 녹화 ) 1517 우리 홈쇼핑 1618 리얼 TV 1719K-TV 1820OUN 1921 아리랑 TV 2022EBS plus1 2123EBS plus2 2224YTN 2325MBN ch 채널이름 2426CEM TV 2527 코미디 TV 2628NHK 월드 프리미엄 2729CNN 2830 불교방송 2931 가톨릭 방송 3032CTS 기독교 TV 3133CBS 3234History 3335 내셔널지오그래픽 3436Q 채널 3537JEI 스스로방송 3638 투니버스 3739 챔프 3840 어린이 TV 3941English TV 4042new 중화 TV 4143KBS Sports 4244SBS Sports 4345MBC ESPN 4446SBS GOLF 4547 퀴 니퀴 니 4648MBC 게임 4749 온게임넷 ch 채널이름 4850FTV 4951 바둑 TV 5052FOOD 채널 5153On Style 5254GTV 5355Home CGV 5456OCN 5557CNTV 5658 무협 TV 5759MBC Movies 5860XTM 5961 수퍼액션 6062KBS 드라마 6163SBS 드라마 6264MBC 드라마넷 6365Xports 6466KMTV 6567m.net 6668MTV

A Starting example: t.v. channel list 1 자료구조란 무엇인가? ► 자료구조는 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법이다. 이용의 의미는 무엇인가? ► 채널 검색 : chNameOf(5); chNumOf(“ 리얼 TV”); ► 채널 삭제 : deleteNum(14); deleteName(“MGM”); ► 채널 추가 : insertCh(14, “ 동의 TV”); 효율적의 의미는 무엇인가? ► 채널번호에 따른 채널 검색 ► 채널이름에 따른 채널 검색 ► 삭제, 추가 Dept. of Multimedia Engineering, DongEui Univ.(6) ch 채널이름 02 시네마 TV 13 금강방송 1 24 금강방송 2 35 금강방송 3 46JTV 57CJ 홈쇼핑 68KBS1 79KBS2 810GS 홈쇼핑 911MBC 1012 현대 홈쇼핑 1113EBS 1214MGM 1315 농수산 TV 1416inet(iTV 녹화 ) 1517 우리 홈쇼핑 1618 리얼 TV 1719K-TV 1820OUN 1921 아리랑 TV 2022EBS plus1 2123EBS plus

A Starting example: t.v. channel list 2 Dept. of Multimedia Engineering, DongEui Univ.(7) ch 채널이름 031 가톨릭 방송 13 금강방송 1 24 금강방송 2 35 금강방송 내셔널지오그래픽 515 농수산 TV 618 리얼 TV 758 무협 TV 851 바둑 TV 930 불교방송 1061 수퍼액션 112 시네마 TV 1221 아리랑 TV 1340 어린이 TV 1449 온게임넷 1517 우리 홈쇼핑 1642 중화 TV 1739 챔프 1827 코미디 TV 1947 퀴 니퀴 니 2038 투니버스 2112 현대 홈쇼핑 2233CBS 2326CEM TV ch 채널이름 247CJ 홈쇼핑 2529CNN 2657CNTV 2732CTS 기독교 TV 2813EBS 2922EBS plus1 3023EBS plus2 3141English TV 3252FOOD 채널 3350FTV 3410GS 홈쇼핑 3554GTV 3634History 3755Home CGV 3816inet(iTV 녹화 ) 3937JEI 스스로방송 406JTV 4162KBS 드라마 4243KBS Sports 438KBS1 449KBS2 4566KMTV 4619K-TV 4767m.net ch 채널이름 4811MBC 4948MBC 게임 5064MBC 드라마넷 5145MBC ESPN 5259MBC Movies 5325MBN 5414MGM 5568MTV 5628NHK 월드 프리미엄 5756OCN 5853On Style 5920OUN 6036Q 채널 6163SBS 드라마 6246SBS GOLF 6344SBS Sports 6465Xports 6560XTM 6624YTN

A Starting example: t.v. channel list 2 자료구조란 무엇인가? ► 자료구조는 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법이다. 이용의 의미는 무엇인가? ► 채널 검색 : chNameOf(5); chNumOf(“ 리얼 TV”); ► 채널 삭제 : deleteNum(14); deleteName(“MGM”); ► 채널 추가 : insertCh(14, “ 동의 TV”); 효율적의 의미는 무엇인가? ► 채널번호에 따른 채널 검색 ► 채널이름에 따른 채널 검색 ► 삭제, 추가 Dept. of Multimedia Engineering, DongEui Univ.(8) ch 채널이름 031 가톨릭 방송 13 금강방송 1 24 금강방송 2 35 금강방송 내셔널지오그래픽 515 농수산 TV 618 리얼 TV 758 무협 TV 851 바둑 TV 930 불교방송 1061 수퍼액션 112 시네마 TV 1221 아리랑 TV 1340 어린이 TV 1449 온게임넷 1517 우리 홈쇼핑 1642 중화 TV 1739 챔프 1827 코미디 TV 1947 퀴 니퀴 니 2038 투니버스 2112 현대 홈쇼핑 22 23

The 1 st Definition of data structure 자료구조란 무엇인가? ► 자료구조는 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법이다. [wiki] ► 자료는 자료 자체뿐만 아니라 자료를 이용하고자 하는 이용방법 ( 연산 ) 을 포함한다. 채널목록 자료는 다음으로 구성된다. ► 자료 : 채널번호와 채널이름 쌍들로 구성된 목록 ► 연산 : 검색연산, 삭제연산, 추가연산, 등. Dept. of Multimedia Engineering, DongEui Univ.(9)

The 2 nd Definition of data structure 자료구조란 무엇인가? ► 자료구조는 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법이다. [wiki] ► 자료구조는 추상자료형이다. 추상자료형은 무엇인가? ► 추상자료형은 객체의 명세와 그 연산의 명세가 객체의 표현과 연산의 구현으로부터 분리된 자료형이다. ► 추상자료형은 객체의 명세와 그 연산의 명세만을 의미한다. 채널목록에 대한 추상자료형은 무엇인가? ► 객체의 명세 : 채널번호와 채널이름 쌍들의 집합 ► 연산의 명세 : 검색연산, 삭제연산, 추가연산 ► 객체의 표현 : 채널번호와 채널이름 쌍들의 집합을 어떻게 저장할 것인가 ? ► 연산의 구현 : 위의 객체의 표현방법에 따른 연산의 실현 절차 Dept. of Multimedia Engineering, DongEui Univ.(10)

Examples of abstract data type 추상자료형의 예 ►C++ 의 각종 변수 : int, bool, float, double, char 등 ► 음료수자판기, 전화기를 포함하는 각종 가전제품 ► 채널목록은 추상자료형인가 ? ► 이 세상에 존재하는 모든 객체 ( 대상, 물건,…) 는 어떤 의미에서 추상자료형이다. Dept. of Multimedia Engineering, DongEui Univ.(11)

The 3 rd Definition of data structure 자료구조란 무엇인가? ► 자료구조는 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법이다. [wiki] ► 자료구조는 추상자료형이다. ► 자료구조는 잘 알려지고 유용한 추상자료형이다. 자료구조 교과목은 무엇을 다루는가? ► 잘 알려지고 유용한 추상자료형 리스트, 스택, 큐, 트리, 그래프 ► 상기 추상자료형에 대한 다양한 형태의 구현 객체의 표현 : 상기 객체를 어떻게 컴퓨터에 저장할 것인가 ? 연산의 구현 : 이러한 저장 방법에 대하여 연산은 어떻게 실현될 것인가 ? 추상자료형의 구현은 C++의 클래스를 이용하여 구현할 수 있다. Dept. of Multimedia Engineering, DongEui Univ.(12)

summaries 자료구조란 무엇인가? ► 자료구조는 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법이다. [wiki] ► 자료구조는 추상자료형이다. ► 자료구조는 잘 알려지고 유용한 추상자료형이다. 도대체 자료구조란 무엇인가? Dept. of Multimedia Engineering, DongEui Univ.(13)