大屏网站做响应,开发网站公司排行榜,广州设计工作室集中地,推广app摘要#xff1a; it人员无论是使用哪种高级语言开发东东#xff0c;想要更高效有层次的开发程序的话都躲不开三件套#xff1a;数据结构#xff0c;算法和设计模式。数据结构是相互之间存在一种或多种特定关系的数据元素的集合#xff0c;即带“结构”的数据元素的集合 it人员无论是使用哪种高级语言开发东东想要更高效有层次的开发程序的话都躲不开三件套数据结构算法和设计模式。数据结构是相互之间存在一种或多种特定关系的数据元素的集合即带“结构”的数据元素的集合“结构”就是指数据元素之间存在的关系分为逻辑结构和存储结构。 此系列专注讲解数据结构数组、链表、队列、栈、树、哈希表、图通过介绍概念以及提及一些可能适用的场景并以C代码简易实现多方面认识数据结构最后为避免重复造轮子会浅提对应的STL容器。本文介绍的是链List。
开发环境VScodeC17
关键词 C数据结构链表List 声明本文作者原创转载请附上文章出处与本文链接。 文章目录 摘要正文介绍特性应用 代码实现对应STL 推荐阅读 正文
介绍 链表Linked List是一种常见的数据结构它通过一系列的节点Node来存储数据每个节点包含两个部分一个是数据域Data Field用于存储数据另一个是链接域Link Field用于存储指向下一个节点的引用在单链表中或前一个节点和下一个节点的引用在双向链表中。链表数据一般都是分散存储于内存中 的无须存储在连续空间内。
双向链表 特性
动态性链表不需要在内存中预先分配固定大小的空间可以根据需要动态地创建和删除节点。这使得链表在处理不确定大小的数据集合时非常灵活。多种类型链表有多种类型包括单向链表、双向链表、循环链表等。每种类型的链表都有其特定的应用场景和优缺点。插入和删除效率高在链表中插入或删除一个节点时只需要修改相关节点的指针或引用即可而不需要移动大量数据。非连续性链表中的节点在内存中不一定是连续存储的。每个节点都包含一个指向下一个节点的指针或引用这些指针或引用将节点连接在一起。
应用
实现堆栈Stack和队列Queue等抽象数据类型。在数据库中实现邻接列表来表示图Graph。在浏览器中表示历史记录或书签。在操作系统中表示进程列表或文件列表。在许多算法中如归并排序Merge Sort和快速排序Quick Sort的链表实现等。
代码实现
#clist.h
#ifndef CLIST_H
#define CLIST_H
#include iostream
#include cstdlibusing namespace std;
// 链表结点
template class T
class DNode
{
public:DNodeT *next;DNodeT *prev;T data;
};// 双向列表类
template class T
class CList
{
public:CList(); // 默认构造函数CList(const CList ln); // 拷贝构造函数~CList(); // 析构函数void add(T e); // 向链表添加数据void remove(T index); // 移除某个结点T find(int index); // 查找结点bool empty(); // 判断是否为空int size(); // 链表长度void print(); // 显示链表void print_reverse(); // 链表反向显示void clear(); // 删除全部结点
private:DNodeT *head;DNodeT *tail;int length;
};// 默认构造函数
template typename T
CListT::CList()
{head new DNodeT;tail new DNodeT;head-next tail;head-prev nullptr;tail-next nullptr;tail-prev head;length 0;
}// 拷贝构造函数
template typename T
CListT::CList(const CList ln)
{head new DNodeT;head-prev nullptr;tail new DNodeT;head-next tail;tail-prev head;length 0;DNodeT* temp ln.head;while (temp-next ! ln.tail){temp temp-next;tail-data temp-data;DNodeT *p new DNodeT;p-prev tail;tail-next p;tail p;length;}tail-next nullptr;
}// 析构函数
template typename T
CListT::~CList()
{if (length 0){delete head;delete tail;head nullptr;tail nullptr;return;}while (head-next ! nullptr){DNodeT *temp head;head head-next;delete temp;}delete head;head nullptr;
}// 向链表添加数据
template typename T
void CListT::add(T e)
{DNodeT* temp this-tail;tail-data e;tail-next new DNodeT;DNodeT *p tail;tail tail-next;tail-prev p;tail-next nullptr;length;
}// 查找结点
template typename T
T CListT::find(int index)
{if (length 0){cout CList is empty;return -1;}if (index length){cout Out of bounds;return -1;}int x 0;DNodeT *p;p head-next;while (p-next ! nullptr x ! index){p p-next;}return p-data;
}// 删除结点
template typename T
void CListT::remove(T index)
{if (length 0){cout CList is empty;return;}DNodeT *p head;while (p-next ! nullptr){p p-next;if (p-data index){DNodeT *temp p-prev;temp-next p-next;p-next-prev temp;delete p;length--;return;}}
}// 删除所有结点
template typename T
void CListT::clear()
{if (length 0){return;}DNodeT *p head-next;while (p ! tail){DNodeT* temp p;p p-next;delete temp;}head-next tail;tail-prev head;length 0;
}// 判断是否为空
template typename T
bool CListT::empty()
{if (length 0){return true;}else {return false;}
}// 链表长度
template typename T
int CListT::size()
{return length;
}// 输出链表
template typename T
void CListT::print()
{if (length 0){cout CList is empty endl;return;}DNodeT *p head-next;while (p ! tail){cout p-data ;p p-next;}cout endl;
}// 反向输出链表
template typename T
void CListT::print_reverse()
{if (length 0)return;DNodeT *p tail-prev;while (p ! head){cout p-data ;p p-prev;}cout endl;
}#endif // !CLIST_H#clist.cpp
#include clist.h
#include iostream
using namespace std;int main(int argc, char**argv)
{CListint list;list.add(6);list.add(443);list.add(767);list.add(56);CListint list2(list);list2.print_reverse();list2.print();cout list2.size(): list2.size() endl;cout list2.find(2): list2.find(2) endl;list2.remove(443);list2.print();return 0;
}对应STL list 双向循环链表。使用起来很高效对于任意位置的插入和删除都很快在操作过后以后指针、迭代器、引用都不会失效。 forward_list 单向链表。只支持单向访问在链表的任何位置进行插入/删除操作都非常快
推荐阅读
C/C专栏https://blog.csdn.net/weixin_45068267/category_12268204.html (包含其它数据结构即对应的STL容器使用)
