C-Project15

자료구조 및 알고리즘

동적메모리 할당
2차원 배열을 힙에 연속으로 할당하는 방법

1. 배열포인터를 사용하여 동적할당

#include<stdio.h>
#include<stdlib.h>

int main(void) {

	int (*p)[4]; //배열포인터 선언
	int m, i, j;

	printf("Enter number of rows: ");
	scanf_s("%d", &m); //행의 개수 입력

	p = (int(*)[4])malloc(sizeof(int)*m*4); 

	if (p == NULL) {
		printf("할당 실패");
		exit(1);
	}

	printf("Enter the elements of the array\n");
	for (i = 0; i < m; ++i) {
		for (j = 0; j < 4; ++j){
			printf("p[%d][%d]", i, j);
			scanf_s("%d", &p[i][j]);
		}
	}

	for (i = 0; i < m; ++i) {
		for (j = 0; j < 4; ++j) {
			printf("%5d", p[i][j]);
		}
		printf("\n");
	}

	return 0;
}

2.포인터 배열을 이용한 2차원 배열의 할당

#include<stdio.h>
#include<stdlib.h>

int main(void) {

	int** p, *q, m, n, i, j;
	printf("Enter number of rows: ");
	scanf_s("%d", &m);
	printf("Enter number of cols: ");
	scanf_s("%d", &n);
	//동적 메모리 할당
	p = (int**)malloc(m * sizeof(int*));
	q = (int*)malloc(m * n * sizeof(int));

	if (p == NULL || q == NULL) {
		printf("할당 실패");
		exit(1);
	}
	//포인터들이 메모리 공간의 시작주소를 가리키도록 설정
	
	for (i = 0; i < m; ++i) {
		p[i] = q;
		q += n; //포인터 q가 열의 개수만큼 이동하도록 설정
	}

	return 0;
}

포인터 배열 하나로 동적할당

#include<stdio.h>
#include<stdlib.h>

int main(void) {

	int** p, m, n, i, j;
	printf("Enter number of rows: ");
	scanf_s("%d", &m);
	printf("Enter number of cols: ");
	scanf_s("%d", &n);
	
	p = (int**)malloc(sizeof(int*) * m);
	for (i = 0; i < m; ++i) {
		p[i] = (int*)malloc(sizeof(int) * n);
	}
	return 0;
}

검색(searching)

: 목록의 요소를 순차적으로 검색하여 원하는 데이터를 찾아내는 알고리즘

• 선형검색 : 목록의 첫 번째 요소로 시작하여 원하는 데이터를 찾거나 마지막 요소를 지나칠 때까지 검색을 수행합니다.

#include<stdio.h>
#include<stdlib.h>

int linear(int arr[], int arr_size, int key);

int main(void) {

	int* arr;
	int i, N, k, index;

	printf("할당할 요소의 개수(배열크기): ");
	scanf_s("%d", &N);
	arr = (int*)malloc(sizeof(int) * N);
	printf("\n %d개의 요소를 입력하세요: ",N);
	for (i = 0; i < N; ++i)
		scanf_s("%d", &arr[i]);
	
	printf("찾을 키 값 입력: ");
	scanf_s("%d", &k);

	index = linear(arr, N, k);
	if (index >= 0)
		printf("%d번째 인덱스에 있는 %d 값을 찾았습니다!\n",(index+1), k);
	else
		printf("찾는 값 %d이 없습니다.\n",k);

	return 0;
}

int linear(int arr[], int arr_size, int key) {
	int i;
	for (i = 0; i < arr_size; ++i) {
		if (arr[i] == key)
			return i;
	}

	if(i==arr_size)
		return -1;
} 

• 이진검색 : 이진 검색을 수행하기 위해서는 데이터들이 순서대로 정렬되어 있어야 합니다.

int binary(int arr[], int arr_size, int key) {
	int i=0, j=arr_size, k;

	while (i <= j) {

		k = (i + j) / 2;

		if (arr[k] == key)
			return k;
		else if (arr[k] < key)
			i = k + 1;
		else
			j = k - 1;
	}
	return -1; //while문을 벗어난 경우는 key값을 못찾음
} 

정렬

: 순서가 정해지지 않은 데이터를 오름차순 또는 내림차순으로 배열하는 알고리즘

-버블 정렬: 데이터를 저장하는 컨테이너의 왼쪽에서 오른쪽으로 순회하는 방식으로 진행하며 각 인접한 요소 쌍을 비교합니다. 비교하는 쌍이 정렬된 상태가 아닌 것을 발견할 때마다 요소의 위치를 교환합니다.

#include<stdio.h>
#include<stdlib.h>
#define N 10
#define TRUE 1
#define FALSE 0

int main(void) {

	int arr[N];
	int flag;
	int size;
	int i, j, temp, count;
	int arr_size;

	printf("배열의 크기 입력: ");
	scanf_s("%d", &size);

	printf("\n배열의 요소 입력: ");
	for (i = 0; i < size; ++i) {
		scanf_s("%d", &arr[i]);
	}

	count = 0;
	arr_size = size;

	do{
		flag == FALSE;
		
		for (j = 0; j < size - 1; ++j) {
			if (arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
				flag = TRUE;
			}
		}
		if (flag == TRUE)
			++count;
		--arr_size;

	} while (flag == TRUE);

	printf("\n정렬된 데이터 출력: ");
	for (i = 0; i < size; ++i)
		printf("%d ", arr[i]);

	printf("\n 패스 횟수: %d\n", count);
	return 0;
}