單向鏈結排序 - 直接修改值.c

#include <stdio.h>
#include <stdlib.h>

// 宣告節點結構
typedef struct nodestruct{
    int data;
    struct nodestruct* next;
} node;

// 宣告相關函式
node* create_node(int);
void insert_node(node*, node*);
void remove_node(node*);
void print_lists(node*);
void free_lists(node*);
int node_value( node*, int);
node* node_link( node*, int);
void insertion_sort(node*, int, int);
/*========================================================================*/
#define ArrayLen 10				//陣列長度
int main(void){
	int array[ArrayLen] = { 8,5,4,6,7,1,3,2,10,9 };
	node* n[ArrayLen];			//宣告節點數量
	int i;
	for(i=0;i<ArrayLen;i++){	//陣列導入指標結構單向鏈結(設初始值)
		n[i] = create_node( array[i] );
		if(i>=1)
	    	insert_node(n[i-1],n[i]);
	}

	printf("Sequence Before \n");
    print_lists(n[0]);			//印出整串節點

	insertion_sort( n[0], 0, ArrayLen-1 );

	printf("Sequence After \n");
    print_lists(n[0]);			//印出整串節點
    free_lists(n[0]);			//歸還記憶體
    system("pause");
}

void insertion_sort(node* lists, int first, int last){
	int i, j, temp;
	for ( i=first+1 ; i<=last; i++){
		temp = node_value(lists,i); 								//與已排序的數逐一比較，大於temp時，該數向後移
		for(j=i-1; j>=first && node_value(lists,j)>temp; j--) 		//当first=0，j循环到-1时，由于[[短路求值]](http://zh.wikipedia.org/wiki/%E7%9F%AD%E8%B7%AF%E6%B1%82%E5%80%BC)，不会运算array[-1]
			node_link(lists,j+1)->data = node_value(lists,j);		//大數往右邊一格，如仍然為大於則繼續丟，往右邊丟X格
		node_link(lists,j+1)->data = temp; 							//插入到正確位置
	}
}
/*========================================================================*/
node* create_node(int data){		    // 動態配置記憶體
    node* n = (node*)malloc(sizeof(node));
    n->data = data;
    n->next = NULL;
    return n;
}

void insert_node(node* n1, node* n2){	// 將N2插在N1後(N2連接將設成原本N1連結)
    n2->next = n1->next;
    n1->next = n2;
}

void remove_node(node* n1){				// 移除節點連結(沒有刪除節點)
    n1->next = n1->next->next;
}

int node_value( node* lists, int i){	// 傳入第一點的地址，回傳指定節點的值
	int j;
	for(j=0;j<i;j++){
		lists=lists->next;
	}
	return lists->data;
}

node* node_link( node* lists, int i){	// 傳入第一點的地址，回傳指定節點地址
	int j;
	for(j=0;j<i;j++)
		lists=lists->next;
	return lists;
}

void print_lists(node* lists){			// 依序印出節點內容
    node* n = lists;
    printf("  Node Lists = ");
    while (n != NULL){
        printf("%d ", n->data);
        n = n->next;
    }
    printf("\n");
}

void free_lists(node* lists){			// 遞迴刪除串列所有節點
    if (lists->next != NULL)
        free_lists(lists->next);
    free(lists);
}
/*========================================================================*/