1、如何判断某个数据元素是否存在于线性表中？
find()操作：
可以为线性表List增加一个查找操作
int find(const T& e)const;
参数：待查找的数据元素
返回值：
大于0：数据元素在线性表中第一次出现的位置
-1：数据元素不存在
针对基础数据类型，首先在顶层父类List中增加一个虚函数virtual int find(const T& e) const = 0;，然后在各子类中实现这个函数
// 顺序表中的实现 SeqList.h int find(const T& e) const // O(n) { int ret = -1; for(int i = 0; i < m_length; i++) { if(m_array[i] == e) { ret = i; break; } } return ret; } // 单链表中的实现 LinkList.h int find(const T& e) const { int ret = -1; int i = 0; Node* node = m_header.next; while(node) { if(node->value == e) { ret = i; break; } else { node = node->next; i++; } } return ret; }针对自定义类类来说
class Test { int i; public: Test(int v = 0) { i = v; } }; int main() { Test t1(1); Test t2(2); Test t3(3); LinkList<Test> list; return 0; } // 会报一个错，错误的地方在LinkList.h int find(const T& e) const { ...... while(node) { if(node->value == e) // 这句话报错 } ...... } /* 报错的原因是： node->value 和 e都是Test对象，并没有重载Test类的"=="操作符，在这里编译器不知道如何去比较这两个Test对象 */解决方案1：在Test类中直接重载相等比较操作符==
class Test { int i; public: Test(int v = 0) { i = v; } bool operator == (const Test& t) { return (i == t.i); } };这样就可以编译通过，但是这样写存在着一个问题，我们的本意是定义一个单链表对象，保存的对象元素是Test对象，并没有进行实际的查找，也就是说还没想用==操作符来比较，我们就要去在Test类中重载==操作符，这意味着，但凡我们想要定一个这样的保存自定义类类型的单链表对象，我们就必须在自定义类类型中重载==操作符。这样find()查找函数的便利性还没有体现出来，编译错误先出现了，find操作使我们自定义类类型的时候也更加麻烦了。
但是find操作还是应该存在的，需要解决的问题是，使find函数依然存在，但是自定义类类型的时候也不需要每次都重载，只在需要用到查找函数的类类型时再重载。
思路：在顶层父类中实现操作符==和!=的重载，定义类时，都继承于这个父类，这样类模板中的find()函数实现就可以通过编译。如果自定义类类型需要用到这个find()函数时，再重载操作符==实现相等比较逻辑。
// Object.h class Object { public: ... bool operator == (const Object& obj); bool operator != (const Object& obj); ... }; // Object.cpp bool Object::operator == (const Object& obj) { // 默认实现的方式最好就是通过比较地址 return (this == &obj); } bool Object::operator != (const Object& obj) { return (this != &obj); } // 使用的时候，就需要在定义自定义类类型的时候继承Object父类 class Test : public Object { int i; public: Test(int v = 0) { i = v; } }; // 这样，这句话就不会出现编译错误了 LinkList<Test> list; // 下面再考虑查找find函数 Test t1(1); Test t2(2); Test t3(3); LinkList<Test> list; list.insert(0,t1); list.insert(0,t2); list.insert(0,t3); list.find(t3); // 查找的依据应该是Test内的i的值，此时就需要在Test类中重载"=="操作符, 提供具体的相等比较逻辑 class Test : public Object { public: ... bool operator ==(const Test& t) { return (i == t.i); } ... };顶层父类中重载的== !=只是提供了一个默认的相等比较符的实现方式，是为了类模板中编译通过，针对某个具体的自定义类类型的时候，如果需要用到==或!=时，需要在自定义类中重载这两个操作符，因为默认的逻辑不是我们需要的相等或不等比较的实现逻辑。
2、顺序表和单链表的对比分析 操作 SeqList LinkListinsert O(n) O(n)
remove O(n) O(n)
set O(1) O(n)
get O(1) O(n)
find O(n) O(n)
length O(1) O(1)
clear O(1) O(n)
从时间复杂上来说，单链表和顺序表比起来并不高效，但是工程上单链表用得比顺序表更多
顺序表的整体时间复杂度比单链表要低，那么单链表还有使用价值吗？
实际工程开发中，时间复杂度只是效率的一个参考指标
对于内置基础类型，顺序表和单链表的效率不相上下
对于自定义类类型，顺序表再效率上低于单链表
效率的深度分析
插入和删除：
顺序表：涉及大量数据对象的复制操作
单链表：只涉及指针操作，效率与数据对象无关
基础内置类型如int，顺序表的复制操作只涉及到4个字节，而单链表涉及的是指针操作，4字节或8字节，两者效率相差不大