ZOE

DoubleLinkedList_Que.c

 이중 연결리스트를 사용하여 que를 구현하였습니다.
삽입, 삭제, 출력이 가능합니다.

 /*==================================================================================*/

/*     이중 연결 리스트 QUE
                     */
/*    - head에 Dummy node 사용.
      즉) 종료 조건이 (head==head->l_link) && (head==head->r_link)  */
/*    - 삽입, 삭제, 출력 가능.
    - 일단 숫자를 데이터로 가짐.                 */

/*==================================================================================*/

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

#define YES x    // 입력이 끝났다는 표시.
#define NO 0   // 입력이 끝이 아님.
#define LIST struct list

typedef struct _list{
 int key;
 struct _list *l_link;
 struct _list *r_link;
} list;

list *head;  //dummy node.

/************************함수들****************************************/

list *node(list *root,int k);     //node함수.(node 삽입)
int inp(int *iag);        //inp함수.(data를 입력받는 함수)
int del_node(int k);       //삭제 함수.(노드를 삭제 함수)
list *find_node(int k);       //탐색 함수.(key값 탐색 함수.)
/*********************************************************************/
/*    main함수.
/*********************************************************************/
int main(void){ 
 list *root;
 int k,c=0;
 int ch=0; //ch가 1이면 삽입, 2이면 삭제, 3이면 탐색.
 head = (list*)malloc(sizeof(list));
 head->key = '\0';
 head->l_link = head;
 head->r_link = head;

 while(ch!=4)
 {
  k=0;
  printf("삽입(1)/ 삭제(2)/ 탐색(3)/ 종료(4) : ");
  scanf("%d",&ch);
  if(ch==1){
   printf("삽입할 데이타(정수)를 입력하십시오.: ");
   while((c=getchar())!='\n')
   {
    k=10*k+(c-'0');
    
   }
   root=node(root,k);
  }
  
  else if(ch==2){
   printf("삭제할 값을 입력하십시오.: ");
   while((c=getchar())!='\n')
   {
    k=k+(c-'0');
    k*=10;
   }
   del_node(k);
  }
  
  else if(ch==3){
   printf("검색할 값을 입력하십시오.: ");
   while((c=getchar())!='\n')
   {
    k=k+(c-'0');
    k*=10;
   }
   printf("검색하신 값: %d",(find_node(k))->key);
  }
 }
 return 0;
}

/*********************************************************************/
/*    node함수.(node 삽입)
    -head의 l_list 즉, QUE의 끝에 생성.
/*********************************************************************/
list *node(list *root,int k){
 list *temp;
 if((temp = (list*)malloc(sizeof(list)))==NULL)
 {
  printf("error\n");
  exit(1);
 }
 temp->key=k;
 temp->l_link=root;
 temp->r_link=head;
 head->l_link=temp;
 root->r_link=temp;
 root=temp;
 return(root);
}
 

/*********************************************************************/
/*    삭제 함수.(노드를 삭제 함수)
    -head의 l_list 즉, QUE의 맨앞노드 삭제.
    -정상 삭제 return 1;
       else return 0;  
/*********************************************************************/
int del_node(int k){
 list *temp;
 temp=head->r_link;
 if(temp != head){
  head->r_link=temp->r_link;
  temp->r_link->l_link=head;
  free(temp);
  return 1;
 }
 return 0;
}

/*********************************************************************/
/*    탐색 함수.(key값 탐색 함수.)
/*********************************************************************/
list *find_node(int k){
 list *temp;
 temp=head->r_link;
 while(temp->key != k && temp != head)
  temp = temp->r_link;
 return temp;
}

이 글은 스프링노트에서 작성되었습니다.