자료구조 수업 2 자료구조란 / Stack의 Push,Pop / 연결리스트 / Queue

자료 구조란

- 사전적 의미 : 데이터를 처리하는 입장에서 데이터 사이에 존재하는 관계를 개념적으로 잡은 것

- 데이터를 효율적으로 사용할 수 있도록 구조를 만들어서 저장하는 것

어떻게 효율적으로 저장할 것이냐 ?

선형 구조

- 데이터를 선의 형태로 일렬로 저장.

- 스택, 큐, 연결리스트

비 선형 구조

- 데이터를 선의 형태가 아닌 다른 형태로 저장하는 방식

- 이전 데이터와 이후 데이터는 1대 다 관계를 가짐

- 트리(보통 위에서 밑으로. 뿌리구조), 그래프

* 스택(Stack) (일종의 약속. 이렇게 사용하자)

- 삽입/삭제가 한쪽 끝에서만 수행되는 구조

- LIFO 구조

입력 : Push / 출력 : Pop

바텀 / 탑을 이용해서 스택의 영역을 나타낸다.

푸쉬 : 탑의 위치가 올라감 / 팝 : 탑의 위치를 내려줌

*큐(Queue)

- 한쪽에서는 삽입만 한쪽에서 삭제만 수행되는 구조

- FIFO : 먼저 들어간 데이터가 먼저 나오는 구조

- Front와 Rear를 통해 사용되며, 데이터 삽입시 rear가 이동한다. 데이터 출력시 front가 움직인다.

*리스트

- 데이터를 순서대로 저장해 놓는 구조

- 대표적으로 배열.

- 스택/큐도 넓은 의미로 리스트에 포함

연결리스트 (뒤에 있는 데이터의 위치정보가 필요하므로 포인터사용)

- 데이터들을 링크를 통해 연결시켜 저장하는 구조

- (데이터 / 링크) 링크는 다음 데이터의 주소를 가지고 있어야 한다.

따라서 구조체를 사용해서 (데이터형 / 다음 구조체에 대한 포인터변수) = 합쳐서 노드. 데이터와 주소로 구성

ex)

typedef struct person_node{

char name[20];

char blood[10];

int age;

struct person_node *p;

}person_node;

void main()

{

person_node p1;

strcpy(p1.name, "홍길동");

strcpy(p1.blood, "RH+B");

p1.age = 100;

p1.p = NULL;

person_node p2;

strcpy(p2.name, "고길동");

strcpy(p2.blood, "RH+AB");

p2.age=150;

p2.p=NuLL;

p1.p=&p2;

}

함수로 만들어주고, 동적할당도 더해준다. (데이터가 얼마나 들어갈지 모르므로)

데이터 삽입시에도 임시변수를 넣어서 흐름이 끊기지 않게 해준다.

2번을 없애려면. 1번이 가르키는 주소를 3번으로 바로 이어주면 된다. -> 1번노드에 있는 주소값이 사라져서 Free를 못시켜준다. 따라서 임시변수가 필요. 임시변수 -> 2번을 가리키고 1번을 3번을 이어준다. 그리고 2번에 있는 주소로 Free 시켜준다.

이중연결리스트

앞뒤를 자유롭게 찾아볼수있다.

NULL 10 NULL-> 다음 구조체의 head 시작 주소

(head / data / tail) 형태의 구조체를 생성

앞구조체의 시작주소 20 NULL-> 다음 구조체의 head 시작 주소

(head / data / tail)

앞구조체의 시작주소 30 NULL

(head / data / tail)

15를 삽입하려고 한다.

임시변수 선언 -> 10 tail에 있는 20의 head 시작주소를 임시변수에 넣어주고 15의 tail에 다시 넣어준다.

원형연결리스트도 있다.

*트리(tree)

l link / data / r link

데이터 추가시 왼쪽에 저장되는건 l link에 저장 오른쪽은 r link에 저장

*그래프

컴퓨터로 계산한결과를 그림등으로 나타냄

알고리즘 - 어떤 문제를 해결하기 위한 방법

#include <stdio.h>

typedef struct stack{

int stackArea[5];

int top;

}Stack, *PStack;

void Push(Stack *st, int data)

{

if(st->top>=((int)sizeof(st->stackArea)/4)-1)

{

printf("Stack is FULL\n");

return;

}

st->top++;

st->stackArea[st->top] = data;

}

void main()

{

Stack s;

s.top =-1;

Push(&s,10);

Push(&s,20);

for (int i=0;i<=s.top;i++)

printf("%d",s.stackArea[i]);

}

Stack의 Push와 Pop 구조

#include <stdio.h>

typedef struct stack{

int stackArea[5];

int top;

}Stack, *PStack;

void Push(Stack *st, int data)

{

if(st->top>=((int)sizeof(st->stackArea)/4)-1)

{

printf("Stack is FULL\n");

return;

}

st->top++;

st->stackArea[st->top] = data;

}

void Pop(Stack *st)

{

if(st->top<0)

{

printf("Stack is Void\n");

return;

}

st->stackArea[st->top] = 0;

st->top--;

}

void main()

{

Stack s;

s.top =-1;

Push(&s,10);

Push(&s,20);

Push(&s,30);

Push(&s,40);

Push(&s,50);

Push(&s,60);

/*for (int i=0;i<=s.top;i++)

printf("%d\n",s.stackArea[i]);*/

printf("\n");

Pop(&s);

/*for (int j = s.top;j>-1;j--)

printf("%d\n",s.stackArea[j]);*/

}

연결리스트

포인터변수는 자료형에 상관없이 주소값을 저장하는 4바이트 공간 하나만 생긴다.

구조체등의 포인터 변수라면 아마도 시작주소값 + 각 멤버변수의 바이트수를 더한 공간값으로 가는듯 하다.

구조체->변수

연결리스트에선 탑에 있는 자료만 확인 하면 되므로 중간중간의 데이터는 중요하지 않다.

그냥 보기 -> 탑, 보기->탑 등 탑만 확인하면 된다.

#include<stdio.h>

#include<stdlib.h>

#define EMPTY 0;

struct node {

int data;

struct node* link;

};

typedef struct node Stack;

Stack* top = EMPTY;

void Push(Stack* *top,int data)

{

Stack* tmp;

tmp = (Stack*)malloc(sizeof(Stack));

(*tmp).link = *top;

*top = tmp;

(*top)->data=data;

}

void Pop()

{

if(top==0)

{

printf("Stack is Void\n");

return;

}

Stack* tmp;

tmp = top;

top =(*top).link;

free(tmp);

}

void main()

{

Push(&top,10);