Tetsuhiko的筆記

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
 
/* 用Linked List來儲存行列式的值 */
struct node{
	float data;
	struct node *next;
};
typedef struct node Node;
 
/* 回傳第{index+1}個節點的值 */
float indexOfNode(Node *first,int index){
	Node *node=first;
	int i = 0;
	while(node != NULL){
		if(i++ == index){
			return node->data;
		}else{
			node=node->next; 
		}
	}
	return 0; 
}
 
/* 釋放Linked List記憶體空間 */
void freeList(Node *first){
	Node *current,*tmp;
	current=first;
	while(current!=NULL){
		tmp=current;
		current=current->next;
		free(tmp);
	}
}
 
/********* 計算行列式結果的函數 ***********/
/* first: 儲存行列式的串列（一維方式儲存）	*/
/* size: 行列式大小			*/
/****************************************/
/* 一維方式存行列式的方式如下：		*/
/* a[0][0] = first[0]			*/
/* a[0][1] = first[1]			*/
/* ....					*/
/* a[0][n] = first[n]			*/
/* a[1][0] = first[n+1]			*/
/* a[1][1] = first[n+2]			*/
/* ....					*/
/* a[1][n] = first[n*2+1]		*/
/* ....					*/
/* a[n][n] = first[n*n+n*2]		*/
/****************************************/
double determinant_calc(Node *first, int size){
	if(size == 2){		//當行列式大小為2*2時，從行列式串列取值並直接做計算
		return indexOfNode(first, 0) * indexOfNode(first, 3) - indexOfNode(first, 1) * indexOfNode(first, 2);
	}
 
	/* 這裡我打算沿著行列式的第一行來做降階 */
	int i, j, k;
	bool isFirst = false;
	double result = 0;
	Node *first0,*current0,*previous0;		//這裡降階後的行列式串列也是用一維方式儲存
	for(i = 0; i < size; i++){		//i為列出行列式的所有橫列（第1列～第{size}列）
		isFirst = true; 
		for(k = 0; k < size; k++){		//k為列出除第i+1列以外的其他橫列
			if(k == i)		//忽略第i+1列
				continue;
			for(j = 1; j < size; j++){		//j為列出除第1行以外的其他縱行（第2行～第{size}行）
				current0 = (Node *) malloc(sizeof(Node));		//建立新的節點
				current0->data = indexOfNode(first, k * size + j);		//將降階後的行列式值存進新的節點
				if(isFirst){
					first0 = current0;		//如果是第一個就把指標first0指向目前剛建立的新節點
					isFirst = false;
				}else{
					previous0->next=current0;		//若不是第一個就把上一個節點的next設為目前的節點
				}
				current0->next = NULL;		//先把目前節點的next設為NULL
				previous0 = current0;		//把上一個節點設為目前的節點
			}
		}
		result += (1 - (i % 2) * 2) * indexOfNode(first, i * size) * determinant_calc(first0, size - 1);		//每個降階後的行列式乘以第一行的所有值加進結果裡頭（注意正負號：第一行第奇數列的為正，也就是乘以1；第一行第偶數列的為負，也就是乘以-1）
		freeList(first0);
	}
	return result;
}
 
int main(int argc, char *argv[]) {
	int i, j, m, size;
	char *str[4] = {"st","nd","rd","th"}, s[10];
	
	Node *first,*current,*previous;
	
	printf("========== Determinant calculator ==========\n");
	printf("Input the size of the determinant:");
	scanf("%d", &size);		//要求使用者輸入行列式大小
	
	if(size < 2)
		printf("[[The size of the determinant must be greater than 1.]]\n");		//行列式大小至少為2*2
	else {
		for(i = 0; i < size; i++){
			m = i + 1;
			sprintf(s, "%d", m);
			printf("Input the %s row of the %d*%d determinant: ", strcat(s, *(str + ((m>3)?3:m-1))) , size, size);
			for(j = 0; j < size; j++){
				current=(Node *) malloc(sizeof(Node));
				scanf("%f", &(current->data));		//要求使用者輸入某列的所有值
				if(i == 0 && j == 0){
					first=current;
				}else{
					previous->next=current;
				}
				current->next=NULL;
				previous=current;
			}
		}
		printf("\nResult = %f\n", determinant_calc(first, size));		//顯示行列式計算結果
	}
	system("PAUSE");
	return 0;
}