'[Public] 컴퓨터공학/자료구조'에 해당되는 글 8건

  1. 2009.10.05 [자료구조] 1. 배열 다루기
2009.10.05 12:36

첨자로 빠르게 접근하는 배열

 

2009. 10. 05 ()

 

 

1.     배열의 개요

1)     배열의 필요성

-       프로그램에서 처리에 필요한 데이터를 저장하기 위해서 변수를 선언하고 이를 이용해서 값을 저장하고 읽는다. 하지만 데이터가 매우 많다면 일일이 변수를 선언해서 각각의 변수명을 처리해야 한다. 그래서 제공되는 것이 배열이다.

-       동일한 성질을 가진 자료들의 집합이라 생각하면 된다.

 

2)     배열의 선언

-       Int   arrScore  [10]

자료형  배열명  배열크기

 

3)     배열에 값 저장하기

-       배열의 첨자는 0부터 시작한다. 10개를 선언하면 0~9 까지

 

#include <stdio.h>

void main()

{

        int T;

        int nArray[10] = {0, };

        int K;

 

        printf("T =  %x\n", &T);

        for(int i=0 ; i<10 ; i++)

        {

           printf("nArray[%d] =  %x\n", i, &nArray[i]);

        }

        printf("K =  %x\n", &K);

}

 

-       여기서 중요하게 볼 것은 배열이 저장될 때 어떻게 저장이 되는가 이다. 나중 포인터 연산연산 나올 때 자주 낚시문제로 나오는 것 중 하나이다. 내용을 보면 변수가 선언되는 순서는 T -> nArray[10] -> K 순서대로 선언되었다. 아래 그림과 같이 스택구조 같이 메모리가 점점 쌓인다. 여기서 배열은 저장할 때 가장 마지막 배열이 먼저 배치됨을 알 수 있다. (쉽게 말하면 T 다음 nArray가 오는데 이는 9부터 오는 것을 알 수 있다.)

 

                         

 

 

 

 

k

0x 22fcc1

nArray[0]

0x 22fc28

nArray[1]

0x 22fc2c

……

….

nArray[8]

0x 22fc48

nArray[9]

0x 22fc4C

T

0x 22fc58

…..

…..

…..

…..

 

2.     배열 다루기

1)     삽입

-       배열은 메모리 상에서 일렬로 이어진 형태로 저장되기 때문에 특정 요소에 데이터를 삽입 하면 그 위치 이후에 있는 배열 요소를 하나씩 이동 시켜야 한다.

-       여기서 중요한 건 뒤에서부터 이동해야 한다. 앞에서 이동하면 다음데이터가 지워지기 때문에 한번 생각쯤은 해보고 for문을 돌리던가 하자.

 

 

 

2)     삭제

-       삭제도 삽입과 비슷하다. 단지 이건 앞에서 해야 뒤 데이터를 살려서 이동시킬 수 있다.

 

 

3)     검색

-       검색은 단순하게 전체부터 검색을 하면 될 것 같다. 여기서 다양한 검색 방법이 나지만 나는 우선 그냥 앞에서부터 검색하는 방법을 선택하였다.

-       각각 만들기 싫어서 한 뭉탱이로 만들어서 설명하겠다.
(
10개 정적배열 크기 설정)

#include <stdio.h>

#include <memory.h>

 

#define MAXVALUE 10

 

void PrintArray(int* nData);

void InsertArray(int* nData, int nWhere, int nValue);

void DeleteArray(int* nData, int nWhere);

int FindArray(int* nData, int nValue);

 

// 메인 루틴

void main()

{

       int Array[MAXVALUE] = {10, 20, 30, 40, 50, 60, 70 };

       int* ptrArray = Array;

 

       InsertArray(ptrArray, 4, 10);

       DeleteArray(ptrArray, 4);

       PrintArray(ptrArray);

 

       int nFindData= FindArray(ptrArray, 60);

       printf("%d60데이터검색\n", nFindData);

}

 

// 출력 함수

void PrintArray(int* nData)

{

       for (int i=0 ; i<MAXVALUE ; i++)

       {

             printf("array[%d] = %d\n", i, nData[i]);

       }

}

 

// 배열에 데이터 삽입

void InsertArray(int* nData, int nWhere, int nValue)

{

       for(int i = MAXVALUE-1 ; i>nWhere+1 ; i--)

       {

             nData[i] = nData[i-1];

       }

       nData[nWhere+1] = nValue;

}

 

// 배열에 데이터 삭제

void DeleteArray(int* nData, int nWhere)

{

       for(int i = nWhere+1 ; i<MAXVALUE ; i++)

       {

             if(i == MAXVALUE-1)

             {

                    nData[i] = 0;

             }

             else

             {

                    nData[i] = nData[i+1];

             }

       }

}

 

// 베열에 데이터 검색

int FindArray(int* nData, int nValue)

{

       int i=0;

       int nResult = -1;

       while(i<MAXVALUE)

       {

             if(nData[i] == nValue)

             {

                    nResult = i+1;

                    break;

             }

             i++;

       }

 

       return nResult;

}


 6번째 10 삽입


 6번째 삭제

 

 

60 검색



3.     배열의 장단점

1)     장점

-       특정 데이터에 빠르게 접근 가능

-       정적인 데이터 처리에서 기억장소를 효율적으로 활용할 수 있다.

 

2)     단점

-       배열내의 특정 위치에 데이터를 삽입 삭제할 경우 많은 작업이 필요하다.

-       배열 크기가 제한이 생긴다.

 

4.     배열의응용

1)     별 그리기

-       학교 레포트나 시험 문제로 가장 많이 나오곤 한다. 역삼각형 별 피라미드라든지 다양한 형태로 나오게 된다. 대표적인 역삼각형 별을 만들어 보겠다.        

-       문제는 다음과 같다.

*

***

*****

*******

 

void Star()

{

 

       char cStar[4][7] = {' ',};

       int j, i;

       int nCount = 3;

       int nCount2 = 1;

 

       for(j=0 ; j<4 ; j++)

       {

             nCount2 = 2 * (3 - nCount) + 1;

             for(i=0 ; i<7 ; i++)

             {

                    if(i >= nCount && nCount2 >0)

                    {

                           cStar[j][i] = '*';

                           nCount2--;

                    }

                    printf("%c", cStar[j][i]);

             }

             printf("\n");

             nCount--;

       }

 

}

 


2)     행렬 예제

-       행렬을 만들어서 사용하는데 STL을 이용하면 쉽게 이용할 수 있다.

-       행렬은 귀찮아서 생략

Posted by 차출발 차출발