실습 코드(예외처리,코드구성 등)

싱글리 링크드 리스트

• bool empty()

• void append(int data)

  • 예외: if(empty())
  • tail의 다음에다 append한다

• void insertion(int idx)

  • 예외 : if(idx == 0) 안에서 if(listSize == 0) 일때, if(idx == listSize), if(idx < 0 || idx > listSize)
  • 중간에 insert할때 for문 : 조금만 돌림 for(int i=0; i <idx-1; i++)
  • for문을 조금만 돌려서 insert할 노드의 직전 노드를 찾는다

• void delection(int idx)

  • 예외 : if(idx ==0) 안에서 if(listSize == 1) 일때, if(empty() || idx<0 || idx>=listSize)
  • 중간의 delete할때 for문 : 삭제할 노드와 삭제할 "직전"노드를 구함
  • for문이 끝났을때 삭제한 노드가 tail 노드였다면 직전노드를 tail로 설정

• void print()

더블리 링크드 리스트

싱글리 리스트와 예외 처리문 delection 메소드 빼고 동일

delection 메소드 에 아래와 같은 예외처리 하나만 추가된다.
=> if(idx == listSize-1) : tail 노드 삭제하는 연산

• 싱글리 리스트에서 중간 삽입시에, 삭제할 노드가 tail 노드인지 물어보던 문장을 제거

배열

• 배열은 예외처리문 아예 없음!!

• 멤버변수 : int* arr, int arrSize;

• 생성자 : 배열 arr을 모두 0으로 초기화 (인덱스 0~arrSize 모두 0으로 초기화)

• void left_shift(int count)

  • int front_number = arr[0]; 생성
  • 이중 for문 돌리면서 원소들을 앞으로 떙기고 맨 뒤에다 front_number 삽입
    • for (int i = 1; i <= arrSize - 1; i++) arr[i-1] = arr[i];
  • front_number = arr[0]; 으로 최신화

• void right_shift(int count)

  • int back_number = arr[arrSize-1]; 생성
  • 이중 for문 돌리면서 원소들을 뒤로 떙기고 맨 앞에다 back_number 삽입
    • for (int i = arrSize - 2; i >= 0; i--) arr[i+1] = arr[i];
  • back_number = arr[arrSize-1]; 으로 최신화

• void reverse(int idx1, int idx2)

  • 배열 복사본 result에다 arr 원소 할당
  • 1중 for문만 돌려도 된다.
  • for(int i=0; i<= idx2-idx1; i++) result[idx1+i] = arr[idx2-i];
  • arr = result

• void add(int idx, int data)

  • for문 ㅈㄴ 조금만 돌림 => for(int i=listSize-2; i >= idx; i--)

• void remove(int idx)

  • for(int i=idx+1; i <= arrSize-1; i++)
  • 맨 마지막 종료 직전에, arr[arrSize-1] = 0 할당하는 것 까먹지말기!!!!!

• void set(int idx, int data)

• void print()

• void find(int data)

스택(1) - 배열구현

• 멤버변수 : topIndex, capacity, int* arr

• topIndex = -1 로 꼭 초기화할것!!

• int size(), bool empty() 모두 topIndex 로 코드구성

• int push()

  • 예외 : if(topIndex+1 == capacity) 일때 FULL 인상태.

• void pop(), void top()

  • 예외 : if(empty())

스택(2) - 싱글리 링크드리스트 구현

• node* topNode;

  • head와 tail을 선언하지 않고 topNode 하나만 선언

• 멤버변수 : node* topNode, int listSize;

• push, pop 모두 맨앞에서(head 위치에서) 진행

• push 는 FULL 에 대해 따로 예외처리하지 않는다

중위표기식 -> 후위표기식(W3_P2)

• int형을 저장하던 스택을 char형을 저장하도록 코드 수정하는거 잊지말기!!

• CASE1) + 또는 -

  • 스택에 쌓인 연산자를 "모두" 출력하며 동시에 제거한다.
    • while(!stack.empty()) cout << s.top(); s.pop();
  • 다 제거됐다면 스택에 str[i] 을 push!!!

• CASE2) * 또는 /

  • 스택에서 * 또는 / 가 계속 쭈르르 나올때까지 계속 출력하면서 제거한다
    • while(stack.top() == '*' || stack.top() == '/') cout <<s.top(); s.pop();
  • 다 제거됐다면 스택에 str[i] 를 push!!

• CASE3) 숫자

  • 그냥 출력하면됌

• 각 연산식의 테스트케이스가 끝나기 직전에 마지막으로 스택에 잔여 연산자들을 모두 출력, 제거한다
  • while(!s.empty()) cout << s.top(); s.pop();

후위표기식 -> 중위표기식(W3_P4)

• w3_p2와 달리, 연산자 케이스를 나누지 않고 숫자와 연산자 케이스 2개로만 나눈다.

• CASE1) str[i] == '+' 또는 '-' 또는 '*' 또는 '/'

  • 스택의 상위의 숫자 2개를 변수 int num1, num2에 입력받고 연산을 진행하고 그 결과를 스택에 push한다
  • "/" 와 "-" 연산의 경우 num2-num1 과 num2/num1 를 진행

• CASE2) 숫자일때

  • 스택에 push

• 테스트케이스가 끝나면, 스택에서 연산의 최종 결과물 s.top() 을 출력해준다.

• case2일때 str[i] 에서 반드시 '0' 을 빼줘서 (str[i]-'0') 문자를 숫자로 만들고 스택에 push할것!

큐(1) - 배열 구현

• 멤버 변수 : frontIndex, rearIndex, int* arr, int arrSize, int capacity

• rearIndex 는 마지막 인덱스의 다음을 나타낸다

• 예외처리할거 특별히 없음. empty() 랑 FULL 일때만 잘 처리해주기

• enqueue(), dequeue()

• front()

• rear() : return arr[rearIndex-1]; 를 리턴해주기!! rearIndex 인덱스가 아니다!!!

• empty()

큐(2) - 싱글리 링크드 리스트 구현

• 멤버변수: node frontNode, node rearNode, int listSize;

• enqueue

  • 예외 : if(empty()) => 최초 삽입시 frontNode = rearNode = newNode; 로 초기화
  • rearNode 에서 삽입이 발생

• dequeue

  • 예외 : if( listSize == 1 ), if(empty())
  • frontNode 에서 삭제가 발생

• front

  • 예외 : if(empty())

카드게임(1) (W4_P2)

• 선언할 변수 : winner, p1_score, p2_score, last_score
• for문 안에서는 int player1 = q1.front(); / int player2 = q2.front(); 를 하기
• 이긴 사람에게 계속해서 채력을 추가해줌

if(player1 > player2) 
{
  winner = 1;
  last_score = player1 - player2;
  p1_score++;
}

카드게임(2) (W4_P4)

• w2_p2 에서 일부분만 수정하면 끝!
• 진 사람에게 채력을 추가해줌 (<=> w2_p2 문제는 이긴 사람에게 채력을 추가해줬음)

벡터

• void insert(int idx, int data)

  • 예외 종류
  • 배열이 꽉 찼을때 reserve( ) 호출 => if ( n == capacity )
  • if ( idx < 0 || idx >= n )

• void reserve(int size) : 더블링 구현 (사이즈 2배로 늘려줌)

  • int newArr = new int[size]; // 새로운 배열에 복사
  • 맨 마지막에 capacity = size 로 설정하기!!
  • arr = newArr;
  • delete[ ] newArr;

• void erase(int idx)

• 부수적인 메소드 : size, empty, at, set

리스트

• 멤버변수 : node header, node trailer, int listSize
• 생성자 : 반드시 header 와 trailer 에 NULL 을 할당하지 않고, new node; 를 할당하기!!!!
• begin()
  • header -> next 를 리턴. => header의 "다음" 노드를 리턴!!!!!
• end()
  • trailer 를 리턴
• insert
  • 주어진 pos "앞에다" insert
• erase
  • 예외구문 : if (pos == trailer), if (empty())

• 부가적인 메소드들
  • nextP : pos가 trailer이면 그대로 있고, 아니면 pos->next 로 이동
  • prevP : pos->prev가 header 이면 그대로 있고, 아니면 pos->prev 로 이동
  • insertFront, insertBack, eraseFront, eraseBack
  • empty, find, print

W5_P2

• 자주하는 실수 : for문 안에서 p = list.nextP(p); 하는것 까먹질말것!!!

• for문 돌릴때 3가지 CASE 로 나눌것

• CASE1) if(i == 0) 즉, if(p == list.begin()) 으로, 맨 처음 합을 구할때

  • sum += p->data; sum += p->next->data;

• CASE2) if(i == n-1) 즉, if(p == list.end()->prev)), 맨 마지막 합을 구할때

  • sum += p->data; sum += p->prev->data;

• CASE3) 그냥 중간에 합을 구할때

  • sum += p->prev->data; sum += data; sum += p->next->data;

W5_P4

반드시!!!!!!!!!!!!!!!!!!!!!!! 리스트 사이즈가 1일때를 따로 예외처리해줄 것.

if(count == 1) // 리스트가 사이즈가 1일때
  cout << 0;  // 최댓값과 최솟값의 차이는 0
  break;     // 그 테스트케이스에 대한 반복문을 종료시킴

트리

• 노드 멤버변수 : node parent, vector<node> childList, int data

  • 노드 생성자 : this->parent, this->data 값을 할당

• find

  • for문 돌려서 if(data == list[i]->data) 일때의 인덱스 i를 리턴

• 생성자

  • root 노드 초기화후 nodeList에 push_back

• void insertNode(int parData, int data)

  • nodeList에다 newNode 를 push_back 해주는 것 까먹지 말것!
  • 예외
    • if( find (data, nodeList) != -1) => 삽입하려는 data노드가 이미 존재하는 경우
    • int idx = find(parData, nodeList) / if(idx == -1) => 부모 노드가 트리에 없는 경우
      

• void deleteNode(int data)

  • 예외 : if(idx == -1) 2) if(delNode == root)
  • 삭제할 것들 목록 3개 (부모의 childList에서, 메모리에서, nodeList에서 삭제)
    // vector<node*>& child = parNode->childList;
    • child.erase(child.begin() + find(data, child)); // 부모의 childList에서 삭제
    • delete nodeList[idx]; // 메모리에서 삭제. => delete delNode; 로 대체 가능!!!
    • nodeList.erase(nodeList.begin() + idx); // nodeList에서 삭제

• 부가적인 메소드들

  • printAncestors, printDepth
    • if(curNode == root) 가 될때만 신경써서 처리 잘 해주기!
  • printParent, printChild, maxChild

전위순회, 후위순회

• W7_P1 (전위순회)

void Tree::preOrder(node* pos, int count)
{
	cout << count << ' ';
	for (int i = 0; i < pos->childList.size(); i++)
	{
		preOrder(pos->childList[i], count + 1);
	}
}

• W7_P3 (후위순회)
  • W7_P1 전위순회에서 cout 출력 위치를 for문 아래로만 바꿔주면 끝이다!

void Tree::preOrder(node* pos, int count)
{
	for (int i = 0; i < pos->childList.size(); i++)
	{
		preOrder(pos->childList[i], count + 1);
	}
	cout << count << ' ';
}

• W7_P2 (external 노드 개수 구하기)

int Tree::postOrder(node* pos)
{
	int count = 0;
	if (pos->childList.size() == 0)   // external 노드인 경우
		return 1;

	for (int i = 0; i < pos->childList.size(); i++)  // 자신의 각 자식으로 부터 계산된 
	{                                               // external 노드 개수를 합산해서 그 결과를 자신의 external 노드 개수로 만들기
		count += postOrder(pos->childList[i]);
	}
	return count;
}

• 폴더 용량 계산하기 (W7_P4)
  • 노드의 데이터 필드로 int data 외에 int folderSize; 추가
  • 후위순회 진행시 return할때 count 에다 자신의 폴더용량 값(pos->size)도 추가해서 리턴 하는 것 까먹지 말기!

int Tree::postOrder(node* pos)
{
	int count = 0;
	if (pos->childList.size() == 0)
		return pos->size;
	for (int i = 0; i < pos->childList.size(); i++)
	{
		count += postOrder(pos->childList[i]);
	}
	return count + pos->size; // 각 서브트리의 용량을 sum에 모두 더했다면, 마지막에는 자신의 폴더 용량도 더해야지 총 용량이 된다.
}

void Tree::folderSize(int data, int folder)
{
	int idx = find(data, nodeList);
	if (idx == -1)
	{
		cout << -1 << endl;
		return;
	}

	node* curNode = nodeList[idx];
	curNode->size = folder;
}