dlistex.h

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

#ifndef DLISTEX_H
#define DLISTEX_H
#include "DList.h"

template <class LDT>
class DListEx : public DList<LDT>
{
private:
/*---插入排序辅助函数---------*/
    inline LNode<LDT> * InPass(LNode<LDT> *pi)
	{
		LNode<LDT> *p=Head,*rp,*q;
		rp=pi->Next;
		while(rp->Data>p->Next->Data) p=p->Next;
		if(p->Next==rp) q=pi->Next;
		else q=pi;
		pi->Next=rp->Next;
		rp->Next=p->Next;		
		p->Next=rp;
		return q;
	}
/*-----堆排序筛子函数-----------------------*/
    void Sift(LNode<LDT> ** adlist,int k,int m)
	{
        int i,j;
        bool unfinished=true;
        LNode<LDT> *rp;
        i=k; j=2*i+1;
        rp=adlist[k];
        while(j<=m&&unfinished)
		{
	        if((j<m)&&(adlist[j]->Data<adlist[j+1]->Data)) j++;
	        if(adlist[j]->Data<rp->Data) unfinished=false;
	        else { adlist[i]=adlist[j]; i=j; j=2*i+1; }
		}
        adlist[i]=rp;
	}
/*--------快速排序辅助函数------------*/
    int QkPass(LNode<LDT> **adlist,int s,int t)
	{
        int i,j;
        LNode<LDT> *rp;
        i=s; j=t;
        rp=adlist[s];
        while(i<j)
		{
	        while((i<j)&&!(rp->Data>adlist[j]->Data)) j--; 
	        adlist[i]=adlist[j];
	        while((i<j)&&!(rp->Data<adlist[i]->Data)) i++;
	        adlist[j]=adlist[i];
		}
        adlist[i]=rp;
        return i;
	}

    void QkSort(LNode<LDT> **adlist,int s,int t)
	{
        if(s<t)
		{
	        int p;
	        p=QkPass(adlist,s,t);
	        QkSort(adlist,s,p-1);
	        QkSort(adlist,p+1,t);
		}
	}
/*----------获取地址表-------------*/
	inline LNode<LDT> ** GetAddressList(int s,int t)
	{
		int i;
		LNode<LDT> **adlist=new LNode<LDT> *[t-s+1];
		LNode<LDT> *p=Head->Next;
		for(i=0;i<s;i++) p=p->Next;
		for(i=0;i<=t-s;i++)
		{
			adlist[i]=p;
			p=p->Next;
		}
		return adlist;
	}
public:
	DListEx():DList<LDT>()
	{}
/*-----------链式交换----------------*/
	void Swap(int index1,int index2)
	{
		if(index1==index2) return;
		LNode<LDT> *p1,*p2,*pre1,*pre2;
		int pos,i;
		if(index1>index2)
		{ pos=index1; index1=index2; index2=pos; }
		for(i=0,pre1=Head;i<index1;i++) pre1=pre1->Next;
		p1=pre1->Next; pre1->Next=p1->Next; //抽出p1
		for(i=index1,pre2=pre1;i<index2-1;i++) pre2=pre2->Next;
		p2=pre2->Next; 
		p1->Next=p2->Next; pre2->Next=p1;  //插入p1,抽出p2
		p2->Next=pre1->Next; pre1->Next=p2; //插入p2
	}
/*-------------冒泡法------------------*/
	void BubbleSort()
	{
		LNode<LDT> *p1,*p2,*rp;
		for(int i=0;i<Count-1;i++)
		{
			p1=Head;
			for(int j=0;j<Count-i-1;j++)
			{
                p2=p1->Next;
				if(p2->Data>p2->Next->Data)
				{
					rp=p2->Next;
					p2->Next=p2->Next->Next;
					rp->Next=p2;
					p1->Next=rp;
				}
				p1=p1->Next;
			}
		}
	}
/*------------------插入法------------------------*/
    void InSort()
	{
		LNode<LDT> *pi=Head->Next;
		while(pi->Next)
			pi=InPass(pi);
	}
/*--------堆排序-----------*/
	void HeapSort()
	{
		int i;
		LNode<LDT> *rp;
		LNode<LDT> **adlist=GetAddressList(0,Count-1);
        for(i=Count/2-1;i>=0;i--)
	        Sift(adlist,i,Count-1);
        for(i=Count-1;i>=1;i--)
		{
	        rp=adlist[0];
	        adlist[0]=adlist[i];
	        adlist[i]=rp;
	        Sift(adlist,0,i-1);
		}
		rp=Head;
		for(i=0;i<Count;i++)
		{
			rp->Next=adlist[i];
			rp=rp->Next;
		}
		rp->Next=0;
		delete []adlist;
	}
/*-------快速排序----------*/
	void QkSort()
	{
		LNode<LDT> **adlist=GetAddressList(0,Count-1);
		QkSort(adlist,0,Count-1);
		LNode<LDT> *p=Head;
        for(int i=0;i<Count;i++)
		{
			p->Next=adlist[i];
			p=p->Next;
		}
		p->Next=0;
		delete []adlist;
	}
/*-----查找-----------*/
	LNode<LDT> * Search(int s,int t,LDT target)
	{
		int i;
		LNode<LDT> *p=Head->Next;
		for(i=0;i<s;i++) p=p->Next;
		for(i=s;i<=t;i++)
		{
			if(p->Data==target) return p;
			p=p->Next;
		}
		return 0;
	}

	LNode<LDT> * BinSearch(int s,int t,LDT target)
	{
		LNode<LDT> **adlist=GetAddressList(s,t);
        int low=0,hig=t-s,mid;
		bool unfinished=true;
		while(low<=hig&&unfinished)
		{
			mid=(low+hig)/2;
			if(target>adlist[mid]->Data) low=mid+1;
			else if(target<adlist[mid]->Data) hig=mid-1;
			else { delete []adlist; return adlist[mid]; }
		}
		delete []adlist;
		return 0;
	}
};
#endif