Data Structure

실습과제 3.2 ◆ 3.1에서 구현한 연결리스트에 기능을 추가해 보자 ■ 노드 탐색 ● 특정 위치의 노드를 찾는 기능 ● 해당 위치의 노드의 주소를 반환 Node* Get_Node(Node* head, int pos); ■ 노드 삭제 ● 임의의 위치에 있는 노드를 삭제하는 기능 void Remove_Node(Node** head, Node* targetNode) ■ 노드 삽입 ● 임의의 위치에 새로운 노드를 삽입하는 기능 void Insert_Node_After(Node* currentNode, Node* newNode) ■ 코드: (1) 헤더파일 (2) 함수 기능 구현 파일 (3) 메인 함수 ■ 실행결과: ■ 과제에 대한 고찰: Append_Node()와 Remove_Node() 함수의 경우 인자로 N..

실습과제 3.1 ◆ 기본적인 연결리스트를 구현해 보자 1) 아래 세 함수를 구현 Node* Create_Node(int newData); void Destroy_Node(Node* node); void Append_Node(Node** head, Node* newNode); ■ 코드: ■ 실행결과: ■ 과제에 대한 고찰: 동적으로 메모리 공간을 관리하며 빈번하게 삽입/삭제가 일어나는 응용문제에 적합한 연결리스트에 대해 알아보고 구현해보았다. 처음 배우는 형태의 자료구조여서 이해하는데 약간의 시간이 걸렸다. 또한 주소값을 통해 값을 변경하고 노드를 추가하고 하다 보니 더블포인터의 개념도 나왔고 아직 포인터에 대한 개념이 제대로 잡히지 않아서 이를 이해하고 코드로 구현하는 데까지 많은 시간이 걸렸다.

실습과제 2.3 ◆ 알고리즘 Poly_Add를 구현해 보자. 1) 아래의 예시를 이용하여 실행 ■ 코드: ■ 실행결과: 2) 두 다항식 A, B의 차수를 모두 동일하게 설정하고 실행 ■ 코드: ■ 실행결과: 3) 두 다항식 A, B의 차수를 모두 다르게 설정하고 실행 ■ 코드: ■ 실행결과: 4) 위 세 가지 경우에 대한 수행시간 논의 m : 다항식 A에서 계수가 0이 아닌 항수 n : 다항식 B에서 계수가 0이 아닌 항수 Worst case 수행시간 : O(m+n) , 두 다항식의 차수가 모두 다름 Best case 수행시간 : O(m) or O(n), 두 다항식의 차수가 모두 같음 ■ 과제에 대한 고찰: 다항식 덧셈 문제의 해결을 위해서 구조체형 배열을 사용하여 자료구조를 설계하였다. 배열 기반의 다..

실습과제 2.2 ◆ 희소행렬 A의 전치행렬 B를 구하는 3번째 알고리즘을 구현하여라. ■ 입력: ■ 출력: ● 입력으로 주어진 희소 행렬 Sparse_A를 이용해 전치행렬 S_b를 계산한다. ● S_b에 저장한 정보를 이용하여 0을 포함한 전치행렬 전체 항을 화면에 출력한다. ■ 조건: ● 실습 과제 1에서 작성한 코드에 아래의 함수를 추가 구현 ● Element* Transpose_Triple2(Element S_a[]) 함수 구현 ■ 코드: ■ 실행결과: ■ 과제에 대한 고찰: - 실습 과제 1이 수행 공간을 고려하나 수행시간을 고려하지 않은 알고리즘이라는 한계점이 있던 반면에 이번 과제는 row의 빈도수를 저장하는 배열(row)와 위치 정보를 저장하는 배열(pos)이라는 추가 저장 공간을 만들어 p..

실습과제 2.1 ◆ 희소행렬 A의 전치행렬 B를 구하는 2번째 알고리즘을 구현하여라. ■ 입력: ■ 출력: ● 입력으로 주어진 희소 행렬 Sparse_A를 이용해 전치행렬 S_b를 계산한다. ● S_b에 저장한 정보를 이용하여 0을 포함한 전치행렬 전체 항을 화면에 출력한다. ■ 조건: ● Element* Transpose_Triple1(Element S_a[]) 함수 구현 ● void Print_Sparse_Mat (Element arr[]) 함수 구현 ■ 코드: ■ 실행결과: ■ 과제에 대한 고찰: - 기존의 코드는 시간복잡도와 공간복잡도를 고려하지 않은 단순한 코드였다. 따라서 0이 아닌 실제 값을 담고 있는 행, 열 정보를 담은 배열을 만들어 이를 통해 전치행렬을 만들어 주었다. 하지만 이 코드 ..

실습과제 1.1 ◆ n x n 행렬이 주어졌을 때 이 행렬의 전치 행렬을 구하는 알고리즘을 의사코드로 기술한다. ■ 입력: ● 정수 값들로 구성된 2차원 n x n 행렬이 배열 A에 저장되어 있다고 가정한다. ● A[i,j] 는 2차원 행렬에서 i번째 행과 j번째 열의 값이 저장된 배열의 원소를 의미한다. ■ 출력: ● 입력으로 주어진 2차원 행렬 A의 전치행렬을 계산하여 2차원 행렬 B에 저장한다. ● 전치 행렬은 행과 열의 값이 뒤 바뀐 행렬을 의미한다. ■ 조건: ● 해당 알고리즘을 의사 코드로 작성 ● 해당 알고리즘의 시간 복잡도를 계산하여 빅오 표기법으로 표현 ■ 실행결과: ● 의사 코드이므로 따로 실행결과는 없다. ■ 과제에 대한 고찰: - 여태껏 코드를 작성하기 전에는 항상 머릿속으로만 이러..