C++泛型线性查找算法——find

C++泛型线性查找算法——find

泛型编程和STL》笔记及思考。

线性查找可能是最为简单的一类查找算法了。他所作用的数据结构为一维线性的空间。这篇文章主要介绍使用 C++ 实现泛型算法 find的过程。

C 版本

首先介绍 C find 算法的实现,用以引入 C++ 版本。

char *find1(char *first,char *last,int c) { while(first != last && *first != c) ++first; return first; }

该版本的算法循环检查每个元素,尾后指针(last)作为结束标识。

使用举例如下:

char A[N]; ... char *result = find1(A,A + N,c); if(result == A + N) printf("search failed\n"); else printf("found it");

C 实现的 find 算法实现很简单,但使用范围很局限,只能应用于字符数组中对指定字符的查找。

C++ 版本

由于 C 版本 find 的使用范围局限性,在 C++ 中,我们可以使用泛型对策,利用 template 将函数的参数类型参数化。

首先,我们可以考虑设计一个类似 C 版本的 find 算法,以任意类型 T 的指针作为参数,代替原来的 char 指针。所以该方法声明如下:

template<class T> T *find2(T *first,T *last,T value);

这样 find 方法就不在局限于一种类型可以使用了。

不过,STL 的泛型做法不像上述那般显而易见。STL 的线性查找算法是这样定义的:

template<class Iterator,class T> Iterator find(Iterator first,Iterator last,const T& value) { while(first != last && *first != value) ++first; return first; }

为什么是 find 而不是看起来更浅显的 find2 呢?

原因简单的说,是因为这样的函数比 find2 更加的一般化。这种一般化的一个主要体现就是,它不再依赖数据结构的具体实现。比如,在链表上的线性查找。

链表上的查找

我们将把 find 用于单链表的线性查找,来证实 find 的一般性。虽然数组和链表对元素的组织方式不同,但是 基于线性序列的 find 仍可以适用于二者。

下面是一个链表结点的数据结构:

struct int_node { int val; int_node* next; };

链表的遍历方法:

int_node* p; for (p = list_head; p != NULL; p = p->next) //pass

单链表是一个线性序列,线性查找是一种常见的行为。既然是线性查找,而我们之前又写过线性查找算法,那么我们不应该编写重复的代码,而是考虑重用这个函数。

首先考虑我们实现过的第一个泛型查找算法 find2。find2 接受的参数为一个范围 [first,last),这个范围通过传递两个指针来界定。但是这里有个显而易见的问题,指向结点的指针如何在单链表上前进?假设我们有一个 int_node 指针 first 并传递给 find2 函数,然后我们希望通过 first++ 来实现指针的移动,注意问题便在这里,first ++ 操作无法到达下一个元素。因为 find2 算法应对的是线性序列使用数组实现的情况,而现在,序列元素的组织方式为链式结构,指针前进的方式不再是通过增加元素指针的值(first++)来实现。对于链表,操作应当是 first = first->next。

如何解决这个问题?

方案一 :使用 C++ 中的操作符重载

如果上述的 operator++ 行为不符合需要,那么就重新定义他的行为,

也即:

原 ++ 操作: a = a + 1; 现 ++ 操作: a = a->next;

使得 find2 可以正常工作。

然而,重新定义参数类型为 int_node* 类型的 operator++ 操作符是不可能的,C++ 允许我们定义操作符的表达式意义,单不允许变动既有的语法意义(我们不能随便的将一个指针的自加行为改变为其他的操作,就像不能将整数 + 运算符定义为 减、乘操作,这是不合适的)。

方案二 : 增加一个包装类(外覆类 wrapper class)

我们通过编写一个简单的外覆类(wrapper class)使他看起来像一个 int_node* ,而他的 operator++ 有更为合适的定义。

外覆类的定义:

template<class Node> //这里传递的参数是 类型 int_node struct node_wrap { Node* ptr; node_wrap(Node* p = 0) : ptr(p) { } Node& operator* const { return *ptr; } Node* operator-> const { return ptr; } node_wrap& oeprator++() { ptr = ptr->next; return *this; } node_wrap operator++(int) { node_wrap tmp = *this; ptr = ptr->next; return tmp; } bool operator== (const node_wrap& i) const { return ptr == i.ptr; } bool operator!= (const node_wrap& i) const { return ptr != i.ptr; } };

事实上我们还是重载了 operator++ 的行为,但是现在是在外覆类上的重载,而不是指针上的重载,对于外覆类来说,这种行为是合适的。

最后,由于 find 函数中的

while(... *first != value)

语句中,*first != value 这个不等运算符的操作并没有定义,所以下面对他进行定义:

bool operator!= (csonst node_wrap& i,int n) const { return i.value != n; }

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpwzww.html