C++模板类插入排序

Posted by Harid十二月 - 1 - 2010 Leave comments

昨天晚上我一直在写这个程序,它是用我定义的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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#ifndef SORT_H_
#define SORT_H_
#include <iostream>
 
template <class Type>
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 <class Type>
void SortNumbers<Type>::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 <class Type>
void SortNumbers<Type>::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; k<j; k++)
            tempJ = tempJ->m_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; n<i; n++)
                tempI = tempI->m_next;
		}
		if(i>=0)
			tempI->m_next->m_number = key.m_number;
		else
			this->m_head->m_number = key.m_number;
    }
}
 
template <class Type>
SortNumbers<Type>::SortNumbers()
{
	this->getItems();
}
 
template <class Type>
SortNumbers<Type>::~SortNumbers()
{
	delete [] m_head;
}
 
template <class Type>
void SortNumbers<Type>::show()
{
	using std::cout;
	using std::endl;
 
	SortLink * temp = this->getHead();
	if((this->getCounts()) != 0)
	{
		cout <<endl<<"Now, the sorted numbers are:\n\t";
		temp = this->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++模板类插入排序

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

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

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

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


分享按钮