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