Written by nodejs-style
on 2021-08-25

6주차. 자료구조

연결리스트

메모리의 여러 군데에 나뉘어져 있더라도, 다음 값의 메모리 주소를 기억하여 배열처럼 값을 연이어서 읽을 수 있도록 함

1) 구조체

typedef struct node // c 위에서 부터 읽기 때문에, 단순히 'typedef struct' 안됨 { int number; struct node *next; } node;

2) 구현

#include #include // 구조체 typedef struct node { int number; struct node *next; } node; int main(void) { // 포인터 list, 초기화 아무것도 없음 node *list = NULL; // 새로운 노드 node *n = malloc(sizeof(node)); if (n == NULL) { return 1; } n->number = 1; // n -> number == (*n).number n->next = NULL; list = n; // 추가 노드 n = malloc(sizeof(node)); if (n == NULL) { return 1; } n->number = 2; n->next = NULL; list->next = n; // 추가노드 n = malloc(sizeof(node)); if (n == NULL) { return 1; } n->number = 3; n->next = NULL; list->next->next = n; // list에 연결된 node(임시포인터 사용)를 처음부터 방문하면서 각 number 값을 출력하기 // for루프 종료 조건 : 마지막 node의 next == Null for (node *tmp = list; tmp != NULL; tmp = tmp->next) { printf("%i

", tmp->number); } // 메모리를 해제해주기 위해 list에 연결된 node들을 처음부터 방문하면서 free 해줍니다. while (list != NULL) { node *tmp = list->next; free(list); list = tmp; } }

연결리스트 확장 자료구조

트리(이진탐색트리) : 포인터가 2개가 있는 연결리스트, 재귀, O(logN)~O(N)

해시 테이블 : 연결 리스트의 배열, O(1)~O(N)

트라이 : 트리구조, 각 노드가 배열로 이루어짐, O(1)(상수값)

큐, 스택, 딕셔너리

팀미션

mission1 #include #include

typedef struct stack{

int top;

int capacity;

int* array;

} Stack;

Stack* createStack(int capacity) {

Stack* stack = (Stack)malloc(sizeof(Stack));

stack->capacity = capacity;

stack->top = -1;

stack->array = (int *)malloc(stack->capacitysizeof(int));

return stack;

}

int isFull(Stack* stack) {

return stack->top == stack->capacity-1;

}

int isEmpty(Stack* stack) {

return stack->top == -1;

}

void push(Stack* stack, int item) {

if (isFull(stack))

return;

stack->array[++stack->top] = item;

printf("%d pushed to stack

", item);

}

int peek(Stack* stack) {

// 스택이 비어있을 때 return

if (isEmpty(stack))

return -9999;

return stack->array[stack->top];

}

int pop(Stack* stack) {

// 스택이 비어있을 때 return

if (isEmpty(stack))

return -9999;

int temp = peek(stack); // top 변경 stack->top--; return temp;

}

int main() {

Stack* stack = createStack(100);

push(stack, 10); push(stack, 20); push(stack, 30); push(stack, 40); printf("%d pop from stack

", pop(stack)); printf("%d pop from stack

", pop(stack)); push(stack, 50); printf("%d pop from stack

", pop(stack)); printf("%d pop from stack

", pop(stack)); return 0;

}

* mission2 ```c #include #include typedef struct stackNode { int data; struct stackNode* next; } StackNode; StackNode* createStackNode(int data) { StackNode* node = (StackNode*)malloc(sizeof(StackNode)); node->data = data; node->next = NULL; return node; } int isEmpty(StackNode* root) { return !root; } void push(StackNode** root, int data) { // 삽입할 노드 생성 StackNode *newNode = createStackNode(data); // 삽입할 노드의 next 를 현재 root가 가리키고 있는 node 를 넣어준다. newNode->next = *root; // 루트는 항상 새로 만들어진 node를 가리키게 한다. (*root) = newNode; printf("%d pushed to stack

", data); } int pop(StackNode** root) { if (isEmpty(*root)) return -9999; int popped; // 루트가 가리키는 node 의 data를 popped에 저장 popped = (*root)->data; // pop할 node 를 tmpNode 에 저장한다. StackNode *tmpNode = (*root); // 루트는 pop할 node의 다음 node를 가리킨다. (*root) = tmpNode->next; // pop할 node 메모리 해제 free(tmpNode); return popped; } int peek(StackNode** root) { if (isEmpty(*root)) return -9999; return (*root)->data; } int main() { StackNode* root = NULL; push(&root;, 10); push(&root;, 20); push(&root;, 30); push(&root;, 40); printf("%d pop from stack

", pop(&root;)); printf("%d pop from stack

", pop(&root;)); push(&root;, 50); printf("%d peeked from stack

", peek(&root;)); printf("%d pop from stack

", pop(&root;)); printf("%d pop from stack

", pop(&root;)); return 0; }

mission3 #include #include

typedef struct queue {

int front;

int rear;

int size;

int capacity;

int* array;

} Queue;

Queue* createQueue(int capacity) {

Queue* queue = (Queue *)malloc(sizeof(Queue));

queue->capacity = capacity;

queue->front = 0;

queue->size = 0;

queue->rear = capacity-1; // 왜 이렇게 초기화 했는지 잘 생각해 보세요!

queue->array = (int *)malloc(sizeof(int) * queue->capacity); return queue;

}

int isFull(Queue* queue) {

return (queue->size == queue->capacity);

}

int isEmpty(Queue* queue) {

return (queue->size == 0);

}

void enqueue(Queue* queue, int item) {

if (isFull(queue)) {

return;

}

// rear 계산 if(queue->rear + 1) = capacity, queue->rear = 0 queue->rear = (queue->rear + 1) % (queue->capacity); // array에 item 넣기 queue->array[queue->rear] = item; // size 증가 queue->size++; printf("%d enqueued to queue

", item);

}

int dequeue(Queue* queue) {

if (isEmpty(queue)) {

return -9999;

}

int item = 0;

// 배열의 가장 앞부분에 위치한 값 가져오기 item = queue->array[queue->front]; // 배열의 끝에 도달시(queue->front + 1 == capacity) 다시 0으로 돌아감 queue->front = (queue->front + 1) % (queue->capacity); // queue 사이즈 감소 queue->size--; return item;

}

int main() {

Queue* queue = createQueue(1000);

enqueue(queue, 10); enqueue(queue, 20); enqueue(queue, 30); enqueue(queue, 40); printf("%d dequeued from queue

", dequeue(queue)); printf("Front item is %d

", queue->array[queue->front]); printf("Rear item is %d

", queue->array[queue->rear]); return 0;

}

* mission4 ```c #include #include typedef struct node{ int data; struct node* next; } Node; void append(Node* head, int data) { Node* node = (Node *)malloc(sizeof(Node)); node->data = data; node->next = NULL; Node* temp = head; while(temp->next != NULL) { temp = temp->next; } temp->next = node; } int getLastNode (Node* head, int k) { Node* fast = head; Node* slow = head; int start = 1; while(fast->next!=NULL) { fast = fast->next; start++; if (start > k) { slow = slow->next; } } return slow->data; } void printList(Node* head) { while(head->next != NULL){ printf("%d ", head->next->data); head = head->next; } } int main() { Node* head = (Node*)malloc(sizeof(Node)); append(head, 9); append(head, 8); append(head, 4); append(head, 14); append(head, 5); printList(head); printf("

%dth last node is %d

", 2, getLastNode(head, 2)); }

from http://jooseop.tistory.com/71 by ccl(A) rewrite - 2021-08-25 00:26:16

Top