[자료구조] 1. 배열 다루기

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

 

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("%d에60데이터검색\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을 이용하면 쉽게 이용할 수 있다.

-       행렬은 귀찮아서 생략