首页 > 代码库 > 多关键字排序
多关键字排序
很欢迎来看我的博客，我还有很多知识没有学习，这是我的考核作业！以此记录我的学习历程！大家参考就好！如有错误，敬请指出！在此，先谢谢一番！
多关键字排序就是基数排序，我是用单链表实现多关键字的排序的，但最主要的方法仍是“分配”，“收集”。单链表只是在分配与收集过程中起暂时的存储作用。不仅可以用链表，还可以用栈、队列……（都是线性的！！！（^_^））
这是结点类模板的定义：
#ifndef NODE_H
#define NODE_H
#define NULL 0
template<class ElemType>
struct Node
{
ElemType date;
Node<ElemType> *next;
Node();
Node(ElemType item,Node<ElemType> *link=NULL);
};
template<class ElemType>
Node<ElemType>::Node()
{
next=NULL;
}
template<class ElemType>
Node<ElemType>::Node(ElemType item,Node<ElemType> *link)
{
date=item;
next=link;
}
#endif // NODE_H
这是链表的代码：
#ifndef LINKLIST_H
#define LINKLIST_H
#include"Node.h"
#include<iostream>
using namespace std;
enum StatusCode{SUCCESS};
template<class ElemType>
class LinkList
{
public:
LinkList();
//这里没有定义析构函数，系统自己定义
int length() const;
bool Empty() const;
StatusCode Delete(int position,ElemType &e);
StatusCode Insert(int position, const ElemType &e);
void Traverse(void(*visit)(ElemType &));
protected:
Node<ElemType> *head;
mutable int curposition;
mutable Node<ElemType> *curPtr;
int count;
Node<ElemType>*GetElemPtr(int position) const;
void Init();
private:
};
//链表的初始化
template<class ElemType>
LinkList<ElemType>::LinkList()
{
Init();
}
template<class ElemType>
void LinkList<ElemType>::Init()
{
head=new Node<ElemType>;
curPtr=head;
curposition=0;
count=0;
}
template<class ElemType>
int LinkList<ElemType>::length() const
{
return count;
}
template<class ElemType>
bool LinkList<ElemType>::Empty() const
{
return count==0;
}
template<class ElemType>
Node<ElemType> *LinkList<ElemType>::GetElemPtr(int position) const
{
if(curposition>position)
{
curposition=0;
curPtr=head;
}
//即当curposition等于position的时候，返回
for(;curposition<position;curposition++)
{
curPtr=curPtr->next;
}
return curPtr;
}
template<class ElemType>
StatusCode LinkList<ElemType>::Delete(int position,ElemType &e)
{
Node<ElemType> *tmpPtr;
tmpPtr=GetElemPtr(position-1);
Node<ElemType> *nextPtr=tmpPtr->next;
tmpPtr->next=nextPtr->next;
e=nextPtr->date;
if(position==length())
{
curposition=0;
curPtr=head;
}else
{
curposition=position;
curPtr=tmpPtr->next;
}
count--;
delete nextPtr;
return SUCCESS;
}
template<class ElemType>
StatusCode LinkList<ElemType>::Insert(int position,const ElemType &e)
{
Node<ElemType> *tmpPtr;
tmpPtr=GetElemPtr(position-1);
Node<ElemType> *newPtr;
//即newPtr指向tmpPtr的下一个结点
newPtr=new Node<ElemType>(e,tmpPtr->next);
tmpPtr->next=newPtr;
curposition=position;
curPtr=newPtr;
count++;
return SUCCESS;
}
template<class ElemType>
void LinkList<ElemType>::Traverse(void(* visit)(ElemType&))
{
for(Node<ElemType> *tmpPtr=head->next;tmpPtr!=NULL;tmpPtr=tmpPtr->next)
{
(*visit)(tmpPtr->date);
}
}
template<class ElemType>
void print(ElemType e)
{
cout<<e<<endl;
}
#endif // LINKLIST_H
多关键字排序代码如下：
#include <iostream>
#include<math.h>
#include"LinkList.h"
using namespace std;
//分配
template<class ElemType>
void Distribute(ElemType elem[],int n,int r,int d,int i,LinkList<ElemType>list[])
{
for(int power=(int)pow((double)r,i-1),j=0;j<n;j++)
{
int index=(elem[j]/power)%r;
list[index].Insert(list[index].length()+1,elem[j]);
}
}
//收集
template<class ElemType>
void Colect(ElemType elem[],int n,int r,int d,int i,LinkList<ElemType>list[])
{
for(int k=0,j=0;j<r;j++)
{
ElemType tmpElem;
while(!list[j].Empty())
{
list[j].Delete(1,tmpElem);
elem[k++]=tmpElem;
}
}
}
template<class ElemType>
void RadixSort(ElemType elem[],int n,int r,int d)
{
LinkList<ElemType> *list;
list=new LinkList<ElemType>[r];
void (*visit)(int&);
visit=print;
for(int i=1;i<=d;i++)
{
Distribute(elem,n,r,d,i,list);
Colect(elem,n,r,d,i,list);
}
delete []list;
}
int main()
{
int a[]={98,67,42,21,18,16,54,32,64,56};
RadixSort(a,10,10,2);
cout << "Hello world!" << endl;
for(int i=0;i<10;i++)
{
if(i==9)
{
cout<<a[i]<<endl;
}
else
{
cout<<a[i]<<",";
}
}
return 0;
}
感悟：
其实我做出上面这个较为成功的代码，是经历了很多的艰辛的（累啊），但是当一个又一个问题被一一解决的成就感（快感，哈哈，又可以去吹了），这是那点艰辛无法比拟的！
所以在遇到困难与挫折的时候，
千万千万千万
要坚持
啊啊啊！！！
最后，在这里开始我的总结！
关于多关键字排序我犯了一个很小很小的错误（但是这个小东西让我找了好久好久，卧槽！），所以，一定要重视小细节！！！
言归正传，说一下问题：
1、关于sigsegv的问题，经过我查找众多资料后的理解：一般是指针的问题，就是引用了无效的内存！
偷偷地告诉你们：其实只是花括号的位置放错了(啊啊啊)！
2、还有一个问题，看下面代码：
NewPtr->date=e;
NewPtr->next=tmpPtr->next;
这导致的结果就是链表用的结点是同一个（啊啊啊）！
PS:我找了好久啊！！！
最后，我用下面这段代码：
NewPtr=new Node<ElemType>(e,tmpPtr->next)
每次都创建新的结点，就OK了（^_^）
很感谢大家耐心看完这么长的代码，辛苦了！希望一路走来，你可以跟我一样，坚持下来！加油！
多关键字排序