CS

202~208p LAB ListNode* search_list(ListNode* head,element x){ ListNode* p = head; while(p !=NULL){ if(p->data == x) return p; p=p->link; } return NULL; } int where_is_x(ListNode* head,element x){ ListNode* p = (ListNode*)malloc(sizeof(ListNode)); p = head; int count =1; ListNode* search = search_list(head,x); if(search != NULL){ while(p!=search){ count++; p=p->link; } return count; } else{ count..

6.1 리스트 추상 데이터 타입 ● 리스트: 항목들이 순서 또는 위치를 가진 채로 차례대로 저장돼 있는 자료구조 - 기호로 L = (item0, item1, item2, ... , item n-1)과 같이 나타낸다. - 리스트의 기본적인 연산으로는 새로운 항목 추가(삽입), 항목 삭제(삭제), 특정한 항목 찾기(탐색) 등이 있다. ● 리스트의 구현 최상단 그림처럼 리스트는 배열과 연결 리스트를 이용하여 구현할 수 있다. 배열 리스트는 구현이 쉽고 빠르지만 크기가 고정되고, 연결 리스트는 크기가 제한되지 않고 중간에 삽입이나 삭제를 유연하게 구현할 수 있지만 구현이 복잡하고, i번째 항목을 추출하려고 할 때는 배열을 사용할 때보다 시간이 오래 걸린다. 6.2 배열로 구현된 리스트 ● 리스트의 정의, 기초 ..

01 (a) 02 front는 첫 번째 요소의 바로 앞을 가리키기 때문에 인덱스 4, 5 에만 요소가 저장돼있으므로 (b) 03 40,50 04 (c) 05 (2) 06 | 0 1 2 3 4 | ㅡ ㅡ ㅡ ㅡ ㅡ | C A D | 07 q->data[index] 와 같이 index로 바로 접근하므로 O(1)의 시간복잡도를 가진다. (a) 08 element get_count(QueueType *q){ element count=0; if(q->front rear){ count = (q->rear - q->front); } else if(q->front > q->rear){ count = MAX_QUEUE_SIZE - (q->front - q->rear); } return count; } 09 #i..

5.5 덱이란? ● 덱: deque(Double-ended queue)는 이름 줄임말처럼, 큐의 front와 rear에서 모두 삽입, 삭제가 가능한 큐이다. *여전히 중간에 삽입하거나 삭제하는 것은 허용하지 않는다. add_front, delete_front -> 스택의 push, pop add_rear, delete_front -> 큐의 enqueue, dequeue delete_rear -> 덱만 가지는 연산 원형큐 코드에 delete_rear, add_front, get_rear 연산을 추가하면 된다. *add_rear는 enqueue, delete_front는 dequeue, get_front는 peek연산과 동일하다. add_front와 delete_rear는 각각 배열의 앞과 뒤에서 인덱스를 ..

5.1 큐 추상 데이터 타입 ● 큐: 뒤(rear)에서 새로운 데이터가 추가되고 앞(front)에서 데이터가 하나씩 삭제되는 구조로 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO: First-In First-Out) 방식을 따른다. - 스택은 삽입과 삭제가 같은 쪽에서 일어나지만 큐에서는 삽입과 삭제가 다른 쪽에서 일어난다. - 따라서 스택에선 top이라는 변수 하나만 사용됐지만 큐에서는 front와 rear 두 변수가 사용된다. - enque는 rear쪽에 삽입 연산을, deque는 front쪽에 삭제 연산을 수행한다. - 은행에서 대기하는 사람들의 대기열, 공항에서 이륙하는 비행기들 등 많은 분야에서 큐를 사용한다. - 컴퓨터와 주변기기 사이에서 속도 차이를 해결하여 CPU를 효율적으로 사용하기..

01 (1) 02 (2) 03 10, 20 04 (4) 05 (1)일 때 공백상태, (3)일 때 포화상태 06 (3) 07 (1) 08 1 → 1, 2 → 1, 2, 3 → 1, 2 → 1, 2, 4 → 1, 2, 4, 5 → 1, 2, 4 09 A a, b, c B d → A a, b B d, c → A a, b, c B d → A a, b, c B 'empty' 10 #include #include #define MAX_ARR_SIZE 6 typedef int element; typedef struct{ element *data; int capacity; int top; }StackType; void init_stack(StackType *s){ s->top=-1; s->capacity = 1; s-..

4.4 스택의 응용: 괄호 검사 문제 괄호는 항상 쌍이 되게끔 사용하여야 한다. 대괄호 [ ], 중괄호 { }. 소괄호 ( ) 등이다. 조건1: 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다. 조건2: 같은 종류의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다. 조건3: 서로 다른 종류의 왼쪽 괄호와 오른쪽 괄호 쌍은 서로를 교차하면 안 된다. 왼쪽 괄호들을 스택에 쌓다가 오른쪽 괄호가 나오면 스택의 최상단부터 괄호가 매칭되는지 검사한다. 괄호짝이 맞는지(조건 3 위배), 스택이 비어 있지는 않는지(조건 1, 조건2 위배), 마지막 괄호까지 처리했는데 스택이 비어있지 않은 지(조건1 위배)를 체크해 준다. #include #include #include #define MAX_STACK_S..

4.1 스택이란? ● 스택 : 입출력이 최상단에서만 이루어지는 선형 나열 구조로, 가장 최근에 들어온 입력값이 가장 먼저 나가는 후입선출(LIFO: Last-In First-Out) 방식을 따른다. - 입출력이 이뤄지는 최상단을 스택 상단(stack top), 반대쪽인 바닥을 스택 하단(stack bottom)이라고 한다. - 스택에 저장되는 것을 요소(element), 스택이 요소가 하나도 없이 비어있으면 공백 스택(empty stack)이라고 한다. - 자료의 출력순서가 입력순서의 역순으로 이루어져야 할 경우에 긴요하게 사용된다. 컴퓨터에서 함수 호출이 이루어질 때, 호출된 함수는 실행이 끝나면 자신을 호출했던 함수로 되돌아가야 한다. 이 때 시스템 스택은 함수가 호출될 때마다 활성 레코드(activ..

01 (4) 4*10*20 = 800 02 (4) 1000 + 4* 10 = 1040 03 (2) (1) 40 (2) 80 (3) 40 (4) 40 04 int main(){ int two[10]; for(int i=0; iwords); free(t); return 0; }

17. 순환적인 이항계수 / 반복적인 이항계수 (반복에서는 팩토리얼만 구현 후 이항계수 공식에 대입) int binomial(int n,int k){ if(k==0 || k==n) return 1; else return binomial(n-1,k-1)+binomial(n-1,k); } int factorial(int n){ int result=1; for(int i=1;i