C 자료구조
-
Linked List의 활용 - 파일 입출력 활용C 자료구조/2. 연결 리스트 2021. 3. 24. 21:42
작업 환경은 Visual Studio 2008 우선 아래는 우리가 읽어올 파일의 내용이다. 각 줄은 배우에 대한 정보들이다. 배우에 대한 정보들이 여러 개이므로 우리는 구조체가 필요함을 알 수 있다. 위의 파일은 당연히 프로젝트 폴더 내에 존재해야 한다. 아래의 그림은 이 프로젝트 폴더 내부이다. 아래는 배우에 대한 구조체 정보와 이 정보들을 저장할 때 필요한 변수들이다. 위의 Actor 구조체에서 유심히 봐야할 변수는 MovieFilmCount와 MovieFilmTitle이다. 배우마다 출연작품의 수는 다르다. 위의 파일 내용을 보면 알 수 있다. 그렇기 때문에, 결론적으로 배우의 출연작품의 제목(문자열)을 저장하는 변수인 MovieFilmTitle는 데이터 유형이 이중 포인터가 되어야 한다. 예를 들..
-
Linked List의 활용 - 다항식의 표현 및 기본 연산C 자료구조/2. 연결 리스트 2021. 3. 24. 17:53
다항식의 항이 지수와 계수로 표현된다고 하자. 다항식은 기본적으로 지수가 높은 항이 먼저 나온다. 즉, 지수에 대한 내림차순이 필요하다. 항을 다항식에 저장할 때, 적당한 위치를 찾아 삽입을 하면 된다. 이 역할을 할 함수의 이름은 SortInsertNode이다. 즉, 연결리스트에 지수값을 큰 값 순으로 저장을 하면 된다. 이는 앞의 내용을 이용하면 쉽게 구현할 수 있다. 아래 글의 SortInsertNum 함수를 적당히 변형해서 만들 수 있다. 차이는 정렬함수의 부등호의 방향만 바꿔주면 된다. designatedroom87.tistory.com/387 Linked List - 여러 가지 연산 아래의 포스트에는 기본적인 연산만을 작업했다. 여기서는 데이터의 중복 삭제, 데이터의 중간 삽입 등에 대한 연산..
-
Linked List - 리스트를 역순으로 바꾸기C 자료구조/2. 연결 리스트 2021. 3. 24. 16:38
아래의 연결 리스트 파일들을 그대로 가지고 와서 구현을 한다. designatedroom87.tistory.com/42?category=868808 Linked List - 기본 연산 2. 구현 프로그래밍은 -1이 입력될 때까지 입력된 데이터를 연결 리스트에 추가한다. 프로그램 실행결과 3. 헤더 파일 & 소스 파일 designatedroom87.tistory.com 1. 개념 세 개의 포인터 p, q, r 포인터를 사용하여 연결 리스트를 순회하면서, 링크의 방향을 역순으로 바꾸면 된다. 주의 사항은 링크의 방향을 역순으로 바꾸기 전에 미리 뒤의 노드를 알아놓아야 한다. p는 아직 처리 되지 않은 노드..
-
Linked List - 여러 가지 연산C 자료구조/2. 연결 리스트 2021. 3. 24. 11:06
아래의 포스트에는 기본적인 연산만을 작업했다. 여기서는 데이터의 중복 삭제, 데이터의 중간 삽입 등에 대한 연산에 대해 구현할 것이다. 여기서 할 작업은 아래의 내용과는 이어지지 않는다. designatedroom87.tistory.com/42?category=868808 Linked List - 기본 연산 2. 구현 프로그래밍은 -1이 입력될 때까지 입력된 데이터를 연결 리스트에 추가한다. 프로그램 실행결과 3. 헤더 파일 & 소스 파일 designatedroom87.tistory.com 아래는 노드 구초체와 head 와 노드의 개수를 전역 변수로 두었다. 전역 변수로 둔 이유는 약간 문제를 쉽게 풀..
-
Open Hashing - ChainingC 자료구조/Hash 2020. 11. 7. 22:26
참고 문헌 뇌를 자극하는 알고리즘, 쉽게 풀어쓴 자료구조 개념 구현할 방식은 Chaining방식이다. 해시 주소가 같은 탐색 키들을 하나의 리스트로 묶어둔다면 불필요한 비교는 하지 않아도 될 것이다. 이러한 리스트는 그 크기를 예측할 수 없으므로, 연결 리스트로 구현하는 것이 가장 바람직하다. 각 버킷에 고정된 슬롯을 할당하는 것이 아니라, 각 버킷에 삽입과 삭제가 용이한 연결리스트를 할당한다. 당연히 버킷 내에서 원하는 항목을 찾을 때는 연결리스트를 순차 탐색한다. 예를 들어, 크기가 7인 해시 테이블에 h(k) = k mod 7 의 해시 함수를 이용하여 8,1,9,6,13을 삽입할 때에의 체이닝에 의한 충돌 처리를 보자. 1. h(8) = 8 mod 7 = 1 (저장) 2. h(1) = 1 mod 7..
-
Spanning TreeC 자료구조/Graph 2020. 10. 15. 21:51
0. 참고 문헌 1. 개념 신장 트리( Spanning tree )란 그래프 내의 모든 정점을 포함하는 트리이다. 신장 트리는 트리의 특수한 형태이므로, 모든 정점들이 연결되어 있어야 하고, 또한 사이클을 포함해서는 안 된다. 따라서, 신장 트리는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결하게 된다. 그래프에서 신장 트리를 찾으려면 깊이 우선 탐색이나 너비 우선 탐색을 사용할 수 있다. 하나의 그래프에는 많은 신장 트리가 존재 가능하다. 여기서는 깊이 우선 탐색 방법을 사용한다. 아래에 하나의 그래프가 주어졌다고 가정하자. 아래의 그림들은 모두 위의 그래프에서 시작정점을 바꾸어 가면서 깊이 우선 탐색 혹은 너비 우선 탐색을 해서 만든 신장 트리의 일부이다. 첫 번째 신장 트리 그래프..
-
스택의 활용 - 미로 탐색C 자료구조/3. 스택( Stack ) 2020. 9. 16. 18:13
참고 문헌 설명 미로에서 탈출하기 위해서는 미로를 체계적으로 탐색하여야 할 것이다. 출구를 찾는 기본적인 방법은 시행 착오 방법으로서 하나의 경로를 선택하여 한 번 시도해보고 안되면 다시 다른 경로를 시도하는 것이다. 문제는 현재의 경로가 안 될 경우에 다른 경로를 선택해야 한다는 것으로 가능한 경로들이 어딘가에 저장되어 있어야 한다. 그리고, 현재 위치에서 가능한 경로 중에서 가장 가까운 경로이면 좋을 것이다. 따라서 가능한 경로들이 저장되는데 그 중에서 가장 최근에 저장한 경로가 쉽게 추출되는 자료구조를 사용해야 할 것이다. 따라서 결론은 "스택"이 후보가 된다. 현재 위치에서 갈 수 있는 칸들의 좌표를 스택에 기억하였다가 막다른 길을 만나면 가장 가깝고, 아직 가보지 않은 칸으로 다시 돌아가서 새로..
-
List SortC 자료구조/Sort Basic 2020. 9. 15. 19:25
구현 방식에는 두 가지 방법이 있다. 1. 데이터를 리스트에 모두 저장하고 나서 리스트 정렬하는 방식 리스트에서 먼저, 정수값이 들어있는 배열(정렬되지 않은 )을 리스트에 데이터를 다 집어 넣고나서, 해당 리스트에서 정렬을 하는 방법을 만들어 보고자 한다. 정렬을 할 때, 여기서 버블 정렬을 이용했다. 프로그램 실행결과 소스 파일 2. 데이터를 리스트에 저장하면서, 리스트를 정렬하는 방식 배열의 데이터를 리스트에 넣어줄때, 정렬을 하면서 노드 생성하는 것을 만들어 볼 것이다. 두 가지 방식으로 만들어 볼 수 있다. 두 함수들을 차례로 보자. 아래는 나머지 부분이다. AddDataTwo함수의 실행결과 AddDataOne함수의 실행결과 소스 파일