belief21c's e-space

재귀함수와 반복함수

Computer science/Programming 2009. 2. 5. 11:19 |

반복함수

재귀함수

/*
단점
1. stack 개념 : 메모리부하 커진다.
=>stack에 쌓였다가 종료조건을 만나면, 역순으로 pop되며 계산되어지는 방식을 취한다.
2. 무한루프에 빠질 가능성이 크다.
3. 속도가 느리다.
*/
/*
장점
=> 코드의 간결성
*/

<대표적인 예제( 피보나치 수열)>

저작자표시 변경금지

'Computer science > Programming' 카테고리의 다른 글

VC++ 디버깅 단축키 및 VC++ 2008을 이용한 디버깅 (0)	2009.02.18
이중 연결리스트 (0)	2009.02.05
stack, deque - 쉬운 예제 (0)	2009.02.04

이중 연결리스트

Computer science/Programming 2009. 2. 5. 09:26 |

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

typedef struct _dnode
{
 int key;
 struct _dnode *next;
 struct _dnode *prev;
}DNODE;

DNODE *start = NULL;
DNODE *cur = NULL;

void insert(void);
void print(void);
void del_node(void);
void delete_node(void);

void main()
{
 int no;

while(1)
 {
  system("cls");
  puts("*** MENU ***");
  puts("1. INSERT");
  puts("2. PRINT");
  puts("3. DELETE");
  puts("4. END");
  printf("choice : ");
  scanf("%d", &no);
  fflush(stdin);

switch(no)
  {
  case 1 : insert(); break;
  case 2 : print();break;
  case 3 : delete_node(); break;
   //del_node(); break;
  case 4 : exit(1);
  }
  getch();
 }
}

void insert(void)
{
 DNODE* newnode;

if(cur != NULL)
  printf("\n\tcur->key : %d\n", cur->key);

newnode = (DNODE*)malloc(sizeof(DNODE));
 printf("\n\tInput number : ");
 scanf("%d", &newnode->key);
 fflush(stdin);
 newnode->next = newnode->prev = NULL;

if(start == NULL)
 {
  start = newnode;
  cur = start;
  printf("\n\t배열이 비어있을 때 삽입...\n");
  return;
 }

if(cur->key < newnode->key) // NEXT...
 {
  while(cur->next != NULL)
  {
   // cur(5)   [newnode(8)]   cur->next(10)    cur->next->next
   if(cur->next->key > newnode->key)
   {
    newnode->next = cur->next;
    newnode->prev = cur;
    cur->next->prev = newnode;
    cur->next = newnode;
    printf("\n\tNEXT... 중간삽입...\n");
    return;
   }
   cur = cur->next;
  }
  // cur(10)   [newnode(15)]   NULL
  newnode->prev = cur;
  cur->next = newnode;
  printf("\n\tNEXT... 맨 마지막삽입...\n");
 }
 else // PREV...
 {
  while(cur->prev != NULL)
  {
   //  3(cur->prev)   [5(newnode)]   6(cur)    10    12
   if(cur->prev->key < newnode->key)
   {
    newnode->next = cur;
    newnode->prev = cur->prev;
    cur->prev->next = newnode;
    cur->prev = newnode;
    printf("\n\tPREV... 중간삽입...\n");
    return;
   }
   cur = cur->prev;
  }
  // NULL  [newnode(2)]   cur, start(3)
  newnode->next = cur;
  cur->prev = newnode;
  start = newnode;
  printf("\n\tPREV... 맨 앞삽입...\n");
 }
}

void print(void)
{
 DNODE* cur;

if(start == NULL)
 {
  printf("\n\t연결리스트가 구성되어있지 않아 출력할 수 없습니다...\n");
  return;
 }

printf("\n\t< 오름차순 >\n");
 cur = start;
 while(cur->next != NULL)
 {
  printf("%d -> ", cur->key);
  cur = cur->next;
 }
 printf("%d\n", cur->key);

printf("\n\t< 내림차순 >\n");
 while(cur->prev != NULL)
 {
  printf("%d -> ", cur->key);
  cur = cur->prev;
 }
 printf("%d\n", cur->key);
}

void del_node(void)
{
 int no;
 DNODE *del;

if(start == NULL)
 {
  printf("\n\t연결리스트가 구성되어있지 않아 삭제할 수 없습니다...\n");
  return;
 }

printf("\n\tCUR->KEY : %d\n", cur->key);
 printf("\n\t삭제할 정수 : ");
 scanf("%d", &no);
 fflush(stdin);

if(cur->key == no)
 {
  //                  del     
  //    cur->prev     cur     cur->next
  del = cur;
  if(cur->next != NULL && cur->prev != NULL)
  {
   cur->prev->next = cur->next;
   cur->next->prev = cur->prev;
   cur = cur->next;
  }
  else if(cur->next == NULL && cur->prev != NULL)
  {
   cur->prev->next = NULL;
   cur = cur->prev;
  }
  else if(cur->next != NULL && cur->prev == NULL)
  {
   cur->next->prev = NULL;
   start = start->next;
   cur = cur->next;
  }
  else //cur->next == NULL && cur->prev == NULL
   start = cur = NULL;
  printf("\n\tCUR... delete... [%d]\n", del->key);
  free(del);
 }
 else if(cur->key < no) // NEXT...
 {
  while(cur->next != NULL)
  {
   //                  del              del->next
   //   5(cur)     8(cur->next)     10(cur->next->next)    12
   if(cur->next->key == no)
   {
    del = cur->next;
    cur->next = del->next;
    if(del->next != NULL)
     del->next->prev = cur;
    printf("\n\tNEXT... delete... [%d]\n", del->key);
    free(del);
    return;
   }
   cur = cur->next;
  }
  printf("\n\t입력하신 정수 [%d]는 존재하지 않습니다...\n", no);
 }
 else // PREV...
 {
  while(cur->prev != NULL)
  {
   //      del->prev             del
   //   3(cur->prev->prev)    5(cur->prev)   8(cur)  10
   if(cur->prev->key == no)
   {
    del = cur->prev;
    if(del->prev != NULL)
     del->prev->next = cur;
    else
     start = start->next;
    cur->prev = del->prev;
    printf("\n\tPREV... delete... [%d]\n", del->key);
    free(del);
    return;
   }
   cur = cur->prev;
  }
  printf("\n\t입력하신 정수 [%d]는 존재하지 않습니다...\n", no);
 }
}

void delete_node(void)
{
 int no;
 DNODE *del;

if(start == NULL)
 {
  printf("\n\t연결리스트가 구성되어있지 않아 삭제할 수 없습니다...\n");
  return;
 }

printf("\n\tCUR->KEY : %d\n", cur->key);
 printf("\n\t삭제할 정수 : ");
 scanf("%d", &no);
 fflush(stdin);

del = cur;
 if(cur->key < no)
 {
  while(cur != NULL && cur->key != no)
   cur = cur->next;
 }
 else if(cur->key > no)
 {
  while(cur != NULL && cur->key != no)
   cur = cur->prev;
 }
 if(cur == NULL)
 {
  printf("\n\t입력하신 정수 [%d]는 존재하지 않습니다...\n", no);
  cur = del;
  return;
 }
 
 //   del->prev    del     del->next
 //   cur->prev    cur     cur->next
 del = cur;
 if(del->prev != NULL)
 {
  del->prev->next = del->next;
  cur = cur->prev;
 }
 else
 {
  start = start->next;
  cur = cur->next;
 }
 if(del->next != NULL)
  del->next->prev = del->prev;
 printf("\n\tdelete... [%d]\n", del->key);
 free(del);
}

저작자표시 비영리 변경금지

'Computer science > Programming' 카테고리의 다른 글

재귀함수와 반복함수 (0)	2009.02.05
stack, deque - 쉬운 예제 (0)	2009.02.04
자료구조 - 연결리스트(쉬운 예제) (0)	2009.01.30

PREV 1 2 3 4 5 6 7 ··· 9 NEXT

belief21c's e-space

Category

Recent Posts

Recent Comments

Links

재귀함수와 반복함수

'Computer science > Programming' 카테고리의 다른 글

이중 연결리스트

'Computer science > Programming' 카테고리의 다른 글

티스토리툴바