자료구조

[자료구조] 연결리스트- 변형된 원형 연결리스트

연결리스트 – 원형 연결리스트 원형리스트의 정의 및 특징 - 우리가 구현한 연결리스트의 (단순연결리스트) 마지막 노드 -> NULL 가르킴 그러면 그 마지막 노드가 첫번째 노드를 가리키게 하면 -> 원형 연결리스트!! - 즉 마지막 노드가 첫번째 노드를 가르켜서 연결의 형태가 원을 이루는 형태 - 원형 연결 리스트에서는 머리와 꼬리의 구분이 없다고 얘기 가능 왜? 결국 두가지 경우 모두 8이 가리키는 건 1이다. - 장점 : 머리,꼬리를 가리키는 포인터 변수를 각각두지 않아도 하나의 포인터 변수만 있어도 머리 , 꼬리에 노드를 간단히 추가 가능 변형된 원형 연결리스트 - 하나의 포인터 변수가 머리가 아닌 꼬리를 가리키게 한다면 새로운 노드가 추가 되었을 때 쉽게 추가가능 - 꼬리를 가리키는 포인터 변수?..

[자료구조]04. 연결리스트 - 연결리스트의 응용 (다항식)

다항식을 연결리스트로 표현해보는게 오늘 목표이다. 다항식의 각 항 = 하나의 노드 각각의 노드-> 계수, 지수, 링크 필드(그다음항을 가리킴)로 구성한다. 다항식의 첫번째 항을 가리키는 포인터로 각각의 다항식을 표현한다. tydef struct ListNode{ int num; int exp; struct ListNode *link; } ListNode; 연결리스트로 표현한 다항식의 덧셈 노드를 구성했다면 다항식들을 덧셈할 때는 포인터 변수 p,q를 설정하여 연산하면 된다. p,q가 가리키는 항의 지수에 따라 3가지로 나눠 각 항들을 덧셈할 수 있다. 1) 지수가 같은 경우 p,q를 더해서 0이 아니면 새로운 항을 만들어 -> 새로운 다항식에 추가(새로운 다항식 노드 만듦), p,q는 다음 항으로 이동 ..

[자료구조]04.연결리스트 (2)- 단순 연결

단순 연결리스트의 ADT/ 구현 새 노드를 추가할 때, 리스트의 머리와 꼬리 중 어디에 저장할 것인가? 머리에 추가한 경우 : tail 이 불필요, 저장된 순서 유지 불가 꼬리에 추가 : 저장된 순서 유지가능, tail이 필요함 문제 04-02 더미 노드를 적용했을 떄의 코드 변화를 확인하기 작성한 코드 head = (Node*)malloc(sizeof(Node));// 더미 노드 추가 tail = head;// 정렬 기능이 추가된 연결 리스트의 구조체와 헤더파일의 정의 연결리스트의 구현에서는 노드를 표현한 구조체의 정의는 빠지지 않는다. typedef struct_node { LData data; struct_node*next; } Node; 연결리스트의 구현에 필요한 변수들을 어찌 됐든 전역변수로 선..

[자료구조]03. 연결 리스트-자료구조

#include int main(void) { int arr[10]; int readCount = 0; int readData; int i; while(1) { printf("자연수 입력"); scanf_s("%d", &readData); if (readData < 1) break; arr[readCount++] = readData; } for (i = 0; i < readCount; i++) printf("%d", arr[i]); return 0; } 배열의 단점은 길이의 변경 불가능이다. 위의 예제에서 0이하의 값을 입력하지 않고 자연수만 입력을 하면 할당된 배열의 길이을 넘어선다. 그래서 메모리의 크기를 유연하게 하기 위해 등장한 것이 ' 동적인 메모리의 구성'이다. 이것이 오늘 내가 공부한 부분이..

[자료구조]01. 알고리즘의 성능분석 방법 - 시간복잡도 / 공간복잡도

시간복잡도와 공간 복잡도 우리는 잘 동작하고 좋은 성능까지 보장받기를 원하기 때문에 알고리즘을 분석 및 평가 할 수 있어야 한다. "알고리즘이 얼마나 빠르고 또는 느린가 " " 어떤 알고리즘이 어떠한 상황에서 메모리를 적게 쓰거나 많이쓰나" -> 알고리즘의 수행시간 "속도" -> 알고리즘이 필요로 하는 기억공간의 양 "메모리의 사용량" -> "시간 복잡도" -> " 공간 복잡도" 시간 복잡도 함수 시간복잡도는 알고리즘의 수행시간 분석을 뜻한다. 연산의 횟수를 통해 알고리즘의 빠르기를 판단한다. = 연산 횟수 통해 시간복잡도를 표시 연산의 수행횟수는 객관적인 근거이다. 데이터의 수를 x로, 연산횟수의 함수를 y로 설정하여 함수 T(n) 으로 구성한다. 왜 함수식으로 구성할까? 그 이유는 함수로 만들어놓으면..