pbing.h

使用指针实现的自然归并排序。是学习指针和数据结构的很好的资料

#include <stdlib.h>
#include <iostream.h>

struct spoint
{
	int data;
	spoint *next;
};

struct sArray
{
	spoint *data;
	sArray *next;
};

spoint *priArray;
sArray *cArray;

void vInput()
{
	int num;
	spoint *temp,*s;

	cout<<"Input your num of data that you want to sort:";
	cin>>num;
	for (int i=0; i<num ;++i)
	{
		temp=(spoint*)malloc(sizeof(struct spoint));
		if (!temp)
		{
			cout<<"\n Out OF Memory!";
			return;
		}
		cout<<"No."<<i+1<<" data:";
		cin>>temp->data;
		temp->next = NULL;
		if (i == 0)
		{
			priArray = temp;
			s = priArray;
		}
		else
		{
			s->next = temp;
			s = temp; 
		}
	}

}

void iFind()//查找已有自然序的子数组段
{
	spoint *s,*ss;
	sArray *temp,*t;

	s = priArray;
	temp=(sArray*)malloc(sizeof(struct sArray));
	if (!temp)
	{
		cout<<"\n Out OF Memory!";
		return;
	}
	temp->next = NULL;
	temp->data = s;
	cArray = temp;
	t = temp;

	while (s->next != NULL)
	{
		ss = NULL;
		if (s->data >= s->next->data)
		{
			ss = s->next;

			s->next = NULL;

			temp=(sArray*)malloc(sizeof(struct sArray));
			if (!temp)
			{
				cout<<"\n Out OF Memory!";
				return;
			}
			temp->next = NULL;
			temp->data = ss;
			t->next = temp;
			t = temp;
		}
		if (ss == NULL)
			s = s->next;
		else
			s = ss;
	}

}

void vPrintS()
{
	sArray *t;
	t = cArray;
	while (t != NULL)
	{
		cout<<t->data->data<<" ";
		t = t->next;
	}
}

void vPrintSP()
{
	sArray *t;
	spoint *s;
	t = cArray;
	while (t != NULL)
	{
		cout<<t->data->data<<" ";
		s = t->data->next;
		while (s != NULL)
		{
			cout<<s->data<<" ";
			s = s->next;
		}
		cout<<"\n";
		t = t->next;
	}
}

void vPrintP()
{
	spoint *t;
	t = priArray;
	while (t != NULL)
	{
		cout<<t->data<<" ";
		t = t->next;
	}
}

void vSort()
{
	sArray *sa;
	sa = cArray;
	spoint *p,*q,*pp,*tmp;

	while (sa->next != NULL)
	{
		if (sa->next != NULL)
		{
			p = sa->data;
			q = sa->next->data;
			pp = p;
			while ((p != NULL) && (q != NULL))
			{
				if (p->data > q->data)
				{
					tmp = q;
					q = q->next;
					if (pp == p)
					{
						sa->data = tmp;
						tmp->next = p;
						p = tmp;
						pp = p;
					}
					else
					{
						pp->next = tmp;				
						tmp->next = p;
						pp = pp->next;
					}
				}
				else
				{
					pp = p;
					p = p->next;
				}
			}
			if (p == NULL)
				pp->next = q;
			sa->next = sa->next->next;
		}
		else
			sa = cArray;

		if ((sa != NULL)&&(sa != cArray))
			sa = sa->next;
	}
	vPrintSP();
	free(priArray);
	free(cArray);
}