전체 글21 Recursion Recursive call 호출하는 주체 = 호출하는 객체 - Direct recursion : 자기 자신을 호출 - Indirect recursion : 다른 함수를 호출 ( f -> g -> h ...) - 주의사항 : 무한 루프를 돌지 않도록 코드를 짜야한다. some Definitions - Base case : 재귀를 빠져나오는 경우 - General(recrusive) case : 재귀를 진행 중인 경우 - Recrusive algorithm : base case + general case Three-Question Method of verifying recursive functions 1. Base-Case Question : Is there a nonrecursive way out of t.. 2023. 5. 1. Linked Sorted List 전반적으로 Linked Unsorted List와 비슷하다. 다른 몇 가지만 살펴보자. sortedList 에서 RetrieveItem() 할 때는 binary Search를 썼었다. 근데 Linked에서는 동적배열이니 midPoint를 찾는게 더 복잡하다. 따라서 그냥 맨 앞에서부터 하나씩 비교하면서 찾는다. void RetrieveItem(ItemType &item, bool found) item이 location의 info보다 작으면 다음 것을 조사, 같으면 ok. 그런데 item이 location의 info보다 커지면 그 후로부터는 더 이상 조사할 필요가 없다. 이후 노드의 info는 전부 item보다 클 것이기 때문. template void RetrieveItem(ItemType &item, .. 2023. 4. 30. Linked Unsorted List unsorted list에서는 private으로 length, info[], currentPos를 가졌었다. linked에서는 private으로 연결된 리스트의 제일 첫 원소를 가리키는 listData를 가진다. (info[] 역할) UnsortedType() template UnsortedType::UnsortedType(){ length = 0; listData = NULL; } ~UnsortedType() template UnsortedType::~UnsortedType(){ MakeEmpty(); } bool IsFull() 새 노드 만들고 지우는거 성공하면 노드 만들 메모리 아직 존재 -> return false 실패하면 IsFull template bool UnsortedType::IsFull.. 2023. 4. 30. Sorted List SortedList 장점 : 원하는 원소를 빠르게 찾을 수 있다. 단점 : 새로운 아이템을 넣을 때 들어갈 자리를 찾아야한다. Unsorted List에서 정보를 어떻게 저장할 것인가만 달라진다. Insert, Delete 함수만 바꿔보자. + RetrieveItem을 좀 더 효율적으로 만들어보자. InsertItem(ItemType newItem) 현재 위치 표시할 location, 끝까지 검사하기 위한 moreToSearch. newItem이랑 리스트 원소 비교했을 때 Less( newItem이 더 작으면) location 앞에 넣는다. Greater(newItem이 더 크면) newItem보다 큰 원소가 나올 때까지 위치를 뒤로 옮긴다. location이 확정되면, location보다 뒤에 있는 원.. 2023. 4. 30. Unsorted List UnsortedList 장점 : 넣을 때 그냥 뒤에 넣으면 되서 간단함. 단점 : 찾을 때 하나하나 크기 비교하면서 찾아야함. Operations - IsFull - LengthIs - RetrieveItem - Make Empty - InsertItem - DeleteItem - ResetList - GetNextItem UnsortedType() 처음 생성하면 빈 리스트. UnsortedType::UnsortedType(){ length = 0; } bool IsFull() bool UnsortedType::IsFull(){ return (length = MAX_ITEMS) } int LengthIs() int UnsortedType::LengthIs(){ return length } void Ret.. 2023. 4. 30. Linked Queue Operations - IsEmpty - IsFull - MakeEmpty - Enqueue - Dequeue LinkedQueue에서는 큐 앞을 관리하는 qFront, 마지막을 관리하는 qRear 가 필요하다. LinkedQType() template LinkedQType::LinkedQType(){ qFront = NULL; qRear = NULL; } ~LinkedQType() template LinkedQType::~LinkedQType(){ MakeEmpty(); } bool IsEmpty() template bool LinkedQType::IsEmpty(){ return (qFront == qRear); } bool IsFull() 새 노드 만들고 지우는거 성공하면 노드 만들 메모리 아직 존재.. 2023. 4. 30. Linked Stack Linked 리스트를 구현할 때 중요한 점은 Item을 추가,삭제할 때 포인터들을 잘 연결해주는 것이다. garbage를 만들지 않기 위해 Push,Pop할 때 tempPtr을 이용하자. NodeType* location을 선언하자. location은 데이터(info)와 다음 노드를 가리키는 포인터(next)를 갖는다. LinkedstStack() 스택의 맨 위를 가리키는 노드 하나를 만들자. 초기 설정 NULL LinkedstType::LinkedstType(){ topPtr = NULL; } ~LinkedstStack() 스택이 scope 밖으로 벗어나면 스택의 로컬변수인 topPtr은 자동으로 할당 해제된다. 그러나 topPtr이 가리키는 노드는 남아있기 때문에 이 메모리를 해제해줘야함!! Link.. 2023. 4. 29. Queue FIFO : First in, First out Operations - IsEmpty - IsFull - MakeEmpty - Enqueue - Dequeue Circular Queue를 만들었을 때 문제점 큐가 비어있을 때 : front == rear +1 큐가 꽉 찼을 때 : front == rear +1 라서 분간이 안된다. 해결 : front를 진짜 맨 앞보다 하나 앞 공간을 가리키게 한다. (reserved area) 큐가 비어있을 때 : front == rear 큐가 꽉 찼을 때 : front == rear+1 2023. 4. 28. Stack LIFO : Last in First Out Operations - IsEmpty - IsFull - ItemType Top - MakeEmpty - Push(ItemType newItem) - Pop Typedef int ItemType; const int MAX_ITEMS = 20; Template으로 구현하려면? //StackType.h #include "ItemType.h" template class StackType{ ... } //StackType.cpp #include "StackType.h" template void StackType::Push(ItemType &newItem){ top++; items[top] = newItem; } 2023. 4. 28. 이전 1 2 3 다음
