Mokwon Univ
알고리즘 - 이중 연결 리스트
용학도리
2008. 8. 16. 16:17
/*****************************************************************************
* *
* ------------------------------- dlist.c -------------------------------- *
* *
*****************************************************************************/
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "dlist.h"
void select(void);
void print_next();
void print_prev();
int search();
DList *start;
void main(void)
{
start=(DList *)malloc(sizeof(DList));
dlist_init(start,NULL);
select();
}
void select(void)
{
int input;
void *add;
while(1)
{
printf("n");
printf(" ┏━━━ dlist menu v1.0━━━━━┓n");
printf(" ┃ 1 -> list init ┃n");
printf(" ┃ 2 -> list insert prev ┃n");
printf(" ┃ 3 -> list insert next ┃n");
printf(" ┃ 4 -> list remove prev ┃n");
printf(" ┃ 5 -> list remove next ┃n");
printf(" ┃ 6 -> list search ┃n");
printf(" ┃ 7 -> list print next ┃n");
printf(" ┃ 8 -> list print prev ┃n");
printf(" ┃ 0 -> Exit ┃n");
printf(" ┣━━━━━━━━━━━━━━━━┫n");
printf(" ┃select number ┃n");
printf(" ┗━━━━━━━━━━━━━━━━┛n");
printf(" ==> ");
scanf("%d",&input);
switch(input)
{
case 1:
dlist_destroy(start);
dlist_init(start,NULL);
system("cls");
break;
case 2:
if((add=(void *)malloc(sizeof(int)))==NULL)
return;
system("cls");
printf(" Data prev insert -> ");
scanf("%d",&add);
if(dlist_ins_prev(start,dlist_head(start),add) !=0 )
{
printf(" Not Insert ");
return;
}
printf(" Insert Ok!nn");
break;
case 3:
if((add=(void *)malloc(sizeof(int)))==NULL)
return;
system("cls");
printf(" Data next insert -> ");
scanf("%d",&add);
if(dlist_ins_next(start,dlist_tail(start),add) !=0 )
{
printf(" Not Insert ");
return;
}
printf(" Insert Ok!nn");
break;
case 4:
system("cls");
printf(" Data remove -> ");
scanf("%d",add);
dlist_remove(start,dlist_tail(start),NULL);
break;
case 5:
system("cls");
printf(" Data remove -> ");
scanf("%d",add);
dlist_remove(start,dlist_head(start),NULL);
break;
case 6:
system("cls");
printf(" Input data ==>");
scanf("%d",&add);
search(add);
break;
case 7:
system("cls");
print_next();
break;
case 8:
system("cls");
print_prev();
break;
case 0:
dlist_destroy(start);
return;
default :
system("cls");
printf(" You select wrong number Try to again selectnn");
break;
}
}
}
void print_next()
{
DListElmt *print_next;
if((print_next=(DListElmt *)malloc(sizeof(DListElmt)))==NULL)
return;
print_next = dlist_head(start);
printf("This size is %d n",dlist_size(start));
printf(" List --> Head");
while(print_next != NULL)
{
printf(" --> %d", print_next->data);
print_next = dlist_next(print_next);
}
printf(" --> NULL n");
return;
}
void print_prev()
{
DListElmt *print_prev;
if((print_prev=(DListElmt *)malloc(sizeof(DListElmt)))==NULL)
return;
print_prev = dlist_tail(start);
printf("This size is %d n",dlist_size(start));
printf(" List --> Tail");
while(print_prev != NULL)
{
printf(" --> %d", print_prev->data);
print_prev = dlist_prev(print_prev);
}
printf(" --> NULL n");
return;
}
int search(void *data)
{
DListElmt *find;
if((find=(DListElmt *)malloc(sizeof(DListElmt)))==NULL)
return -1;
for(find=dlist_head(start);find!=NULL;find=dlist_next(find))
{
if(find->data==data)
{
printf(" Data Find Success n");
return 0;
}
}
printf(" Data no Find n");
return 0;
}
/*****************************************************************************
* *
* ------------------------------ dlist_init ------------------------------ *
* *
*****************************************************************************/
void dlist_init(DList *list, void (*destroy)(void *data)) {
/*****************************************************************************
* *
* Initialize the list. *
* *
*****************************************************************************/
list->size = 0;
list->destroy = destroy;
list->head = NULL;
list->tail = NULL;
return;
}
/*****************************************************************************
* *
* ---------------------------- dlist_destroy ----------------------------- *
* *
*****************************************************************************/
void dlist_destroy(DList *list) {
void *data;
/*****************************************************************************
* *
* Remove each element. *
* *
*****************************************************************************/
while (dlist_size(list) > 0) {
if (dlist_remove(list, dlist_tail(list), (void **)&data) == 0 && list->
destroy != NULL) {
/***********************************************************************
* *
* Call a user-defined function to free dynamically allocated data. *
* *
***********************************************************************/
list->destroy(data);
}
}
/*****************************************************************************
* *
* No operations are allowed now, but clear the structure as a precaution. *
* *
*****************************************************************************/
memset(list, 0, sizeof(DList));
return;
}
/*****************************************************************************
* *
* ---------------------------- dlist_ins_next ---------------------------- *
* *
*****************************************************************************/
int dlist_ins_next(DList *list, DListElmt *element, const void *data) {
DListElmt *new_element;
/*****************************************************************************
* *
* Do not allow a NULL element unless the list is empty. *
* *
*****************************************************************************/
if (element == NULL && dlist_size(list) != 0)
return -1;
/*****************************************************************************
* *
* Allocate storage for the element. *
* *
*****************************************************************************/
if ((new_element = (DListElmt *)malloc(sizeof(DListElmt))) == NULL)
return -1;
/*****************************************************************************
* *
* Insert the new element into the list. *
* *
*****************************************************************************/
new_element->data = (void *)data;
if (dlist_size(list) == 0) {
/**************************************************************************
* *
* Handle insertion when the list is empty. *
* *
**************************************************************************/
list->head = new_element;
list->head->prev = NULL;
list->head->next = NULL;
list->tail = new_element;
}
else {
/**************************************************************************
* *
* Handle insertion when the list is not empty. *
* *
**************************************************************************/
new_element->next = element->next;
new_element->prev = element;
if (element->next == NULL)
list->tail = new_element;
else
element->next->prev = new_element;
element->next = new_element;
}
/*****************************************************************************
* *
* Adjust the size of the list to account for the inserted element. *
* *
*****************************************************************************/
list->size++;
return 0;
}
/*****************************************************************************
* *
* ---------------------------- dlist_ins_prev ---------------------------- *
* *
*****************************************************************************/
int dlist_ins_prev(DList *list, DListElmt *element, const void *data) {
DListElmt *new_element;
/*****************************************************************************
* *
* Do not allow a NULL element unless the list is empty. *
* *
*****************************************************************************/
if (element == NULL && dlist_size(list) != 0)
return -1;
/*****************************************************************************
* *
* Allocate storage to be managed by the abstract data type. *
* *
*****************************************************************************/
if ((new_element = (DListElmt *)malloc(sizeof(DListElmt))) == NULL)
return -1;
/*****************************************************************************
* *
* Insert the new element into the list. *
* *
*****************************************************************************/
new_element->data = (void *)data;
if (dlist_size(list) == 0) {
/**************************************************************************
* *
* Handle insertion when the list is empty. *
* *
**************************************************************************/
list->head = new_element;
list->head->prev = NULL;
list->head->next = NULL;
list->tail = new_element;
}
else {
/**************************************************************************
* *
* Handle insertion when the list is not empty. *
* *
**************************************************************************/
new_element->next = element;
new_element->prev = element->prev;
if (element->prev == NULL)
list->head = new_element;
else
element->prev->next = new_element;
element->prev = new_element;
}
/*****************************************************************************
* *
* Adjust the size of the list to account for the new element. *
* *
*****************************************************************************/
list->size++;
return 0;
}
/*****************************************************************************
* *
* ----------------------------- dlist_remove ----------------------------- *
* *
*****************************************************************************/
int dlist_remove(DList *list, DListElmt *element, void **data) {
/*****************************************************************************
* *
* Do not allow a NULL element or removal from an empty list. *
* *
*****************************************************************************/
if (element == NULL || dlist_size(list) == 0)
return -1;
/*****************************************************************************
* *
* Remove the element from the list. *
* *
*****************************************************************************/
*data = element->data;
if (element == list->head) {
/**************************************************************************
* *
* Handle removal from the head of the list. *
* *
**************************************************************************/
list->head = element->next;
if (list->head == NULL)
list->tail = NULL;
else
element->next->prev = NULL;
}
else {
/**************************************************************************
* *
* Handle removal from other than the head of the list. *
* *
**************************************************************************/
element->prev->next = element->next;
if (element->next == NULL)
list->tail = element->prev;
else
element->next->prev = element->prev;
}
/*****************************************************************************
* *
* Free the storage allocated by the abstract data type. *
* *
*****************************************************************************/
free(element);
/*****************************************************************************
* *
* Adjust the size of the list to account for the removed element. *
* *
*****************************************************************************/
list->size--;
return 0;
}
/*****************************************************************************
* *
* ------------------------------- dlist.h -------------------------------- *
* *
*****************************************************************************/
#ifndef DLIST_H
#define DLIST_H
#include <stdlib.h>
/*****************************************************************************
* *
* Define a structure for doubly-linked list elements. *
* *
*****************************************************************************/
typedef struct DListElmt_ {
void *data;
struct DListElmt_ *prev;
struct DListElmt_ *next;
} DListElmt;
/*****************************************************************************
* *
* Define a structure for doubly-linked lists. *
* *
*****************************************************************************/
typedef struct DList_ {
int size;
int (*match)(const void *key1, const void *key2);
void (*destroy)(void *data);
DListElmt *head;
DListElmt *tail;
} DList;
/*****************************************************************************
* *
* --------------------------- Public Interface --------------------------- *
* *
*****************************************************************************/
void dlist_init(DList *list, void (*destroy)(void *data));
void dlist_destroy(DList *list);
int dlist_ins_next(DList *list, DListElmt *element, const void *data);
int dlist_ins_prev(DList *list, DListElmt *element, const void *data);
int dlist_remove(DList *list, DListElmt *element, void **data);
#define dlist_size(list) ((list)->size)
#define dlist_head(list) ((list)->head)
#define dlist_tail(list) ((list)->tail)
#define dlist_is_head(element) ((element)->prev == NULL ? 1 : 0)
#define dlist_is_tail(element) ((element)->next == NULL ? 1 : 0)
#define dlist_data(element) ((element)->data)
#define dlist_next(element) ((element)->next)
#define dlist_prev(element) ((element)->prev)
#endif
* *
* ------------------------------- dlist.c -------------------------------- *
* *
*****************************************************************************/
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "dlist.h"
void select(void);
void print_next();
void print_prev();
int search();
DList *start;
void main(void)
{
start=(DList *)malloc(sizeof(DList));
dlist_init(start,NULL);
select();
}
void select(void)
{
int input;
void *add;
while(1)
{
printf("n");
printf(" ┏━━━ dlist menu v1.0━━━━━┓n");
printf(" ┃ 1 -> list init ┃n");
printf(" ┃ 2 -> list insert prev ┃n");
printf(" ┃ 3 -> list insert next ┃n");
printf(" ┃ 4 -> list remove prev ┃n");
printf(" ┃ 5 -> list remove next ┃n");
printf(" ┃ 6 -> list search ┃n");
printf(" ┃ 7 -> list print next ┃n");
printf(" ┃ 8 -> list print prev ┃n");
printf(" ┃ 0 -> Exit ┃n");
printf(" ┣━━━━━━━━━━━━━━━━┫n");
printf(" ┃select number ┃n");
printf(" ┗━━━━━━━━━━━━━━━━┛n");
printf(" ==> ");
scanf("%d",&input);
switch(input)
{
case 1:
dlist_destroy(start);
dlist_init(start,NULL);
system("cls");
break;
case 2:
if((add=(void *)malloc(sizeof(int)))==NULL)
return;
system("cls");
printf(" Data prev insert -> ");
scanf("%d",&add);
if(dlist_ins_prev(start,dlist_head(start),add) !=0 )
{
printf(" Not Insert ");
return;
}
printf(" Insert Ok!nn");
break;
case 3:
if((add=(void *)malloc(sizeof(int)))==NULL)
return;
system("cls");
printf(" Data next insert -> ");
scanf("%d",&add);
if(dlist_ins_next(start,dlist_tail(start),add) !=0 )
{
printf(" Not Insert ");
return;
}
printf(" Insert Ok!nn");
break;
case 4:
system("cls");
printf(" Data remove -> ");
scanf("%d",add);
dlist_remove(start,dlist_tail(start),NULL);
break;
case 5:
system("cls");
printf(" Data remove -> ");
scanf("%d",add);
dlist_remove(start,dlist_head(start),NULL);
break;
case 6:
system("cls");
printf(" Input data ==>");
scanf("%d",&add);
search(add);
break;
case 7:
system("cls");
print_next();
break;
case 8:
system("cls");
print_prev();
break;
case 0:
dlist_destroy(start);
return;
default :
system("cls");
printf(" You select wrong number Try to again selectnn");
break;
}
}
}
void print_next()
{
DListElmt *print_next;
if((print_next=(DListElmt *)malloc(sizeof(DListElmt)))==NULL)
return;
print_next = dlist_head(start);
printf("This size is %d n",dlist_size(start));
printf(" List --> Head");
while(print_next != NULL)
{
printf(" --> %d", print_next->data);
print_next = dlist_next(print_next);
}
printf(" --> NULL n");
return;
}
void print_prev()
{
DListElmt *print_prev;
if((print_prev=(DListElmt *)malloc(sizeof(DListElmt)))==NULL)
return;
print_prev = dlist_tail(start);
printf("This size is %d n",dlist_size(start));
printf(" List --> Tail");
while(print_prev != NULL)
{
printf(" --> %d", print_prev->data);
print_prev = dlist_prev(print_prev);
}
printf(" --> NULL n");
return;
}
int search(void *data)
{
DListElmt *find;
if((find=(DListElmt *)malloc(sizeof(DListElmt)))==NULL)
return -1;
for(find=dlist_head(start);find!=NULL;find=dlist_next(find))
{
if(find->data==data)
{
printf(" Data Find Success n");
return 0;
}
}
printf(" Data no Find n");
return 0;
}
/*****************************************************************************
* *
* ------------------------------ dlist_init ------------------------------ *
* *
*****************************************************************************/
void dlist_init(DList *list, void (*destroy)(void *data)) {
/*****************************************************************************
* *
* Initialize the list. *
* *
*****************************************************************************/
list->size = 0;
list->destroy = destroy;
list->head = NULL;
list->tail = NULL;
return;
}
/*****************************************************************************
* *
* ---------------------------- dlist_destroy ----------------------------- *
* *
*****************************************************************************/
void dlist_destroy(DList *list) {
void *data;
/*****************************************************************************
* *
* Remove each element. *
* *
*****************************************************************************/
while (dlist_size(list) > 0) {
if (dlist_remove(list, dlist_tail(list), (void **)&data) == 0 && list->
destroy != NULL) {
/***********************************************************************
* *
* Call a user-defined function to free dynamically allocated data. *
* *
***********************************************************************/
list->destroy(data);
}
}
/*****************************************************************************
* *
* No operations are allowed now, but clear the structure as a precaution. *
* *
*****************************************************************************/
memset(list, 0, sizeof(DList));
return;
}
/*****************************************************************************
* *
* ---------------------------- dlist_ins_next ---------------------------- *
* *
*****************************************************************************/
int dlist_ins_next(DList *list, DListElmt *element, const void *data) {
DListElmt *new_element;
/*****************************************************************************
* *
* Do not allow a NULL element unless the list is empty. *
* *
*****************************************************************************/
if (element == NULL && dlist_size(list) != 0)
return -1;
/*****************************************************************************
* *
* Allocate storage for the element. *
* *
*****************************************************************************/
if ((new_element = (DListElmt *)malloc(sizeof(DListElmt))) == NULL)
return -1;
/*****************************************************************************
* *
* Insert the new element into the list. *
* *
*****************************************************************************/
new_element->data = (void *)data;
if (dlist_size(list) == 0) {
/**************************************************************************
* *
* Handle insertion when the list is empty. *
* *
**************************************************************************/
list->head = new_element;
list->head->prev = NULL;
list->head->next = NULL;
list->tail = new_element;
}
else {
/**************************************************************************
* *
* Handle insertion when the list is not empty. *
* *
**************************************************************************/
new_element->next = element->next;
new_element->prev = element;
if (element->next == NULL)
list->tail = new_element;
else
element->next->prev = new_element;
element->next = new_element;
}
/*****************************************************************************
* *
* Adjust the size of the list to account for the inserted element. *
* *
*****************************************************************************/
list->size++;
return 0;
}
/*****************************************************************************
* *
* ---------------------------- dlist_ins_prev ---------------------------- *
* *
*****************************************************************************/
int dlist_ins_prev(DList *list, DListElmt *element, const void *data) {
DListElmt *new_element;
/*****************************************************************************
* *
* Do not allow a NULL element unless the list is empty. *
* *
*****************************************************************************/
if (element == NULL && dlist_size(list) != 0)
return -1;
/*****************************************************************************
* *
* Allocate storage to be managed by the abstract data type. *
* *
*****************************************************************************/
if ((new_element = (DListElmt *)malloc(sizeof(DListElmt))) == NULL)
return -1;
/*****************************************************************************
* *
* Insert the new element into the list. *
* *
*****************************************************************************/
new_element->data = (void *)data;
if (dlist_size(list) == 0) {
/**************************************************************************
* *
* Handle insertion when the list is empty. *
* *
**************************************************************************/
list->head = new_element;
list->head->prev = NULL;
list->head->next = NULL;
list->tail = new_element;
}
else {
/**************************************************************************
* *
* Handle insertion when the list is not empty. *
* *
**************************************************************************/
new_element->next = element;
new_element->prev = element->prev;
if (element->prev == NULL)
list->head = new_element;
else
element->prev->next = new_element;
element->prev = new_element;
}
/*****************************************************************************
* *
* Adjust the size of the list to account for the new element. *
* *
*****************************************************************************/
list->size++;
return 0;
}
/*****************************************************************************
* *
* ----------------------------- dlist_remove ----------------------------- *
* *
*****************************************************************************/
int dlist_remove(DList *list, DListElmt *element, void **data) {
/*****************************************************************************
* *
* Do not allow a NULL element or removal from an empty list. *
* *
*****************************************************************************/
if (element == NULL || dlist_size(list) == 0)
return -1;
/*****************************************************************************
* *
* Remove the element from the list. *
* *
*****************************************************************************/
*data = element->data;
if (element == list->head) {
/**************************************************************************
* *
* Handle removal from the head of the list. *
* *
**************************************************************************/
list->head = element->next;
if (list->head == NULL)
list->tail = NULL;
else
element->next->prev = NULL;
}
else {
/**************************************************************************
* *
* Handle removal from other than the head of the list. *
* *
**************************************************************************/
element->prev->next = element->next;
if (element->next == NULL)
list->tail = element->prev;
else
element->next->prev = element->prev;
}
/*****************************************************************************
* *
* Free the storage allocated by the abstract data type. *
* *
*****************************************************************************/
free(element);
/*****************************************************************************
* *
* Adjust the size of the list to account for the removed element. *
* *
*****************************************************************************/
list->size--;
return 0;
}
/*****************************************************************************
* *
* ------------------------------- dlist.h -------------------------------- *
* *
*****************************************************************************/
#ifndef DLIST_H
#define DLIST_H
#include <stdlib.h>
/*****************************************************************************
* *
* Define a structure for doubly-linked list elements. *
* *
*****************************************************************************/
typedef struct DListElmt_ {
void *data;
struct DListElmt_ *prev;
struct DListElmt_ *next;
} DListElmt;
/*****************************************************************************
* *
* Define a structure for doubly-linked lists. *
* *
*****************************************************************************/
typedef struct DList_ {
int size;
int (*match)(const void *key1, const void *key2);
void (*destroy)(void *data);
DListElmt *head;
DListElmt *tail;
} DList;
/*****************************************************************************
* *
* --------------------------- Public Interface --------------------------- *
* *
*****************************************************************************/
void dlist_init(DList *list, void (*destroy)(void *data));
void dlist_destroy(DList *list);
int dlist_ins_next(DList *list, DListElmt *element, const void *data);
int dlist_ins_prev(DList *list, DListElmt *element, const void *data);
int dlist_remove(DList *list, DListElmt *element, void **data);
#define dlist_size(list) ((list)->size)
#define dlist_head(list) ((list)->head)
#define dlist_tail(list) ((list)->tail)
#define dlist_is_head(element) ((element)->prev == NULL ? 1 : 0)
#define dlist_is_tail(element) ((element)->next == NULL ? 1 : 0)
#define dlist_data(element) ((element)->data)
#define dlist_next(element) ((element)->next)
#define dlist_prev(element) ((element)->prev)
#endif
출처 - C로 구현한 알고리즘, 한빛미디어