隨筆札記

完整程式碼:

/* arr1:Bubble sort       *\
   arr2:Selection sort
   arr3:Insertion sort
   arr4:Merge sort
   arr5:Quick sort
\* arr6:BinaryTree track  */

#include "pch.h"
#include <stdio.h>
#include <stdlib.h>
#include<time.h>
#define MAX 16
int* load_add(int *, char*);//讀txt檔案
void show(int*, int); //顯示陣列
//***********Bubble sort ***********
void bubble_sort(int*, int);
//***********Selection sort***********
void select_sort(int*, int);
//***********Insertion sort***********
void insert_sort(int*, int);
//***********Merge sort***********
void merge(int *, int*, int*, int, int);
//***********Quick sort***********
void quick_sort(int*, int, int);
int Partition(int*, int, int);
//***********BinaryTree track***********
typedef struct node{
	int value;
	struct node *rightsub, *leftsub;
}Node;
void find(Node* , int);
void output(Node *);
void binarytree(int*, int);
Node *newnode(int);
//**********END***********

int main()
{
	//***********1.宣告未排序好的陣列***********//
	int *arr1 =NULL, *arr2 = NULL, *arr3 = NULL;//1,2,3
	int inde_num = 1,i=0,j=0,cnt = 0;//通用變數
	int *arr4 = (int*)calloc(200, sizeof(int));//Merge sort
	int *arr5 = (int*)calloc(20, sizeof(int)); //Quick sort
	int *arr6 = (int*)calloc(20, sizeof(int)); //BinaryTree track
	char path1[] = "D:/檔案存放區/想變強嗎人類/那就來寫程式吧/binary資料產生/data_txt/total_value_100_1.txt";
	char path2[] = "D:/檔案存放區/想變強嗎人類/那就來寫程式吧/binary資料產生/data_txt/total_value_100_2.txt";
	char path3[] = "D:/檔案存放區/想變強嗎人類/那就來寫程式吧/binary資料產生/data_txt/total_value_100_3.txt";
	char path4[] = "D:/檔案存放區/想變強嗎人類/那就來寫程式吧/binary資料產生/data_txt/total_value_100_4.txt";
	arr1 = load_add(arr1, path1);//Bubble sort
	arr2 = load_add(arr2, path2);//Selection sort
	arr3 = load_add(arr3, path3);//Insertion sort
	while(cnt <20){
		for (j = 0; j < i; j++) {
			if (arr5[j] == arr1[i])inde_num = 0;
		}
		if (inde_num) {
			arr5[cnt] = arr1[i];//Quick sort
			arr6[cnt] = arr1[i];//BinaryTree track
			cnt++;
			i++;
		}
		else {
			inde_num = 1;
			i++;
		}
	}

	//***********2.前置準備***********//
	int totalnum1=100,totalnum2 = 20,totalnum4 =200;//arr1~arr6內部資料數量
	//***********Bubble sort ***********
	bubble_sort(arr1,totalnum1);
	printf("\nBubble sort:\n");
	show(arr1, totalnum1);
	//***********Selection sort ***********
	select_sort(arr2, totalnum1);
	printf("\nSelection sort:\n");
	show(arr2, totalnum1);
	//***********Insertion sort***********
	insert_sort(arr3,totalnum1);
	printf("\nInsert sort:\n");
	show(arr3, totalnum1);
	//***********Merge sort***********
	merge(arr1, arr2, arr4, totalnum1, totalnum1);
	printf("\nMerge sort(merge the arr1 and arr2):\n");
	show(arr4, totalnum4);
	//***********Quick sort***********
	quick_sort(arr5, 0, totalnum2);
	printf("\nQuick sort:\n");
	show(arr5, totalnum2);
	//***********BinaryTree Track***********
	printf("\nBinaryTree Track:\n");
	binarytree(arr6, totalnum2);
	printf("\n\n");
	return 0; 
}

int* load_add(int *arr,char* path) {//以倍增算法來開動態陣列空間
	int totalnum = 0, limit = MAX;

	FILE *fp = fopen(path, "r");
	if (fp == NULL) {
		perror("Error printed by perror");
	}
	arr = (int*)calloc(MAX, sizeof(int));
	
	while (fscanf(fp, "%d", &arr[totalnum]) != EOF) {
		if (totalnum >= limit) {
			limit *= 2;
			int *arr_new = (int*)calloc(limit, sizeof(int));
			for (int i = 0; i < totalnum; i++) {
				arr_new[i] = arr[i];
			}
			free(arr);
			arr = arr_new;
		}
		totalnum++;
	}
	return arr;
}

//***********Bubble sort ***********
void bubble_sort(int*arr, int totalnum) {
	int i = 0, j = 0, temp = 0;
	bool isend = true;
	for (; i < totalnum; i++) {
		isend = true;
		for (j=0; j < totalnum - 1; j++) {
			if (arr[j] > arr[j + 1]) {
				temp = arr[j + 1];
				arr[j + 1] = arr[j];
				arr[j] = temp;
				isend = false;
			}
		}
		if (isend)break;
	}
}
void show(int*arr, int totalnum) {
	for (int i = 0; i < totalnum; i++) {
		printf("%d ", arr[i]);
		if((i+1)%25==0)printf("\n");
	}
	printf("\n");
}

//***********Selection sort***********
void select_sort(int* arr, int totalnum) {
	int index = 0, temp = 0, i = 0, j = 0;
	for (; i < totalnum; i++) {
		temp = arr[i];
		index = i;
		for (j = i; j < totalnum; j++) {
			if (temp > arr[j]) {
				index = j;
				temp = arr[j];
			}
		}
		if (index != i) {
			arr[index] = arr[i];
			arr[i] = temp;
		}
	}
}

//***********Insertion sort***********
void insert_sort(int *arr, int totalnum) {
	int index = 0, i = 1, temp = 0;
	for (; i < totalnum; i++) {
		temp = arr[i];
		index = i;
		while (index > 0 && arr[index - 1] > temp) {
			arr[index] = arr[index-1];
			arr[index - 1] = temp;
			index--;
			if (index == 0)break;
		}
	}
}
//***********Merge sort***********
void merge(int *arr1, int*arr2, int*arrsum, int totalnum1, int totalnum2) {
	int index1 = 0, index2 = 0, sumnum = totalnum1 + totalnum2, index3 = 0;
	while (sumnum > index3) {
		if (index1 >= totalnum1) {
			if (index2 >= totalnum2 )break; 
			arrsum[index3++] = arr2[index2++];
		}
		else if (index2 >= totalnum2 ) {
			if (index1 >= totalnum1 )break;
			arrsum[index3++] = arr1[index1++];
		}
		else {
			if (arr1[index1] < arr2[index2]) {
				arrsum[index3++] = arr1[index1++];
			}
			else if(arr1[index1] > arr2[index2]) {
				arrsum[index3++] = arr2[index2++];
			}
			else {
				arrsum[index3++] = arr1[index1++];
				arrsum[index3++] = arr2[index2++];
			}
		}
	}
}
//***********Quick sort***********
void quick_sort(int* arr, int left, int right) {
	int q;
	if (left < right) {
		q = Partition(arr, left, right);
		quick_sort(arr,left,q-1);
		quick_sort(arr, q + 1, right);
	}
}
int Partition(int* arr, int left, int right){
	int i = 0, j = 0, temp = 0, mid = 0;
	mid = arr[right];//中間值
	i = left - 1;
	j = left;
	for (; j < right; j++) {
		if (mid >= arr[j]) {
			i++;
			if (j != i) {
				temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
	}
	temp = arr[i + 1];
	arr[i + 1] = arr[right];
	arr[right] = temp;
	return i+1;
}
//***********BinaryTree track***********
Node *newnode(int target) {
	Node *node = (Node*)malloc(sizeof(Node));
	node->value = target;
	node->leftsub = NULL;
	node->rightsub = NULL;
	return node;
}
void find(Node* node, int target) {
	int leftnull = 0, rightnull = 0;
	if (node->rightsub == NULL)rightnull = 1;
	if (node->leftsub == NULL)leftnull = 1;
	if (target > node->value) {
		if (rightnull)node->rightsub = newnode(target);
		else find(node->rightsub,target);
	}
	else if (target < node->value) {
		if (leftnull)node->leftsub = newnode(target);
		else find(node->leftsub,target);
	}
	else printf("ERROR:CANNOT ENTER TWO SAME VALUE IN THE ARRAY!\n");
}
void output(Node * node) {
	if (node != NULL) {
		output(node->leftsub);
		printf("%d ",node->value);
		output(node->rightsub);
	}
}
void binarytree(int* arr, int totalnum) {
	Node *root = newnode(arr[0]);
	if (totalnum <= 0)printf("ERROR:THE ARRAY IS NULL!\n");
	else if (root == NULL)printf("ERROE:MUST GIVE THE MEMORY TO ROOT!/ n");
	else {
		for (int index = 1; index < totalnum; index++) {
			find(root, arr[index]);
		}
	}
	output(root);
}

執行結果:

_______________________________________________

我們透過閱讀，拼湊出真實世界的面貌，
並在反覆的探索及思維中，打破由自我無知與偏見所建立的籓籬。