- Programming/- 자료구조 썸네일형 리스트형 ★ 11. 링크드 리스트와 배열의 차이 링크드 리스트와 배열의 차이 - 배열과 연결 리스트는 데이터를 나열한다는 점에서 비슷함 - 배열과 연결 리스트는 엄연히 다르기 때문에 사용하기에 따라 프로그램의 성능이 달라지게 됨. - 배열 (Array) 1. 배열은 데이터를 논리적 순서에 따라 순차적으로 데이터를 입력하며, 물리적 주소 또한 순차적이다. 2. 인덱스를 가지고 있어서 원하는 데이터를 한번에 접근이 가능하기 때문에 데이터 접근 속도가 매우 빠르다. 3. 배열은 데이터의 삽입/삭제에는 취약하다. 배열 특성상 데이터 삽입/삭제가 이루어지면 삽입/삭제가 이루어진 위치의 다음부터 모든 데이터의 위치를 변경해야 하기 때문이다. - 연결리스트 (Linked List) 1. 연결리스트는 데이터를 논리적 순서에 따라 데이터를 입력한다. 하지만 물리적 주.. 더보기 ★ 10. 연결 리스트를 이용한 스택 구현하기 연결 리스트를 이용한 스택 구현 전과 마찬가지로 각 기능별 함수로 구현되었습니다. // # 연결 리스트를 이용한 스택 ##include #include using namespace std;typedef int element; struct stackNode { element data; // # 다음 노드를 가리키는 포인터 변수 # stackNode *link; }; stackNode* top; // # 스택이 비어 있으면 true 아니면 false를 반환 # int isEmpty() { // # top 포인터가 NULL이면 스택이 비어 있는 것 # return (top == NULL); } // # 스택의 TOP에 원소를 삽입 # void push(element item) { // # 새로운 노드 공간을 .. 더보기 ★ 9. 배열을 이용한 스택 구현하기 배열을 이용한 스택 구현 // # 배열을 이용한 스택 ##include using namespace std; // # 배열 크기 # #define MAX_STACK_SIZE 5 typedef int element; // # 스택에 원소를 저장하기 위한 배열 # element stack[MAX_STACK_SIZE]; // # TOP의 위치 # int top = -1; // # 처음엔 맨 아래를 위치하기 때문에 '-1' # // # 스택 초기화 함수 # void initialize() { // # TOP 인덱스를 -1로 주어 스택을 비움 # top = -1; } // # 스택이 비어 있으면 true 아니면 false를 반환 # int isEmpty() { // # TOP 인덱스가 -1이면 true # ret.. 더보기 ★ 8. 스택 스택 스택은 제일 먼저 삽입(push)된 데이터가 맨 아래에 쌓여 있고가장 최근에 삽입된 데이터가 맨 위에 쌓이는 구조를 가지고 있습니다. 데이터를 삭제(pop)할 때에는 가장 최근에 삽입한 데이터를 꺼내는구조이고 스택에서의 입출력은 맨 위에서만 일어나고중간에서는 데이터를 삽입 또는 삭제를 할 수 없는 구조입니다.~ ★ 스택은 가장 최근에 들어온 데이터가 가장 먼저 나가기 때문에[후입선출] : LIFO( Last - In, First - Out : 라이포 리포)라고도 합니다. 스택에서 원소의 삽입과 삭제가 일어나는 곳을 TOP라 하고 스택의다른 한쪽 끝, 즉 TOP의 반대쪽 끝을 BOTTOM이라고 합니다. 다음 포스팅에서 코드적인 부분으로올리겠습니다. 더보기 ★ 7. 이중 연결 리스트 구현하기 - 이중 연결 리스트 - (이중 원형 연결리스트) 각 기능별로 함수로 구현이 된 이중 연결 리스트 예제 소스입니다."한번에 이해되는 C 자료구조" 책을 참조하였습니다. // # 이중 원형 연결 리스트에 원소 추가, 삽입하기 # #include #include using namespace std;typedef int element;struct tagListNode { tagListNode* leftLink; // # 왼쪽 노드를 가리키는 링크 필드 # element data; // # 노드를 구성하는 데이터 필드 # tagListNode* rightLink; // # 오른쪽 노드를 가리키는 링크 필드 # };// # 헤더의 정보를 저장할 구조체 선언 # struct tagListHead { tagListN.. 더보기 ★ 6. 이중 연결 리스트 - 이중 연결 리스트 - 원형 연결 리스트는 단순 연결 리스트보다는 이점이 있다. 그러나!아직도 몇 가지 단점이 있는데, 단점으로는 리스트를 뒤로 순회할 수없다는 점과 삭제하고자 하는 노드에 대한 포인터만으로는 그 노드를삭제할 수 없다는 점 등이 있다. 이러한 문제를 해결하기 위하여 어떤 노드에 대한 다음 노드뿐만아니라 전 노드까지 알 수 있도록 하여, 한 가지 방향의 탐색이 아닌양쪽 방향의 탐색이 가능하게 구성한 것이 이중 연결 리스트이다. 하나의 노드를 가진 구조체입니다.~struct LISTNODE{LISTNODE* lLink; // # 왼쪽(선행) 노드를 가리키는 링크 필드 #int data; // # 노드를 구성하는 데이터 필드 #LISTNODE* rLink; // # 오른쪽(후속) 노드를 가리.. 더보기 ★ 5. 원형 연결 리스트 구현하기 - 원형 연결 리스트 - 각 기능별로 함수로 구현이 된 원형 연결 리스트 예제 소스입니다."한번에 이해되는 C 자료구조" 책을 참조하였습니다. // # 원형 연결 리스트에 원소 추가, 삽입하기 # #include #include using namespace std; typedef int element; struct tagListNode { // # 노드를 구성하는 데이터 필드 # element data; // # 다음 노드를 가리키는 링크 필드 # tagListNode* link; }; // # 헤더의 정보를 저장할 구조체 선언 # struct tagListHead{ tagListNode* head; }; // # 연결 리스트를 초기화하는 함수 # tagListHead* createLinkedListHe.. 더보기 ★ 4. 원형 연결 리스트 - 원형 연결 리스트 - 이전에 다룬 리스트는 마지막 노드가 NULL인 구조였다.이런한 노드를 단순 연결 리스트라고 부른다. 마지막 노드의 링크가 NULL이 아닌 첫 번째 노드를 가리키도록구성할 수 있는데 이러한 리스트가 바로 원형 연결 리스트이다. 다음 포스팅에서 코드적인 부분으로포스팅 해보겠습니다. 더보기 ★ 3. 선형 연결 리스트 구현하기[추가] 기존 선형 연결 리스트에서 좀 더 추가된 소스입니다. #include #include using namespace std;// # 노드 구조체 # struct tagListNode { int data; // # 노드를 구성하는 데이터 필드 # tagListNode* link; // # 다음 노드를 가리키는 링크 필드 # };// # 헤드 구조체 # struct tagListHead { tagListNode* head; };// # 리스트를 초기화 하는 함수 # tagListHead* createLinkedHeadList() { tagListHead* L; // # 헤더의 공간을 확보 # L = new tagListHead; L->head = NULL; return L; }// # 연결 리스트에 노드를 추.. 더보기 ★ 2. 선형 연결 리스트 구현하기 선형 연결 리스트 구현 기능별로 함수로 나누어서 구현하였습니다.출처는 대학 교재로 사용하던 "한번에 이해되는 C 자료구조" 책을 보면서..#include #include using namespace std;// # 노드 구조체 # struct tagListNode { int data; // # 노드를 구성하는 데이터 필드 # tagListNode* link; // # 다음 노드를 가리키는 링크 필드 # };// # 헤드 구조체 # struct tagListHead { tagListNode* head; };// # 리스트를 초기화 하는 함수 # tagListHead* createLinkedHeadList() { tagListHead* L; // # 헤더의 공간을 확보 # L = new tagListHead.. 더보기 이전 1 2 다음