#include <stdio.h> //writer 5396952 Hyeonmin LEE
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
typedef int element;
typedef struct DlistNode{
element data;
struct DlistNode *llink;
struct DlistNode *rlink;
} DlistNode;
typedef struct DequeType{
DlistNode *head;
DlistNode *tail;
} DequeType;
void error(char *message)
{
fprintf(stderr,"%s\n", message);
exit(1);
}
void init(DequeType *dq){
dq->head = NULL;
dq->tail = NULL;
}
DlistNode* createNode(DlistNode *llink, element item, DlistNode *rlink)
{
DlistNode *newNode = (DlistNode*)malloc(sizeof(DlistNode));
if(newNode == NULL)
{
error("Memory allocation error");
}
newNode->llink = llink;
newNode->rlink = rlink;
newNode->data = item;
return newNode;
}
int isEmpty(DequeType *dq)
{
if(dq->head == NULL) return TRUE;
else return FALSE;
}
void addRear(DequeType *dq, element item)
{
DlistNode *newRear = createNode(dq->tail, item , NULL);
if(isEmpty(dq))
{
dq->head = newRear;
dq->tail = newRear;
}
else{
dq->tail->rlink = newRear;
dq->tail = newRear;
}
}
void addFront(DequeType *dq, element item)
{
DlistNode *newFront = createNode(NULL, item, dq->head);
if(isEmpty(dq))
{
dq->head = newFront;
dq->tail = newFront;
}
else{
dq->head->llink = newFront;
dq->head = newFront;
}
}
element deleteFront(DequeType *dq)
{
if(isEmpty(dq))
{
error("Empty deque");
}
//printf("got in deleteFront\n");
element pop = dq->head->data;
//printf("saved data\n");
dq->head = dq->head->rlink;
free(dq->head->llink);
if(dq->head == NULL)// nothing in the deque
{
init(dq);
}
else {
dq->head->llink = NULL;
}
//printf("moved front\n");
return pop;
}
element deleteRear(DequeType *dq) {
if(dq->tail == NULL)
{
error("Empty rear");
}
//printf("got in deleteRear\n");
element pop = dq->tail->data;
//printf("saved data\n");
dq->tail = dq->tail->llink;
free(dq->tail->rlink);
if(dq->tail == NULL)// nothing in the deque
{
init(dq);
}
else {
dq->tail->rlink = NULL;
}
//printf("moved front\n");
return pop;
}
void display(DequeType *dq)
{
DlistNode *tracker;
printf("(");
for(tracker = dq->head; tracker != NULL; tracker = tracker->rlink)
{
printf("%d %p %p\n ", tracker->data, tracker->llink, tracker->rlink);
}
printf(")");
}
int main()
{
DequeType deque;
init(&deque);
addFront(&deque, 10);
addFront(&deque, 20);
addFront(&deque, 30);
display(&deque);
deleteFront(&deque);
deleteRear(&deque);
display(&deque);
return 0;
}
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
typedef int element;
typedef struct DlistNode{
element data;
struct DlistNode *llink;
struct DlistNode *rlink;
} DlistNode;
typedef struct DequeType{
DlistNode *head;
DlistNode *tail;
} DequeType;
void error(char *message)
{
fprintf(stderr,"%s\n", message);
exit(1);
}
void init(DequeType *dq){
dq->head = NULL;
dq->tail = NULL;
}
DlistNode* createNode(DlistNode *llink, element item, DlistNode *rlink)
{
DlistNode *newNode = (DlistNode*)malloc(sizeof(DlistNode));
if(newNode == NULL)
{
error("Memory allocation error");
}
newNode->llink = llink;
newNode->rlink = rlink;
newNode->data = item;
return newNode;
}
int isEmpty(DequeType *dq)
{
if(dq->head == NULL) return TRUE;
else return FALSE;
}
void addRear(DequeType *dq, element item)
{
DlistNode *newRear = createNode(dq->tail, item , NULL);
if(isEmpty(dq))
{
dq->head = newRear;
dq->tail = newRear;
}
else{
dq->tail->rlink = newRear;
dq->tail = newRear;
}
}
void addFront(DequeType *dq, element item)
{
DlistNode *newFront = createNode(NULL, item, dq->head);
if(isEmpty(dq))
{
dq->head = newFront;
dq->tail = newFront;
}
else{
dq->head->llink = newFront;
dq->head = newFront;
}
}
element deleteFront(DequeType *dq)
{
if(isEmpty(dq))
{
error("Empty deque");
}
//printf("got in deleteFront\n");
element pop = dq->head->data;
//printf("saved data\n");
dq->head = dq->head->rlink;
free(dq->head->llink);
if(dq->head == NULL)// nothing in the deque
{
init(dq);
}
else {
dq->head->llink = NULL;
}
//printf("moved front\n");
return pop;
}
element deleteRear(DequeType *dq) {
if(dq->tail == NULL)
{
error("Empty rear");
}
//printf("got in deleteRear\n");
element pop = dq->tail->data;
//printf("saved data\n");
dq->tail = dq->tail->llink;
free(dq->tail->rlink);
if(dq->tail == NULL)// nothing in the deque
{
init(dq);
}
else {
dq->tail->rlink = NULL;
}
//printf("moved front\n");
return pop;
}
void display(DequeType *dq)
{
DlistNode *tracker;
printf("(");
for(tracker = dq->head; tracker != NULL; tracker = tracker->rlink)
{
printf("%d %p %p\n ", tracker->data, tracker->llink, tracker->rlink);
}
printf(")");
}
int main()
{
DequeType deque;
init(&deque);
addFront(&deque, 10);
addFront(&deque, 20);
addFront(&deque, 30);
display(&deque);
deleteFront(&deque);
deleteRear(&deque);
display(&deque);
return 0;
}
댓글
댓글 쓰기