'C++프로그래밍/자료구조'에 해당되는 글 29건

typedef struct node* tree_pointer;
typedef struct node{
 int data;
 tree_pointer left_child,right_child;
};

//중위순회
void inorder(tree_pointer ptr)
{
 if(ptr){
  inorder(ptr->left_child);
  printf("%d\n",ptr->data);
  inorder(ptr->right_child);
 }
}

//전위순회
void preorder(tree_pointer ptr)
{
 if(ptr){
  printf("%d\n",ptr->data);
  preorder(ptr->left_child);
  preorder(ptr->right_child);
 }
}

//후위순회
void postorder(tree_pointer ptr)
{
 if(ptr){
  postorder(ptr->left_child);
  postorder(ptr->right_child);
  printf("%d\n",ptr->data);
 }
}

//반복적인 중위순회(stack)
void iter_inorder(tree_pointer node)
{
 int top = -1;
 tree_pointer stack[MAX_STACK_SIZE];
 for( ; ; ){
  for( ; node; node->left_child)
   add(&top,node);
  node = delete(&top);
  if(!node) break;
  printf("%d\n", ptr->data);
  node = node->right_child;
 }
}

//레벨순서 트리 순회
void level_order(tree_pointer ptr)
{
 int front,rear = 0;
 tree_pointer queue[MAX_QUEUE_SIZE];
 if (!ptr) return;
 addq(front, &rear, ptr);
 for( ; ; ){
  ptr = deleteq(&front, rear);
  if(ptr){
   printf("%d\n",ptr->data);
   if(ptr->left_child)
    addq(front,&rear,ptr->left_child);
   if(ptr->right_child)
    addq(front,&rear,ptr->right_child);
  }
  else break;
 }
}

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

typedef struct Treenode{
 int data;
 struct Treenode *left,*right;
}Treenode;

Treenode n1={4,NULL,NULL};
Treenode n2={2,&n1,NULL};
Treenode n3={5,NULL,NULL};
Treenode n4={6,NULL,NULL};
Treenode n5={3,&n3,&n4};
Treenode n6={1,&n2,&n5};

Treenode* root = &n6;

inorder(Treenode *root){
 if(root){
  inorder(root->left);
  printf("%d->",root->data);
  inorder(root->right);
 }
}

preorder(Treenode* root){
 if(root){
  printf("%d->",root->data);
  preorder(root->left);
  preorder(root->right);
 }
}

postorder(Treenode* root){
 if(root){
  postorder(root->left);
  postorder(root->right);
  printf("%d->",root->data);
 }
}

void main()
{
 printf("중위순회 : ");
 inorder(root);
 printf("\n");
 printf("전위순회 : ");
 preorder(root);
 printf("\n");
 printf("후위순회 : ");
 postorder(root);
 printf("\n");
}

/*↓↓↓↓↓↓↓↓↓선형  큐↓↓↓↓↓↓↓↓↓*/
#define MAX_QUEUE_SIZE 100
typedef struct{
 int key
}element;

element queue[MAX_QUEUE_SIZE];
int rear = -1;
int front = -1;

void addq(int *rear,element item)
{
 if(*rear == MAX_QUEUE_SIZE-1){
  queue_full();
  return;
 }
 queue[++*rear]=item;
}

void deleteq(int *front, int rear)
{
 if(*front == rear)
  return queue_empty;
 return queue[++*front];
}
/*↓↓↓↓↓↓↓↓↓원형  큐↓↓↓↓↓↓↓↓↓*/
int rear = 0;
int front = 0;

void addq(int front, int *rear,element item)
{
 *rear=(*rear+1) % MAX_QUEUE_SIZE;
 if(front == *rear){
  queue_full(rear);
  return ;
 }
 queue[*rear]=item;
}

void deleteq(int *front,int rear)
{
 element item;
 if(*front == rear)
  return queue_empty();
 *front=(*front+1) % MAX_QUEUE_SIZE;
 return queue[*front];
}
/*↓↓↓↓↓↓↓↓↓연결된 큐↓↓↓↓↓↓↓↓↓*/
#define MAX_QUEUES 10
typedef struct queue* queue_pointer;
typedef struct queue{
 element item;
 queue_pointer link;
};

queue_pointer front[MAX_QUEUE],rear[MAX_QUEUE];

void addq(queue_pointer* front,queue_pointer* rear,element item)
{
 queue_pointer temp = (queue_pointer)malloc(sizeof(queue));
 if(IS_FULL(temp)){
  fprintf(stderr,"the memory is full\n");
  exit(1);
 }
 temp->item=item;
 temp->link=NULL;
 if(*front){
  (*rear)->link=temp;
 }
 else{
  *front = temp;
}
  *rear = temp;
}

element deleteq(queue_pointer *front)
{
 queue_pointer temp = *front;
 element item;
 if(IS_EMPTY(*front)){
  fprintf(stderr,"the queue is empty\n");
  exit(1);
 }
 item=temp->item;
 *front=temp->link;
 free(temp);
 return item;
}

precedence stack[MAX_STACK_SIZE];
static int isp[]={0,19,12,12,13,13,13,0};
static int icp[]={20,19,12,12,13,13,13,0};

void postfix()
{
 char symbol;
 precedence token;
 int n=0;
 int top=0;

 stack[0] = eos;
 for(token = get_token(&symbol,&n); token!=eos ; token=get_token(&symbol,&n))
 {
  if(token == operand)
   printf("%c",symbol);
  else if(token == rparen)
  {
   //왼쪽 괄호가 나올때까지 토큰들을 제거해서 출력시킴
   while(stack[top]!=lparen)
    printf_token(delete(&top));
   delete(&top);//좌괄호를버린다
  else
   //symbol의 isp가 token의 icp보다 크거나 같으면 symbol을 제거하고 출력시킴
   while(isp[stack[top]]>=icp[token])
    printf_token(delete(&top));
  add(&top,token);
  }

 }
 while((token = delete(&top))!=eos)
  printf_token(token);  // printf_token함수는 get_token함수의 수행하는 과정을 역으로만든다.
 printf("\n");
}

#include <stdio.h>
#define MAX_STACK_SIZE 100
#define MAX_EXPR_SIZE 100

typedef struct{
 int key;
}element;
element stack[MAX_STACK_SIZE];
int top = -1;

//스택으로의 삽입함수
void add(int* top, element item)
{
 //전역 stack에 item을 삽입
 if(*top>=MAX_STACK_SIZE-1){
  stack_full();
  return ;
 }
 stack[++*top] = item;
}
//스택으로부터 삭제함수
element delete(int *top)
{
 if(*top == -1)
  return stack_empty();
 return stack[(*top)--];
}

/*-------------------------------------------------------------------------------*/
typedef enum {
 lparen, rparen, plus, minus, times, divide, mod, eos, operand
}percedence;
int stack[MAX_STACK_SIZE];
char expr[MAX_EXPR_SIZE];

//후위표기식 함수
int eval()
{/*전역 변수로 되어있는 후위표기식 expr을 연산한다.\0은 수식의 끝을 나타낸다.stack과top은 전역변수이다
 함수get_token은 토큰의 타입과 문자 심벌을 반환한다.피연산자는 한 문자로 된 숫자임을 가정한다.*/
 precedence token;
 char symbol;
 int op1,op2;
 int n=0; //수식 문자열을 위한 카운터
 int top = -1;
 token = get_token(&symbol,&n);
 while(token !=eos){
  if(token == operand)
   add(&top,symbol- '0'); //스택삽입
  else{
   op2=delete(&top); //스택삭제,삭제하면서 그자리에 있던값을 반환.
   op1=delete(&top); //스택삭제
   switch(token){
    case plus: add(&top,op1+op2); break;
    case minus: add(&top,op1-op2); break;
    case times: add(&top,op1*op2); break;
    case divide: add(&top,op1/op2); break;
    case mod: add(&top,op1%op2); break;
   }
  }
  token = get_token(&symbol,&n)
 }
 return delete(&top);//결과를 반환
}

precedence get_token(char* symbol, int* n)
{/*다음 토큰을 취한다. symbol은 문자표현이며 token은 그것의 열거된 값으로 표현되고 명칭으로 반환된다*/
 *symbol = expr[(*n)++];
 switch(*symbol){
  case '(' :return lparen;
  case ')' :return rparen;
  case '+' :return plus;
  case '-' :return miuns;
  case '/' :return divide;
  case '*' :return times;
  case '%' :return mod;
  case '\0':return eos;
  default  :return operand;//오류검사는 하지 않고 기본값은 피연산자
 }
}

invalid-file

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

typedef int element;
typedef struct DlistNode{
 element data;
 struct DlistNode* llink;
 struct DlistNode* rlink;
}DlistNode;

void init(DlistNode* phead)
{
 phead->llink=phead;
 phead->rlink=phead;
}

void display(DlistNode* phead)
{
 DlistNode* p;
 for(p=phead->rlink ; p!=phead ; p=p->rlink)
 {
  printf("<---| %x | %d | %x |--->\n",p->llink , p->data, p->rlink);
 }
 printf("\n");
}

main()
{
 DlistNode head_node;
 DlistNode* p[10];
 int i;

 init(&head_node);
 for(i=0 ; i<5 ; i++)
 {
  p[i] = (DlistNode*)malloc(sizeof(DlistNode));
  p[i]->data = i;

  dinsert_node(&head_node,p[i]);
 }
 dremove_node(&head_node,p[4]);
 display(&head_node);
}