C++模板类插入排序

Posted by Harid2010 - Dec - 01 留个言

昨天晚上我一直在写这个程序,它是用我定义的C++模板类来实现简单的插入排序算法的程序,可以根据需求输入一串预先知道长度(长度须输入)的数进行从小至大的排序。插入排序应该是排序算法里最简单的了,因此,它也只能对数据量比较小的数据排序,其算法时间函数是 n²,随着数字的个数 n 的增大,算法效率会大大降低

该模板类里面使用单链表而非数组来保存未知类型的数,原因是我觉得链表以后可以扩展元素。这个模板类,还可以通过重载大于操作符(>)来扩展功能,使之不仅仅是对数字进行排序。另外,如果使用双向链表,将会使这段程序更简单。

一开始,它老是无法通过编译,出现一些莫名其妙的错误。唉,很久没用了,我忘得连类怎么声明都不会了!!!错误诸如:

In function `main’:|
main.cpp|8|undefined reference to `SortNumbers::SortNumbers()’|
main.cpp|9|undefined reference to `SortNumbers::show()’|
main.cpp|10|undefined reference to `SortNumbers::~SortNumbers()’|
main.cpp|10|undefined reference to `SortNumbers::~SortNumbers()

在main.cpp里面实例化模板类的时候,编译器报错说我的一些方法没有定义,甚至包括构造函数。我后来发现问题出在编译器上。在大多数的编译器里,模板类的定义违背了我们通常认定的头文件规则,即:“不要放置分配存储空间的任何东西于头文件里”。这条规则是为了防止在连接期间的多重定义错误,但是对于模板类而言,template <……>之后的任何东西都意味着编译器在当时不为它分配存储空间,而是一直处于等待状态直到被一个模板实例告知。在编译器与连接器中有机制能去掉同一模板的多重定义。所以,一般都是将模板类的声明与定义均放置于头文件中。如果必须将定义与声明分开,则得查阅编译器的文档看如何才能做到这一点。

程序代码 sort.h:

#ifndef SORT_H_
#define SORT_H_
#include 

template 
class SortNumbers
{
private:
	struct SortLink
	{
		Type m_number;
		SortLink * m_next;
		SortLink(Type number, SortLink * next): m_number(number), m_next(next) {}
		SortLink() : m_number(0), m_next(0){}
	};
	SortLink * m_head;
	SortLink * m_last;
	int m_counts;
protected:
	void getItems();
	void sortArr();
public:
    SortNumbers();
    ~SortNumbers();
	SortLink * getHead()const{
		return this->m_head; }
	SortLink * getLast()const{
		return this->m_last; }
	SortLink * getSorted()const{
		return this->m_sorted; }
	int getCounts()const{
		return this->m_counts; }
	void show();
};

template 
void SortNumbers::getItems()
{
	using std::cout;
	using std::cin;

	cout <<"Enter the length of your items:  ";
	while(!(cin>>(this->m_counts)) || (this->m_counts)<0 || cin.get()!='\n')
	{
		cout <<"\tOOps! Enter error, enter again  ";
		cin.clear();
		while(cin.get()!='\n')
			continue;
	}
	SortLink * temp;
	for(int i=0;i<(this->getCounts()); i++)
	{
        temp = new SortLink;
		cout <<"\nPlease enter a positive number:  ";
		while(!(cin>>(temp->m_number)) || (temp->m_number)<0 || cin.get()!='\n')
		{
			cout <<"\tOOps, it has encounted an error! please enter it again:  ";
			cin.clear();
			while(cin.get()!='\n')
				continue;
		}
		temp->m_next = 0;
		if(i == 0)
			this->m_head = this->m_last = temp;
		else
		{
			this->m_last->m_next = temp;
			this->m_last = temp;
			if(i==((this->getCounts())-1))
                this->sortArr();
		}
	}
}

template 
void SortNumbers::sortArr()
{
	SortLink * tempJ;
	SortLink * tempI;
	SortLink key;
	int i = 0;
	tempI = tempJ =  this->getHead();
	for(int j=1; j<(this->getCounts()); j++)
	{
		tempI = tempJ = this->getHead();
		for(int k=0; km_next;
        for(int m=0; m<(j-1); m++)
            tempI = tempI->m_next;
		key.m_number = tempJ->m_number;
		key.m_next = 0;
		i = j-1;
		while(i>=0 && ((tempI->m_number)>(key.m_number)))
		{
			tempI->m_next->m_number = tempI->m_number;
			i--;
            tempI = this->getHead();
            for(int n=0; nm_next;
		}
		if(i>=0)
			tempI->m_next->m_number = key.m_number;
		else
			this->m_head->m_number = key.m_number;
    }
}

template 
SortNumbers::SortNumbers()
{
	this->getItems();
}

template 
SortNumbers::~SortNumbers()
{
	delete [] m_head;
}

template 
void SortNumbers::show()
{
	using std::cout;
	using std::endl;

	SortLink * temp = this->getHead();
	if((this->getCounts()) != 0)
	{
		cout <m_head;
		for(int k=0; k<(this->getCounts()); k++)
		{
			cout <<(temp->m_number)<<" ";
			if(temp->m_next != 0)
				temp = temp->m_next;
		}
	}
	else
		cout <<"No numbers.\n";
}

#endif

程序运行的一个例子:

sort-instance

   声明:本文采用 BY-NC-SA 协议进行授权 | 星期九
   原创文章转载请注明:转自《C++模板类插入排序

Comments(9) Leave comments
  1. Gravatar
    野丫头姐姐 Google Chrome Google Chrome 7.0.517.24 Windows Windows 7
    十二月 3rd, 2010 at 23:14  | #1

    只能用佩服了,我头度大了,呜呜……

  2. Gravatar
    Tanky Woo SouGou Browser SouGou Browser 2.X Windows Windows XP
    十二月 1st, 2010 at 17:25  | #2

    嘿嘿,看到这个标题,果断点开了。

    不过代码插件似乎 不给力哦,有几个小问题:
    1.他只把几个简单的关键字高亮了
    2.没有缩进
    3.前面的行号会和代码一起被复制。

    模版类我用的不太多。。还没尝试过在模板中嵌套一个struct….

    • Gravatar Harid  @  十二月 1st, 2010 at 23:35 replied.

      @Tanky Woo, 我没有用代码插件呀,所以就只能有这种效果了。以前有用过插件,后来感觉没必要,遂卸了。

      • Gravatar Tanky Woo  @  十二月 2nd, 2010 at 13:37 replied.  | #3

        @Harid,

        感觉看着有点憋屈。。。不过你从编辑器里复制过来的时候应该会保留缩进吧。。。

  3. Gravatar
    Demon Internet Explorer Internet Explorer 9.0 Windows Windows 7
    十二月 1st, 2010 at 15:48  | #4

    你的代码高亮不给力啊

    • Gravatar Harid  @  十二月 1st, 2010 at 23:40 replied.

      @Demon, 我没有用插件,只是用CSS稍微高亮了一下,所以就只能是这个效果了。

  4. Gravatar
    Suitear Google Chrome Google Chrome 7.0.517.44 Windows Windows XP
    十二月 1st, 2010 at 12:38  | #5

    ❓ 不懂的直接飘~

  5. Gravatar
    南阳SEO Internet Explorer Internet Explorer 8.0 Windows Windows XP
    十二月 1st, 2010 at 11:54  | #6

    你好,博主。你刚才光临小站了,我也来光顾一下贵站。你的站不错啊! ❗ 不知道你是怎么找到我的站的呢?

    • Gravatar Harid  @  十二月 1st, 2010 at 12:00 replied.

      @南阳SEO, 我是从别的站过去了,以后会经常拜访!

13 + 57 =  (required)
comment_ad

 NOTICE1: You should type some Chinese word (like “你好”) in your comment to pass the spam-check, thanks for your patience!

 NOTICE2: 请申请gravatar头像(http://en.gravatar.com),木有头像的会显示为“小怪物”头像,将难以通过审核!

分享按钮