231217(덱 구현)

덱을 구현해보자..

우선 헤더파일이다.

#ifndef __DEQUE_H__
#define __DEQUE_H__

#define TRUE	1
#define FALSE	0

typedef int Data;

typedef struct _node
{
	Data data;
	struct _node * next;
	struct _node * prev;
} Node;

typedef struct _dlDeque
{
	Node * head;
	Node * tail;
} DLDeque;

typedef DLDeque Deque;

void DequeInit(Deque * pdeq);
int DQIsEmpty(Deque * pdeq);

void DQAddFirst(Deque * pdeq, Data data);
void DQAddLast(Deque * pdeq, Data data);

Data DQRemoveFirst(Deque * pdeq);
Data DQRemoveLast(Deque * pdeq);

Data DQGetFirst(Deque * pdeq);
Data DQGetLast(Deque * pdeq);

#endif

요구사항은 양뱡향 연결리스트를 잘 바꾸면 된다. 이때 더미가 있는 양뱡향 연결을 사용하는게 좋을까?

양뱡향 연결리스트 만들때 LInsert에서 썼던 트릭을 생각해보자.

void LInsert(List* plist, Data data)
{
	Node* temp = (Node*)malloc(sizeof(Node));
	temp->data = data;

	temp->next = plist->head; //첫 노드에는 NULL 할당
	**if (plist->head != NULL)
		plist->head->prev = temp;**

	temp->prev = NULL;
	plist->head = temp;

	(plist->numOfData)++;
}

#include <stdio.h>
#include <stdlib.h>
#include "Deque.h"

void DequeInit(Deque* pdeq)
{
	pdeq->head = NULL;
	pdeq->tail = NULL;
}

int DQIsEmpty(Deque* pdeq)
{
	if (pdeq->head == NULL || pdeq->tail == NULL) // &&으로 할지, ||으로 할지 추후 결정 필요
		return 1;
	else
		return 0;
}

void DQAddFirst(Deque* pdeq, Data data)
{
	Node* tmpN = (Node*)malloc(sizeof(Node)); //임시 노드 생성
	tmpN->data = data; //데이터 저장

	if (pdeq->head == NULL)
	{
		pdeq->head = tmpN;//머리 할당
		pdeq->tail = tmpN;//꼬리 할당
	}
	else
	{
		tmpN->next = pdeq->head; //새 노드에 머리 연결
		pdeq->head->prev = tmpN; //머리에 새 노드 연결
		pdeq->head = tmpN; //머리 이동
	}
	tmpN->prev = NULL;
		
}

void DQAddLast(Deque* pdeq, Data data)
{
	Node* tmpN = (Node*)malloc(sizeof(Node)); //임시 노드 생성
	tmpN->data = data; //데이터 저장

	if (pdeq->tail == NULL)
	{
		pdeq->tail = tmpN;
		pdeq->head = tmpN;
	}
	else
	{
		tmpN->prev = pdeq->tail;
		pdeq->tail->next = tmpN;
		pdeq->tail = tmpN;
	}
}

Data DQRemoveFirst(Deque* pdeq)
{
	if (pdeq->head == NULL)
	{
		printf("Memorry error!");
		exit(-1);
	}
	Node* rNode = pdeq->head; //헤드 주소 백업
	Data rdata = pdeq->head->data; //헤드 데이터 백업

	if (pdeq->head == pdeq->tail)
	{
		pdeq->head = NULL;
	}
	else
		pdeq->head = pdeq->head->next; //헤드 이동
	

	free(rNode); //노드 메모리 할당 해제

	return rdata;
}

Data DQRemoveLast(Deque* pdeq)
{
	if (pdeq->tail == NULL)
	{
		printf("Memorry error!");
		exit(-1);
	}
	Node* rNode = pdeq->tail; //꼬리 주소 백업
	Data rdata = pdeq->tail->data; //꼬리 데이터 백업

	if (pdeq->head == pdeq->tail)
	{
		pdeq->tail = NULL;
	}
	else
		pdeq->tail = pdeq->tail->prev; //꼬리 이동

	free(rNode); //노드 메모리 할당 해제

	return rdata; //데이터 반환
}

Data DQGetFirst(Deque* pdeq)
{
	if (pdeq->head == NULL)
	{
		printf("Memorry error!");
		exit(-1);
	}
	Data rdata = pdeq->head->data; 

	return rdata;
}

Data DQGetLast(Deque* pdeq)
{
	if (pdeq->tail == NULL)
	{
		printf("Memorry error!");
		exit(-1);
	}
	Data rdata = pdeq->tail->data;

	return rdata;
}

덱 소스코드이다.

#include <stdio.h>
#include "Deque.h"

int main(void)
{
	// Deque의 생성 및 초기화 ///////
	Deque deq;
	DequeInit(&deq);

	// 데이터 넣기 1차 ///////
	DQAddFirst(&deq, 3); 
	DQAddFirst(&deq, 2); 
	DQAddFirst(&deq, 1); 

	DQAddLast(&deq, 4); 
	DQAddLast(&deq, 5); 
	DQAddLast(&deq, 6);

	// 데이터 꺼내기 1차 ///////
	while(!DQIsEmpty(&deq))
		printf("%d ", DQRemoveFirst(&deq));

	printf("\\n");

	// 데이터 넣기 2차 ///////
	DQAddFirst(&deq, 3); 
	DQAddFirst(&deq, 2); 
	DQAddFirst(&deq, 1);
	
	DQAddLast(&deq, 4); 
	DQAddLast(&deq, 5); 
	DQAddLast(&deq, 6);

	// 데이터 꺼내기 2차 ///////
	while(!DQIsEmpty(&deq))
		printf("%d ", DQRemoveLast(&deq));

	return 0;
}

덱 메인

Untitled

실행결과

책에서 나온 소스코드와 내 코드를 비교해보자. 코드를 짜면서도 간결하게 더 짤 수 있을 것 같다는 생각이 계속 들었다.

void DQAddFirst(Deque* pdeq, Data data)
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	newNode->next = pdeq->head; //첫 노드일 경우에는, next에 NULL 할당/두번째 이후부터는 새 노드와 헤드 연결
	if (pdeq->head == NULL) 
		pdeq->tail = newNode; // 새 노드가 첫 노드일시 꼬리도 새 노드에 할당.
	else
		pdeq->head->prev = newNode; // 아닐경우, 헤드와 새 노드 연결

	newNode->prev = NULL; 
	pdeq->head = newNode; //헤드 이동
}

강의에 나온 코드인데… 그냥 양뱡향때랑 거의 다른게 없다.

내 코드랑 비교해보면..

void DQAddFirst(Deque* pdeq, Data data)
{
	Node* tmpN = (Node*)malloc(sizeof(Node)); //임시 노드 생성
	tmpN->data = data; //데이터 저장

	if (pdeq->head == NULL)
	{
		pdeq->head = tmpN;//머리 할당
		pdeq->tail = tmpN;//꼬리 할당
	}
	else
	{
		tmpN->next = pdeq->head; //새 노드에 머리 연결
		pdeq->head->prev = tmpN; //머리에 새 노드 연결
		pdeq->head = tmpN; //머리 이동
	}
	tmpN->prev = NULL;
		
}

문장은 거의 비슷한데, 분기문에서 차이가 있다. 이건 사실 양뱡향 할때도 다뤘던 내용이다.

tmpN->next = pdeq->head; //새 노드에 머리 연결