공부/자료구조 | 알고리즘 (23) 썸네일형 리스트형 [자료구조] 큐 Queue / 배열을 이용한 큐의 구현 What is Queue? 큐는 입력된 순서대로 순차적으로 처리되기 위해 기다리는 자료들의 모음이다. 따라서 입력 순서에 따라 차례대로 일이 처리되는 성질을 이용하여 다음과 같은 곳에 사용된다. 운영체제의 작업 스케쥴링 공유 프린터 작업 스케쥴링 및 버퍼 데이터 통신/네트워크 등 각종 시뮬레이션 (대기열 처리, 큐잉 이론) 선입선출 (FIFO : First-In First-Out) 먼저 들어 온 것이 먼저 사용 또는 제거되는 특징을 가진다. 스택의 후입선출(LIFO : Last-In First-Out)과 반대되는 개념 기본적으로 첫 원소와 마지막 원소를 각각 가리키는 두개의 포인터(인덱스)를 사용한다. 예) front/rear 실전에서는 front는 첫 원소가 아닌 바로 그 앞을 가리키도록 설정 (fro.. [자료구조] 미로찾기 maze / 스택 스택을 이용한 미로찾기 스택 s과 출구의 위치 x, 현재 생쥐의 위치를 초기화 ; while( 현재의 위치가 출구가 아니면 ) { 현재위치를 방문한 것으로 표기 if( 현재 위치의 상하좌우 위치 중 아직 방문되지 않았고 갈수 있는 길이 있으면 ) 그 위치들을 모두 스택 s에 push(순서는 관계 없음); if( is_empty(s) ) 실패; else 스택 s에서 하나의 위치를 꺼내어 현재 위치로 만든다; } 성공; #include #include #define MAX_SIZE 100 #define MAZE_SIZE 10 typedef struct Mouse { short x; short y; }Mouse; typedef struct Stack { Mouse data[MAX_SIZE]; int top; .. [자료구조] 후기표기식 계산하기 postfix / 스택 스택을 이용하여 후위표기식 계산하기 - 피연산자를 만나면 스택에 push 한다. - 연산자를 만나면 필요한 개수 만큼의 피연산자를 스택에서 pop 한다. - 연산결과를 다시 스택에 push 한다. - 수식이 끝나면, 마지막으로 스택을 pop하여 출력한다. #include using namespace std; const int MAX_NUM = 100; //define MAX_NUM 100 typedef int element; typedef int element2; class Stack{ public: element data[MAX_NUM]; int top; //마지막 원소를 가리키는 인덱스 Stack(){ top=-1; //초기화 } bool is_empty(){ //if(top == -1) return.. [자료구조] 후위표기식 변환 postfix / 스택 후기표기식 변환 중위표기 수식을 후위표기 수식으로 변환 알고리즘 개요 수식의 각 연산자에 대해 우선순위에 따라 괄호를 적용 각 연산자를 그에 대응하는 오른쪽 괄호 뒤로 이동 괄호를 제거 예) A*B-C/D 수식의 후위표기 수식 변환 ((A*B)-(C/D)) ((A B)* - (C D)/) ((A B)* (C D)/)- A B * C D / - 스택을 이용한 후위표기식 변환 1. 왼쪽 괄호를 만나면, 무시하고 다음 문자를 읽는다. 2. 피연산자를 만나면 출력한다. 3. 연산자를 만나면 스택에 넣는다. 4. 오른쪽 괄호를 만나면 스택을 pop하여 출력한다. 5. 수식이 끝나면 스택이 공백이 될 때까지 pop 하여 출력한다. 연산자만 스택에 넣고, 피연산자는 그대로 출력 오른쪽 괄호가 나오면 스택에 있던 연산.. [자료구조] 스택 stack / 배열을 이용한 스택의 구현 스택이란? 스택은 자료나 물건들을 차례대로 쌓아둔 더미를 의미한다. 스택의 특성 2가지 대표적인 함수 : push/pop 함수 push 함수 : 스택에 값을 넣을때(제일 상단에 값을 추가함) pop 함수 : 스택에서 값을 꺼낼 때(제일 상단의 값을 꺼냄) 후입선출 (LIFO : Last-In First-Out) 방식 먼저 들어 온 것이 아래에 있으므로 나중에 들어온 것이 먼저 사용 또는 제거되는 특징을 가진다. (반대 개념 FIFO : First-In First-Out) 스택 관련 주요 연산/함수 createStack() - 스택을 생성한다. is_empty(s) - 스택 s가 비어있는지를 검사한다. is_full(s) - 스택 s가 가득 찼는지를 검사한다. (배열인 경우) push(s, e) - 스택 .. [자료구조] 이중연결리스트 Doubly Linked List 단순/단일연결리스트의 문제점 선행 노드를 찾기가 힘들다 삽입이나 삭제 시에는 반드시 선행 노드에 대한 정보가 필요 이중연결리스트 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 갖는 연결리스트 장점 : 링크가 양방향이므로 양방향으로 검색이 가능 단점 : 공간(2개의 포인터)을 많이 차지하고 코드가 복잡 이중연결리스트의 변형 두 개의 포인터 사용 첫 노드를 가리키는 포인터와 끝 노드를 가리키는 포인터를 각각 사용 head/tail 또는 front/rear 명칭 사용 이중연결리스트 + 원형연결리스트 실전에서 더욱 유용하게 사용됨. 첫 노드와 마지막 노드 간의 양방향 link 유지 link값이 NULL인 경우가 없다. 이중연결리스트 + 원형연결리스트 + 헤드노드 헤드노드 사용: 코딩 편의 (빈리스.. [자료구조] 연결리스트 다항식 덧셈 Linked List 연결리스트 다항식 덧셈 Q. 하나의 다항식을 하나의 연결리스트로 표현하여, 2개의 다항식을 더하는 덧셈 연산을 구현하라. A = 3x^12 + 2x^8 + 1 B = 8x^12 - 3x^10 + 10x^6 C = A+B = ? #include #include //다항식 리스트의 노드 구조 정의 typedef struct Node{ int coef; //계수 int expo; //지수 struct Node* link; } Node; typedef struct ListHead{ Node* head; } ListHead; //공백 다항식 리스트 생성 연산 ListHead* createLinkedList(void) { ListHead* L; L = (ListHead *)malloc(sizeof(ListHead).. [자료구조] 연결리스트 역순 연산 리스트 역순 만들기 Node *reverse(Node *head) { // 순회 포인터로 p, q, r을 사용 Node *p, *q, *r; p = head; // p는 현재 가리키는 노드, q는 이전 노드 q = NULL; while (p != NULL){ r = q; // r은 q, q는 p를 차례로 따라간다. q = p; p = p->link;// p를 미리 옮겨 놓자. q->link = r; // q의 링크 방향을 바꾼다. } head = q; // q는 역순으로 된 리스트의 헤드 포인터 return head; } 예제) 연결 리스트 역순 만들기 #include using namespace std; class Node { public: int score; //점수 Node *link; //다음 노.. 이전 1 2 3 다음
