전공 깍두기/데이터 구조 조각 (14) 썸네일형 리스트형 [데이터 구조] 퀴즈 정답 및 해설 | 1~13차시 [ 2차시 ] 정답: 구현 정답: 4번 설계 해설: 설계 단계의 핵심 단어는 '알고리즘'이다. 정답: 2번 구현 레벨 해설: Abstract(추상화)는 구현과 거리가 멀다 정담: 2번 ADL 변환기 정답: 3번 해설: 특정 Programming 언어로 작성되어 있지 않다. 이건 목적이다. 정답: 2번 해설: x [데이터 구조] 13차시 스택(Stack) | 추상 데이터 타입(ADT), 순차 표현, 연결 표현, 복수 스택, C 구현 모듈 1. 스택 ADT와 순차 표현 1. 스택 추상 데이터 타입 1) 스택(Stack)이란? "쌓아 놓은 더미" - 정의: 삽입과 삭제가 한쪽 끝, top에서만 이루어지는 유한 순서(순서가 중요한) 리스트 - finite ordered list 2) 스택의 특징 - 후입선출(LIFO:Last-In First-Out, FILO: First-In Last-Out 구조) 리스트 특징: 가장 최근에 들어온 데이터가 가장 먼저 나감 기능: 삽입(push), 삭제(pop) 별명: 스택을 pushdown 리스트라고도 함 3) 스택 기본 연산 - push(): 스택에 데이터를 추가 - pop(): 스택에서 데이터를 삭제 - create(): 빈 스택을 생성 - is_empty(s): 스택이 공백 상태인지 검사 - is.. [데이터 구조] 12차시 헤더 노드와 다항식의 리스트 표현 | 덧셈 1. 헤더 노드 1) 기존 연결 리스트 처리 알고리즘 - 문제점: 첫 번째 노드나 마지막 노드, 그리고 리스트가 공백인 경우에 따라 처리 방법이 각기 달라, 서로 예외적인 경우로 처리해야 함 2) 헤더 노드(header node)를 추가하는 방법 - 상기 문제가 되는 예외 경우를 가급적 제거하고, 코드를 간단하게 하기 위한 해결책으로 사용 가능 - 헤더 노드에는 리스트를 처리하는데 1️⃣필요한 포인터나 2️⃣통계 정보를 미리 저장 리스트의 첫 번째 노드를 가리키는 포인터 리스트의 길이 마지막 노드를 가리키는 포인터 등의 필요 정보 ⭐헤더 노드의 구조가 리스트의 노드 구조와 달라도 문제 없음 3) 헤더 노드를 가진 연결 리스트의 정의 typedef struct listNode { /*리스트 노드 구조*/ .. [데이터 구조] 11차시 연결 데이터 표현 | 자유 공간 리스트, 원형 연결 리스트, 이중 연결 리스트 모듈1. 자유 공간 리스트 1) 메모리의 획득과 반납 방법 (1) 연결 리스트가 필요로 하는 두 가지 연산 [방법 1] : 데이터 필드와 링크 필드를 가진 하나의 공백 노드를 획득하는 방법 (프로그램 수행 중, 즉석에서 필요한 메모리를 OS에서 malloc()하는 방식) [방법 2] : 사용하지 않는 노드는 다시 반납하여 재사용하는 방법 (미리 malloc()하여 free space list를 만든 후, 여기서 할당/회수하는 방식) (2) [방법 2] 자유 공간 리스트(free space list)를 만들어 놓은 경우 - OS와 분리를 해보자! 추가로 우리가 만들어야 하는 함수1 : getNode() - malloc() 대응 : 데이터와 링크 필드로 되어 있는 새로운 공백 노드를 free space li.. [데이터 구조] 10차시 연결 데이터 표현 | 단순 연결 리스트 (2) 1. 단순 연결 리스트의 구체적 구현(C Implementation) 1) 리스트 생성 알고리즘 2) 원소를 첫 번째 노드로 삽입 3) 노드의 삽입 - 주어진 리스트 L에서 원소 값이 x인 노드를 p가 가리키는 노드 다음에 삽입 - 코드로도 확인해보자 insertNode(L, p, x) // 리스트 L에서, p 노드 다음에 원소 x를 삽입 // p가 null인 경우는, 현재 pointing하는 노드가 없는 경우임 newNode [데이터 구조] 9차시 연결 데이터 표현 | 단순 연결 리스트 1. 단순 연결 리스트의 정의 및 특징 정의: 하나의 링크 필드를 가진 노드들이, 모두 자기 후속 노드와 연결되어 있는 노드 열(list) 특징: 마지막 노드의 링크 필드는 리스트의 끝을 표시하는 null 값을 가짐 별칭: 선형 연결 리스트(linear linked list), 단순 연결 선형 리스트(singly linked linear list), 연결 리스트(linked list), 체인(chain) 2. 삽입과 삭제 연산 개념 1) 원소 삽입 연산 (1) Node 삽입 연산이란? list에는 포인터 변수, ptr이 가리키는 list로서, 기존에 10과 20이 있음. list의 추적을 위한 포인터 변수, node_tracer를 선언하고 이를 ptr과 같은 노드를 지칭하게 함 50을 가진 새로운 노드를.. [데이터 구조] 8차시 노드와 포인터 | C언어 포인터 1. 노드와 포인터 1) 배열의 순서 리스트 표현 리뷰 - Orderd list(순서 리스트)에 있어서 임의의 위치에 대한 삽입, 삭제 비용이 크다. [bat, cat, nature, orphan, test] -> 이들은 물리적 메모리 공간에 연속적으로 write되는 특성을 가진다! "Fast but inconvenient!!" - 순서 리스트 L의 순차 표현과 원소 삽입 - 순서 리스트 L의 원소 삭제 - 배열로 순서 리스트를 표현할 때 장점 1️⃣ 표현이 간단함 2️⃣ 빠른 임의 접근(Immediate Random Access): 인덱스는 직접 메모리 주소로 변환할 수 있기 때문에 원소 접근이 빨라짐 - 배열로 순서 리스트를 표현할 때 단점 1️⃣ ! 순차적으로만 ! 표현할 수 있음 2️⃣ 어떤 작업.. [데이터 구조] 7차시 희소 행렬 추상 데이터 타입과 희소 행렬 연산의 C 구현 | ADT 모듈1. 희소 행렬 ADT 1) Sparse Matrix란? - 일반적으로 matrix는 m개의 행(row)과 n개의 열(column)로 구성되며, m * n(m by n으로 읽음)으로 표시된다. - 36개 element 중 8개의 element만이 non-zero임 → Sparse Matrix(희소 행렬): 0이 아닌 element가 희소한 행렬 2) Sparse Matrix의 표현 2차원의 경우는 (row, col, Non-0 value)로 표현됨 3차원의 경우는 (row, col, depth, Non-0 value)로 표현됨 3) Sparse Matrix ADT(2차원) 모듈2. 희소 행렬 연산의 C 구현 참고하면 좋을 블로그 https://m.blog.naver.com/nabilera1/22204.. 이전 1 2 다음
