23년 이전 글/자료구조
연결구조, 환형 연결리스트, 이중 연결리스트, 환형 이중 연결리스트
환형 연결리스트 개요 연결리스트의 제한성(어떤 특정 노드의 선행 노드를 찾기 위해 head부터 시작)을 해결하기 위한 자료구조 마지막 노드의 연결필드가 NULL이 아닌 첫 번째 노드의 주소를 가짐 한 노드에서 모든 노드로의 접근이 가능함 LINK를 따라 계속 순회하면 이전 노드에 접근이 가능함 삽입과 삭제가 용이함 탐색 시 무한반복이 발생함 - 헤드노드로 보완 리스트 전체를 가용공간 리스트에 반환할 때 리스트의 길이에 관계없이 일정 시간에 반환할 수 있음 환형 연결리스트의 ADT ADT CircularLinkedlist 데이터 0개 이상의 노드를 가진 유한순서 리스트(Element는 데이터 값) 연산자 및 연산내용 // CL∈CLinkedlist, n∈node, p∈position CLlinkedlist..
연결구조, 연결리스트, 단일 연결리스트
연결리스트(linked list) 연결리스트 자료구조가 생기게 된 배경 선형리스트(ordered list)의 구현 원소들간의 논리적 관계가 순차적으로 인접해 있는 자료구조의 배열을 이용한 구현함 배열의 적합성 - 주기억장치의 물리적인 구조가 인접되게 구성됨 - 순차적인 기억장소의 표현은 임의의 원소를 탐색하거나 스택이나 큐를 사용할 경우 자료의 삽입/삭제 등의 작업에 효율적임 배열의 부적합성 - 여러 개의 선형리스트를 사용하는 경우 각 리스트를 최대 크기의 배열(선언문에 의해서 고정된 기억장소를 유지)에 저장해야 하기 때문에 기억장소의 낭비를 초래할 수 있음 - 순차적인 기억장소 표현이 선형리스트에 적용되면 삽입/삭제 시 자료이동에 따른 처리시간의 비효율성이 발생함 연결리스트 자료구조의 특징 순차 자료구..
큐, 우선순위 큐, 데크
큐의 응용 응용 분야 FIFO 구조, 즉 먼저 요청한 작업에 대해 먼저 처리해주는 형태로 동작하는 큐의 특징을 직간접적으로 다양한 분야에 응용할 수 있음 컴퓨터 운영체제에서 실행을 요청한 작업들을 순서 대로 처리하기 위해서 큐(버퍼 큐와 프로세스 스케줄링 큐)를 사용함 산업공학분야에서 최적의 시스템을 설계하기 위한 시뮬레이션에서 대기행렬 큐를 사용함(공항에서 비행기들의 이륙, 은행에서 고객의 대기열) 실시간 시스템에서 인터럽트를 제어(first come firsst served)하는데 사용함 통신에서 데이터 패킷들의 모델링, 콜센터의 고객응대 시스템 등에서 사용함 프로그래머의 도구 및 많은 알고리즘에서 사용함 운영체제 작업 큐 프린터 버퍼 큐(buffer queue) 인쇄 작업에서 cpu에 비해 프린터의..
스택 자료구조
삽입/삭제가 제한된 자료구조 자료 성질에 따라, 삽입, 삭제하는 방법이 다름 프로그램에 내장된 자료구조가 아님 자료를 차곡차곡 쌓아 올린 형태 순서리스트의 특별한 자료구조 후입선출(LIFO : Last in First out) 프로토콜을 구현하는 자료구조 스택의 주소를 알여주는 포인터(top 위치에서만 원소를 삽입하므로 먼저 삽입한 원소는 밑에 쌓임 스택에 저장된 원소는 top로 정한 곳에서만 접근 가능 스택의 밑에서부터 스택의 크기까지의 범위를 가짐 스택의 ADT ADT Stack 데이터 0개 이상의 원소를 가진 유한 순서리스트 연산자 및 연산내용 //s∈Stack, e∈Element Stack createStack() //공백 스택을 생성 Stack push(s, e) //스택의 top에 원소 e를 ..