본문 바로가기

자료구조9

[자료구조] 5주차 - 정렬 (Sorting) Sorting 리스트 연산은 정렬된 리스트일 때 성능이 더 좋음 정렬 : 데이터를 정해진 키에 따라서 크기 순으로 배열 하는 것 O(n^2) 정렬 알고리즘 : 버블, 삽입, 선택, ··· 이동 기반 : 삽입 정렬 교환 기반 : 버블 정렬, 선택 정렬 O(n log n) 정렬 알고리즘 : 합병, 쾌속, ··· 분할 정복 방식(divide&conquer) : 합병, 쾌속 트리 구조 이용 : 히입 정렬 O(n^2) 정렬 : 삽입, 버블, 선택 삽입 정렬(Insertion sort) 추가(insert) 연산에 기반한 정렬 알고리즘 정렬되지 않은 리스트의 원소들을 차례로 정렬된 리스트에 추가하며 정렬을 수행 배열의 가장 앞자리부터 정렬된 부분 배열을 생성하고 그 크기를 증가시킴 void insert( int x,.. 2021. 1. 29.
[자료구조] 4주차 - 스택(Stack)과 큐(Queue) Stack 원소와 그 도착한 시간을 반대순서로 저장한 리스트 원소의 추가와 제거가 탑(top)이라 불리는 한 끝에서만 일어나는 리스트 Last-In First-Out (LIFO 또는FILO) push와 pop 스택의 자료구조 class Stack { int size; DataType *Items; int TOP; } 스택의 연산 생성 (CreateStack) void Stack::CreateStack( int_size ) { size = _size ; tItem= new Datatype[size]; TOP = 0; } 엠티 (IsEmpty) int Stack::is_Empty( ) { return ( TOP == 0 ); } 풀 (IsFull) int Stack::is_Full ( ) { return (.. 2021. 1. 28.
[자료구조] 3주차 - 연결 리스트 (Linked list) Linked List 원소들이 메모리에서 임의의 위치에 배치되어 있음 한 원소는 다음 원소를 가리키는 주소 (link, pointer)를 가지고 있음(포인터 기반의 자료구조) node = data + link, node는 메모리의 임의의 위치에 배치됨 단일 연결 리스트 (singly linked list) : node 당 하나의 link 정의 class node { data_type item; node *link; }; class hnode { node *link; }; 생성 void main ( ) { hnode first; } 검색 (선형 탐색만 가능) 보류 node *hnode::search( data_type item ) { return this->link->search ( item ); } no.. 2021. 1. 27.
[자료구조] 2주차 - 배열 (Array) List 리스트의 정의 유일한 원소들의 나열 각 원소들은 인덱스에 대응됨 List의 구현에는 Array와 Linked list가 있음 배열 (Array) : 메모리에 배열의 크기보다 더 큰 공간이 허용 될 때 사용 연결 리스트 (Linked list) : 연속된 공간이 없어도 사용 가능 Array 리스트를 index를 이용해서 구현한 구조 연속적으로 할당된 기억 공간 모든 언어에서 기본적으로 제공 모든 원소들이 index에 대응 n개의 자료를 하나의 주소로 접근 가능 기본 연산 - 생성(create), 인출(retrieve), 저장(store) 추가 연산 - 검색(search), 추가(insert), 제거(delete), ··· 검색(Search) 찾는 원소(key element)가 배열에 있는지 여부를.. 2021. 1. 26.