자료구조 (34) 썸네일형 리스트형 [자료구조] 스택 - 04 . 사칙 연산 계산기 [사칙 연산 계산기] [사칙연산계산기] =>사칙연산만으로 이루어진 식을 분석해서 풀어보려 한다. ex) 1+3.334 / (4.28*(110-2279)) =>해당 문제를 사람이 본다면 , 우선순위가 눈에 들어오겠지만 컴퓨터는 아니다! : 컴퓨터가 사용 할 도구 (알고리즘)을 제공해야 한다. =>알고리즘을 위한 과정은 이렇다 수식을 프로그램이 풀기 적당한 형식 (후위 표기법)으로 변환한다 . 변환된 수식을 프로그램이 계산한다 . [수식의 표기법] [전위 표기법 (Prefix Notation) ] =>연산자가 피연산자 앞에 위치한다 . 폴리쉬 표기법이라고도 한다. ex) 3+4 => +34 [중위 표기법 (Infix Notation) ] =>흔히 사용하는 표기법 .연산자가 피연산자 가운데에 위치한다 . ex.. [자료구조] 스택 - 03 . 링크드 리스트로 구현하는 스택 [스택과 스택의 노드 표현하기] [노드] 링크드 리스트로 구현하는 스택의 노드는 자신의 위에 위치한 노드에 대한 포인터가 필요하다 . typedef struct tagNode { char* Data; struct tagNode* NextNode; }Node; =>데이터 필드가 char*이기에 문자열이 저장되어 있는 주소만을 담을 수 있어야 한다. 또한 해당 문자열은 자동 메모리가 아닌 자유 저장소에 저장 되어야 한다. [스택] typedef struct tagLinkedListStack { Node* List; Node* Top; }LinkedListStack; =>List 포인터는 스택이 기반하고 있는 링크드 리스트에 접근 =>Top 포인터는 최상위 노드에 대한 정보를 유지 [스택의 기본 연산 구현하기.. [자료구조] 스택 - 02 . 배열로 구현하는 스택 [배열로 구현하는 스택] [배열로 구현하는 스택] =>동적으로 스택의 용량을 조절하기 어렵다는 단점이 있다 . =>구현이 간단하다는 장점이 있다. =>배열기반의 스택은 각 노드를 동적으로 생성하고 제거하는 대신, 스택 생성 초기에 사용자가 부여한 용량만큼 노드를 한꺼번에 생성 , 최상위 노드의 위치를 나타내는 변수를 이용하여 삽입과 제거 연산을 수행한다. [스택과 스택의 노드 표현하기] [노드] =>스택의 각 층을 구성한다. =>데이터만 담는 구조체로 표현된다. (노드의 위치는 배열의 인덱스로 알 수 있어 뒷노드의 포인터는 필요 없다) typedef int ElementType; typedef struct tagNode { ElementType Data; }Node; [스택 구조체] =>배열 기반의 스택.. [자료구조] 스택 - 01 . 스택의 개념 [스택] [예시] =>좁은 주차장에서 가장 안쪽에 주차한 차는 앞의 모든 차가 빠져줘야 주차가 가능하다. [스택 (Stack)] =>스택(Stack)은 무언가를 쌓아놓은 "더미"를 뜻한다 . =>가장 먼저 들어간 것이 마지막에 빠지는 (First In , First Out (FIFO)) 구조를 가지고 있다. [스택의 사용 사례] =>변수의 수명주기가 끝나고 자동으로 변수를 제거하는 자동 메모리도 스택으로 구현되어 있다. (지역변수는 스택(자동 메모리)에 할당 된다.) =>대부분의 네트워크 프로토도 스택으로 구현되어 있다. [스택의 주요기능] [삽입] =>스택위에 새로운 노드(혹은 요소)를 쌓는 작업 . [제거] =>최상위 노드를 걷어내는 작업 . [자료구조] 리스트 - 03 . 환형 링크드 리스트 <구현> [환형 링크드 리스트 구현] =>헤더 #ifndef CDLL #define CDLL #include #include typedef struct TagNode { int Data; TagNode* PrevNode; TagNode* NextNode; }Node; //생성 Node* CDLL_CreateNode(int _Data); //소멸 void CDLL_DestroyNode(Node* Destroy); //추가 void CDLL_AppendNode(Node** Head, Node* NewNode); //삽입 void CDLL_InsertNode(Node* Current, Node* NewNode); //출력 void CDLL_PrintNode(Node* Head); //역출력 void CDLL_Rever.. [자료구조] 리스트 - 03 . 환형 링크드 리스트 [환형 링크드 리스트] [환형 링크드 리스트] =>환형 링크드 리스트는 헤드의 앞 노드는 테일이며 테일의 뒷노드는 헤드이다. =>장점은 테일에 접근하는 비용이 거의 없는 것이 되어 , 노드를 추가할때 성능의 향상이 가능하다. [환형 링크드 리스트 주요 연산] =>환형 링크드 리스트의 주요 연산시 가장 신경 쓸 부분은 다음과 같다. 테일은 헤드의 "앞노드"이다 . 헤드는 테일의 "뒷노드"이다. 주요한 연산 추가 ,삭제를 살펴보겠다.이외의 연산은 DLL에서 본 것과 동일하여 생략하려 한다. [노드 추가] void CDLL_AppendNode(Node** Head,Node* NewNode) { if((*Head)==NULL)//헤드노드가 NULL인경우 { *Head=NewNode; *Head->NextNode.. [자료구조] 리스트 - 02 . 더블 링크드 리스트 <구현> 앞서 봤던 DLL을 구현하여 코드상에서 확인해보겠다. 01 . 헤더 파일 //DLL.h #ifndef DLL_H #define DLL_H #include #include typedef int ElementType; typedef struct TagNode { ElementType Data; TagNode* PrevNode; TagNode* NextNode; }Node; #include"DLL.h" //생성 Node* DLL_CreateNode(ElementType Data); //소멸 void DLL_DestroyNode(Node* Node); //추가 void DLL_AppendNode(Node** Head, Node* NewNode); //삽입 void DLL_InsertNode(Node* Curre.. [자료구조] 리스트 - 02 . 더블 링크드 리스트 [더블 링크드 리스트] [더블 링크드 리스트] =>링크드 리스트의 탐색기능을 개선한 자료구조 : 헤드 -> 테일의 일방탐색에서 양방향 탐색이 가능하다 . [구조] =>자신의 앞에 있는 노드 와 자신의 다음 노드 두가지 포인터를 가지고 있다. [구조체로 표현] =>구조체로 표현해보자면 다음과 같다. typedef struct tagNode { int Data;//데이터 필드 struct tagNode* PrevNode;//그전 노드를 가리키는 포인터 struct tagNode* NextNode;//다음 노드를 가리키는 포인터 }Node; [더블 링크드 리스트의 주요 연산] [노드의 생성과 소멸] 생성 //노드 생성 void DLL_CreateNode(ElementType data) { Node* NewNo.. 이전 1 2 3 4 5 다음
