sortable_list.cpp

包括图、二叉树、链表

#include"Sortable_list.h"

void Sortable_list::merge_sort()
{
	recursive_merge_sort(head);
}

void Sortable_list::recursive_merge_sort(Node *&sub_list)
{
	if(sub_list!=NULL&&sub_list->next!=NULL)
	{
		Node *second_half=divide_from(sub_list);
		print(sub_list);
		print(second_half);
		recursive_merge_sort(sub_list);
		recursive_merge_sort(second_half);
		sub_list=merge(sub_list,second_half);
		print(sub_list);
	}
}

Node *Sortable_list::divide_from(Node *sub_list)
{
	Node *position,*midpoint,*second_half;
	if((midpoint=sub_list)==NULL) return NULL;
	position=midpoint->next;
	while(position!=NULL)
	{
		position=position->next;
		if(position!=NULL)
		{
			midpoint=midpoint->next;
			position=position->next;
		}
	}
	second_half=midpoint->next;
	midpoint->next=NULL;
	return second_half;
}

Node *Sortable_list::merge(Node *first,Node *second)
{
	Node *last_sorted;
	Node combined;
	last_sorted=&combined;
	while(first!=NULL&&second!=NULL)
	{
		if(first->entry<=second->entry)
		{
			last_sorted->next=first;
			last_sorted=first;
			first=first->next;
		}
		else
		{
			last_sorted->next=second;
			last_sorted=second;
			second=second->next;
		}
	}
	if(first==NULL) last_sorted->next=second;
	else last_sorted->next=first;
	return combined.next;
}

void Sortable_list::creat_list()
{
	cout<<"input the sort numbers,end of '0'."<<endl;
	int num;
	cin>>num;

	Node *node=new Node(num);
	head=node;
	cin>>num;
	while(num!=0)				//结束符
	{
		node->next=new Node(num);
		node=node->next;
		cin>>num;
	}
}

void Sortable_list::print(Node *head)
{
	Node *pt=head;
	while(pt!=NULL)
	{
		cout<<pt->entry<<" ";
		pt=pt->next;
	}
	cout<<endl;
}


void Sortable_list::print()
{
	Node *pt=head;
	while(pt!=NULL)
	{
		cout<<pt->entry<<" ";
		pt=pt->next;
	}
	cout<<endl;
}