很歡迎來看我的部落格,這是我的考核作業!以此記錄我的學習曆程!大家參考就好!如有錯誤,敬請指出!在此,先謝謝一番!
多關鍵字排序就是基數排序,我是用單連結清單實作多關鍵字的排序的,但最主要的方法仍是“配置設定”,“收集”。單連結清單隻是在配置設定與收集過程中起暫時的存儲作用。不僅可以用連結清單,還可以用棧、隊列……(都是線性的!!!(^_^))
這是結點類模闆的定義:
#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了(^_^)
很感謝大家耐心看完這麼長的代碼,辛苦了!希望一路走來,你可以跟我一樣,堅持下來!加油!