자료구조 LAB 00~07 (중간고사 범위)

dain·2022년 10월 24일
자료구조
0
post-thumbnail

💻 LAB 00

  • Encoding 주의: Mac(CR) → Windows(CRLF)
  • CRT_SECURE ERROR
    : strcpy_s()로 수정
  • include 순서: 시스템 헤더 먼저 > 사용자 정의 헤더

💻 LAB 01

  • ADT 규격 명세서
    • Function
    • Precondition
    • Postcondition

💻 LAB 02

  • 개행 문자
    ? 텍스트의 한줄이 끝남을 표시하는 문자/문자열 (= newline, EOL)

    • Windows: CRLF
    • Unix/Linux/Mac: LF (CR에서 변경, 강의자료는 CR 기준)

  • Command-line argument
    ? main 함수가 가지는 parameter

    • int main(int argc, char** argv)
      • argc: command line argument의 수
      • argv: char의 이중 포인터 => char[]의(string) 포인터

  • Redefinition problem
    : 같은 헤더 파일을 여러 개의 소스파일에서 include 시키는 경우 재정의 에러 발생

    • 해결 방법
    1. #ifndef
      • 전처리기 지시자
      • 모든 컴파일러에서 동작, 느림
    2. #pragma once
    • 컴파일러 지시자
    • 특정 컴파일러에서만 동작, 처음 한 번만 컴파일해서 빠름

Q1

강의자료는 맥(CR) → 윈도우, 실습은 윈도우 → 맥(LF)

Q2. Unsorted List(array)의 DeleteItem 수정

  • 교재
    : 리스트에 삭제할 아이템, one & only 존재

    void UnsortedType::DeleteItem(ItemType item) {
	location = 0;
   
    while(item.ComparedTo(info[location]) != EQUAL)
    	location++;
   
    info[loaction] = info[length - 1];
    length--;
 }

  • (a)
    : 삭제할 item이 리스트에 존재하지 않는 경우 리스트 변경X
    (교재의 코드에선 while 무한 루프 에러 → 검색횟수 제한)

    void UnsortedType::DeleteItem(ItemType item) {

    for (int location=0; location<length; location++){ //검색횟수 제한
    	if (item.ComparedTo(info[location] == EQUAL){
        	info[location] = info[length - 1];
            length;
            return; //같은 값 찾고 삭제하면 반복문 종료
        }
 }

  • (c)
    : 삭제할 item과 같은 리스트의 모든 item 삭제

    void UnsortedType::DeleteItem(ItemType item) {
	int location = 0;
    while (location < length) { //검색횟수 제한
    	if (item.ComparedTo(info[location]) == EQUAL){
        	info[location] = info[length - 1];
            length--;
        }
        else
        	location++;
    } 
}

💻 LAB03. Sorted/Unsorted List

Q1. 2개의 SortedList 병합

  • SortedList는 array의 형태로 구현됨
  • 클라이언트 함수로 작성
  • 조건: list1과 list2는 정렬되어 있는 상태 
void SortedType::GetNextItem(ItemType& item)
{
  currentPos++;
  item = info[currentPos];
}

void SortedType::ResetList()
{
  currentPos = -1;
}

MergeList(SortedType list1, SortedType list2, SortedType& result) { 
	list1.ResetList(); //GetNextItem() 위해 초기화
    list2.ResetList();
    result.ResetList(); //result 초기화 안하면 오류남
	int length1 = list1.LengthIs(); //list1의 길이
    int length2 = list2.LengthIs(); //list2의 길이
    
    ItemType item;
    
    //insert시 자동 정렬
    for (int i=0; i<length1; i++) {
    	list1.GetNextItem(item); //item = info[0] 
    	result.InsertItem(item);
    }
    for (int i=0; i<length2; i++) {
    	list2.GetNextItem(item); //item = info[0] 
    	result.InsertItem(item);
    }

  • (a)
    : 대상(value)이 배열(array[])의 몇 번째에 있는지 리턴
    (찾는 대상이 없는 경우 -1 리턴)
int BinarySearchA(int array[], int sizeOfArray, int value) {
	int midPoint;
	int first = 0;
	int last = sizeOfArray - 1;
	bool found = false;

	while (first <= last) { //검색 횟수 제한
		midPoint = (first + last) / 2;

		if (array[midPoint] == value) { //찾은 경우 break
			found = true;
			break;
		}
		else if (array[midPoint] > value)
			last = midPoint - 1;
		else if (array[midPoint] < value)
			first = midPoint + 1;
	}
	if (found)
		return midPoint; //배열에서 value의 index
	else
		return -1;
}
  • (b)
    : 찾고자 하는 값보다 작거나 같은 값들 중에서 가장 큰 값 리턴
int BinarySearchB(int array[], int sizeOfArray, int value) {
	int midPoint;
	int first = 0;
	int last = sizeOfArray - 1;
	bool found = false;

	while (first <= last) { //검색 횟수 제한
		midPoint = (first + last) / 2;

		if (array[midPoint] == value) { //찾은 경우 break
			found = true;
			break;
		}
		else if (array[midPoint] > value)
			last = midPoint - 1;
		else if (array[midPoint] < value)
			first = midPoint + 1;
	}
	if (found)
    	//찾은 경우 -> 같은 값 리턴
		return array[midPoint];
	else
    	//찾지 못한 경우 -> 작은 값들 중 가장 큰 값 리턴 -> value-1에 대해 재귀 
		return BinarySearchB(array, sizeOfArray, value-1);
}
  • (c)
    : 찾고자 하는 값보다 크거나 같은 값들 중에서 가장 작은 값 리턴
int BinarySearchC(int array[], int sizeOfArray, int value) {
	int midPoint;
	int first = 0;
	int last = sizeOfArray - 1;
	bool found = false;

	while (first <= last) { //검색 횟수 제한
		midPoint = (first + last) / 2;

		if (array[midPoint] == value) { //찾은 경우 break
			found = true;
			break;
		}
		else if (array[midPoint] > value)
			last = midPoint - 1;
		else if (array[midPoint] < value)
			first = midPoint + 1;
	}
	if (found)
    	//찾은 경우 -> 같은 값 리턴
		return array[midPoint];
	else
    	//찾지 못한 경우 -> 큰 값들 중 가장 작은 값 리턴 -> value+1에 대해 재귀 
		return BinarySearchB(array, sizeOfArray, value+1);
}

Q3.

  • 연산자 overloading
  bool HouseType::operator<(HouseType house) const {
    if (lastName < house.lastName)
        return true;
    else if (house.lastName < lastName)
        return false;
    else if (firstName < house.firstName)
        return true;
    else if (house.firstName < firstName)
        return false;
    else //같은 경우
        return false;
}

bool HouseType::operator==(HouseType house) const {
    if (lastName == house.lastName)
        return true;
    else 
        return false;
}

💻 LAB 04. Stack

Q1. Stack 이해

  • ItemType 템플릿으로 정의된 stack, int형으로 선언
  • Stack은 array로 구현됨
  • StackType.h
template<class ItemType>
StackType<ItemType>::StackType()
{
  top = -1;
}

template<class ItemType>
void StackType<ItemType>::Push(ItemType newItem) 
{
    if (IsFull())
        throw FullStack();
    items[top] = newItem;
    top++;
}

template<class ItemType>
void StackType<ItemType>::Pop()
{
    if( IsEmpty() )
        throw EmptyStack();
    top--;
}

template<class ItemType>
ItemType StackType<ItemType>::Top()
{
    if (IsEmpty())
        throw EmptyStack();
    return items[top];
}
  • main
#include <iostream>
#include "StackType.h"

using namespace std;

int main()
{
	StackType<int> stack; 
	stack.Push(1);
	stack.Push(2);
	stack.Push(3);
	stack.Push(4);
	stack.Push(5);
	stack.Push(6);

	while (!stack.IsEmpty()) {
		int top = stack.Top();
		stack.Pop();
		cout << top << endl;
	}
}

Q2. Copy Stack

  • 스택의 데이터를 변경하지 않고 기존의 스택과 동일한 값 갖는 스택 만드는 클라이언트 함수 구현
  • stack은 Pop & Push시 순서가 뒤집히기 때문에, 임시 저장을 위한 tempStack 필요
template<class ItemType>
//기존 stack: reference로 안 받음
//copyStack: reference로 받음
void Copy(StackType<ItemType> stack, StackType<ItemType>& copyStack)
{
	StackType<ItemType> tempStack;

	while (!stack.IsEmpty()) {
		ItemType item = stack.Top();
		tempStack.Push(item);
		stack.Pop(); //referenceX -> 함수 종료되면 기존 stacK에 영향 x
	}
	while (!tempStack.IsEmpty()) {
		ItemType item = tempStack.Top();
		copyStack.Push(item);
		tempStack.Pop();
	}
}

Q3. Double Stack

  • 하나의 배열에 stack 두 개 구현
    • 첫 번째 스택은 1000 이하의 수 저장
    • 두 번째 스택은 1000 초과의 수 저장
const int MAX_ITEMS = 200;

class DoubleStack
{
private:
	int top_small; //1000 이하의 수 저장하는 스택의 top
	int top_big; //1000 초과의 수 저장하는 스택의 top
	int items[MAX_ITEMS];
public:
	DoubleStack() : top_small(-1), top_big(200) {} //생성자
	void Push(int item);
	void Print();
};

void DoubleStack::Push(int item) {
	if (item <= 1000) {
		top_small++;
		items[top_small] = item;
	}
	else if (item > 1000) {
		top_big--;
		items[top_big] = item;
	}
}

void DoubleStack::Print() { //top부터 출력
	for (int i = top_small; i >= 0; i--) {
		cout << items[i] << ' ';
	}
	cout << endl;
    
	for (int i = top_big; i < MAX_ITEMS; i++) {
		cout << items[i] << ' ';
	}
	cout << endl;
}

Q4. ReplaceItem

  • stack의 모든 oldItem을 newItem으로 치환하는 함수
  • 클라이언트 함수
    : item 값을 저장할 임시 스택 필요
void ReplaceItemA(StackType& stack, int oldItem, int newItem) {
	StackType tempStack; //임시스택

	while (!stack.IsEmpty()) {
		if (stack.Top() == oldItem)
			tempStack.Push(newItem);
		else
			tempStack.Push(stack.Top());
		stack.Pop();
	}

	while (!tempStack.IsEmpty()) {
		stack.Push(tempStack.Top());
		tempStack.Pop();
	}
}
  • 멤버 함수
    : StackType 클래스의 멤버변수에 직접적인 접근 가능 -> 임시 스택 필요 X
//top은 인덱스니까 +1
void StackType::ReplaceItemB(int oldItem, int newItem) {
    for (int i = 0; i < top+1; i++) {
        if (items[i] == oldItem)
            items[i] = newItem;
    }
}

💻 LAB 05. Queue

Q1. Queue의 이해

  • 실습 코드는 circular queue (reserved 메모리 있는)로 구현됨
  • Enqueue & Dequeue 위주

Q2. ReplaceItem

  • queue(정수형)의 oldItem, newItem으로 치환
  • 클라이언트 함수
void ReplaceItemA(QueType& queue, int oldItem, int newItem) {
	QueType tempQue; //임시큐 선언 
    //queue는 Enqueue & Dequeue 과정에서 순서가 뒤집히진 않지만,
    //클라이언트 함수이므로 queue의 멤버 변수에 직접적으로 접근할 수 없기 때문에 
    //임시큐 필요 
	int item;

	while (!queue.IsEmpty()) {
		queue.Dequeue(item);
		if (item == oldItem) 
			tempQue.Enqueue(newItem);
		else
			tempQue.Enqueue(item);		
	}
	while (!tempQue.IsEmpty()) {
		tempQue.Dequeue(item);
		queue.Enqueue(item);
	}
}
  • 멤버 함수
void QueType::ReplaceItemB(ItemType oldItem, ItemType newItem) {
	//circular니까 case 나눠서
    if (rear > front) {
        for (int i = front+1; i <= rear; i++) { //front가 가리키고 있는 건 reserved 공간이니까
            if (items[i] == oldItem)
                items[i] = newItem;
        }
    }
    else if (rear < front) { //rear == front인 경우는 empty
        for (int i = (front+1)%maxQue; i <= rear+maxQue; i++) {
            if (items[i] == oldItem)
                items[i] = newItem;
        }
    }
}

Q3. 두 개의 Queue 비교

  • 두 개의 queue(정수형) 같으면 true, 다르면 false 리턴
  • front부터 순차적으로 비교
  • 클라이언트 함수
bool IdenticalA(QueType& queue1, QueType& queue2) {
	int item1, item2;

	while (!queue1.IsEmpty() && !queue2.IsEmpty()) {
		queue1.Dequeue(item1);
		queue2.Dequeue(item2);
		if (item1 == item2)
			continue; 
		else
			return false; //queue 내부에 서로 다른 아이템이 있는 경우 false
	}
	if (queue1.IsEmpty() && queue2.IsEmpty())
		return true; //queue 내부에 서로 다른 아이템이 없고 두 queue의 길이가 같은 경우
	else
		return false; //두 queue의 길이가 다른 경우 
}
  • 멤버 함수
bool QueType::IdenticalB(QueType& queue) {
    ItemType item;

    if (rear > front) {
        for (int i = front + 1; i <= rear; i++) { 
            if (!queue.IsEmpty()) {
                queue.Dequeue(item);
                if (items[i] != item)
                    return false;
            }
        }
    }
    else if (rear < front) { //rear == front인 경우는 empty 
        for (int i = (front + 1) % maxQue; i <= rear + maxQue; i++) {
            if (!queue.IsEmpty()) {
                queue.Dequeue(item);
                if (items[i] != item)
                    return false;
            }
        }
    }
    return true;
}

Q4. Queue의 길이

  • queue에 몇 개의 item이 저장되었는지 리턴하는 함수
  • 클라이언트 함수
int LengthA(QueType queue) { 
	QueType tempQue;
	int item;
	int length = 0;

	while (!queue.IsEmpty()) {
		queue.Dequeue(item);
		length++;
	}
	return length;
}
  • 멤버 함수
int QueType::LengthB() {
    int length;
    if (front > rear)
        length = rear - front + maxQue;
    else
        length = rear - front;
    return length;
}

Q5. Length 변수 이용해 Queue 구현

  • front 앞 (reserved) 공간 사용하도록 queue 재설계
  • length 변수 이용해서 큐의 크기 계산
QueType::QueType(int max)
{
    maxQue = max; 
    front = 0;
    rear =  maxQue-1; 
    items = new ItemType[maxQue];
    length = 0; 
}

QueType::QueType()        
{
    maxQue = 500;
    front = 0;
    rear =  maxQue-1;
    items = new ItemType[maxQue];
}

void QueType::MakeEmpty()
{
    front = 0;
    rear =  maxQue-1;
}

bool QueType::IsEmpty() const
{
    return (length == 0);
}

bool QueType::IsFull() const
{
    return (length == maxQue);
}

void QueType::Enqueue(ItemType newItem)
{
  if (IsFull())
      throw FullQueue();
  else{
      length++;
      rear = (rear +1) % maxQue;
      items[rear] = newItem;
  }
}

void QueType::Dequeue(ItemType& item)
{
  if (IsEmpty())
      throw EmptyQueue();
  else
  {
      front = (front + 1) % maxQue;
      item = items[front];
      length--;
  }
}

int QueType::LengthIs() {
    return length;
}

Q6. Dequeue 수정

  • 기존의 Dequeue
    : '넣는 순서' 기준으로 먼저 넣은 값이(front) 먼저 나오도록 구현됨
  • 수정할 Dequeue
    : '값이 작은 순서' 기준으로 아이템 반환
    • int minumum_pos 멤버 변수로 선언
    • 알고리즘
    1. minimum_pos: queue 내부에서 가장 작은 값을 가지는 위치(인덱스)
    2. MinDequeue() -> items[minimum_pos] 리턴 -> items[minmum_pos] = -1로 초기화 -> minumum_pos 초기화
    3. Enqueue(item) ->-1로 초기화되어 있는 위치에 item 삽입
코드를 입력하세요

💻 LAB 06. Linked List (1)

  • Heap
    ? 프로그램이 실행될 때 사용되는 가변적인 양의 데이터를 저장하기 위해 프로그램의 프로세스가 사용할 수 있도록 미리 예약되어 있는 메인 메모리 영역
    • 동적 할당을 통하여 Heap 영역에 메모리 할당
    • 메모리 해제 필수
    • 에러
      • Heap 공간이 부족하여 더 이상 메모리 할당할 수 없는 경우(overflow)
      • 이미 해제하거나 할당되지 않은 메모리를 해제하는 경우

Q1. Stack(LinkedList)의 ReplaceItem

  • 초기화되어 있는 스택(조건)의 모든 oldItem을 newItem으로 치환

  • 클라이언트 함수

void ReplaceItemA(StackType& stack, ItemType oldItem, ItemType newItem) {
	StackType tempStack; // 백업용 스택
	ItemType topItem; // top 받는 아이템 
	
	while (!stack.IsEmpty()){
		topItem = stack.Top();
		stack.Pop();
		
		if (topItem == oldItem)
			tempStack.Push(newItem);
		else
			tempStack.Push(topItem);
	}
	while (!tempStack.IsEmpty()) {
		topItem = tempStack.Top();
		tempStack.Pop();
		stack.Push(topItem);
	}
}
  • 멤버 함수
void StackType::ReplaceItemB(ItemType oldItem, ItemType newItem) {
    // 함수 설명: 링크 구조로 연결되어 있는 노드들을 top에서부터 시작하여 하나씩 검사해 가며
	// olditem 값과 같은 아이템을 newitem으로 변경
    NodeType* location = topPtr; // 현재 노드를 가리키기 위한 포인터 선언 및 초기화

    while (location != NULL) { 
        if (location->info == oldItem) {
            location->info = newItem; //교체
            location = location->next;
        }
        else
            location = location->next;
    }
}

Q2. Queue(LinkedList)의 ReplaceItem

  • 초기화되어 있는 큐(조건)의 모든 oldItem을 newItem으로 치환
  • template 사용
  • 클라이언트 함수
template <class ItemType>
void ReplaceItemA(QueType<ItemType>& queue, ItemType oldItem, ItemType newItem) {
//값 변경하고 돌려줘야 하니까 &
    QueType<int> tempQue;
    ItemType item;
    
    while (!queue.IsEmpty()) {
        queue.Dequeue(item);
        if (item == oldItem)
            tempQue.Enqueue(newItem);
        else
            tempQue.Enqueue(item);
    }
    
    while (!tempQue.IsEmpty()) {
        tempQue.Dequeue(item);
        queue.Enqueue(item);
    }
}
  • 멤버 함수
template <class ItemType>
void QueType<ItemType>::ReplaceItemB(ItemType oldItem, ItemType newItem) {
    NodeType<ItemType>*;location; //node 가리키는 포인터 ptr 선언
    location = front; // 초기화
    while (location != NULL) { //rear->next == NULL
        if (location->info == oldItem) {
            location->info = newItem;
            location = location->next;
        }
        else
            location = location->next;
    }
}

Q3. 두 개의 LinkedList를 하나로 병합

  • 가정
    • 각각의 리스트에는 중복 아이템 존재 X

  • SortedType (정렬 리스트는 오름차순으로 정렬되어 있음)

    • 클라이언트 함수

      template <class ItemType>
void MergeListsA(SortedType<ItemType>& listA, SortedType<ItemType>& listB, SortedType<ItemType>& result) {
	ItemType itemA;
	ItemType itemB;
	listA.ResetList(); // currentPos = NULL로 초기화
	listB.ResetList(); // currentPos = NULL로 초기화
	
   //sortedList는 insert 과정에서 자동 정렬
	for (int i = 0; i < listA.LengthIs(); i++) {
		listA.GetNextItem(itemA);
		result.InsertItem(itemA);
	}
	for (int i = 0; i < listB.LengthIs(); i++) {
		listB.GetNextItem(itemB);
		result.InsertItem(itemB);
	}
}

    • 멤버 함수

      template <class ItemType>
void SortedType<ItemType>::MergeListsB(SortedType<ItemType>& other, SortedType<ItemType>& result) {
  NodeType<ItemType>* ptr1 = listData;
  NodeType<ItemType>* ptr2 = other.listData;

  while (ptr1 != NULL && ptr2 != NULL) {
      //ptr1 NULL 아니고 ptr2도 NULL 아닐 때 -> 하나라도 NULL 이면 나옴
      result.InsertItem(ptr1->info);
      result.InsertItem(ptr2->info);
      ptr1 = ptr1->next;
      ptr2 = ptr2->next;
  }
  //두 리스트의 길이가 다를 때, 긴 쪽을 뒤에 붙이는 예외 처리
  if (ptr1 != NULL) { //ptr2는 null인데 ptr1은 null 아님 -> ptr2가 더 짧아서 먼저 끝남
      while (ptr1 != NULL) {
          result.InsertItem(ptr1->info);
          ptr1 = ptr1->next;
      }
  }
  else if(ptr2 != NULL) { //ptr1는 null인데 ptr2은 null 아님 -> ptr1가 더 짧아서 먼저 끝남
      while (ptr2 != NULL) {
          result.InsertItem(ptr2->info);
          ptr2 = ptr2->next;
      }
  }
}

  • UnsortedType (결과 Unsorted List)

    • 클라이언트 함수

      template <class ItemType>
void MergeListsC(UnsortedType<ItemType>& listA, UnsortedType<ItemType>& listB, UnsortedType<ItemType>& result) {
	ItemType itemA;
	ItemType itemB;
	listA.ResetList(); // currentPos = NULL로 초기화
	listB.ResetList(); // currentPos = NULL로 초기화

	for (int i = 0; i < listA.LengthIs(); i++) {
		listA.GetNextItem(itemA);
		result.InsertItem(itemA);
	}
	for (int i = 0; i < listB.LengthIs(); i++) {
		listB.GetNextItem(itemB);
		result.InsertItem(itemB);
	}
}

    • 멤버 함수

      void UnsortedType<ItemType>::MergeListsD(UnsortedType<ItemType>& other, UnsortedType<ItemType>& result) {
  NodeType<ItemType>* ptr1 = listData;
  NodeType<ItemType>* ptr2 = other.listData;

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

Q4. UnsortedList (LinkedList)의 DeleteItem 수정

  • 교재
    : 리스트에 아이템이 반드시 존재하는 것을 전제로 함
    → 존재하지 않을 경우 무한 루프 에러

  • (A)
    : 존재하지 않는 아이템을 삭제할 경우 발생하는 오류 수정 (preLoc & location 이용)

template <class ItemType>
void UnsortedType<ItemType>::DeleteItemA(ItemType item) {
  	NodeType<ItemType>* predLoc = NULL; //이전 노드 가리키는 포인터
   	NodeType<ItemType>* location = listData; //현재 노드 가리키는 포인터
   	NodeType<ItemType>* tempLocation; //delete 위한 포인터

   	if (item == listData->info)
   	{
   	    tempLocation = location;
   	    listData = listData->next;		// Delete first node. (listData->next == NULL)
   	    delete tempLocation;
   	    length--;
   	}
   	else {
   	    while (location != NULL) { //같지 않으면 location 업데이트
   	        if (item != (location->info)) {
   	            predLoc = location;
   	            location = location->next;
   	            if (location == NULL)
   	                cout << "존재 x" << endl;
   	        }
   	        else { //같으면 삭제
   	            tempLocation = location;
   	            predLoc->next = location->next;
   	            location = location->next;
   	            delete tempLocation;
   	            length--;
   	        }
   	    }
   	}
 }
  • (B)
    : 삭제하고자 하는 아이템이 리스트 내에 여러 개 있을 경우 모두 삭제
template <class ItemType>
  void UnsortedType<ItemType>::DeleteItemB(ItemType item)
{
    NodeType<ItemType>* predLoc = NULL; //이전 노드 가리키는 포인터
    NodeType<ItemType>* location = listData; //현재 노드 가리키는 포인터
    NodeType<ItemType>* tempLocation; //delete 위한 포인터

    if (item == listData->info)
    {
        tempLocation = location;
        listData = listData->next;		// Delete first node. (listData->next == NULL)
        delete tempLocation;
        length--;
    }
    else {
        while (location != NULL) { //같지 않으면 location 업데이트
            if (item != (location->info)) {
                predLoc = location;
                location = location->next;
            }
            else { //같으면 삭제
                tempLocation = location;
                predLoc->next = location->next;
                location = location->next;
                delete tempLocation;
                length--;
            }
        }
    }
}

근데 너무 슬프게도... 다 잘 되는데... 마지막 아이템 & 바로 이전 아이템이 중복인 경우 마지막 아이템이 삭제되지 않는 오류가 발생한다 왤까...?!?! 난 정말 맞게 짠 것 같은데...🥲


Q5. SortedList의 DeleteItem 수정

  • 교재
    : 리스트에 아이템이 반드시 존재하는 것을 전제로 함
    → 존재하지 않을 경우 무한 루프 에러

  • (A)
    : 존재하지 않는 아이템을 삭제할 경우 발생하는 오류 수정 (preLoc & location) 이용

template <class ItemType>
void SortedType<ItemType>::DeleteItemA(ItemType item)
// Pre:  item's key has been initialized.
//       An element in the list has a key that matches item's.
// Post: No element in the list has a key that matches item's.
{
    NodeType<ItemType>* predLoc = NULL; //이전 노드 가리키는 포인터
    NodeType<ItemType>* location = listData; //현재 노드 가리키는 포인터
    NodeType<ItemType>* tempLocation; //delete 위한 포인터

    if (item == listData->info)
    {
        tempLocation = location;
        listData = listData->next;		// Delete first node. (listData->next == NULL)
        delete tempLocation;
        length--;
    }
    else {
        while (location != NULL) { //같지 않으면 location 업데이트
            if (item != (location->info)) {
                predLoc = location;
                location = location->next;
                if (location == NULL)
                    cout << "존재 x" << endl;
            }
            else { //같으면 삭제
                tempLocation = location;
                predLoc->next = location->next;
                location = location->next;
                delete tempLocation;
                length--;
                return;
            }
        }
    }
}
  • (B)
    : 삭제하고자 하는 아이템이 리스트 내에 여러 개 있을 경우 모두 삭제
template <class ItemType>
void SortedType<ItemType>::DeleteItemB(ItemType item){
// Pre:  item's key has been initialized.
//       An element in the list has a key that matches item's.
// Post: No element in the list has a key that matches item's.


    NodeType<ItemType>* predLoc = NULL; //이전 노드 가리키는 포인터
    NodeType<ItemType>* location = listData; //현재 노드 가리키는 포인터
    NodeType<ItemType>* tempLocation; //delete 위한 포인터

    if (item == listData->info)
    {
        tempLocation = location;
        listData = listData->next;		// Delete first node. (listData->next == NULL)
        delete tempLocation;
        length--;
    }
    else {
        while (location != NULL) { //같지 않으면 location 업데이트
            if (item != (location->info)) {
                predLoc = location;
                location = location->next;
            }
            else { //같으면 삭제
                tempLocation = location;
                predLoc->next = location->next;
                location = location->next;
                delete tempLocation;
                length--;
            }
        }
    }
}

얘는 또 오류 안나는 걸 보면... UnsortedType 클래스 문제?

💻 LAB 07. Linked List (2)

Q1. SortedList의 PrintReverse()

  • PrintRevers()? SortedList의 모든 원소 역순으로 출력하는 함수
  • SortedList는 circular LinkedList로 구현되어 있음
  • FindItem 관련 내용: chap06 p.12~21 (double linked list임)
  • 방법1. location & length 변수 이용
template <class ItemType>
void SortedType<ItemType>::PrintReverse() {
//논리적으론 맞는 것 같은데 잘 모르겠... 계속 오류 ㅠㅠ
    NodeType<ItemType>* location;

    for (int i = 0; i < length; i++) {
        location = listData;
        for (int j = 0; j < length - i - 1; j++) {
            location = location->next; //last -> last-1 -> last-2 -> ... -> 0
        }
            
            
        ItemType item = location->info;
        cout << item << endl;
    }
}
  • 방법2. location, 데이터 하나씩 읽어가면서 stack에 저장 -> stack을 통해 역순으로 출력

Q2. Stack(LinkedList)의 Copy

  • deep copy로 구현
void StackType::Copy(StackType& anotherStack) { //처음에 꼭 pass by reference
    NodeType* ptr1; //anotherStack에 관한 포인터 (복사할 대상)
    NodeType* ptr2; //self에 관한 포인터 (새롭게 쓰여지는 대상)

    if (anotherStack.topPtr == NULL) // 비어있으면
        topPtr = NULL;
    else {
        topPtr = new NodeType;
        topPtr->info = anotherStack.topPtr->info;
        ptr1 = anotherStack.topPtr->next;
        ptr2 = topPtr;
        while (ptr1 != NULL) {
            ptr2->next = new NodeType;
            ptr2 = ptr2->next;
            ptr2->info = ptr1->info;
            ptr1 = ptr1->next;
        }
        ptr2->next = NULL;
    }
}
profile
dain
자라나는 감자
이전 포스트

[UE5]RayTrace(2) Progress bar

다음 포스트

01. Introduction

0개의 댓글