C++数据结构第23课、顺序表和单链表的对比分析

问题 如何判断某个数据元素是否存在于线性表中？遗失的操作— find — 可以为线性表（List）增加一个查找的操作 — int find(const T& e)const

模板参数是基本类型的数据元素查找：

List.h

virtual int find(const T& e)const = 0;

SeqList.h

int find(const T& e)const { int ret = -1; for(int i = 0; i < m_length; i++) { if(m_array[i] == e) { ret = i; break; } } return ret; }

LinkList

int find(const T& e)const { int ret = -1; int i = 0; Node* node = m_header.next; while (node != nullptr) { if(node->value == e) { ret = i; break; } else { node = node->next; i++; } } return ret; }

main.cpp

#include <iostream> #include "LinkList.h" using namespace std; using namespace DTLib; int main() { LinkList<Test> list; for(int i = 0; i < 5; i++) { list.insert(i); } cout << list.find(3) << endl; return 0; }

当查找的类型是类类型时，单链表程序会报错，因为在编译if(node->value == e)这条语句时，编译器不知道怎么判断两个类类型相等，这时候我们可以选择在 Test 类里面重载 == 操作符，这样确实可以解决问题。但是难道我们模板类是类对象是我们都要重载类对象嘛？因此我们可以选择在 基类 Object 类里面重载 == 和 != 操作符，让我们定义的类继承于Object 类，这样就可以解决问题，再遇到不同的情况，我们就在类里面重写 == 操作符重载函数即可。

Object.h

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); }

main.cpp

#include <iostream> #include "LinkList.h" using namespace std; using namespace DTLib; class Test : public Object { int i; public: Test(int v = 0) { i = v; } bool operator==(const Test& obj) { return (i == obj.i); } }; int main() { Test t1(1); Test t2(2); Test t3(3); LinkList<Test> list; list.insert(t1); list.insert(t2); list.insert(t3); cout << list.find(t3) << endl; return 0; }

时间复合度对比分析

有趣的问题 顺序表的整体时间复杂度比单链表要低，那么单链表还有使用价值吗？

效率的深度分析 — 实际工程开发中，时间复杂度只是效率的一个参考指标 　　1、对于内置基础类型，顺序表和单链表的效率不相上下 　　2、对于自定义类类型，顺序表在效率上低于单链表

工程开发中的选择

小结 — 线性表中元素的查找依赖于相等比较操作符( == ) — 顺序表适用于 访问 需求量 较大的场合（随机访问） — 单链表适用于数据元素的 频繁插入和删除 的场合（顺序访问） — 当数据类型相对简单时，顺序表和单链表的效率不相上下