最接近的数(双向链表)

the_closet_value.c

/**
 * @author monkindey
 * @date 2014.11.24
 * @idea {
 *       1. 给A数组排序(快排)
 *       2. 从小到大顺序构造双向链表
 * }
 */

#include <stdio.h>
#include <malloc.h>
#define LIST_SIZE sizeof(struct DbLinkList) 

struct DbLinkList{
	struct DbLinkList *prev;
	struct DbLinkList *next;
	int data;
};

int main() {
	void quick_sort(int *arr, int low, int high);
	void log4Array(int *arr, int length);
	struct DbLinkList * buildListByArray(int *arr, int length);
	void traverseList(struct DbLinkList *list);
	void calculateMin(int data, struct DbLinkList *head, int *min, int idx);

	struct DbLinkList *list;
	int original[6] = {2,6,5,10,4,7};
	int sample[6] = {2,6,5,10,4,7};
	int min[6], i;

	quick_sort(sample, 0, 5);
	list = buildListByArray(sample, 6);

	for(i = 5; i >= 1; i--) {
		calculateMin(original[i], list, min, i);
	}

	min[0] = 0;
	log4Array(min, 6);
	return 0;
}

void calculateMin(int data, struct DbLinkList *head, int *min, int idx) {
	struct DbLinkList *p = head;
	int prevData, nextData;
	while(p->next != NULL) {
		if(p->data == data) {
			break;
		}
		p = p->next;
	}
	prevData = p->prev->data;
	if(p->next != NULL){
		nextData = p->next->data;
		min[idx] = (data - prevData) > (nextData - data) ? (nextData - data) : (data - prevData);
		p->next->prev = p->prev;
		p->prev->next = p->next;
	}else {
		min[idx] = data - prevData;
		p->prev = NULL;	
	}
	free(p);
}

// 打印出数组
void log4Array(int *arr, int length) {
	int i;
	for(i = 0; i < length; i++) {
		printf("%d\n", *(arr + i));
	}
}

void traverseList(struct DbLinkList *list) {
	struct DbLinkList *p;
	p = list;
	while(p->next != NULL) {
		printf("%d\n", p->data);
		p = p->next;
	}
	printf("%d\n", p->data);
	while(p != NULL) {
		printf("%d\n", p->data);
		p = p->prev;
	}
}

struct DbLinkList * buildListByArray(int *arr, int length) {
	int i;
	struct DbLinkList *head, *nodePre, *nodeNext;
	nodeNext = nodePre = (struct DbLinkList *)malloc(LIST_SIZE);
	nodeNext->data = *(arr + 0);
	head = nodeNext;
	head->prev = NULL;
	for(i = 1; i < length; i++){
		nodeNext = (struct DbLinkList *)malloc(LIST_SIZE);
		nodeNext->data = *(arr + i);
		nodePre->next = nodeNext;
		nodeNext->prev = nodePre;
		nodePre = nodeNext;
	}
	nodePre->next = NULL;
	return head;
}

// 用快排实现排序
void quick_sort(int *arr, int low, int high){
	int partition(int *arr, int low, int high);
	int pivot;
	if(low < high) {
		pivot = partition(arr, low, high);
		quick_sort(arr, low, pivot - 1);
		quick_sort(arr, pivot + 1, high);
	}
}
/**
 * 将数组一分为二并算出枢轴
 * 找到关键字，想尽方法把它放到一个位置，使得左边的数比它小，
 * 右边的数比它大。
 * @param  arr  
 * @param  low  
 * @param  high 
 */
int partition(int *arr, int low, int high) {
	void swap(int *arr, int low, int high);
	int pivot;
	pivot = *(arr + low);
	while(low < high) {
		while(low < high && pivot < *(arr + high)){
			high--;
		}
		swap(arr, low, high);
		while(low < high && *(arr + low) < pivot){
			low++;
		}
		swap(arr, low, high);
	}
	return low;
}

// 交换数据
void swap(int *arr, int low, int high) {
	int temp;
	temp = *(arr + low);
	*(arr + low) = *(arr + high);
	*(arr + high) = temp;
}