CS

01 (3) 02 삽입이나 삭제 연산을 하지 않는 나머지 데이터들을 전체적으로 한 칸씩 옮겨주어야 하므로 배열로 구현된 리스트가 가장 많이 실행시간이 소요된다. (1) 03, 04 ListNode *search(ListNode *L,element data){ //03 ListNode *temp = L->link;; for(temp;temp != L;temp = temp->link){ if(temp->data == data){ return temp; } } return NULL; } int get_size(ListNode* L){ //04 int count=1; ListNode *temp = L->link;; for(temp;temp != L;temp = temp->link){ count++; } retu..

7.5 연결 리스트로 구현한 스택 ● 연결된 스택(linked stack) : 연결리스트를 이용한 스택 - 크기가 제한되지 않은 채 동적 메모리 할당을 통해 새로운 요소를 삽입할 수 있다. - 동적 메모리 할당 및 해제에 소요되는 시간으로 인해 삽입과 삭제 시 소요 시간은 늘어난다. - top 변수를 가장 최근에 삽입된 데이터를 나타내는 정수가 아닌, 노드를 가리키는 포인터로 선언 typedef int element; typedef struct StackNode{ element data; struct StackNode* link; }StackNode; typedef struct{ StackNode *top; }LinkedStackType; 각 노드는 data 필드와 다음 노드를 가리키는 링크 필드로 이루..

7.1 원형 연결 리스트 ● 원형 연결 리스트의 소개, 정의, 처음에 삽입, 끝에 삽입 · 원형 리스트: 마지막 노드가 첫 번째 노드를 가리키는 리스트. - 마지막 노드의 링크 필드가 NULL이 아닌 첫 번째 노드 주소를 가리킨다. - 하나의 노드에서 모든 노드를 거쳐 자기 자신으로 되돌아올 수 있다. - 삭제나 삽입 시 선행 노드를 가리키는 포인터를 통해 연산이 용이해진다. - 특히 리스트의 끝에 노드를 삽입하는 연산 시 모든 노드를 다시 탐색할 필요 없이 헤드 포인터가 마지막 노드를 가리키도록 구성한다. 아래는 원형 리스트의 처음에 삽입하는 코드이다. ListNode* insert_first(ListNode* head, element data){ ListNode *node = (ListNode*)ma..

01 (2) 02 (1) 인덱스를 통해 바로 접근할 수 있다 03 (3) 04 (c) 05 p = p->link; 06 q = p; 07 D 08 (4) delete는 insert와 달리 탐색을 한 후 삭제를 해야되기 때문에 DQ부터 Xn까지의 탐색이 필요 09 ListNode* insert_last(ListNode* head,element item){ ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); newnode->data = item; newnode->link = NULL; ListNode* p = head; if(p==NULL) head = newnode; else { while(p->link !=NULL){ p = p->link; } p->li..

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-..