반응형
다음은 백준 넷에 있는 문제를 2중연결 리스트를 활용 하여 풀었다.
우선은 이중연결리스를 구현의 Node 생성을 위해 구조체 선언을 하였고 구조체 안에 동일한 포인터형 구조체를 입력 하였다.
이중연결리스트의 경우 핵심은 노드의 위치정보를 기억할 주소값을 저장할 포인터가 필수 인데,
동일한 구조체가 아니면 데이터 형 변수들을 담을수 없기에 사이즈 및 같은 형 같은 데이터 들이 들어있는 구조체를 포인터로 사용 하여
야 하는게 핵심이다.
구조체 안에 포인터 구조체 선언 이라고 생각을 하면 어렵지만, 구조체 안의 구조체는 단지 , 노드의 주소값 들을 저장 할수있게 만들었
다고 생각 하면 쉬울거 같다,
항상 시작점의 위치는 구조체 포인터형 번수인 head 란 구조체 이고,
이 구조체가 연결을 하지 않는다면 널값을 하고 있을것이다.
도한 새로운 노드를 생성 할때 마다 count 횟수를 증가 시켰고 , 이 증가 된 카운터 횟수로 ,
노드의 위치를 탐색 할수 있다.
for 문을 돌리는 방법은 우선은 헤드는 시작 주소를 가지고 있기에 head의 위치 정보는 바껴서는 안된다.
따라서 임시로 저장 할 같은 구조체 형식의 구조체 포인터를 선언한 후 , temp =head 헤드의 모든 정보를 템프에 그냥 담아 버린다.
그렇게 된다면 헤드 와 템프는 똑같이
첫번째 노드를 가리키는 주소값을 가진 구조체가 될것이고 ,
for문을 돌면서 ,
주의 해야 할점은!
temp =temp 계속 계속 담으면 .. 필자의 경우 부끄럽지만 노드가 한칸식 이동 할거라 생각했다....
하지만 이렇게 할경우 , 제자리 걸음이 된다는 것이다 !,
temp 를 한칸씩 노드 따라 가게 하고 싶다면 !!!!
temp = temp.next_node 를 담아야 할것이다!!!!
#include <stdio.h>
#include <iostream>
using namespace std;
typedef struct Node // typedef srtcut 자료형 을 의미 한다. // Node <-- 자료형의 이름.
{
Node *next_node; // 포인터화 시켜서 다음 노드의 주소 값을 넣기 위해 포인터 선언 .
int cnt; // 노드의 생성 개수 를 알기 위해서 cnt 를 구조체에 넣는다.
int data; // 구조체의 넣을 데이터
}node; // 구조체 별명??????
void init(Node *head) // 구조체의 자료형을 초기화 하기 위해서 필요하다 .
{
head->cnt = 0; // 노드를 연결한 순간 첫 생성 노드 부터 cnt 가 증가 하여야 하기 때문에 , 0으로 초기화 .
head-> next_node = NULL; // head 노드의 경우 연결 하기 전까진 가리키는 곳이 없기에 NULL로 초기화 .
head-> data = 0; // data 역시 head노드의 경우 주소 값만 가지기 위해서 필요함.
}
void insert_node(Node *head, int n) //노드 삽입을 위해서 구현한 함수.
{
Node* newnode = ((Node*)malloc(sizeof(Node))); // 포인터형의 노드를 malloc <-- 동적할당 하겠다. (sizeof(구조체 크기만큼))
Node* temp;
if ((head)->next_node == NULL) //만약 헤드의 Next_node 가 가리키는 주소 값이 없다면.. 연결이 최초로 해주는 곳
{
head->next_node = newnode; // if문의 구현 head가 가리키는 노드를 새로 생성한 New_node 가리키게 함.
head->cnt += 1; // 새로 생성된 노드가 있으므로 cnt 가 +1 증가 하게 됨.
newnode->data = n; // 이부분은 insert함수에서 받아 온메게 변수 값을 새로 생성한 노드에 입력 한다.
// 따라서 순차적으로 본다면 입력받은 메게변수를 받아와 노드를 생성하게 되고 , 생성된 노드에 //입력 값을 넣는다.
}
else { // 헤드 노드가 가리키는 곳이 있다면, insert 함수가 호출된 이상. 1개의 노드는 생성해야 한다.//
temp = head; // 하지만 헤드노드의 가리키는 곳이 있으므로 다음 노드의 주소값을 다음노드에 연결 시켜 주기 위해
// temp 에 헤드의 정보를 넣는다.. 즉 temp는 헤드의 다음노드주소값을 가지게 된다.
for (int i = 0; i < head->cnt; i++)
{
temp = temp->next_node; // 노드의 마지막 주소값을 알기 위해 head 부분에 미리 INDEX로 활용할 cnt 변수를 선언 // 했으므로 cnt 값만큼 for 문이 돌면서 주소값의 마지막 생성 노드로 갈수 있다
} // for을 돌며 주소로 찾아 간다음 거기서 가리키는 또 주소를 찾아가고 이런식으로 for // 를 돈다
temp->next_node = newnode; // 최종 번지수를 찾은 temp에 newnode의 주소 값을 입력.
(head)->cnt++; // 또다른 노드가 생겼으므로 head의 카운터 값에 cnt로 증가 시킨다.
newnode->data = n; // 이후 생성된 노드의 데이터에 입력된 값을 삽입.
}
}
void pop(Node *head) //Stack구현 함수 //Node* temp 의 경우 head 값을 입력 하게 되므로 초기화가 필요 하지 않지만.
{ //Node *temp_tail 의 경우 . NULLPTR로 초기화 하여야 한다.
Node* temp_tail = nullptr; // 삭제할 노드의 주소값을 가진 노드 삭제후는 꼬리가 되므로 주소값 cnt-1번째 노드.
Node* temp; //head의 주소 정보는 절대 변해서는 안된다 .따라서 이번에도 temp에 head의 정보를 복사.
temp= head;
if (head->next_node == NULL) //팝의 경우 제일 stak의 제일 위에 쌓인것을 의미//head의 주소값을 시작으로 포문을 돌면서 // 최종 주소 값으로 가면 다음의 노드가 없다면 노드 연결 이 안되어 있을것이 므로, NULL 값.
{
cout << "-1" << endl; // NULL 값이 라면 -1일 출력 한다.
cout << "===========" << endl; // 출력문
return; // 이후 함수 리턴 후 종료
}
//아래의 포문은 끝에 있는 노드의 값을 출력 하 노드 삭제 하기 위한 구현 부
for (int i = 0; i < head->cnt; i++) // 위의 if 문 조건이 만족 하지 않는다면 , for문으로 올것이며 , 그경우 NULL값이 아닌걸 의미,
{ // for문은 cnt 만큼 돌아야 끝 노드 까지 도달 할수 있다.
if (i == (head->cnt)-1) { //따라서 조건문의 cnt 만큼 도는 도중 cnt-1의 지점에서 Node_tail 에 주소 값 저장.
// ( 마지막 노드를 삭제 하기 위해선 , 마지막 노드의 주소 값을 가르키는 노드가 필요 함.)
// (직전의 노드가 마지막 노드를 가리킨다.)
temp_tail= temp; // temp는 마지막 노드 앞번재의 주소 값을 가진
}
temp = temp->next_node;
}
cout << temp->data << endl;
temp_tail->next_node = NULL;
head->cnt--;
}
void Size(Node *head)
{
cout << head->cnt << endl;
}
void num(Node *head)
{
if (head->cnt > 0)
{
cout << 0;
}
if (head->cnt == 0) {
cout << 1;
}
}
void menue() // UI 사용자 화면에 뿌려줄 함수.
{
cout << "1. push" << endl;
cout << "2.pop" << endl;
cout << "3. size" << endl;
cout << "4. empty" << endl;
cout << "5. top" << endl;
}
void top(Node *head)
{
Node *temp;
temp = head;
for (int i = 0; i < head->cnt; i++)
{
temp = temp->next_node;
if (i == head->cnt) {
cout << temp->data;
}
}
cout << temp->data << endl;
}
int show(Node *head)
{
int n;
int k;
int a;
cin >> n;
cout << "명령의 수를 입력 하세요" << endl;
cout << "========================" << endl;
//cout << n << endl;
menue();
while (1) {
cin >> a;
switch (a)
{
case 1:
cin >> k;
insert_node(head, k);
break;
case 2:
pop(head);
break;
case 3:
Size(head);
break;
case 4:
num(head);
break;
case 5:
top(head);
break;
return 0;
}
}
}
int main()
{
Node *head = (Node*)malloc(sizeof(Node));
int n = 0 ;
init(head);
show(head);
insert_node(head, n);
system("pause");
}
반응형
'프로그래밍 _공부자료. > C++ 공부' 카테고리의 다른 글
| C++ 선택정렬 (0) | 2019.12.03 |
|---|---|
| C++ 버블정렬 (0) | 2019.12.03 |
| 배열의 숫자 의 차 최대치 구하기. (0) | 2019.11.27 |
| 은행 ATM기 C++로 작성. (0) | 2019.11.25 |
| 역 방향 행렬 360도 회전하기. (0) | 2019.11.25 |
댓글