[SW정글] 4/30 TIL - pointer -> Linked List, Queue(feat, C)

주소값

데이터의 주소값이란 해당 데이터가 저장된 메모리의 시작 주소를 의미한다.

예를 들어 int data는 4바이트 크기를 가지지만 int형 데이터의 주소값은 시작 주소 1바이트만 가리킨다.

 

포인터

메모리의 주소값을 저장하는 변수이다.

 

 

연산자

 

주소 연산자 &

변수의 이름 앞에 사용하며, 해당 변수의 주소값을 반환한다. ampersand라고 읽는다.

 

참조 연산자 *

포인터의 이름이나 주소 앞에 사용하며, 포인터에 가리키는 주소에 저장된 값을 반환한다.

 

---

stack 구현

전역변수 Ver

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

#define MAX_STACK_SIZE 100
#define MAX_STRING 100

// 학생 구조체 선언
typedef struct {
  int student_number;
  char student_name[MAX_STRING];
  char student_address[MAX_STRING];
}student;

student stack[MAX_STACK_SIZE]; // 스택 배열을 전역 변수로 선언
int top= -1; // 스택에 아무 요소가 없을 때는 0이 아닌 -1

// is_empty()
bool is_empty(){
  return top == -1;
}

// is_full(s) 
bool is_full(){
  return top == MAX_STACK_SIZE-1;
}

// push(s, item)
void push(student object){
  if (is_full()){
    printf("STACK IS FULL\n");
    return;
  }
  stack[++top] = object;
}

// pop(s)
student pop(){
  if(is_empty()){
    printf("STACK IS EMPTY\n");
    exit(1);
    // return;
  }
  return stack[top--];
}

// peek(s) : 제일 위 원소 출력
student peek(){
  if(is_empty()){
    printf("STACK IS EMPTY\n");
    exit(1);
    // return;
  }
  return stack[top];
}

int main(void){
  student keys = {
    20220430, "YH", "DAEJEON"
  };
  student object;
  push(keys);
  object = pop();

  printf("number : %d\n", object.student_number);
  printf("name : %s\n", object.student_name);
  printf("address : %s\n", object.student_address);
}

포인터 ver

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

#define MAX_STACK_SIZE 100
#define MAX_STRING 100

typedef struct {
  int student_number;
  char student_name[MAX_STRING];
  char student_address[MAX_STRING];
}student;

typedef struct {
  student data[MAX_STACK_SIZE];
  int top;
}Stack;

void init_stack(Stack *s){
  // (*s).top == s->top
  s->top = -1;
  return;
}

bool is_empty(Stack *s){
  // (*s).top == -1
  return s->top == -1;
}

bool is_full(Stack *s) {
  return s->top >= MAX_STACK_SIZE-1;
}

void push(Stack *s, student object){
  if(is_full(s)){
    printf("STACK IS FULL\n");
    return;
  }
  s->data[++s->top] = object;
}

student pop(Stack * s){
  if(is_empty(s)){
    printf("STACK is EMPTY\n");
    // return;
    exit(1);
  }
  return s->data[s->top--];
}

student peek(Stack *s){
  if(is_empty(s)){
    printf("STACK IS EMPTY\n");
    exit(1);
  }else return s->data[s->top];
}

int main(void){
  Stack s;
  init_stack(&s);
  student keys = {
    20220430, "YH", "DAEJEON"
  };
  student object;

  push(&s, keys);
  object=pop(&s);

  printf("student number : %d \n", object.student_number);
  printf("student name : %s \n", object.student_name);
  printf("student address : %s \n", object.student_address);
  return 0;
}

 

---

Queue 구현

 

전역 ver

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

#define MAX 100

int queue[MAX];
int front = 0, rear= 0;
int s = 0;

bool is_full(){
  if((rear+1) % MAX == front) return true;
  return false;
}

bool is_empty(){
  if(front == rear )return true;
  return false;
}

int Dequeue(){
  if (is_empty()) return -999;
  front = (front + 1) % MAX;
  s--;
  return queue[front];
}
bool Enqueue(int a){
  if (is_full()) return false;
  rear = (rear + 1) % MAX;
  queue[rear] = a;
  s++;
  return true;
}

int Size(){
  return s;
}

int main() {
  Enqueue(1);
  Enqueue(2);
  Enqueue(3);
  Enqueue(4);
  Enqueue(5);
  printf("%d\n", Dequeue());
  printf("%d\n", Dequeue());
  printf("%d\n", Dequeue());
  printf("%d\n", Dequeue());

  return 0;
}

 

포인터 ver

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

#define MAX 100

typedef struct {
  int friend_number;
  char friend_name[MAX];
}friend;

typedef struct{
  friend data[MAX];
  int rear;
  int front;
  int size;
}Queue;

void init_queue(Queue *q){
  q->size = 0;
  q->rear = 0;
  q->front = 0;
  return;
}

// is full
bool is_full(Queue *q){
  return (q->rear + 1) % MAX == q->front;
}
// is empty
bool is_empty(Queue *q){
  return q->rear == q->front;
}

// deque
friend deque(Queue *q){
  if(is_empty(q)){
    printf("QUEUE IS EMPTY\n");
    exit(1);
  }

  q->size -= 1;
  // q->rear -= 1;
  return q->data[(q->rear--) % MAX];
}

// enque
bool enque(Queue *q, friend object){
  if(is_full(q)){
    printf("QUEUE IS FULL\n");
    return false;
  }
  // rear = (rear+1) % MAX
  q->rear = (q->rear+1) % MAX;

  q->data[q->rear] = object;
  // size + 1
  q->size += 1;
  return true;
  
}
// size
int size(Queue *q) {
  return q->size;
}

int main(){
  Queue q;
  init_queue(&q);
  friend keys = {
    20220328, "JUNGLE"
  };
  friend object;

  enque(&q, keys);
  object = deque(&q);
  printf("friend number : %d \n ", object.friend_number);
  printf("friend name : %s \n ", object.friend_name);
  return 0;
}

 

여기까지하고 *과 &이 하는 일을 정확하게 알 수 있었다.

그러나, 아직은 매개변수를 호출 설정할때 *, &을 써야하는지 헷갈린다.

 

---

 

 

Linked List 구현

 

#include <stdio.h>
#include <stdlib.h> // malloc, free함수가 선언된 헤더 파일

typedef int element;

typedef struct ListNode {
  element data;
  struct ListNode * link;
}ListNode;

// 앞부분에 노드 삽입
ListNode * insert_first(ListNode * head, element value){
  ListNode * p = (ListNode*)malloc(sizeof(ListNode));
  p->data = value;
  p->link = head;
  head= p;
  return head;
}

// 노드 pre뒤에 새로운 노드 삽입
ListNode * insert(ListNode*head, ListNode* pre, element value) {
  ListNode* p = (ListNode*)malloc(sizeof(ListNode));
  p->data = value;
  p->link = pre->link;
  pre->link = p;
  return head;
}

// 앞부분의 노드 제거
ListNode* delete_first(ListNode*head){
  ListNode* removed;
  if(head == NULL) return NULL;
  removed = head;
  head = removed->link;
  free(removed);
  return head;
}

//pre가 가리키는 노드의 다음 노드 삭제
ListNode* delete(ListNode * head, ListNode*pre){
  ListNode * removed;
  removed = pre->link;
  pre->link = removed->link;
  free(removed);
  return head;
}

// concat two lists
ListNode* concat_list(ListNode*head1, ListNode*head2)
{
  if(head1 == NULL) return head2;
  else if (head2==NULL) return head1;
  else {
    ListNode*p;
    p= head1;
    while(p->link != NULL){
      p = p->link;
    }
    p->link = head2;
    return head1;
  }
}

//reverse LIST
ListNode* reverse(ListNode * head){
  ListNode *p, *q, *r;

  p= head; // p는 역순으로 만들 리스트
  q= NULL; // q는 역순으로 만들 노드
  while(p!=NULL){
    r = q;  //r은 역순으로 된 리스트
    q = p;  // r은 q,q는 p를 차례로 따라간다
    p = p->link; 
    q->link = r;  // q의 링크 방향을 바꾼다
  }
  return q;
}

// Print list length
int get_length(ListNode * head){
  int count = 0;
  for(ListNode*p=head; p!=NULL; p= p->link)
  {
    count++;
  }
  return count;
}

// get list sum
int get_sum(ListNode*head){
  int sum = 0;
  for(ListNode *p =head; p!= NULL; p=p->link){
    sum+= p->data;
  }return sum;
}

// get list max number
int get_max(ListNode*head){
  int maxNum = 0;
  for(ListNode*p = head; p!=NULL; p=p->link){
    if (maxNum < p->data){
      maxNum = p->data;
    }
  }return maxNum;
}

//get value's count in list
int count(ListNode* head, int value){
  int count = 0;
  for(ListNode*p=head;p!=NULL; p=p->link){
    if (value == p->data){
      count++;
    }
  }
  return count;
}

// delete value in list
ListNode* delete_node(ListNode*head, int value){
  ListNode * pre = NULL;

  for(ListNode* p = head; p!=NULL; pre=p, p=p->link){
    if(p->data == value){
      if (p== head){
        ListNode* removed = head;
        head = head->link;
        free(removed);
      }else{
        pre->link = p->link;
        free(p);
        p = pre;
      }
    }
  }
  return head;
}

// print LIST
void print_list(ListNode * head)
{
  for (ListNode*p=head; p != NULL; p= p->link){
    printf("%d -> ",p->data);
  }
  printf("NULL \n");
}

// insert Last Node
ListNode* insert_last(ListNode*head, var value){
  ListNode * p = (ListNode*)malloc(sizeof(ListNode));
  p->data = value;
  if(head == NULL){
    p->link = head;
    head = p;
  }else{
    ListNode * q = head;
    while(q->link != NULL){q=q->link}
    p->link = q->link;
    q->link = p;
  }
  return head;
}

// merge list
ListNode * merge(ListNode* list1, ListNode* list2){
  ListNode* result = NULL;
  ListNode* p1 = list1, *p2 = list2;
  if(p1 == NULL) return list2;
  if(p2==NULL) return list1;
  while(p1!= NULL && p2!=NULL){
    if(p1->data < p2->data){
      result = insert_last(result, p1->data);
      p1=p1->link;
    }else {
      result = insert_last(result, p2->data);
      p2=p2->link;
    }
  }
  while(p1 != NULL){
    result = insert_last(result, p1->data);
    p1 = p1->link
  }
  while(p2!=NULL){
    result = insert_last(result, p2->data);
    p2=p2->link;
  }
  return result;
}

// create list odd in list
ListNode * odd_extract(ListNode * list){
  ListNode * oddList = NULL;
  ListNode * p;
  for(p=list; p!=NULL; p=p->link){
    if (p->data % 2 != 0){
      oddList = insert_first(oddList, p->data);
      p= p->link;
    }
  }
  return oddList;
}

int main(void){
  ListNode *head = NULL;
  int i;
  for(i=0; i<5; i++){
    head = insert_first(head,i);
    print_list(head);
  }
  printf("#####################\n");
  for(i=0; i<5; i++){
    head = delete_first(head);
    print_list(head);
  }
  return 0;
}

 

linked list는 어려워서 다른 블로그를 참조했다.

 

코드 스타일이 달라서 그런가 더 헷갈리기 시작했다.

 

또한 malloc과 free에 대해서도 빨리 공부할 필요성을 느끼게 되었다...

 

내일은 malloc과 free에 대해서 배우고 tree를 구현해보고 하루 빨리 rb tree를 구현을 시작해보도록 하쟈 ...!!

 

모두들 열코다 🔥!🔥!🔥!🔥!