[DataStruct 08.31] 1. 정리 첫째날!!ㅋㅋ

1. 자료구조란??

  컴퓨터상의 다양한 정보를 좀더 빠르고 효율적으로 검색하며 가장 이상적으로 저장할수 있게 정리하는 기술 방법을 자료구조라고 한다. 실제로 사용해보면 실제로 얼마나 이상적인줄 알 것이다. 컴퓨터를 사용하면 어떤 종류의 프로그램이든 자료구조를 사용해야 좀더 좋은 프로그램이 될 수 있기에 자료구조를 사용한다.

2. Swap Algorithm in Bubble Sort

bubble(int a[],int n) { int i, j, temp;    for(i=0; i<n-1; i++)       for(j=1; j<n; j++)          if(a[j-1] > a[j])             swap (a[j-1], a[j]); } swap(int *x,int y) { int t; t=*x; *x=*y; *y=*t; }

3. 재귀 호출(Recursive Call)
재귀 호출은 함수를 실행중 함수 자기자신을 다시 호출하는 것을 재귀 호출이라고 한다. 여기서 중단시키는 조건은 Recursive hatch라고 한다.

main() { printf("\n Factorial of 3: %d",fact(3));} void fact(int n) {        if(n==1)                 return 1;        else                 return n * fact(n-1); }

4. 큐(Queue)
  큐는 한쪽 끝에서 데이터가 삽입되고 삭제는 반대쪽 끝에서만 할 수 있도록 되어 있는 자료 구조 이와 같은 원리는 극장의 표를 구매하기 위한 사람이나 화장실을 비교할수 있으면 FIFO(First in First out)이라고 불리기도 한다.
선형 큐 한쪽 방향으로 데이터 항목들이 삽입,  삭제가능
선형큐의 문제점  front와 rear가 하한에서 상한으로 계속 증가하기 때문에 결국 삽입을 할수 없는 문제가 발생
해결방법으로는 환형큐와 rear가 MAX가 되었을때 rear를 큐의 제일 왼쪽으로 이동하는 방법이 있다.
환형 큐 시작점과 끝점이 서로 연결되어 있는 큐

 

                    








               


                선형                                                                                                                             환형

선형 큐의  동작

1.큐의 초기화하여 하나의 비어있는 큐를 만들다.->2. 큐에 새로운 데이터 항목 삽입->3. 큐의 프론트에 있는 항목삭제 -> 4. 큐가 비었는가 검사->5. 큐가 가득찼는지를 검사->6. 데이터 항목을 출력
삽입할 때

void enqueue(char queue[], int *rear, char data) {       if(*rear==MAX){                   //큐가 가득차 있는지를 검사                   printf("The queue is full");        }        *rear=*rear+1;        queue[*rear]=data; }

삭제할 때

void dequeue(char queue[], int *front, int rear, char data) {       if(*front==rear){                   //큐가 비었는지 검사                  printf("The queue is empty");        }        *front=*front+1;        *data=queue[*front]; }

출력할 때

void display(char queue[], int *front, int rear) {         int i;         for(i=0;i<MAX;i++)         {                  if(i<=front)                 {                         printf("    |");                 }                   if(i>rear)                 {                         printf("    ");                 }                   if(i>front && i<=rear)                 {                         printf("    %c   ",queue[i]);                         printf(" |");                 }          }      printf("\n"); }

환형큐 (Circular Queue)
선형큐의 문제점을 보완하기 위해 만들어진 구조
삽입부분

void enqueue() {          rear=(rear+1)%MAX;          if(rear==front){                    printf("circular_queue is full.\n");                    exit(0);          }          queue(rear)=data; }

삭제부분

void dequeue(char queue[],int *front,int rear, char *data) {         if(rear==*front){                    printf("circular_queue is Empty.\n");                    exit(0);          }          *front=(*front+1)%MAX;          *data=queue(*front); }

출력부분

void displayQueue() {         if(rear<front){                    printf("\n|");                    for(int i=0;i<MAX;i++)                    {                             if(i>rear && i<=front)                                       printf("        |");                             if(i>front||i<=rear){                                         printf("         %c  ",queue[i]);                                         printf("|");                             }                    }                 printf("\n");          } }

추가적으로 데크랑 Double Ended Queue로써 삽입과 삭제가 양쪽 끝에서 발생하는 것을 말한다.
이때 출력이 두개이면 스크롤(scroll) 입력이 두군대이면 쉘프(shelf)라고 부른다.

위의 방식 말고도 링크드 리스트로도 표현 할수 있다.