数据结构
数据结构 就是描述数据之间的关系
常见的数据结构分类
数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成
- 队列（Queue）
- 链表（Linked List）
- 数组（Array）
- 堆（Heap）
- 栈（Stack）
- 图（Graph）
- 按数据的逻辑分类：
- 线性结构
- 线性结构有且仅有一个开始结点和终端结点
- 栈，队列，串
- 非线性结构
- 就是表中各个结点之间具有多个对应关系
- 非线性结构的一个结点可能有多个直接前趋结点和多个直接后继结点
- 数组，广义表，树结构，图结构
- 存储分类：
- 顺序存储
- 一段连续的内存空间，随机访问
- 缺点 ：插入删除效率低，大小固定
- 链式存储
- 不连续的内存空间，大小动态扩展，插入删除效率高
- 缺点：不能随机访问
数组
- 固定数组
- 优点： 按照索引查询元素速度快 方便
- 缺点： 大小固定无法扩容，只能添加一种类型的数据，添加，删除慢
- 使用场景： 频繁查询，对存储空间要求不大，很少增加和删除的情况
- 动态数组
链表
- 单链表
- 是链表的一种，由节点构成，每个节点指向下一个节点的指针，依次链接成为链表
- 优点 ： 增加删除方便
- 缺点： 查找慢
- 代码实现
//节点结构 template <typename T> class Node { public : T _value;//节点的值 Node* _next;//指针，指向下一个节点 public: Node() = default; Node(T value, Node * next) : _value(value), _next(next){} };
- 双向链表
- 格式： 指针域1（前一个节点） 数据 指针域2（后一个节点）
- 循环链表
- 格式： 最后一个节点 指向第一个节点
- 链表的优点
- 添加删除快，不需要初始化容量，任意加减元素
- 缺点：
- 含有大量的指针域，占用空间大，遍历查找耗时
- 结构
/* 双向链表的节点结构 */ template <typename T> struct Node { public: Node()= default; Node(T value, Node<T>* preptr, Node<T>* nextptr) :_value(value), pre_ptr(preptr), next_ptr(nextptr){} public: T _value;//节点元素的值 Node<T>* pre_ptr;//指向前驱的指针 Node<T>* next_ptr;//指向后继的指针 };
与单链表定义相似，定义链表类
/* * 双向链表类 */ template<typename T> class DoubleLink { public: typedef Node<T>* pointer; public: DoubleLink(); ~DoubleLink(){}; public: Node<T>* insert(int index, T value);//插入指定位置 Node<T>* insert_front(T value);//插入第一个位置 Node<T>* insert_last(T value);//插入到链表尾部 Node<T>* del(int index);//删除指定位置 Node<T>* delete_front();//删除第一个节点 Node<T>* delete_last();//删除最后一个节点 bool isEmpty(); int size(); T get(int index); T get_front(); T get_last(); Node<T>* getHead(); private: Node<T>* phead; int count; private : Node<T>* getNode(int index); };
实现添加节点
/* *将新节点插到第一个位置 */ template <typename T> Node<T>* DoubleLink<T>::insert_front(T value) { Node<T>* newNode = new Node<int>(value, phead, phead->next_ptr);// phead->next_ptr ->pre_ptr= newNode; phead->next_ptr = newNode; count++; return newNode; }; /* *将新节点插到链表尾部 */ template <typename T> Node<T>* DoubleLink<T>::insert_last(T value) { Node<T> * newNode = new Node<int>(value, phead->pre_ptr, phead); phead->pre_ptr->next_ptr = newNode; phead->pre_ptr = newNode; count++; return newNode; }; /* *将节点位置插到index位置之前 */ template <typename T> Node<T>* DoubleLink<T>::insert(int index, T value) { if (index == 0) return insert_front(value); Node<T>* pNode = getNode(index); if (pNode == nullptr) return nullptr; Node<T>* newNode = new Node<T>(value, pNode->pre_ptr, pNode); pNode->pre_ptr->next_ptr = newNode; pNode->pre_ptr = newNode; count++; return newNode; };
实现删除节点
/* *删除链表第一个节点 *返回删除后链表第一个节点 */ template<typename T> Node<T>* DoubleLink<T>::delete_front() { if (count == 0) { return nullptr; } Node<T>* pnode = phead->next_ptr; phead->next_ptr = pnode->next_ptr; pnode->next_ptr->pre_ptr = phead; delete pnode; count--; return phead->next_ptr; }; /* *删除链表的末尾节点 *返回删除后链表尾部元素 */ template<typename T> Node<T>* DoubleLink<T>::delete_last() { if (count == 0) { return nullptr; } Node<T>*pnode = phead->pre_ptr; pnode->pre_ptr->next_ptr = phead; phead->pre_ptr = pnode->pre_ptr; delete pnode; count--; return phead->pre_ptr; } /* *删除指定位置的元素 * */ template <typename T> Node<T>* DoubleLink<T>::del(int index) { if (index == 0) return delete_front(); if (index == count - 1) return delete_last(); if (index >= count) return nullptr; Node<T>* pnode = getNode(index); pnode->pre_ptr->next_ptr = pnode->next_ptr; pnode->next_ptr->pre_ptr = pnode->pre_ptr; Node<T>* ptemp = pnode->pre_ptr; delete pnode; count--; return ptemp; };
双向链表测试代码
int main() { DoubleLink<int> dlink; //插入测试 for (int i = 0; i < 10; i++) { dlink.insert(0, i+10); } dlink.insert(0, 100); dlink.insert_last(1000); cout <<"链表长度:"<< dlink.size() << endl; //删除测试 dlink.delete_front(); dlink.delete_last(); dlink.del(3); DoubleLink<int>::pointer ptr = dlink.getHead(); ptr = ptr->next_ptr; while (ptr != dlink.getHead()) { cout << ptr->_value<<endl; ptr = ptr->next_ptr; } getchar(); return 0; }
- 双链表github源代码：https://github.com/huanzheWu/Data-Structure/blob/master/DoubleLink/DoubleLink/DoubleLink.h