darrayex.h

类模板,助于参考及编写代码,代码以数据结构值的排序方式及链表操作为主.

#ifndef DARRAYEX_H
#define DARRAYEX_H
#include "DArray.h"
template <class ADT>
class DArrayEx:public DArray<ADT>
{
private:
/*快速排序辅助函数*/
    int QkPass(int s,int t)
	{
        int i,j;
        ADT rp;
        i=s; j=t;
        rp=Head[s];
        while(i<j)
		{
	        while((i<j)&&!(rp>Head[j])) j--; 
	        Head[i]=Head[j];
	        while((i<j)&&!(rp<Head[i])) i++;
	        Head[j]=Head[i];
		}
        Head[i]=rp;
        return i;
	}

    void QkSort(int s,int t)
	{
        if(s<t)
		{
	        int p;
	        p=QkPass(s,t);
	        QkSort(s,p-1);
	        QkSort(p+1,t);
		}
	}
/*-----堆排序筛子函数-----------------------*/
    void Sift(int k,int m)
	{
        int i,j;
        bool unfinished=true;
        ADT rp;
        i=k; j=2*i+1;
        rp=Head[k];
        while(j<=m&&unfinished)
		{
	        if((j<m)&&(Head[j]<Head[j+1])) j++;
	        if(Head[j]<rp) unfinished=false;
	        else { Head[i]=Head[j]; i=j; j=2*i+1; }
		}
        Head[i]=rp;
	}
/*-----希尔二分排序辅助函数--------*/
    void ShellBins(int i,int dh)
	{
        int j,s,t,m;
        ADT rp=Head[i];
        s=i%dh; t=i-dh;
        while(s<=t)
		{
	        m=(s+t)/2;
	        if(Head[m]<rp) s=m+1;
	        else t=m-1;
		}
        for(j=i-dh;j>=s;j-=dh)
	        Head[j+dh]=Head[j];
        Head[j+dh]=rp;
	}

    void ShellPass(int dh)
	{
        int i;
        for(i=dh;i<Count;i++)
	        ShellBins(i,dh);
	}
/*----------------------------------------------------------*/
public:
	DArrayEx(int size=10):DArray<ADT>(size)
	{ }
/*快速排序*/

    void QkSort()
	{ QkSort(0,Count-1); }

	void HeapSort()
	{
		int i;
		ADT rp;
        for(i=Count/2-1;i>=0;i--)
	        Sift(i,Count-1);
        for(i=Count-1;i>=1;i--)
		{
	        rp=Head[0];
	        Head[0]=Head[i];
	        Head[i]=rp;
	        Sift(0,i-1);
		}
	}

	
    void ShellSort(int *dh,int t)
	{
        int i;
        for(i=0;i<t;i++)
	        ShellPass(dh[i]);
	}

	void ShellSort()
	{
		int dh=Count/2;
		while(dh)
		{
			ShellPass(dh);
			dh/=2;
		}
	}
/*查找*/
	int Search(int s,int t,ADT target)
    {
		for(int i=s;i<=t;i++)
			if(target==Head[i]) return i;
		return -1;
	}

	int BinSearch(int s,int t,ADT target)
	{
		int low=s,hig=t,mid;
		bool unfinished=true;
		while(low<=hig&&unfinished)
		{
			mid=(low+hig)/2;
			if(target>Head[mid]) low=mid+1;
			else if(target<Head[mid]) hig=mid-1;
			else unfinished=false;
		}
		if(unfinished) return -1;
		else return mid;
	}

	void BubbleSort()
	{
		ADT rp;
		for(int i=0;i<Count-1;i++)
			for(int j=0;j<Count-i-1;j++)
			{
				if(Head[j]>Head[j+1])
				{
					rp=Head[j];
					Head[j]=Head[j+1];
					Head[j+1]=rp;
				}
			}
	}

};

#endif