자료구조 001 | Basic Concepts

Yunny.Log ·2021년 9월 25일

1. macro version of swap

주의사항 :

1) for (i=0; i<n-1; i++)

검사할 대상은 i, i는 n이 아닌 n-1까지만 설정 가능 -> n 순서 때는 이미 정렬 완료된 상태

2) for (j = i+1; j < n; j++)

i이하는 이미 검사 완료했으므로 j는 i+1을 대입해야 한다.

#define SWAP(x,y,t) ((t) = (x), (x) = (y), (y) = (t))
void sort (int list[], int n)
{
int i, j, min, temp;
for (i=0; i<n-1; i++) {
	min = i;
	for (j = i+1; j < n; j++)
		if (list[j] < list[min])
		min = j;
	SWAP(list[i], list[min], temp);
	}
}

2. fibo iterative

피보나치 수열
-> 0, 1, 1, 2, 3, 5, 8 .... 숫자는 앞의 두 숫자의 합으로 구성됨
-> n번째의 피보나치 수를 구하는 것

int fibo(int n)
{
int g, h, f, i;
if (n>1) {
	g = 0;
	h = 1;
	for (i = 2; i<= n; i++) { //입력된 n번의 숫자만큼 피보나치 수열을 진행
		f = g+h;
		g = h;
		h = f;
	}
}
else  (입력된 수가 1보다 크지 않은 1,0 그 이하의 수인 경우, 바로 그 숫자 return~)
	f = n;
	return f;
}

3. fibo recursive

int rfibo (int n)
{
if (n > 1)
	return rfibo(n-1) + rfibo(n-2);
else
	return n;
}

4. binary search

주의사항 :

1) 이진 검색은 정렬된 배열에서만 가능

2) int left, right, middle 은 모두 list라는 배열의 인덱스

#define COMPARE(x<y?-1:x==y?0:1)
int binarysearch(int list[], int searchnum, int left, int right){
	int middle;
    while(left<=right){
    	middle=(left+right)/2;
        switch(COMPARE(middle,searchnum)){
        	case -1 : left=middle-1;
            case 0 : return middle;
            case 1: right=middle-1;
            }
    }

5. binary search _ recursive

int binsearch(int list[], int searchnum, int left, int right)
{
/* search list[0] <= list[1] <= . . . <= list[n-1] for searchnum.
Return its position if found. Otherwise return -1 */
int middle;
if (left <= right) {
	middle = (left + right)/2;
	switch (COMPARE(list[middle], searchnum)) {
		case -1 : return binsearch(list, searchnum, middle + 1, right);
		case 0 : return middle;
		case 1 : return binsearch(list, searchnum, left, middle - 1);
		}
	}
return -1;
}

6. permutation _ recursive

=> 문자의 순열 모든 조합

주의사항 :

1) 이진 검색은 정렬된 배열에서만 가능

2) int left, right, middle 은 모두 list라는 배열의 인덱스

3) perm에 입력되는 i,n은 각각 가장 초기 인덱스, 가장 마지막 인덱스

#define SWAP(x,y,t) (t=x;x=y;y=t)
void perm(char * list, int i, int n){
	int j, temp;
    if (i==n){
    	for(j=0;j<n;j++){
        	printf("%c",list[j]);
            printf("  ");
        }
     }
    else {
    	SWAP(list[i],list[j],temp);
        perm(list,i+1,n);
        SWAP(list[i],list[j],temp);
    	}
    }
}

7. magic_square

#include <stdio.h>
#define MAX_SIZE 15 /* maximum size of square */
void main(void){
	static int square[MAX_SIZE] [MAX_SIZE];
	int i, j, row, column; /* indices */
	int count; /* counter */
	int size; /* Square size */

	printf("Enter the size of the square:");
	scanf("%d", &size);
	/* check for input errors */
	if (size<1 || size>MAX_SIZE+1) {
		fprintf(stderr, "Error! Size is out of range\n");
		exit(1);
	}
	if (!(size % 2)) {
	fprintf(stderr, "Error! Size is even\n");
	exit(1);
	}
	for (i=0; i<size; i++)
		for (j=0; j<size; j++)
			square[i][j] = 0;

	square[0][(size-1)/2] = 1; /* middle of first row */
	/* i and j are current position */
	i = 0;
	j = (size-1) / 2;

	for (count = 2; count <= size * size; count++) {
		row = (i-1 < 0) ? (size-1) : (i-1); /* up */
		column = (j-1 < 0) ? (size-1) : (j-1); /* left */
		if (square[row][column]) /* down */
			i = (++i) % size;
		else { /* square is unoccupied */
			i = row;
			j = column;
		}
	square[i][j] = count;
}


	printf("Magic Square of the size %d : \n\n", size);
	for (i = 0; i < size; i++) {
		for (j = 0; j < size; j++)
			printf ("%5d", square[i][j]);
	printf("\n");
}
printf("\n \n ");
}