3.1 배열
-동일한 타입의 데이터 한 번에 여러 개 만들 때 사용.
-배열 사용하면 연속적 메모리 공간이 할당되고 인덱스번호 사용하여 쉽게 접근 가능, 반복루프 이용
-배열 ADT: 배열은 <인덱스, 값>의 쌍으로 이루어진 집합(index 주어지면 해당 value가 대응)
ㄴ연산: set(주어진 인덱스에 값 저장), get(인덱스 주어지면 값 추출)
- 1차원배열:
*인덱스 0부터 시작
컴파일러: 배열에 메모리의 연속된 위치에 할당> list[0] 이 기본주소(base)
프로그램에 list[i]라 적으면 컴파일러는 base+i*sizeof(int)에 있는 값 가져옴
- 2차원 배열: list[0][0] 0행 0열에서 시작.
3.2 구조체
-구조체: 타입이 다른 데이터 묶는 방법, struct 키워드 써서 표기
구조체 tag: 구조체와 구조체를 구별할 수 있게 해주는 식별자.
-실제로 구조체 만들려면 struct studentTag s; 선언해줘야 함.
-구조체 사용은?
-typedef 사용하여 구조체 새로운 타입으로 선언 가능
-> student가 새로운 데이터 타입의 이름 됨.
> student 만 사용하여 변수 선언 가능.(int 나 float처럼)
3.3 배열의 응용: 다항식
[다항식 표현]
1. 모든 차수 계수값을 배열에 저장
>>단점; 대부분 항이 0인 다항식에서는 공간의 낭비가 심함
2. 다항식에서 0이 아닌 항만을 하나의 전역 배열에 저장. ( (계수, 차수)의 형식으로 구조체 배열에 저장.
>> 단점: 하나의 다항식이 시작되고 끝나는 위치 가리키는 인덱스 변수 관리해야 함. 차수도 저장해야 함> 다항식에 따라 첫번째 방식보다 공간 더 필요로 할수도! +연산 구현도 어려워짐
3.4 배열의 응용: 희소행렬
1. 행렬 2차원배열로 나타내기
>> 희소행렬(많은 항들이 0으로 되어 있는 행렬)인 경우 메모리 낭비 심함.
2. 행렬 배열로 나타내되 0이 아닌 항만 표현
>> 전치연산(대각선 기준 (i,j)->(j,i) 구현할때는 방법 1이 더 빠름.
3.5 포인터
-포인터: 다른 변수의 주소를 갖고 있는 변수
-p는 int 형을 가리키는 포인터로 정의. p가 a를 가리키게 하려면 a의 주소를 p에 대입.
변수의 주소는 &연산자를 변수에 적용시켜서 추출
- &연산자: 주소연산자 - 변수의 주소를 &연산자로 추출하여 p에 대입
- *연산자: 간접참조 연산자-포인터가 가리키는 장소에 값 저장
-> *p= a (동일한 실제적 객체 가리킴)
-null 포인터: 어떤 객체도 가리키지 않는 포인터(NULL)_포인터가 아무것도 가리키고 있지 않으면 항상 널 포인터 상태로 만들어놓기
-배열의 이름=배열의 시작위치 가리키는 포인터
3.6 동적 메모리 할당
-동적 메모리 할당: 필요한 만큼의 메모리를 운영체제로부터 할당받아 사용, 사용 끝나면 시스템에 메모리 반납
ㄴ동적 메모리 할당되는 공간: 히프(운영체제가 사용되지 않는 메모리 공간 모아놓음)
1. malloc()함수는 size 바이트만큼의 메모리 블록 할당, sizeof 키워드는 변수나 타입 크기 숫자 반환. 크기 단위: byte.
2. 동적 메모리는 포인터로만 사용할 수 있음. *p는 p가 가리키는 장소.
3. free()함수는 할당된 메모리 블록 운영체제에게 반납(malloc() 함수가 반환했던 포인터 값 잊어버리면 동적메모리 반환 불가.) , malloc은 시스템 메모리가 부족해서 요구된 메모리 할당할 수 없으면 NULL 반환.
<구조체와 포인터>
-ps가 구조체를 가리키는 포인터일때.
'자료구조' 카테고리의 다른 글
| [자료구조] chap6. 연결리스트 I (1) | 2024.10.18 |
|---|---|
| [자료구조] chap5. 큐 (0) | 2024.10.17 |
| [자료구조] chap4. 스택 (4) | 2024.10.16 |
| [자료구조] chap2. 순환 (0) | 2024.10.07 |
| [자료구조] chap1. 자료구조와 알고리즘 (2) | 2024.09.24 |