青岛公司建设网站,爱是做的电影网站吗,什么网站可以设计接单做,黑龙江建设银行交通违法网站C中的链表是一种非常常见的数据结构#xff0c;它由一系列节点组成#xff0c;每个节点包含一个数据元素和一个指向下一个节点的指针。
链表结构包括单向链表、双向链表和循环链表#xff1b;
1.单向链表
单向链表由一系列节点组成#xff0c;每个节点包含一个数据元素和…C中的链表是一种非常常见的数据结构它由一系列节点组成每个节点包含一个数据元素和一个指向下一个节点的指针。
链表结构包括单向链表、双向链表和循环链表
1.单向链表
单向链表由一系列节点组成每个节点包含一个数据元素和一个指向下一个节点的指针
1.1 定义
//单向链表结构
class Node
{
public:int data;Node* next;
};//单向链表类
class LinkedList {
public:LinkedList() {head nullptr;}
private:Node* head;
};1.2 初始化
对于定义的单向链表类可以通过构造函数定义元素为空的链表也可以通过initialize来初始化包含一个元素的链表
示例 LinkedList() {head nullptr;}void initialize(int value) {head new Node();head-data value;head-next nullptr;}1.3 获取链表的长度
获取链表的长度即计算链表中包含多少个元素通过遍历其中的元素计算 int length() {int count 0;Node* current head;while (current ! nullptr) {count;current current-next;}return count;}1.4 插入元素 元素追加
插入元素
根据元素插入的位置和元素来进行元素的插入操作
示例 void insertNode(int index, int value) {// 判断是否满足插入条件if (index 0 || index length()) {return;} else if (index 0) { //首元素Node* newNode new Node();newNode-data value;newNode-next head;head newNode;} else {Node* prevNode getNode(index - 1); //根据下标获取元素的方法Node* newNode new Node();newNode-data value;newNode-next prevNode-next;prevNode-next newNode;}}元素追加
元素的追加将元素插入到元素的末尾 void append(int value) {Node* newNode new Node();newNode-data value;newNode-next nullptr;if (head nullptr) {head newNode;} else {Node* current head;while (current-next ! nullptr) {current current-next;}current-next newNode;}}1.5 删除元素 清空 判断是否为空
删除元素
根据下标对元素进行删除 void deleteNode(int index) {if (index 0 || index length()) {return;} else if (index 0) {Node* temp head;head head-next;delete temp;} else {Node* prevNode getNode(index - 1);Node* currentNode prevNode-next;prevNode-next currentNode-next;delete currentNode;}}清空链表
清空链表中的元素 void clear() {Node* current head;while (current ! nullptr) {Node* next current-next;delete current;current next;}head nullptr;}判断链表是否为空 bool isEmpty() {return (head nullptr);}1.6 根据下标获取元素
根据链表的下标来获取该位置的元素 Node* getNode(int index) {if (index 0 || index length()) {return nullptr;} else {Node* current head;int i 0;while (i index) {current current-next;i;}return current;}}1.7 链表数据元素的打印 void printList() {Node* current head;while (current ! nullptr) {std::cout current-data ;current current-next;}std::cout std::endl;}1.8 应用场景
数据缓存单向链表可以用作缓存数据结构新的数据可以插入到链表的头部而旧的数据可以从尾部移除以限制缓存大小并保持最近使用的数据在链表的头部。
队列和栈的实现单向链表可以用来实现队列和栈这两种常见的数据结构。在队列中数据从尾部插入入队从头部删除出队。在栈中数据只在链表的头部插入和删除模拟了后进先出LIFO的行为。
2.双向链表
双向链表与单向链表不同之处在于每个节点除了指向下一个节点的指针外还包含指向前一个节点的指针这使得双向链表可以在前后两个方向上遍历和操作节点。
2.1 定义
双向链表这里使用了模板
templatetypename T
class Node {
public:T data;NodeT* prev;NodeT* next;
};templatetypename T
class DoublyLinkedList {
public:DoublyLinkedList() {head nullptr;}
private:NodeT* head;
};2.2 初始化 void initialize(const T value) {head new NodeT();head-data value;head-prev nullptr;head-next nullptr;}2.3 获取链表的长度 int length() {int count 0;NodeT* current head;while (current ! nullptr) {count;current current-next;}return count;}2.4 插入元素 元素追加
插入元素 void insertNode(int index, const T value) {if (index 0 || index length()) {return;} else if (index 0) {NodeT* newNode new NodeT();newNode-data value;newNode-prev nullptr;newNode-next head;if (head ! nullptr) {head-prev newNode;}head newNode;} else {NodeT* prevNode getNode(index - 1);NodeT* nextNode prevNode-next;NodeT* newNode new NodeT();newNode-data value;newNode-prev prevNode;newNode-next nextNode;prevNode-next newNode;if (nextNode ! nullptr) {nextNode-prev newNode;}}}元素追加 void append(const T value) {NodeT* newNode new NodeT();newNode-data value;newNode-prev nullptr;newNode-next nullptr;if (head nullptr) {head newNode;} else {NodeT* current head;while (current-next ! nullptr) {current current-next;}current-next newNode;newNode-prev current;}}2.5 删除元素 清空 判断是否为空
删除元素 void deleteNode(int index) {if (index 0 || index length()) {return;} else if (index 0) {NodeT* temp head;head head-next;if (head ! nullptr) {head-prev nullptr;}delete temp;} else {NodeT* currNode getNode(index);if (currNode nullptr) {return;}NodeT* prevNode currNode-prev;NodeT* nextNode currNode-next;prevNode-next nextNode;if (nextNode ! nullptr) {nextNode-prev prevNode;}delete currNode;}} 清空 void clear() {NodeT* current head;while (current ! nullptr) {NodeT* next current-next;delete current;current next;}head nullptr;}判断链表是否为空 bool isEmpty() {return (head nullptr);}2.6 根据下标来获取元素 NodeT* getNode(int index) {if (index 0 || index length()) {return nullptr;} else {NodeT* current head;int i 0;while (i index) {current current-next;i;}return current;}}2.7 链表数据元素的打印
双向链表支持正向输出和反向输出
void printListForward(NodeT* first) {NodeT* current first;while (current ! nullptr) {std::cout current-data ;current current-next;}std::cout std::endl;}void printListBackward(NodeT* last) {NodeT* current last;while (current ! nullptr) {std::cout current-data ;current current-prev;}std::cout std::endl;}2.8 应用的场景
实现链表或双端队列双向链表天然支持在链表头和链表尾高效地插入和删除元素使其适用于实现链表或双端队列deque等数据结构。
实现LRU缓存算法LRULeast Recently Used缓存算法中当缓存已满时最近最少使用的元素会被淘汰。双向链表可以方便地记录元素的访问顺序并且在需要淘汰元素时可以快速删除链表尾部的节点。
实现迭代器双向链表的双向遍历特性使其非常适合用于实现迭代器。迭代器可以用于遍历容器中的元素而双向链表可以提供前向和后向的遍历方式。
3.循环链表
循环链表是一种特殊类型的链表其中链表的最后一个节点指向第一个节点形成一个循环。与普通链表不同循环链表没有一个明确的末尾节点可以通过任何一个节点遍历整个链表。
3.1 定义
templatetypename T
class Node {
public:T data;NodeT* next;
};templatetypename T
class CircularLinkedList {
public:CircularLinkedList() {head nullptr;}
private:NodeT* head;
};3.2 初始化 void initialize(const T value) {head new NodeT;head-data value;head-next head;}3.3 获取链表的长度 int length() {if (head nullptr) {return 0;} else {int count 1;NodeT* current head-next;while (current ! head) {count;current current-next;}return count;}}3.4 插入元素 元素追加
插入元素 void insertNode(int index, const T value) {NodeT* newNode new NodeT();newNode-data value;if (isEmpty() || index 0) {head newNode;head-next head;} else {NodeT* prevNode getNode(index - 1);if (prevNode nullptr) {delete newNode;return;}newNode-next prevNode-next;prevNode-next newNode;}}元素追加 void append(const T value) {NodeT* newNode new NodeT;newNode-data value;newNode-next head;if (head nullptr) {head newNode;newNode-next head;} else {NodeT* current head;while (current-next ! head) {current current-next;}current-next newNode;}}3.5 删除元素 清空 判断是否为空
删除元素 void deleteNode(int index) {if (isEmpty() || index 0) {return;} else if (index 0) {NodeT* currNode head;if (head-next head) {head nullptr;} else {NodeT* lastNode head;while (lastNode-next ! head) {lastNode lastNode-next;}lastNode-next head-next;head head-next;}delete currNode;} else {NodeT* prevNode getNode(index - 1);if (prevNode nullptr || prevNode-next head) {return;}NodeT* currNode prevNode-next;prevNode-next currNode-next;delete currNode;}}清空 void clear() {NodeT* current head;while (current ! nullptr current-next ! head) {NodeT* next current-next;delete current;current next;}head nullptr;}判断是否为空 bool isEmpty() {return (head nullptr);}3.6 根据下标来获取元素 NodeT* getNode(int index) {if (index 0 || index length()) {return nullptr;} else {NodeT* current head;int i 0;while (i index) {current current-next;i;}return current;}} 3.7 链表元素的打印 void printCircularLinkedList(NodeT* head) {if (head nullptr) {return; // 空链表}NodeT* current head;do {std::cout current-data ;current current-next;} while (current ! head);std::cout std::endl;}3.8 应用场景
环形缓冲区Circular Buffer环形缓冲区是一种常用的高效数据存储结构常用于实现循环队列。在环形缓冲区中最后一个元素的下一个位置是第一个元素形成一个循环。循环链表提供了一种有效的数据结构来实现环形缓冲区。
循环播放列表在音乐播放器或视频播放器中可以使用循环链表来实现循环播放列表。每个歌曲或视频可以用链表节点表示通过调整节点的顺序可以实现循环播放功能。
