C言語の練習
Cはもうほとんど忘れてしまっているので、復習をかねて昔読んだアルゴリズムの本の問題をやってみようと思った。
- bubble sort
#include <stdio.h> void swap( int *a, int *b); void bubbleSort( int *a, int length ); void bubbleSort( int *a, int length ) { for(int i=length-1; i>0; i--) { for(int j=0; j<i; j++){ if(a[j] > a[j+1]) swap(a+j, a+j+1); } } } inline void swap( int *a, int *b ){ int tmp = *a; *a = *b; *b = tmp; } int main(int *argv, int args) { int a[] = {5,4,3,2,1}; bubbleSort( a, 5 ); for(int i=0; i<5; i++) { printf("a[%d]: %d\n", i, a[i]); } return 0; }
- selection sort
#include <stdio.h> void swap( int *a, int *b); void selectionSort( int *a, int length ); void selectionSort( int *a, int length ) { for(int i=0; i<length-1; i++) { int min_index=i; for(int j=i+1; j<length; j++){ if(a[min_index]>a[j]) min_index=j; } swap( a+i, a+min_index ); } } inline void swap( int *a, int *b ){ int tmp = *a; *a = *b; *b = tmp; } int main(int *argv, int args) { int a[] = {4,3,1,12, 15, 20, 2, 5}; selectionSort( a, 5 ); for(int i=0; i<5; i++) { printf("a[%d]: %d\n", i, a[i]); } return 0; }
- selection sort
#include <stdio.h> void swap( int *a, int *b); void selectionSort( int a[], int length ); void shift( int a[], int start, int end ); void selectionSort( int a[], int length ) { for(int i=1; i<length; i++) { int tmp=a[i]; for(int j=0; j<i; j++){ if( a[j] > tmp ) { shift(a, j, i-1); a[j] = tmp; break; } } } } void shift( int a[], int start, int end ){ for( int i=end; start<=i; i-- ){ a[i+1] = a[i]; } } inline void swap( int *a, int *b ){ int tmp = *a; *a = *b; *b = tmp; } int main(int *argv, int args) { int a[] = {4,3,1,12, 15, 20, 2, 5}; selectionSort( a, 5 ); for(int i=0; i<5; i++) { printf("a[%d]: %d\n", i, a[i]); } return 0; }
- stack class
push, pop, peek
- queue class
insert, delete, peek
- circular queue class
- priority queue class
insert, delete, peek
- InToPost 関数
中値記法をReverse Polish Notation に変換する。