[TIL] 21-07-20

알고리즘 스터디

• 백준 2629 양팔 저울 O
• 종만북 18장 선형 자료 구조 O
• 종만북 19장 큐와 스택, 데크 O
• 백준 1406 에디터 O
• 백준 5397 키로거 O
• 백준 3190 뱀 O
• 백준 3078 좋은 친구 O
• 백준 3015 오아시스 재결합 ~

📌참고자료

• c++ deque container
• c++ 단일 연결 리스트 구현

#include <iostream>
using namespace std;
//노드 구조체
struct Node {
	int data;
	struct Node* link; 
};
//헤드 노드 구조체
struct HeadNode {
	Node* head; 
};
//단일 연결 리스트 클래스
class Singlist {
public:
	//리스트 생성 
	HeadNode* createList() {
		HeadNode* H = new HeadNode; 
		H->head = NULL;
		return H;
	}
	//리스트의 마지막에 노드 삽입
	void addNode(HeadNode* H, int x) { 
		Node* NewNode = new Node; 
		Node* LastNode; 
		NewNode->data = x;
		NewNode->link = NULL;
		// 리스트가 비어있을 경우
		if (H->head == NULL) { 
			H->head = NewNode;
			return;
		}
		// 연결리스트의 마지막 노드를 찾는 과정
		LastNode = H->head; 
		while (LastNode->link != NULL) 
  			LastNode = LastNode->link; 
		LastNode->link = NewNode; 
	}
	// 리스트의 마지막 노드 삭제
	void deleteNode(HeadNode* H) {  
		Node* prevNode; 
		Node* delNode; 
		// 리스트가 빈 경우
		if (H->head == NULL) return; 
  		// 한 개의 노드만 가진 경우
		if (H->head->link == NULL) { 
			delete H->head;  // head가 가리키던 메모리 공간을 힙 영역에 반환
			H->head = NULL;  // 헤드 노드의 link 부분인 head를 null로 설정
			return;
		}
  		// 리스트에 노드 여러 개 있는 경우
		else {
			prevNode = H->head;
			delNode = H->head->link;
			while (delNode->link != NULL) { //delNode가 마지막노드가 될 때까지
				prevNode = delNode;       // prevNode를 한칸씩 가고
				delNode = prevNode->link; // delNode도 한칸씩 끝으로 간다
			}
			free(delNode);  // 마지막 노드의 메모리 공간을 반환
			prevNode->link = NULL;
		}
	}
	// 리스트의 특정 노드 삭제
	void deleteThisNode(HeadNode* H, int deldata) {
		Node* delNode;  // 삭제하려는 노드
		Node* prevNode; // 삭제하려는 노드의 앞 노드
		prevNode = H->head;
		while (prevNode->link->data != deldata) {
			prevNode = prevNode->link;
		}
		delNode = prevNode->link;   // prevNode가 가리키는 노드가 삭제할 노드
		prevNode->link = delNode->link;  // prevNode가 delNode 다음 노드를 가리키도록
		free(delNode);  // delNode 삭제
		cout << deldata << " 데이터 값을 가진 노드가 삭제됐습니다." << endl;
		return;
	}
	// 리스트에 특정 노드 삽입
	void addThisNode(HeadNode* H, int afterthisdata, int adddata) {
		// afterthisdata 뒤에 adddata 삽입
		Node* prevNode;  //삽입하려는 노드의 이전 노드
		prevNode = H->head;
		while (prevNode->data != afterthisdata) {
			prevNode = prevNode->link;
		}
		Node* NewNode = new Node;
		NewNode->data = adddata;
		NewNode->link = prevNode->link;
		prevNode->link = NewNode;
		return;
	}
	// 리스트의 특정 노드 검색
	void searchNode(HeadNode* H, int thisdata) {
		Node* someNode;
		someNode = H->head;
		while (someNode->data != thisdata) {
			someNode = someNode->link;
		}
		cout << thisdata << " 데이터를 검색하는 데 성공했습니다." << endl;
	}
	// 연결리스트 출력
	void printList(HeadNode* L) {
		//노드 순서대로 리스트 출력
		Node* p = L->head;
		while (p != NULL) {
			cout << p->data;
			p = p->link;
			if(p != NULL) cout << " -> ";
		}
	}
};