[자료구조] stack, queue, sorted list, unsorted list

MergeList

-> 배열 기반 Sorted

-> list1 과 list2를 합쳐서 result로 반환

-> big o:  O(N^2)

 

Sorted List

1. 클라이언트 함수: 배열, 링크드 리스트 모두 같은 구현

void MergeList(SortedType list1, SortedType list2, SortedType& result) {
	result = list1;
	ItemType it;
	list2.ResetList();
	for (int i = 0; i < list2.LengthIs(); i++) {
		list2.GetNextItem(it);
		result.InsertItem(it);
	}
}

template <class ItemType>
void MergeLists(SortedType<ItemType>& l_a, SortedType<ItemType>& l_b, 
	SortedType<ItemType>& result) {
	l_a.ResetList();
	l_b.ResetList();

	ItemType item1, item2;
	for (int i = 0; i < l_a.LengthIs(); i++) {
		l_a.GetNextItem(item1);
		result.InsertItem(item1);
	}
	for (int i = 0; i < l_b.LengthIs(); i++) {
		l_b.GetNextItem(item2);
		result.InsertItem(item2);
	}	
}

2. 멤버 함수

 

링크드 리스트

template <class ItemType>
void SortedType<ItemType>::MergeLists(SortedType<ItemType>& other,
    SortedType<ItemType>& result) {
    
    NodeType<ItemType>* a = listData;
    NodeType<ItemType>* b = other.listData;

    while (a != NULL) {
        result.InsertItem(a->info);
        a = a->next;
    }
    while (b != NULL) {
        result.InsertItem(b->info);
        b = b->next;
    }

}

 

 

Unsorted list

1. 클라이언트 함수: 배열, 링크드 리스트 모두 같은 구현

template <class ItemType>
void MergeLists(UnsortedType<ItemType>& l_a, UnsortedType<ItemType>& l_b,
	UnsortedType<ItemType>& result) {
	
	l_a.ResetList();
	l_b.ResetList();
	result.ResetList();

	ItemType item1, item2;
	for (int i = 0; i < l_a.LengthIs(); i++) {
		l_a.GetNextItem(item1);
		result.InsertItem(item1);
	}
	for (int i = 0; i < l_b.LengthIs(); i++) {
		l_b.GetNextItem(item2);
		result.InsertItem(item2);
	}

}

 

2. 멤버 함수

링크드 리스트 구현

template <class ItemType>
void UnsortedType<ItemType>::MergeLists(UnsortedType<ItemType>& another, UnsortedType<ItemType>& result) {
    NodeType<ItemType>* a = this->listData;
    NodeType<ItemType>* b = another.listData;

    ItemType item;
    while (a != NULL) {
        item = a->info;
        result.InsertItem(item);
        a = a->next;
    }
    while (b != NULL) {
        item = b->info;
        result.InsertItem(item);
        b = b->next;
    }  
    
    // 가이드 코드
    	while (a_location != NULL || b_location != NULL)
	{
		if (a_location == NULL && b_location != NULL)
		{
			result.InsertItem(b_location->info);
			b_location = b_location->next;
		}
		else if (a_location != NULL && b_location == NULL) {
			result.InsertItem(a_location->info);
			a_location = a_location->next;
		}
		else {
			if(a_location->info < b_location->info){
				result.InsertItem(a_location->info);
				a_location = a_location->next;
			}
			else if (a_location->info > b_location->info) {
				result.InsertItem(b_location->info);
				b_location = b_location->next;
			}
			else {
				result.InsertItem(a_location->info);
				a_location = a_location->next;
				result.InsertItem(b_location->info);
				b_location = b_location->next;
			}
		}
	}
    
    // 내가 생각한 부분
        while (a != NULL && b != NULL) {
        if (a->info < b->info) {
            result.InsertItem(a->info);
            a = a->next;
        }
        else {
            result.InsertItem(b->info);
            b = b->next;
        }
    }
    if (a != NULL) {
        while (a != NULL) {
            result.InsertItem(a->info);
            a = a->next;
        }
    }
    else if (b != NULL) {
        while (b != NULL) {
            result.InsertItem(b->info);
            b = b->next;
        }
    }


}

 

 

---

Binary Search 수정

1. 작거나 같은 값 중에서 가장 큰 값을 return

int BinarySearch(int* arr, int sizeofarray, int value) {
	int start = 0;
	int end = sizeofarray - 1;

	while (start <= end) {
		int mid = (start + end) / 2;

		if (arr[mid] == value) {
			return mid;
		}
		else if (arr[mid] < value) {
			start = mid + 1;
		}
		else if (arr[mid] > value) {
			end = mid - 1;
		}
	}
	for (int i = 0; i < sizeofarray; i++) {
		if (arr[i] > value) {
			return arr[i - 1];
		}
	}

}

 

2. 크거나 같은 값 중에서 가장 작은 값을 return 

int BinarySearch(int* arr, int sizeofarray, int value) {
	int start = 0;
	int end = sizeofarray - 1;

	while (start <= end) {
		int mid = (start + end) / 2;

		if (arr[mid] == value) {
			return mid;
		}
		else if (arr[mid] < value) {
			start = mid + 1;
		}
		else if (arr[mid] > value) {
			end = mid - 1;
		}
	}
	for (int i = 0; i < sizeofarray; i++) {
		if (arr[i] > value) {
			return arr[i];
		}
	}
}

---

unsorted deleteItem 수정

배열 기반

1. 중복된 데이터들을 모두 삭제하도록

void UnsortedType::DeleteItem_c(ItemType it) {
    // function: 삭제될 요소가 리스트에 있으면 중복해서 모두 삭제함
    // precondition: 리스트가 초기화되어야한다.
    // postcondition: 중복되는 요소도 모두 삭제가 되어야한다.
    for (int i = 0; i < length; i++) {
        if (info[i].ComparedTo(it) == EQUAL) {
            int idx = i;
            for (idx; idx < length - 1; idx++) {
                info[idx] = info[idx + 1];
            }
            length--;
        }
    }
}

 

링크드 리스트 기반

1. 찾는 아이템이 리스트에 없는 경우

template <class ItemType>
void UnsortedType<ItemType>::DeleteItem_A(ItemType item){
    NodeType<ItemType>* location = listData;
    NodeType<ItemType>* tempLocation;

    if (item == listData->info)
    {
        tempLocation = location;
        listData = listData->next;

        delete tempLocation;
        length--;
    }
    else
    {
        bool found = 0;
        while (location->next != NULL && !found) {
            if (item == (location->next)->info) {
                found = 1;
                break;
            }
            else {
                location = location->next;
            }

        }

        if (found==1) {
            tempLocation = location->next;
            location->next = (location->next)->next;

            delete tempLocation;
            length--;
        }
        else {
            cout << "no data in list" << endl;
        }
        location = NULL;
     
    }
}

 

2. 중복되는 아이템을 모두 삭제

template <class ItemType>
void UnsortedType<ItemType>::DeleteItem_B(ItemType item){
    NodeType<ItemType>* location = listData;
    NodeType<ItemType>* tempLocation;

    if (item == listData->info)
    {
        tempLocation = location;
        listData = listData->next;	
        
        delete tempLocation;
        length--;
    }
    else
    {
        bool found = 0;
        while (location->next != NULL && !found) {
            if ((location->next)->info == item) {
                found = 1;
                break;
            }
            else {
                location = location->next;
            }
        }
        if (found == 0) {
            cout << "no data in list" << endl;
        }
        while (found == 1) {
            tempLocation = location->next;
            location->next = (location->next)->next;
           
            delete tempLocation;
            length--;

            while (location->next != NULL) {
                if ((location->next)->info == item) {
                    found = 1;
                    break;
                }
                else {
                    location = location->next;
                    found = 0;
                }
            }
            
        }
        location = NULL;
    }
}


// 가이드 코드
   NodeType<ItemType>* location = listData;
	NodeType<ItemType>* preLoc = NULL;
    NodeType<ItemType>* tempLocation;
	
	bool stop = false;

	while (!stop) {

		// Locate node to be deleted.
		if (location == NULL)
		{
			break;
		}
		else
		{
			// Sorted 경우엔 조건을 더해서 삭제 연산 그만둠
			if (location->info == item)
			{
				tempLocation = location;

				if (preLoc == NULL) {

					// 처음인 경우엔 location만 옮김
					location = location->next;
					listData = location;

				}
				else {

					if (location->next == NULL) {
						stop = true;
					}
						
					// 이전 노드를 현재 노드의 다음을 가리킴
					preLoc->next = location->next;
					location = location->next;
					
				}
				//한번만할 경우
				// stop = true
				delete tempLocation;
				length--;
				
			}
			else {
				// 못찾은 경우엔 한칸씩 이동
				preLoc = location;
				location = location->next;
			}

			
		}
		

	}

 

 

---

Sorted DeleteItem 수정

링크드 리스트 기반

1. 찾는 아이템이 리스트에 없는 경우

template <class ItemType>
void SortedType<ItemType>::DeleteItem_A(ItemType item)
{
    NodeType<ItemType>* location = listData;
    NodeType<ItemType>* tempLocation;
    NodeType<ItemType>* prelocation = NULL;

// 구현 1번
    bool moretosearch = 1;
    while (moretosearch) {
        if (location->info != item) {
            prelocation = location;
            location = location->next;
            moretosearch = (location != NULL);
        }
        else {
            moretosearch = 0;
        }
    }
    if (location == NULL) {
        cout << "no data in list" << endl;
    }
    else {
        tempLocation = location;
        prelocation = location->next;
        delete tempLocation;
        length--;
    }

// 구현 2번
    if (item == listData->info)
    {
        tempLocation = location;
        listData = listData->next;

        delete tempLocation;
        length--;
    }
    else
    {
        bool found = 0;
        while (location->next != NULL && !found) {
            if (item == (location->next)->info) {
                found = 1;
                break;
            }
            else {
                location = location->next;
            }
        }
        if (found == 1) {
            tempLocation = location->next;
            location->next = (location->next)->next;

            delete tempLocation;
            length--;
        }
        else {
            cout << "no data in list" << endl;
        }
        location = NULL;
    }
}

 

2. 중복되는 아이템을 모두 삭제

template <class ItemType>
void SortedType<ItemType>::DeleteItem_B(ItemType item){
    NodeType<ItemType>* location = listData;
    NodeType<ItemType>* tempLocation;

    if (item == listData->info)
    {
        tempLocation = location;
        listData = listData->next;

        delete tempLocation;
        length--;
    }
    else
    {
        bool found = 0;
        while (location->next != NULL && !found) {
            if (item == (location->next)->info) {
                found = 1;
                break;
            }
            else {
                location = location->next;
            }
        }
        if (found == 0) {
            cout << "no data in list" << endl;
        }
        bool moretosearch = 1;
        while (found == 1 && moretosearch) {

            tempLocation = location->next;
            location->next = (location->next)->next;

            delete tempLocation;
            length--;

            while (location->next != NULL) {
                if (item < (location->next)->info) {
                    moretosearch = 0;
                    break;
                }
                else if(item == (location->next)->info){
                    found = 1;
                    break;
                }
                else {
                    location = location->next;
                }
            }
            if (location->next == NULL) {
                break;
            }
            
        }
        location = NULL;
    }

}

 

 

---

ReplaceItem

stack

1. 클라이언트: 배열, 링크드 리스트 모두 구현 같음

void ReplaceItem(StackType& st, int olditem,int newitem) {
	StackType s;
	int item;
	while (!st.IsEmpty()) {
		item = st.Top();
		if (item == olditem) {
			item = newitem;
		}
        else {
        	s.Push(item);
		}
		st.Pop();
	}
	while (!s.IsEmpty()) {
		st.Push(s.Top());
		s.Pop();
	}
}

 

2. 멤버 함수

 

배열기반으로 구현

void StackType::ReplaceItem(int olditem, int newitem) {
    for (int i = 0; i <= top; i++) {
        if (items[i] == olditem) {
            items[i] = newitem;
        }
    }
}

 

링크드 리스트 기반으로 구현

void StackType::ReplaceItem(ItemType olditem, ItemType newitem) {
    NodeType* location = topPtr;
    while (location != NULL) {
        if (location->info == olditem) {
            location->info = newitem;
        }
        location = location->next;        
    }
    location = NULL;    
}

 

---

Queue

1. 클라이언트: 링크드 리스트, 배열 모두 구현 같음

void ReplaceItem(QueType& queue, int olditem, int newitem) {
	int item;
	QueType q;

	while (!queue.IsEmpty()) {
		queue.Dequeue(item);

		if (item == olditem) {
			q.Enqueue(newitem);
		}
		else {
			q.Enqueue(item);
		}
	}
	while (!q.IsEmpty()) {
		q.Dequeue(item);
		queue.Enqueue(item);
	}
}

template <class ItemType>
void ReplaceItem(QueType<ItemType> &queue, 
	ItemType olditem, ItemType newitem) {
	QueType<ItemType> q;
	ItemType it;
	while (!queue.IsEmpty()) {
		queue.Dequeue(it);
		if (it == olditem) {
			q.Enqueue(newitem);
		}
		else {
			q.Enqueue(it);
		}
	}
	while (!q.IsEmpty()) {
		q.Dequeue(it);
		queue.Enqueue(it);
	}

}

 

2. 멤버 함수

 

배열 기반으로 구현

void QueType::ReplaceItem(int olditem, int newitem) {
    for (int i = 0; i < this->maxQue; i++) {
        if (items[i] == olditem) {
            items[i] = newitem;
        }
    }
}

 

링크드 리스트로 구현

template <class ItemType>
void QueType<ItemType>::ReplaceItem(ItemType olditem, ItemType newitem) {
    NodeType<ItemType>* location = front;
    while (location != NULL) {
        if (location->info == olditem) {
            location->info = newitem;
        }
        location = location->next;
    }
    location = NULL;

}

---

Identical

Queue 배열 기반

1. 클라이언트

bool Identical(QueType queue1, QueType queue2) {
	int item1, item2;
	QueType q1(queue1), q2(queue2);

	bool iden = true;
	while (!q1.IsEmpty() && !q2.IsEmpty()) {
		q1.Dequeue(item1);
		q2.Dequeue(item2);

		if (item1 != item2) {
			iden = false;
		}
	}
	if (q1.IsEmpty() != q2.IsEmpty()) {
		iden = false;
	}

	return iden;
}

 

2. 멤버 함수

QueType::QueType(QueType& q) {
    maxQue = q.maxQue;
    front = q.front;
    rear = q.rear;
    items = new ItemType[q.maxQue];
    for (int i = 0; i < q.maxQue; i++) {
        items[i] = q.items[i];
    }
} // 복사 생성자

bool QueType::Identical(QueType queue) {
    QueType q(queue);
    if(this->maxQue != q.maxQueue)
    	return false;  // 길이가 다르면 false
        
      for (int i = 0; i < q.maxQue; i++) {
          if (q.items[i] != this->items[i]) {
              return false;          // 값이 다르면 false
             }
       }
    return true;  // 아니면 true
}




//QueType QueType:: operator=(const QueType& obj) {
//	this->front = obj.front;
//	this->rear = obj.rear;
//	this->maxQue = obj.maxQue;
//	this->items = obj.items;
//
//	cout << "this" << endl;
//
//	return *this;
//}

---

Queue에서 Reserved cell 사용하지 않기

-> length 변수 추가

#include "QueType.h"

QueType::QueType(int max)
// Parameterized class constructor
// Post: maxQue, front, and rear have been initialized.
//       The array to hold the queue elements has been dynamically
//       allocated.
{
  maxQue = max + 1;
  front = maxQue - 1;
  rear = maxQue - 1;
  len = 0;
  items = new ItemType[maxQue];
}
QueType::QueType()          // Default class constructor
// Post: maxQue, front, and rear have been initialized.
//       The array to hold the queue elements has been dynamically
//       allocated.
{
  maxQue = 501;
  front = maxQue - 1;
  rear = maxQue - 1;
  len = 0;
  items = new ItemType[maxQue];
}
QueType::~QueType()         // Class destructor
{
  delete [] items;
}

void QueType::MakeEmpty()
// Post: front and rear have been reset to the empty state.
{
  front = maxQue - 1;
  rear = maxQue - 1;
  len = 0;
}

bool QueType::IsEmpty() const
// Returns true if the queue is empty; false otherwise.
{
    return (len == 0);
}

bool QueType::IsFull() const
// Returns true if the queue is full; false otherwise.
{
    return (len == maxQue);
}

void QueType::Enqueue(ItemType newItem)
// Post: If (queue is not full) newItem is at the rear of the queue;
//       otherwise a FullQueue exception is thrown.  
{
  if (IsFull())
    throw FullQueue();
  else
  {
      //가이드 
      rear = rear % maxQue;
      items[rear] = newItem;
      rear += 1;

      // me
      items[rear] = newItem;
      rear = (rear + 1) % maxQue;
      len++;
  }
}

void QueType::Dequeue(ItemType& item)
// Post: If (queue is not empty) the front of the queue has been 
//       removed and a copy returned in item; 
//       othersiwe a EmptyQueue exception has been thrown.
{
  if (IsEmpty())
    throw EmptyQueue();
  else
  {
      len--;
      item = items[front];
      front = (front + 1) % maxQue;
  }
}

---

MinDequeue

->값이 작은 순서부터 삭제하면서 출력