스택 : 먼저 들어간 것이 나중에 나온다. 후입선출. LIFO(Last-In, First-Out) ex) 배열기반 스택 ArrayBaseStack.h #ifndef __AB_STACK_H__ #define __AB_STACK_H__ #define TRUE1 #define FALSE0 #define STACK_LEN100 typedef int Data; typedef struct _arrayStack { Data stackArr[STACK_LEN]; int topIndex; } ArrayStack; typedef ArrayStack Stack; void StackInit(Stack * pstack); int SIsEmpty(Stack * pstack); void SPush(Stack * pstack, Da..
앞에 우리가 구현한 연결 리스트의 마지막 노드는 NULL을 가리켰다. 이 마지막 노드가 첫 번째 노드를 가리키게 하면 '원형 연결 리스트'가 된다. 머리에 추가할려면 머리 하나만 필요. 꼬리에 추가할려면 꼬리도 필요. 장점이 반감 원형 연결 리스트의 장점 : 하나의 포인터 변수만 있어도 머리 또는 꼬리에 노드를 간단히 추가할 수 있다. 변형된 원형 연결 리스트 하나의 포인터 변수가 머리가 아닌 꼬리를 가리키게 하자. => 꼬리를 가리키는 포인터 변수 : tail 머리를 가리키는 포인터 변수 : tail->next 어렵지 않게 머리와 꼬리에 노드 추가 가능 ex) CLinkedList.h #ifndef __C_LINKED_LIST_H__ #define __C_LINKED_LIST_H__ #define TR..
자료구조를 제대로 공부하려면 다음 세가지 순서를 지켜서 공부 1. 자료구조의 ADT 정의 2. 정의한 ADT의 구현 3. 구현이 완료된 자료구조의 활용 ex) 연결 리스트. 간단 예제(ADT를 정의 X, 삽입, 삭제, 조회의 기능이 함수로 구분 X) #include #include typedef struct _node { int data; struct _node* next; } Node; int main(void) { Node* head = NULL; // NULL 포인터 초기화 Node* tail = NULL; Node* cur = NULL; Node* newNode = NULL; int readData; /**** 데이터를 입력 받는 과정 ****/ while (1) { printf("자연수 입력: ..
추상 자료형(Abstract Data Type) : 구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지를 나열한 것 리스트 순차 리스트 : 배열을 기반으로 구현된 리스트 연결 리스트 : 메모리의 동적 할당을 기반으로 구현된 리스트 리스트 자료구조 1. 리스트 자료구조의 ADT를 정의한다. 2. ADT를 근거로 리스트 자료구조를 활용하는 main 함수를 정의한다. 3. ADT를 근거로 리스트를 구현한다. ex) 순차 리스트 ArrayList.h #ifndef __ARRAY_LIST_H__ #define __ARRAY_LIST_H__ #define TRUE1 #define FALSE0 /*** ArrayList의 정의 ****/ #define LIST_LEN100 typedef int LDa..
재귀(Recursion)
재귀함수 : 어떠한 함수가 있을 때 자기 자신을 호출하는 함수 ex1) 팩토리얼 #include int Factorial(int n) { if(n==0) return 1; else return n * Factorial(n-1); } int main(void) { printf("1! = %d \n", Factorial(1)); printf("2! = %d \n", Factorial(2)); printf("3! = %d \n", Factorial(3)); printf("4! = %d \n", Factorial(4)); printf("9! = %d \n", Factorial(9)); return 0; } ex2) 피보나치 수열 #include int Fibo(int n) { printf("func call p..
시간 복잡도(Time Complexity) : 어떤 알고리즘이 어떠한 상황에서 더 빠르고 더 느리냐 공간 복잡도(Space Complexity) : 어떤 알고리즘이 어떠한 상황에서 메모리를 적게 쓰고 또 많이 쓰냐 순차 탐색(Linear Search) T(n)=n #include int LSearch(int ar[], int len, int target) { int i; for (i = 0; i < len; i++) { if (ar[i] == target) return i; // 찾은 대상의 인덱스 값 반환 } return -1; // 찾지 못했음을 의미하는 값 반환 } int main(void) { int arr[] = { 3, 5, 2, 4, 9 }; int idx; idx = LSearch(arr,..