双方向チェーンテーブルの選択ソートアルゴリズム


本文の転載http://blog.csdn.net/zhipi/article/details/4425533
先日、双方向チェーンテーブルをキーワードドメインでソートする問題がありました.
      ネットで探してみると、いずれもアルゴリズムが1つしかなく、しかも頭のないノードの双方向チェーンテーブルのソートで、ポインタの交換に対して、8つの状況に分かれていて、うんざりしています.そこで自分で考えて、先頭ノードの双方向チェーンテーブルの選択ソートアルゴリズムを書いて、ポインタの交換を4つの状況に濃縮して、しかも選択ソート関数の中の構造が巧みだと思って、そこで貼って人と分かち合います!
#define OVERFLOW 0
#define OK       1
#define TRUE     1
#define ERROR    0

#include "stdlib.h"
#include 
using namespace std;

typedef int Status;
typedef struct{        //     
	int no;     //    ——  
	char name[13]; //  
}ElemType;
typedef struct DuLNode{  //      
	ElemType data;      //   
	struct DuLNode * prior;  //    
	struct DuLNode * next;   //    
}DuLNode, * DuLinkList;

Status Create(DuLinkList &H)  //      
{
	H=(DuLNode *)malloc(sizeof(DuLNode));
	if(!H)
		return OVERFLOW;
	H->prior=NULL;
	H->next=NULL;
	return OK;
}

void Insert(DuLinkList &H,int n=1) //             1 (  ) n (    )  
{
	DuLNode *t;
	if(H->next==NULL)    //     
		t=H;
	else
	{
		t=H->next;
		while(t->next!=NULL)
		t=t->next;
	}
	cout<>p->data.no>>p->data.name;
		t->next=p; 
		p->prior=t;
		p->next=NULL;
		t=t->next;
	}
}

void Output(DuLinkList H)  //      
{
	DuLNode *p;
	p=H->next;
	cout<data.no<data.name<next;
	}
}

void swap(DuLinkList &H,DuLNode *p,DuLNode *t)  //p,t    ,p    ,t    
{
	DuLNode *temp;
	if(t->next==NULL) //t        
	{
		if(p->next==t) //p,t      
		{
			//           
			t->next=p;
			t->prior=p->prior;
			p->next=NULL;
			p->prior->next=t;
			p->prior=t;
		}
		else
		{
			//            
			t->next=p->next;
			t->prior->next=p;
			temp=t->prior;
			t->prior=p->prior;
			p->next->prior=t;
			p->next=NULL;
			p->prior->next=t;
			p->prior=temp;
		}
	}
	else
	{
		if(p->next==t) //p,t      
		{
			//       
			t->next->prior=p;
			temp=t->next;
			t->next=p;
			t->prior=p->prior;
			p->next=temp;
			p->prior->next=t;
			p->prior=t;
		}
		else
		{
			//        
			t->next->prior=p;
			temp=t->next;
			t->next=p->next;
			p->next->prior=t;
			p->next=temp;
			t->prior->next=p;
			temp=t->prior;
			t->prior=p->prior;
			p->prior->next=t;
			p->prior=temp;
		}
	}
}

void Sort(DuLinkList &H)  //      
{
	DuLNode *i,*j,*k;
	if(!H->next)  //         
	return;
	for(i=H->next;i->next!=NULL;i=k->next)  //i=k->next   ,k                i  (  )
	{
		for(j=i->next,k=i;j!=NULL;j=j->next)
			if(k->data.no>j->data.no)
				k=j;
		if(k!=i)
			swap(H,i,k);
	}
}

void main()
{
	DuLinkList H;
	Create(H);
	Insert(H,4);
	Output(H);
	Sort(H);
	Output(H);
}