array

배열의 개념

• 리스트 는 일상 생활에서 가장 많이 쓰이는 자료 형태다. 순서가 있는 자료 구조다.
• 배열은 컴퓨터 언어에서 리스트를 저장하는 데이터 타입이다.
• 리스트와 배열은 같은 개념이지만 다른 차원의 용어이다.

배열에 관한 연산

• 새로운 배열의 생성
  • ex) int x[5];
    • 언어에 따라 첨자 0 혹은 1에서 시작
• 순서를 유지하는 배열에서 데이터의 삽입과 삭제
  • 배열에 값을 삭제 이후에 나머지 값을 한 칸 씩 이동한다.
  • 배열에 새로운 값 삽입 시 나머지 값들을 한 칸 씩 이동한다.
  • → 삽입 삭제의 어려움이 있다. 하나가 추가 됐을 때 다른 곳에서 정보 수정이 일관적으로 이뤄지기 때문에 어렵다고 판단.

배열과 기억 장소

• 배열은 기억 장소에서 연속된 위치를 차지한다.
  • ex) int list[5];
    • sizeof() 함수는 데이터의 길이를 byte로 반환하는 함수
    • C언어에서 sizeof(int)의 값은 2byte이지만 시스템에 따라서 4byte로 표현되기도 함

포인터 타입

• 포인터 타입은 데이터가 기억장소의 주소를 저장하는 타입이다.
• 사람이 사는 모든 집에 주소 가 있고 컴퓨터의 기억 장소에도 주소가 있다.

포인터 타입 예

int x;
/*내용을 저장하는 변수*/
int *y;
/*주소를 저장하는 포인터 변수*/
int z;

x=10; /*내용 10을 저장*/
y=&x; /*변수 x의 주소를 저장*/
z=*y; /* 주소 y가 가리키는 곳의 내용을 저장, z=x와 같은 의미*/

int a[20]; /*배열 변수 a는 주소 값으로 처리한다. 배열의 내용 전체
이동시 주소 값을 알려주면 편함.*/

#include <stdio.h>
int main() {
	int list[5] = { 10,20,30,40,50 };
	printf("%d\\n", sizeof(int));
	printf("%d\\n", list);
	printf("%p\\n", list);
	printf("%d\\n", list+1);
	printf("%d\\n", list[0]);

}

8~18 페이지 생략 → 이후 삽입 예정

 

구조체

• 구조체는 데이터를 표현하는 단위이다.
• ex) 학생의 명단, 은행 거래 고객 명단, 월별 판매액 등
  • but!
    • 학생의 명단 = 학생의 학번, 이름, 즈소
    • 고객의 명단 = 고객의 이름, 주소, 계좌번호 등데이터 타입은 복합 데이터에 해당 ⇒ 복합 데이터를 1개의 변수로 표현 == 구조체
    • ⇒ 여러 개의 작은 값들이 합해서 한 개의 데이터를 구성한다.
  → 구조체는 각 데이터가 타입과 이름을 갖는다.

구조체의 예

 

“사람” 데이터 타입

• 어떤 사람의 신상 정보 컴퓨터 기입
  • field 1 이름=char[]
  • field 2 나이 = int
  • field 3 급여 = float
• 선언
• struct{ char name[10]; int age; float salary;} person;

구조체에 데이터 저장하는 법

• 치환문
  • struct 전체를 치환한다.
  • human_being person1, person2; ... person1=person2;
  • struct 필드 단위로 치환한다.
  • strcpy(person1.name, person2.name); person1.age=person2.age; person1.salary=person2.salary;

 

구조체 배열

24~28 page 생략

 

자기참조 구조체

• 구조체의 필드 중 하나가 구조체에 대한 포인터를 나타내는 타입이다.
• 연결리스트, 트리, 그래프의 구현에 쓰이는 방법
• 다른 구조체를 연결하고 있기 때문에 동적 기억 장소 구현에 쓰이는 방법
• typedef struct list{ char data; list * link;};
• Link 필드의 값
  • 기억 장소에 대한 포인터로 list 타입을 가리킨다.
  • 아무것도 가리키지 않으면 0(null) 값을 갖는다.

자기참조 구조체 노드 선언

• 기억장소가 가르키는 것이 없는 것으로 할당
• 데이터+포인터로 묶어서 하나의 자료구조를 만든다.

list_node item1,item2, item3;

item1.data='a';
item2.data='b';
item3.data='c';
item1.link=item2.link=item3.link=Null;

자기참조 구조체의 연결

item1.link=&item2;
item2.lint=&item3;

• 데이터의 insert/delete의 연산이 복잡한 편이다. 이에 다른 데이터를 건드리지 않도록 함.
• 배열은 연속해야 한다. Sometimes 기억 장소 속 여기저기에 흩뿌려 있을 수 있으나 이 것을 한 줄로 묶고 싶다!

희소 행렬

• 배열 응용 예
• 정의 : 값이 드물게 있는 행렬을 계산 할 시 연산 결과의 값이 대부분 0값을 갖게 된다. 이 행렬을 희소행렬이라고 한다.
• ex) 행렬을 프로그램에 저장하려면 다음과 같은 선언
  • 행렬을 표현하는데 기억 장소 많이 필요함
  → 기억 공간 활용의 비효율성
  • 개선된 방법의 사용!
    • 큰 행렬은 값이 0인 항이 많다. 0이 아닌 항만 <행, 열, 값>으로 저장!

 

C언어로 희소 행렬의 자료구조를 선언

#define MAX_THERMS 101
typedef stuct{
	int col;
	int row;
	int value;
} term;
term a[MAX_THERMS];

• a[0].row : 행의 수
• a[0].col : 열의 수
• a[0].value : 0이 아닌 항의 수

다차원 배열의 저장

• 1차원 배열은 기억장소에 순서대로 저장한다.
• N차원 배열이 어떻게 1차원의 물리적인 기억장소에 저장될까?
• N차원 배열의 임의의 원소는 기억장소의 어디에 저장되어 있는가?

💡 int a [upper0][upper1]….[uppern-1] /선언/

 

• 배열의 전체 원소의 수 구하는 법:
  • int a[6][7][8] : 전체 원소의 수 = 6*7*8 =336

 

다차원 배열의 저장 방법

• 행 우선 저장
• 열 우선 저장

1차원 배열

• ex) int x[8]로 선언되어 있을 때, x[0]의 주소가 100번지
  • x[5]의 주소는?
  • → int[5]의 주소 = 100+5*2=110번지

2차원 배열

• ex) int x[4][5]로 선언, x[0][0]=100번지, x[2][3]의 주소는?
  • 행 우선 저장!! int → 2byte
  • 100+2(2*5+3)=126번지

3차원 배열

• int x[3][4][5], 초기 → 100번지, x[2][3][4]주소는?
  • 행우선, int=2byte
  • 100+2(245+3*5+4)
• int x[3][4][5], 초기 → 100번지, x[2][3][4]주소는?
  • 열우선, int=2byte
  • 100+2(2+33+43*4)