복습노트 복습노트

예전에 배운 다항식 연산을 연결리스트로 구현하는 것입니다. typedef struct poly_node* poly_pointer; typedef struct poly_node { int coef; int expon; poly_pointer link; }poly_node; 다항식을 계산하기 위한 리스트의 원형입니다. coef 부분은 계수 expon 부분은 차수 link 부분은 다음 리스트를 가리킵니다. 리스트의 덧셈 부분입니다. a = 3x^14 + 2x^8 + 1 b = 8x^14 + 4x^10 - 2x^8 이라고 가정하면 오른쪽 그림과 같은 모습이 됩니다. poly_pointer padd(poly_pointer a, poly_pointer b) { poly_pointer front, rear, temp..

Selction sort (선택 정렬) 배열이 있으면 맨 앞에 인덱스를 기준으로 배열 끝까지 돌면서 맨앞에 인덱스와 비교해 가장 작은 수와 바꿔주면 됩니다. #include #include #include #include #define SWAP(x,y,t) ((t)=(x), (x)=(y), (y)=(t)) void sort(int list[], int n); int main() { int arr[5] = { 5,2,1,4,3 }; sort(arr, 5); for (int i = 0; i < 5; i++) { printf("%d ", arr[i]); } return 0; } void sort(int list[], int n) { int i, j, min, temp; for (i = 0; i < n - 1;..

Linked list for merge (연결리스트를 이용한 오름차순 정렬 merge) 연결리스트 방법을 사용하여 오름차순을 하는 코드 입니다. X = {11, 36} 이 있고 Y = {16, 21} 이 있는 상태입니다. 이 둘의 연결리스트들을 합쳐서 오름차순으로 정렬해야 합니다. typedef struct list_node *list_pointer; typedef struct list_node { int data; list_pointer link; }list_node; list_pointer ptr = NULL; 연결리스트의 원형입니다. void merge(list_pointer x, list_pointer y, list_pointer* z) { list_pointer last; //노드 맨끝에 포인터..

컴파일러의 표기법 (후위 표기법 표현) 중위 표기법(Infix) 전위 표기법(Prefix) 후위 표기법(Postfix) ex) 2 + 3 * 4 ex) + 2 * 3 4 ex 2 3 4 * + ex) a * b + 5 ex) + * a b 5 ex) a b * 5 + ex) (1 + 2) * 7 ex) * + 1 2 7 ex) 1 2 + 7 * 우리는 일반적으로 중위 표기법을 사용해서 문제를 해결합니다. 그렇지만 컴퓨터는 후위 표기법으로 수식을 인식하고 계산합니다. 그래서 컴퓨터의 입장을 체험하고자 컴퓨터의 편의를 위해 우리가 미리 후위표기법 표현해주면 더 빠른 연산이 가능합니다. 이를 위해 우리는 stack 자료구조를 활용합니다. 배열 "8 2 / 3 -" 배열을 입력받았다고 가정하면 아래와 같은 과정..

스택을 이용하여 미로를 만들 수 있습니다. MAZE (미로 만들기 (stack 활용)) Initilize (미로 초기화) 먼저 2차원 배열을 통해 미로를 생성해 줄것입니다. 미로는 1과 0으로 이루어져있는데 0은 갈 수 있는 길이고 1은 막힌 길입니다. 우리가 미로를 통과하게 경로를 탐색하는 과정에서 벗어나지 않게 미로의 둘레를 막힌 길 1로 둘어쌓아줍니다. 따라서 2차원 배열의 행과 열을 ROW와 COL이라 할때, 실제적으로는 ROW+2, COL+2 입니다. 결국 미로 2차원 배열은 maze[ROW+2][COL+2] 라고 선언 가능합니다. 또한 시작점과 미로의 끝 점은 maze[1][1] 과 maze[ROW][COL] 이라고 할 수 있습니다. void initialize() {//미로 초기화 srand..

문자열 c언어에서 문자열은 char형 배열로 볼 수 있습니다. 특징은 맨 마지막 문자열 \0(NULL)에 의해 종료됩니다. 예를들어 "dog" 라는 char형 3개로 이루어진 문자열을 저장하려면 문자열의 메모리를 4로 두어야합니다. 맨마지막 문자에 \0이 들어가기 때문입니다. [0] [1] [2] [3] d o g \0 문자열의 합체 (strcat) 서로 다른 문자열 끼리 합칠 수 있습니다. 보통 strcat 함수를 사용합니다. 예를 들어 char s[20] = "dog", char t[20] = "house"라고 한다면 둘의 문자열을 합치면 "doghouse" 가 됩니다. #include #include #include int main() { char s[20] = "dog"; char t[20] = ..

Sparse Matrix는 희소행렬이라고도 하며 행렬 원소가 0이 많은 것을 의미합니다. 이렇게 되면 쓸데 없이 많은 메모리를 사용하게 됩니다. 예를들어 (방법 1) 0 1 2 3 4 5 0 0 0 0 7 0 0 1 9 0 0 0 0 8 2 0 0 0 0 0 0 3 6 5 0 0 0 0 4 0 0 0 0 0 1 5 0 0 2 0 0 0 이러한 2차원 배열은 0이라는 쓸모없는 원소를 저장하기 위해 메모리를 6*6의 크기를 사용합니다. 이를 0을 제외한 (행, 열, 값)으로 표현하면 좀더 메모리를 절약할 수 있습니다. (방법 2) 행 열 값 0 0 3 7 1 1 0 9 2 1 5 8 3 3 0 6 4 3 1 5 5 4 5 1 6 5 2 2 이렇게 7*3의 크기를 가지고 행렬을 표현 할 수 있습니다. 하지만 ..

2차원 배열 동적 할당 #include #include #include int main() { int** x; //이중 포인터 int rows; //행 int cols; //열 scanf("%d", &rows); x = (int**)malloc(rows * sizeof(int*)); //행을 동적할당 scanf("%d", &cols); for (int i = 0; i < rows; i++) { x[i] = (int*)malloc(cols * sizeof(int)); //행마다 열의 크기만큼 동적할당 } for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { scanf("%d", &x[i][j]); } } for (int i = 0; i < r..