[알고리즘 스터디] 자료구조_1

1. 배열

• 정적배열

  우리가 생각하는 일반적인 배열. 크기가 고정되어 있다.

• 동적배열 (vector)

  중간에 값을 추가하거나 삭제할 수 있다.
  https://blockdmask.tistory.com/70
  이 링크에서 배열의 사용법을 자세하게 배울 수 있다.

2. 문자열

3. 배열

   • 여러 글자로 이루어진 문자 그룹을 하나의 자료로 취급하여 메모리에 연속적으로 저장하는 자료 형식.
     https://blockdmask.tistory.com/338

4. 연결리스트

   • 연결 자료구조는 순차 자료구조 (ex배열)과 달리 원소의 논리적인 순서와 물리적인 순서가 일치하지 않아도 된다.

   • 연속한 물리주소에 의해 원소 순서를 표현하는 것이 아니라, 각 원소에 저장되어 있는 다음 원소의 주소(링크)에 의해 순서가 연결되는 구현 방식이기 때문이다.

   • 노드 단위로 메모리가 할당되며, 삽입 및 삭제 연산 후 논리적인 순서가 변경되어도 각 노드의 링크정보만 변경되고 물리적인 위치는 변경되지 않는다.

   • 포인터(링크)를 담을 공간이 추가적으로 필요한 대신에, 삽입 삭제 연산시에 물리적 순서를 맞추려는 오버헤드가 발생하지 않는다.

   • 연결 자료구조의 노드
     <데이터, 다음 원소의 주소>

https://medium.com/wasd/c-c-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%97%B0%EA%B2%B0-%EB%A6%AC%EC%8A%A4%ED%8A%B8-1-41a312399a8f

단순연결리스트

#include <stdio.h>
#include <stdlib.h>
typedef int element;
typedef struct ListNode{
   element data;
   struct ListNode *link;
}ListNode;
void remove_node(ListNode **phead, ListNode *p, ListNode *removed)
{
   if(p==NULL)
      *phead = (*phead)->link;
   else
      p->link = removed->link;
   free(removed);
}
void insert_node(ListNode **phead, ListNode *p, ListNode *new_node)//phead 헤드포인터를 가르키는 포인터, p 삽입할 곳의 선행 노드, new_node 삽입될 노드 
{
   if((*phead)==NULL)
   {
      new_node->link = NULL;
      *phead = new_node; 
   }
   else if(p==NULL)
   {
      new_node->link = *phead;
      *phead = new_node;
   }
   else
   {
      new_node->link = p->link;
      p->link = new_node;
   }
}
void display(ListNode *head)
{
   ListNode *p = head;
   while (p!=NULL)
   {
      printf("%d->",p->data);
      p = p->link;
   }
   printf("\n");
}
ListNode* create_node(element data, ListNode *link)
{
   ListNode *new_node;
   new_node = (ListNode*)malloc(sizeof(ListNode));
   new_node->data = data;
   new_node->link = link;
   return new_node;
}

int main(void)
{
   ListNode *head = NULL;
   ListNode *p;

   insert_node(&head, NULL, create_node(10,NULL));
   insert_node(&head, NULL, create_node(20,NULL));
   insert_node(&head, head, create_node(30,NULL));
   display(head);

   //remove_node(&head,NULL,head);
   display(head);
   return 0;
}

원형연결리스트

#include <stdio.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");
}
void dinsert_node(DlistNode *before,DlistNode *new_node) {
    new_node->llink = before;
    new_node->rlink = before->rlink;
    before->rlink->llink = new_node;
    before->rlink=new_node;
}
void dremove_node(DlistNode *phead_node, DlistNode *removed) {
    if (removed == phead_node) return;
    removed->llink->rlink=removed->rlink;
    removed->rlink->llink=removed->llink;
    free(removed);
}
int main(void) {
    DlistNode head_node;
    DlistNode *p[10];
    init(&head_node);
    int i; 
    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[3]);
    display(&head_node);

    return 0;
}

5. 스택
   • 접시를 쌓아 올리듯 데이터를 차곡차곡 쌓아올린 현태로 자료를 구성하는 방식이다.
   • 같은 구조와 같은 크기의 데이터를 정해진 방향으로만 쌓을 수 있고, top으로 정한 한 곳으로만 접근하도록 제한되어 있다.
   • top은 삽입과 삭제가 일어나는 위치로, 현재 스택의 가장 위에 있는 데이터의 위치가 된다.
   • 삽입
     top 위치에 있는 데이터 위에 새로운 데이터가 쌓이게 된다. 따라서 top은 새로 삽입된 데이터의 위치로 갱신된다.
   • 삭제
     top 위치에 있는 데이터가 삭제된다. 따라서 top은 top 바로 아래에 위치한 데이터의 위치로 갱신된다
     가장 마지막에 삽입된 데이터가 가장 먼저 삭제된다 (LIFO)

링크를 이용해 구현한 스택

#include <stdio.h> 

typedef int element;

typedef struct StackNode {
    element item;
    struct StackNode *link;
}StackNode;

typedef struct{    //메인함수에 탑 선언해도되지만 스택여러개인경우 때문에씀   
    StackNode *top;
}StackType;

void init(StackType *s) {
    s->top=NULL;
}
int is_empty(StackType *s) {
    return (s->top==NULL);
}
void push(StackType *s, element item) { //삽입  

    StackNode *temp = (StackNode *)malloc(sizeof(StackNode));
    temp->item=item;
    temp->link=s->top;
    s->top=temp;
} 
int pop(StackType *s) { //삭제  
    if(is_empty(s)) {
        printf("스택이 비어있음\n");
        exit(1);
    }
    else {
        StackNode *temp=s->top;
        int item=temp->item;
        s->top =s->top->link;
        free(temp);
        return item;
    }
}

int main(void) {
    StackType s;
    init(&s);
    push(&s,10);
    push(&s,20);
    push(&s,30);
    printf("%d\n",pop(&s));
    printf("%d\n",pop(&s));
    printf("%d\n",pop(&s));
    printf("is_empty:%d\n",is_empty(&s));

    return 0;
}

6. 큐
   삽입 삭제의 위치와 방법이 제한된 유한 순서 리스트라는 점은 스택과의 공통점이지만, 리스트의 한쪽 끝에서는 삽입만, 반대쪽 끝에서는 삭제 작업만 이루어진다는 것이 스택과 다르다.
   은행에서 번호표를 뽑아 줄을 서는 방식과 비슷하다. 먼저 삽입된 데이터가 먼저 삭제되는 (FIFO) 구조로 운영된다.
   한쪽 끝을 front(머리), 다른쪽 끝을 rear or tail (꼬리)로 정하여 머리에서는 삭제만, 꼬리에서는 삽입 연산만 수행할 수 있다.

#include <stdio.h>
#include <stdlib.h>
typedef int element;
typedef struct QueueNode {
    element item;
    struct QueueNode *link;
}QueueNode;
typedef struct {
    QueueNode *front,*back;
}QueueType;

void init(QueueType *q) {
    q->front=q->back=NULL;
}
int is_empty(QueueType *q) {
    return(q->front==NULL);
}
void enqueue(QueueType *q,element item) {
    QueueNode *temp=(QueueNode*)malloc(sizeof(QueueNode));
    if(temp==NULL) printf("메모리를 할당할 수 없습니다.");
    else {
        temp->item=item;
        temp->link=NULL;
        if(is_empty(q)){ //큐가 공백이면  
            q->front=temp;
            q->back=temp;
        }
        else {
            q->back->link=temp;
            q->back=temp;
        }
    }
}
element dequeue(QueueType *q) {
    QueueNode *temp=q->front;
    element item;
    if(is_empty(q)) printf("큐가 비어 있습니다.");
    else {
        item=temp->item;
        q->front=q->front->link;
        if(q->front==NULL)
            q->back=NULL; //하나남았을 때 삭제하면  
        free(temp);
        return item;
    }
    return -1;
} 

int main(void) {
    QueueType *q;
    init(&q);

    enqueue(&q,100);
    enqueue(&q,200);
    enqueue(&q,300);
    printf("dequeue()=%d\n", dequeue(&q));
    printf("dequeue()=%d\n", dequeue(&q));
    printf("dequeue()=%d\n", dequeue(&q));
    return 0;
    }

• 환형 큐
  1차원 배열을 이용해서 큐를 구현했을 때는 큐가 포화상태가 아닐 때만 삽입 연산을 수행하도록 되어있는데, 실제로 메모리가 다 차지 않고 중간이 비어있음에도 불구하고 포화상태로 인식해서 더 이상 삽입 연산을 수행하지 않는다.
  이것을 해결하기 위해 원형 큐를 사용한다. 1차원 배열을 사용하지만, 논리적으로 배열의 처음과 끝이 연결되어 있는 원형 구조로 가정하고 사용한다.

  • 삽입 위치
    rear = (rear+1)mod n (원형 큐)
    rear = rear+1 (순차 큐)

  • 삭제 위치
    front = (front+1) mod n (원형 큐)
    front = front+1 (순차 큐)

    #include <stdio.h>
    #include <stdlib.h>
    #define SIZE 4
    
    typedef char element;
    typedef struct {
        element queue[SIZE];
        int front, rear;
    } QueueType;
    
    QueueType *init() {
        QueueType *q;
        q = (QueueType *)malloc(sizeof(QueueType));
        q->front=0;
        q->rear=0;
        return q;
    }
    int isEmpty(QueueType* q){
        if (q->front == q->rear){
            printf("q is empty");
            return 1;
        }
        else return 0;
    }
    int isFull(QueueType *q){
        if (((q->rear)%SIZE)==q->front){
            printf("q is full");
            return 1;
        }
        else return 0;
    }
    void enqueue(QueueType *q, element item){
        if (isFull(q)) return;
        else {
            q->rear = (q->rear+1)%SIZE;
            q->queue[q->rear]=item;
        }
    }
    element dequeue(QueueType *q){
        if (isEmpty(q)) exit(1);
        else {
            q->front = (q->front+1)%SIZE;
            return q->queue[q->front];
        }
    }
    int main(void){
        QueueType *q=init();
        element data;
        //삽입
        enqueue(q,'A');
        enqueue(q,'B');
        data = dequeue(q); 
        return 0;
    }

• 우선순위 큐
  https://hannom.tistory.com/36

7. 덱

   • 큐 두개 중 하나를 좌우로 뒤집어서 붙인 구조로, 큐의 양쪽에서 삽입,삭제 연산을 모두 수행할 수 있도록 확장한 구조이다.

     #include <stdio.h>
     #include <stdlib.h>
     
     typedef char element;
     typedef struce Node{
     	element data;
     	struct Node *llink;
     	struct Node *rlink;
     }Node;
     typedef struct{
     	Node *front, *rear;
     }DQueType;
     DQueType *init(){
     	DQueType *dq;
     	dq = (DQueType *)malloc(sizeof(DQueType));
     	dq->front = NULL;
     	dq->rear = NULL;
     	return dq
     }
     int isEmpty(DQueType *dq){
     	if (dq->front==NULL){
     		printf("dq is empty");
     		return 1;
     	}
     	else return 0;
     }
     void insertFront(DQueType *dq, element item){
     	Node *newNode = (Node *)malloc(sizeof(Node));
     	newNode->data = item;
     	if (dq->front==NULL){
     		dq->front=newNode;
     		dq->rear=newNode;
     		newNode->rlink=NULL;
     		newNode->llink=NULL;
     	}
     	else {
     		dq->front->llink = newNode;
     		newNode->rlink=dq->front;
     		dq->front=newNode;
     	}
     }
     void insertRear(DQueType *dq, element item){
     	Node *newNode = (Node *)malloc(sizeof(Node));
     	newNode->data = item;
     	if (dq->rear==NULL){
     		dq->front=newNode;
     		dq->rear=newNode;
     		newNode->rlink=NULL;
     		newNode->llink=NULL;
     	}
     	else {
     		dq->rear->llink = newNode;
     		newNode->rlink=dq->front;
     		dq->rear=newNode;
     	}
     }
     element deleteFront(DQueType *dq){
     	Node *old = dq->front;
     	element item;
     	if(isEmpty(dq)) return 0;
     	else {
     		item = old->data;
     		if(dq->front->rlink==NULL){
     			dq->front=NULL;
     			dq->rear=NULL;
     		}
     		else{
     			dq->front=dq->front->rlink;
     			dq->front->llink=NULL;
     		}
     		free(old);
     		return item;
     	}
     }
     element deleteRear(DQueType *dq){
     	Node *old = dq->rear;
     	element item;
     	if(isEmpty(dq)) return 0;
     	else {
     		item = old->data;
     		if(dq->rear->rlink==NULL){
     			dq->front=NULL;
     			dq->rear=NULL;
     		}
     		else{
     			dq->rear=dq->front->rlink;
     			dq->rear->llink=NULL;
     		}
     		free(old);
     		return item;
     	}
     }
     int main(void){
     	DQueType *dq = init();
     	element data;
     	insertFront(dq,'A');
     	insertRear(dq,'A');
     	data=deleteFront(dq);
     	return 0;
     }