main.cpp

数据结构及C++相关的一些小程序

#include"iostream.h"
#include"node.h"
#include"dblinkedlist.h"
template <class T> 
void DoubleSort( T a[], int n)//此函数是排序的具体实现
{
	DbLinkedList<T> list(a[0]);             //以数组的第一个元素初始化双向链表
	for(int i=1;i<n;i++)
	{
		/*以下是当前操作位置指向头节点时的处理过程*/
		if(list.currentPos==list.head)
		{
			if(a[i]>=list.currentPos->info)
			{
				if(list.tail==list.head)
					list.push_back(a[i]);
				else
				{
				    while(1)
					{
					    list.currentPos=list.currentPos->next;
						if(a[i]<list.currentPos->info)
						//找到比它大的元素，在那个位置插入链表并跳出循环
						{
							list.insertNode(a[i]);
							break;
						}
					}
				}
			}
			else
				list.push_front(a[i]);
		}
		
		/*以下是当前操作位置指向尾节点时的处理过程*/
		else if(list.currentPos==list.tail)
		{
			if(a[i]>=list.currentPos->info)
				list.push_back(a[i]);
			else
			{
				if(list.head==list.tail)
					list.push_front(a[i]);
				else
				{
				    while(1)
					{
					    list.currentPos=list.currentPos->prev;
						if(a[i]>=list.currentPos->info)
						//第一次找到比待插入元素小的节点时，将当前操作指针后移一个节点，
						//然后将待插入的元素在当前操作位置插入链表，跳出循环
						{
							list.currentPos=list.currentPos->next;
							list.insertNode(a[i]);
							break;
						}
					}
				}
			}
		}
		
		/*以下是当前操作位置指向链表中间某个元素时的处理过程*/
		else
		{
			while(1)
			{
				if(a[i]>=list.currentPos->prev->info&&a[i]<=list.currentPos->info)
				//当找到比前一个节点大比后一个节点小的合适位置时，插入链表，跳出循环
				{
					list.insertNode(a[i]);
					break;
				}
				if(a[i]>=list.currentPos->info)list.currentPos=list.currentPos->next;
				//待插入元素相比当前节点内容较大则后移当前操作位置指针
				else list.currentPos=list.currentPos->prev;
				//待插入元素相比当前节点内容较小则前移当前操作位置指针
			}

		}
		
	}
	
	
	cout<<endl<<"排序后双向链表中的元素如下："<<endl;
	list.display();//显示双向链表的内容

    /*以下是将排序好的链表的内容重新赋值给数组，使数组成为排好序的数组*/
	list.currentPos=list.head;
	int j=0;
	while(list.currentPos!=NULL)
	{
		a[j]=list.currentPos->info;
		list.currentPos=list.currentPos->next;
		j++;
	}

	list.destroy();//所有的操作完成后，释放双向链表所占用的内存空间
}
void main()
{
	int i;
	int a[]={0,9,7,8,4,3,6,5,2,1};     //未排序前的数组
	/*显示排序前的数组*/
	cout<<"数组a排序前如下："<<endl;
	for(i=0;i<10;i++)
		cout<<a[i]<<" ";

	DoubleSort(a,10);//调用相关函数，数组的元素一个一个依次找到合适的位置插入链表，
	//从而达到排序的目的

	//以下是输出排序后的数组的实现
	cout<<endl<<"数组a排序后如下："<<endl;
	for(i=0;i<10;i++)
		cout<<a[i]<<" ";
}