qsort_of_link.txt

linux gcc编译通过的链表的快速排序法

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct node * link;
typedef struct node{
	int age;
	char name[20];
	link prev;
	link next;
}Tnode;
typedef struct headnode * linkhead;
typedef struct headnode{
	int node_num;
	link next;
	link end;
}Theadnode;
link NODE(int age, char *name, link prev, link next)							/* 创建节点 */
{
	link t = (link)malloc(sizeof(*t));
	t->age = age;
	strcpy(t->name, name);
	t->prev = prev;
	t->next = next;

	return t;
}
linkhead init_link()												/* 链表初始化 */
{
	linkhead p = (linkhead)malloc(sizeof(Theadnode));
	p->node_num = 0;
	p->next = NULL;
	p->end = NULL;

	return p;
}
void destroy_link(linkhead h)										/* 销毁链表 */
{
	link t, x;
	for(t = h->next; t; t=t->next, free(x))
		x = t;
	free(h);

	return;
}
void insert_node(linkhead h, int age, char *name)					/* 往表尾插入新节点 */
{
	link t, after_t;
	for(t = h->next, after_t = t; after_t; t = after_t, after_t = after_t->next);
	if(t)
	{
		t->next = NODE(age, name, t, t->next);
		h->end = t->next;
	}
	else
	{
		h->next = NODE(age, name, t, t);
		h->end = h->next;
	}

	h->node_num++;

	return;
}
void remove_node(linkhead h, int age, char *name)					/* 删除节点 */
{
	link t, after_t;
	for(t = h->next, after_t = t; after_t; t = after_t, after_t = after_t->next)
		if(after_t->age == age && strcmp(after_t->name, name) == 0)
			break;
	if(after_t)
	{
		if(after_t->next == NULL)
			h->end = after_t->prev;
		if(t !=	after_t)
		{
			t->next = after_t->next;
			if(after_t->next)
				after_t->next->prev = t;
			free(after_t);
		}
		else
		{
			h->next = after_t->next;
			free(after_t);
		}
		h->node_num--;
	}
	else
		printf("sorry! can't find the item!\n");
}
void traverse(linkhead h)											/* 遍历链表 */
{
	link t;
	for(t = h->next; t; t = t->next)
		printf("Name: %s, Age: %d\n", t->name, t->age);

	return;
}
linkhead cat_link(linkhead h1, linkhead h2)							/* 合并链表 */
{
	link t, after_t;
	for(t = h1->next, after_t = t; after_t; t = after_t, after_t = after_t->next);
	if(t)
	{
		t->next = h2->next;
		if(h2->next)
			h2->next->prev = t;
	}
	else
	{
		h1->next = h2->next;
	}
	if(h2->end)
		h1->end = h2->end;
	h1->node_num += h2->node_num;

	/* free(h2); */													/* 根据需要选择释放与否 */

	return h1;
}
void swap_node(linkhead *h, link *a, link *b)									/* 交换节点 */
{
	printf("\nIn swap(%d, %d)\n", (*a)->age, (*b)->age);
	if(*a == *b) return;
	link tmp;
	if((*h)->next == *a)
		(*h)->next = *b;
	else if((*h)->next == *b)
		(*h)->next = *a;
	
	if((*h)->end == *a)
		(*h)->end = *b;
	else if((*h)->end == *b)
		(*h)->end = *a;

	if((*a)->prev != (*b) && (*a)->next != (*b) && (*b)->prev != (*a) && (*b)->next != (*a))
	{
		if((*a)->prev)
			(*a)->prev->next = (*b);
		if((*a)->next)
			(*a)->next->prev = (*b);

		if((*b)->prev)
			(*b)->prev->next = (*a);
		if((*b)->next)
			(*b)->next->prev = (*a);

		tmp = (*a)->prev;
		(*a)->prev = (*b)->prev;
		(*b)->prev = tmp;

		tmp = (*a)->next;
		(*a)->next = (*b)->next;
		(*b)->next = tmp;

		tmp = *a;
		*a = *b;
		*b = tmp;
	}
	else
	{
		if((*a)->next == (*b))
			(*a)->next = (*a);
		else if((*a)->next)
			(*a)->next->prev = (*b);
		if((*b)->next == (*a))
			(*b)->next = (*b);
		else if((*b)->next)
			(*b)->next->prev = (*a);
		if((*a)->prev == (*b))
			(*a)->prev = (*a);
		else if((*a)->prev)
			(*a)->prev->next = (*b);
		if((*b)->prev == (*a))
			(*b)->prev = (*b);
		else if((*b)->prev)
			(*b)->prev->next = (*a);
		
		tmp = (*a)->prev;
		(*a)->prev = (*b)->prev;
		(*b)->prev = tmp;

		tmp = (*a)->next;
		(*a)->next = (*b)->next;
		(*b)->next = tmp;

		tmp = *a;
		*a = *b;
		*b = tmp;
	}
}
void my_qsort_link(linkhead h, link l, link r)									/* 链表快排 */
{
	if(l == NULL || r == NULL) return;
	if(r->next == l || r == l) return;
	link i, j;
	j = l;
	for(i = l->next; i != r; i = i->next)
	{
		if(i->age < l->age)
		{
			j = j->next;
			swap_node(&h, &i, &j);
		}
	}
	if(r->age < l->age)
	{
		j = j->next;
		swap_node(&h, &r, &j);
	}
	if(j == r)
	{
		swap_node(&h, &j, &l);
		r = j;
	}
	else
		swap_node(&h, &j, &l);

	/* traverse(h); */
	my_qsort_link(h, l, j->prev);
	my_qsort_link(h, j->next, r);
}

int main()
{
	linkhead male_std = init_link();
	linkhead female_std = init_link();

	insert_node(male_std, 18, "Mikeal");
	insert_node(male_std, 23, "Tom");
	insert_node(male_std, 21, "Seven");
	insert_node(male_std, 16, "John");
	insert_node(male_std, 10, "David");
	insert_node(male_std, 26, "Smith");
	printf("Male students are:\n");
	traverse(male_std);

	insert_node(female_std, 19, "Joan");
	insert_node(female_std, 29, "Mary");
	insert_node(female_std, 36, "Alice");
	insert_node(female_std, 18, "Kitty");
	insert_node(female_std, 17, "Blanny");
	printf("Female students are:\n");
	traverse(female_std);


	printf("Now we delete the male student \"26 Smith\",then they are:\n");
	remove_node(male_std, 26, "Smith");
	traverse(male_std);

	printf("Now we sort them in age...\n");
	my_qsort_link(male_std, male_std->next, male_std->end);
	my_qsort_link(female_std, female_std->next,female_std->end);
	printf("After sorted!!!!!!\n");
	printf("Male students are:\n");
	traverse(male_std);
	printf("Female students are:\n");
	traverse(female_std);

	printf("Now we cat the female students to the male students.\n");
	male_std = cat_link(male_std, female_std);
	printf("Traverse them:\n");
	traverse(male_std);

	printf("Now we sort them in age...\n");
	my_qsort_link(male_std, male_std->next, male_std->end);
	printf("Traverse them:\n");
	traverse(male_std);

	printf("Now we add the male student \"26 Smith\",then they are:\n");
	insert_node(male_std, 26, "Smith");
	traverse(male_std);
	printf("the 1st student in link is Age %d, Name %s\n",  
									male_std->next->age, male_std->next->name);
	printf("the last student in link is Age %d, Name %s\n",
									male_std->end->age, male_std->end->name);
	printf("there are %d students in the link.\n", male_std->node_num);

	printf("现在生成一张新的全部学生的链表名叫all_std.\n");
	linkhead all_std = init_link();
	cat_link(all_std, male_std);
	printf("Traverse them in link all_std, there is %d students:\n", all_std->node_num);
	traverse(all_std);

	printf("Now we sort all_std in age...\n");
	my_qsort_link(all_std, all_std->next, all_std->end);
	printf("Traverse them:\n");
	traverse(all_std);
	printf("Now we sort male_std(now it's NULL) in age...\n");
	my_qsort_link(male_std, male_std->next, male_std->end);
	printf("Traverse them:\n");
	traverse(male_std);

	printf("Traverse the female_std:\n");
	traverse(female_std);

	destroy_link(all_std);
	destroy_link(male_std);
	destroy_link(female_std);

	printf("Traverse the female_std after destroyed:\n");
	traverse(female_std);

	return 0;
}