자료구조
-
추가적인 리스트 연산자료구조 2022. 7. 12. 13:31
📌 추가적인 리스트 연산 💡 추가적인 리스트 연산들 단일 연결 리스트(Chain) 에 대한 연산 체인의 방향을 반대로 : invert() 두 개의 체인을 통합 : concatenate() 원형 리스트에 대한 연산 원형 연결리스트의 길이를 계산하는 연산 : length() 원형 연결리스트의 제일 앞에 새로운 노드 삽입 : insert_front() 💡 Invert 함수 포인터 3개를 사용해 가리키는 포인터를 변경해준다. lead, middle, tail 세 개의 포인터를 사용한다고 하면, return 값은 middle 이다. 💡 concatenate 함수 A 체인 혹은 B 체인이 NULL 일 경우, 나머지를 반환한다. A를 순회하면서 접근하고, A 마지막 노드의 포인터를 B로 가리켜준다. 💡 원형 연결리스..
-
연결리스트의 개념자료구조 2022. 7. 10. 13:47
📌 연결리스트의 개념 💡 자기참조 구조체 동일한 타입의 구조체에 대한 포인터를 속성으로 포함하는 구조체 Link Node 구조체에 대한 포인터 -> 메모리의 주소를 가리키는 자료형 여러 개의 Node 구조체를 연결하는 역할 💡 연결리스트 단순 연결리스트(Singly Linked List) 자기 참조 구조체(Node)들의 연결 천번째 노드에 대한 포인터만 유지 리스트의 이름 = 첫번째 노드의 수조 이후 노드들은 구조체의 Link 포인터를 통해 참조 마지막 노드의 Link 포인터는 NULL로 설정한다. 다른 연결리스트 이중 연결 리스트(Doubly Linked List) 앞 뒤의 노드들의 정보를 가지고 있다. 원형 연결 리스트(Circular Linked List) 마지막 노트와 첫노드를 연결 연결리스트 연..
-
배열을 이용한 희소행렬의 표현자료구조 2022. 7. 10. 13:46
📌 배열을 이용한 희소행렬의 표현 💡 희소행렬 행렬의 표현 2차원 배열 : Array[MaxRows][MaxCols] 0이 많이 포함된 경우, 희소행렬이라고 한다. 0이 아닌 데이터의 수 배열 맨 처음에 행렬의 정보기록 = (행, 열, 0이 아닌 데이터의 수) 💡 행렬의 전치 전치연산 (Transposing a Matrix) row & column 을 교환 를 희소행렬 M의 어디에 저장하는가? -> -> -> 전치연산을 위한 연속적인 삽입으로 인해 기존에 저장된 항목들..
-
배열을 이용한 다항식의 표현자료구조 2022. 7. 10. 13:44
📌 배열을 이용한 다항식의 표현 💡 순서리스트 (Orderd List) 데이터들의 순서가 유지되는 집합 집합이란, 원소들의 모임, 순서를 중요시 하지 않음. 한 주의 요일들 섞여진 카드들 미국의 2차 세계 대전 참전 연도 스위스의 2차 세계 대전 참전 연도 (원소가 없는 집합도 순서리스트에 포함된다.) 💡 순서리스트의 연산 순서리스트에 적용 가능한 연산들 리스트 길이 연산 리스트의 모든 데이터들을 왼쪽에서 오른쪽으로 읽기 리스트로부터 i번째 데이터를 검색 리스트로부터 i번째 데이터를 교체 리스트의 i번째 위치에 새로운 데이터 추가 (i번째 이후에 있던 데이터는 한 칸씩 밀림) 리스트의 i번째 위치에 있는 데이터를 삭제 (i번째 이후에 있던 데이터는 한 칸씩 당겨짐) 💡 다항식 소개 순서리스트를 구현하는 ..
-
배열과 구조체의 정의자료구조 2022. 7. 10. 13:42
📌 배열과 구조체의 정의 💡 배열의 정의 배열이란? 동일한 데이터 타입의 데이터들을 묶는 구조 메모리의 연속된 위치에 차례대로 저장(Index, Data) 쌍의 집합 배열에 적용 가능한 연산 인덱스 i 번째에 저장된 데이터를 출력 인덱스 i 번째에 데이터 d 를 저장 배열의 저장된 데이터의 수는 얼마인가? 💡 구조체 구조체의 정의 하나 이상의 기본 자료형을 기반으로 사용자 정의 자료형을 만들 수 있는 문법요소 다양한 자료형을 포함한다. 구조체 비교 구조체의 내용이 동일한지를 검사하는 방법은 모든 속성이 같은지 하나씩 비교하는 것이다. 💡 자기 참조 구조체 정의 : 자기 자신을 가리키는 포인터를 속성으로 갖는 구조체 연결리스트에 많이 사용된다.
-
알고리즘의 복잡도 계산자료구조 2022. 7. 6. 15:07
📌 알고리즘의 복잡도 계산 💡 성능분석 주어진 문제를 해결 정확성 문서화 얼마나 주석을 잘 달았는가? / 관련 문서가 얼마나 잘 작성되었는가? 모듈화 함수를 얼마나 체계적으로 잘 나누었는가? 가독성 변수 또는 함수의 이름이 얼마나 의미있게 쓰였는가? 공간 효율성 시간 효율성 필수적인 요소 - 1, 2 좋은 프로그래밍의 습관 - 3, 4, 5 성능과 관련 - 6, 7 💡 성능 분석 VS 성능 측정 성능 분석 시뮬레이션, 복잡도 성능 측정 실제로 실행시켜서 실행 시간을 측정 💡 복잡도의 정의 공간 복잡도 : 프로그램 실행에 사용되는 메모리 시간 복잡도 : 프로그램 실행에 걸리는 시간 💡 시간복잡도 실행에 걸리는 시간(T[p]) = 컴파일 시간 + 실행 시간 컴파일 시간은 고정 and 한번만 필요 T[p]는 ..
-
자료구조의 정의와 알고리즘의 정의 및 표현자료구조 2022. 7. 5. 16:57
📌 자료구조 💡 정의 문제해결을 위해 데이터를 조직하여 표현하는 방법 전화번호부 - List, Linked List, Tree 수강신청, 대기열 - Queue 지하철 노선도 - Graph 💡 중요성 주어진 문제의 특성에 맞는 자료구조를 선택한다. 프로그램의 개발이 쉽고 성능이 향상한다. 💡 추상 데이터 타입 (Abstract Data Type) 자료구조를 기술할 때 사용하는 방법 데이터 객체 및 연산명세와 데이터 객체 내부 표현양식 / 연산의 구현 내용을 분리 사용자가 원하는 서비스를 표현하는 부분과 서비스를 내부적으로 구현하는 부분을 분리하겠다. Ada Package, C++ Class ADT에서 연산의 명세 구성요소 : 함수 이름, 인자들의 타입 함수의 호출 방법 및 결과물이 무엇인지를 설명 함수의 ..