本文主要是介绍数据结构与算法---线性表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
线性表
1.顺序表
需求分析
/*创建顺序表具体功能：初始化顺序表销毁顺序表获取顺序表元素个数输出顺序表中的内容自动扩容增 --- 插入数据（包含了尾部添加功能）删 --- 删除数据（包含了尾部删除功能）改 --- 修改数据查 --- 查找数据尾部追加尾部删除*/
C语言实现
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>// 定义顺序表存储的数据类型
typedef int dataType;// 定义顺序表结构
typedef struct SeqList {dataType* arr; // 用来记录表的地址int capacity; // 用来记录表的容量int size; // 用来记录表中元素的个数
}SeqList;// 功能声明：
// ----------------------------------------------------
bool initList(SeqList&, int); // 初始化顺序表
void destroyList(SeqList&); // 销毁顺序表
int sizeList(SeqList&); // 获取顺序表元素个数
void printList(SeqList&); // 输出顺序表中的内容
bool expandList(SeqList&, int); // 自动扩容
// ----------------------------------------------------
bool insertList(SeqList&, dataType, int); // 增
bool deleteList(SeqList&, int); // 删
bool modifyList(SeqList&, dataType, int); // 改
int findList(SeqList&, dataType); // 查
// ----------------------------------------------------
bool appendList(SeqList&, dataType); // 尾部追加数据 --- 增的扩展
bool popList(SeqList&); // 删除尾部数据 --- 删的扩展
// ----------------------------------------------------int main()
{// 创建顺序表SeqList myList;// 初始化顺序表bool res = initList(myList, 5); // 指定顺序表的数据空间为5个(res == true) ? printf("顺序表初始化成功！\n") : printf("顺序表初始化失败！\n");// 获取顺序表元素个数int size = sizeList(myList);printf("顺序表中元素的个数：%d\n", size);// 输出顺序表中的内容printList(myList);// 插入数据insertList(myList, 10, 0);insertList(myList, 20, 0);insertList(myList, 30, 0);insertList(myList, 40, 0);printList(myList);// 删除数据deleteList(myList, 2); // 删除顺序表中下标为2的元素printList(myList);// 修改数据modifyList(myList, 66, 2); // 将顺序表中下标为2的元素修改为66printList(myList);// 查找数据int searchTarget = 40;int index = findList(myList, searchTarget);printf("元素%d的下标：%d\n", searchTarget, index);// 尾部追加appendList(myList, 50);printList(myList);// 尾部删除popList(myList);printList(myList);// 销毁顺序表destroyList(myList);char justPause = getchar(); // 让程序暂停一下return 0;
}// 功能实现：
// ----------------------------------------------------
// 初始化顺序表
bool initList(SeqList& sl, int capacity)
{// 开辟空间，形成一个表，并记录表的地址sl.arr = (dataType*)malloc(sizeof(dataType) * capacity);if (sl.arr == NULL) return false; // 开辟空间失败// 其他初始化操作sl.capacity = capacity; // 初始化表的容量sl.size = 0; // 初始化表中元素的个数return true;
}// 销毁顺序表
void destroyList(SeqList& sl)
{free(sl.arr); // 释放内存空间sl.arr = NULL;sl.size = 0;sl.capacity = 0;
}// 获取顺序表元素个数
int sizeList(SeqList& sl)
{return sl.size;
}// 输出顺序表中的内容
void printList(SeqList& sl)
{printf("[ ");for (int i = 0; i < sl.size; i++){printf("%d, ", sl.arr[i]);}printf("]\n");
}// 自动扩容
bool expandList(SeqList& sl, int size)
{// 开辟一片新内存空间dataType* p = (dataType*)malloc(sizeof(dataType) * (sl.capacity + size));if (sl.arr == NULL) return false; // 扩容失败// 开辟成功，将数据迁移到新的空间for (int i = 0; i < sl.size; i++){p[i] = sl.arr[i];}// 释放原来的空间free(sl.arr);// 更新数据sl.capacity += size;sl.arr = p;p = NULL;return true;
}// ----------------------------------------------------// 插入数据
bool insertList(SeqList& sl, dataType element, int index)
{// 判断下标是否合法if (index < 0 || index > sl.size) return false;// 判断顺序表是否已经满了，如果满了，进行扩容操作if (sl.size == sl.capacity){if (expandList(sl, 10) == false) return false; // 扩容：10个数据空间}// 元素迁移for (int i = sl.size; i > index; --i){sl.arr[i] = sl.arr[i - 1];}// 在目标位置插入元素sl.arr[index] = element;// 更新表中元素的个数sl.size++;return true;
}// 删除数据
bool deleteList(SeqList& sl, int index)
{// 判断表是否为空if (sl.size == 0) return false;// 判断插入的下标是否合法if (index < 0 || index > sl.size - 1) return false;// 数据覆盖for (int i = index; i < sl.size - 1; i++){sl.arr[i] = sl.arr[i + 1];}// 更新数据sl.size--; // 这里实现了逻辑删除，而不是实际删除，因为也没有必要进行实际删除return true;
}// 修改数据
bool modifyList(SeqList& sl, dataType element, int index)
{// 判断插入的下标是否合法if (index < 0 || index > sl.size - 1) return false;// 修改数据sl.arr[index] = element;return true;
}// 查找数据
int findList(SeqList& sl, dataType element)
{for (int i = 0; i < sl.size; i++){if (sl.arr[i] == element) return i;}return -1; // 查找不到元素，返回-1
}// ----------------------------------------------------// 尾部追加
bool appendList(SeqList& sl, dataType element)
{return insertList(sl, element, sl.size);
}// 尾部删除
bool popList(SeqList& sl)
{return deleteList(sl, sl.size - 1);
}
C++实现
#include <iostream>// 定义顺序表类
template<class T> // 顺序表存储的数据类型为T
class SeqList
{
private:// 顺序表的属性:T* arr; // 记录表的地址int capacity; // 记录表的容量int size; // 记录表中元素的个数public:// 顺序表提供的方法（类内声明）// ----------------------------------------------------SeqList(); // 初始化顺序表~SeqList(); // 销毁顺序表int sizeList(); // 获取顺序表元素个数void printList(); // 输出顺序表中的内容bool expandList(); // 自动扩容// ----------------------------------------------------bool insertList(T, int); // 增bool deleteList(int); // 删bool modifyList(T, int); // 改int findList(T); // 查// ----------------------------------------------------bool appendList(T); // 尾部追加数据 --- 增的扩展bool popList(); // 删除尾部数据 --- 删的扩展// ----------------------------------------------------
};int main()
{// 创建顺序表 + 初始化顺序表SeqList<int> sl;// 获取顺序表元素个数int size = sl.sizeList();printf("顺序表中元素的个数：%d\n", size);// 输出顺序表中的内容sl.printList();// 插入数据sl.insertList(10, 0);sl.insertList(20, 0);sl.insertList(30, 0);sl.insertList(40, 0);sl.printList();// 删除数据sl.deleteList(2); // 删除顺序表中下标为2的元素sl.printList();// 修改数据sl.modifyList(66, 2); // 将顺序表中下标为2的元素修改为66sl.printList();// 查找数据int searchTarget = 40;int index = sl.findList(searchTarget);printf("元素%d的下标：%d\n", searchTarget, index);// 尾部追加sl.appendList(50);sl.printList();// 尾部删除sl.popList();sl.printList();// 销毁顺序表// 不用手动销毁，因为对象被回收时会自动调用析构函数system("pause"); // 让程序暂停一下return 0;
}// 顺序表提供的方法（类外实现）
// ----------------------------------------------------
// 初始化顺序表
template<class T>
SeqList<T>::SeqList()
{this->arr = new T[capacity]; // 创建表空间this->capacity = capacity; // 记录表的容量this->size = 0; // 记录表中元素的个数
}// 销毁顺序表
template<class T>
SeqList<T>::~SeqList()
{delete this->arr; // 释放表空间this->capacity = 0; // 容量大小置空this->size = 0; // 元素个数置空
}// 获取顺序表元素个数
template<class T>
int SeqList<T>::sizeList()
{return this->size;
}// 输出顺序表中的内容
template<class T>
void SeqList<T>::printList()
{std::cout << "[ ";for (int i = 0; i < this->size; i++){std::cout << this->arr[i] << ", ";}std::cout << "]" << std::endl;
}// 自动扩容
template<class T>
bool SeqList<T>::expandList()
{// 开辟新的内存空间T* temp = new T[this->capacity + 10]; // 每次扩容10个空间if (temp == nullptr) return false;// 将数据迁移到新的内存空间for (int i = 0; i < this->size; i++){temp[i] = this->arr[i];}// 释放原来的空间delete this->arr;// 更新数据this->arr = temp;this->capacity += size;temp = nullptr;return true;
}// ----------------------------------------------------// 插入数据
template<class T>
bool SeqList<T>::insertList(T element, int index)
{// 判断下标是否合法if (index < 0 || index > this->size) return false;// 判断顺序表是否已经满了，如果满了，进行扩容操作if (this->size == this->capacity) expandList();// 元素迁移for (int i = size; i > index; i--){this->arr[i] = this->arr[i - 1];}// 在目标位置插入元素this->arr[index] = element;// 更新数据this->size++;return true;
}// 删除数据
template<class T>
bool SeqList<T>::deleteList(int index)
{// 判断下标是否合法if (index < 0 || index > this->size - 1) return false;// 数据覆盖for (int i = index; i < this->size - 1; i++){this->arr[i] = this->arr[i + 1];}// 更新数据this->size--;return true;
}// 修改数据
template<class T>
bool SeqList<T>::modifyList(T element, int index)
{// 判断下标是否合法if (index < 0 || index > this->size - 1) return false;// 修改数据this->arr[index] = element;return true;
}// 查找数据
template<class T>
int SeqList<T>::findList(T element)
{for (int i = 0; i < this->size; i++){if (this->arr[i] == element) return i;}return -1; // 查找不到结果，返回-1
}// ----------------------------------------------------// 尾部追加
template<class T>
bool SeqList<T>::appendList(T element)
{return insertList(element, this->size);
}// 尾部删除
template<class T>
bool SeqList<T>::popList()
{return deleteList(this->size - 1);
}
2.链表
需求分析
/*创建链表具体功能：初始化链表销毁链表获取链表元素个数输出链表中的内容插入数据删除数据修改数据查找数据尾部追加尾部删除*/
C语言实现
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>// 数据类型
typedef int dataType;// 节点的结构
typedef struct Node
{dataType data; // 用来存放数据Node* next; // 用来存放下一个节点的内存地址
}Node;// // -------------------------- 功能声明 --------------------------
void init(Node*);
int size(Node*);
void print(Node*);
bool insert(Node*, dataType, int);
bool remove(Node*, int);
bool modify(Node*, dataType, int);
int find(Node*, dataType);
bool append(Node*, dataType);
bool pop(Node*);
void destroy(Node*);int main()
{// 创建链表 (创建一个头节点)Node headNode;// 初始化链表 (初始化头节点)init(&headNode);// 获取链表元素个数printf("链表元素的个数：%d\n", size(&headNode));// 输出链表中的内容print(&headNode);// 插入数据insert(&headNode, 66, 1);insert(&headNode, 77, 1);insert(&headNode, 88, 1);print(&headNode);// 删除数据remove(&headNode, 1);print(&headNode);// 修改数据modify(&headNode, 99, 0);print(&headNode);// 查找数据int index = find(&headNode, 66);(index == -1) ? printf("查找不到此数据！\n") : printf("查到此数据的下标：%d\n", index);// 尾部追加append(&headNode, 6666);print(&headNode);// 尾部删除pop(&headNode);print(&headNode);// 销毁链表destroy(&headNode);char justPause = getchar(); // 让程序暂停return 0;
}// -------------------------- 功能实现 --------------------------
// 初始化链表
void init(Node* node)
{node->next = NULL;
}// 获取链表元素个数
int size(Node* node)
{// 默认就有1个元素 (即:头节点)int size = 1;// node 是一个整体，请把 node->next 也看作是一个整体，如果 node->next 这个整体不为 NULL，说明这个整体对应的空间有数据(元素)！！while (node->next){size++;node = node->next;}return size;
}// 输出链表中的内容
void print(Node* node)
{printf("(*) -> ");while (node->next){node = node->next;printf("%d -> ", node->data);}printf("\n");
}// 插入数据
bool insert(Node* node, dataType element, int index)
{// 检查下标是否合法 (检查左边界)if (index < 1) return false;// 根据index确定步长，将node更新(移动)对应的次数// 更新(移动)结束后，node关联的就是要被插的节点的上一个节点while (--index){node = node->next;if (node == NULL) return false;}// 将数据放到新节点中Node* temp = (Node*)malloc(sizeof(Node)); // 申请一块内存作为新节点if (temp == NULL) return false; // 申请内存空间失败temp->data = element; // 在新节点里面存放要插入的数据// 完成节点的插入 (下面代码顺序不可替换!!)temp->next = node->next;node->next = temp;return true;
}// 删除数据
bool remove(Node* node, int index)
{// 检查下标是否合法 (检查左边界)if (index < 1) return false;// 根据index确定步长，将node更新(移动)对应的次数// 更新(移动)结束后，node关联的就是要被删除的节点的上一个节点while (--index){node = node->next;if (node == NULL) return false;}// 删除节点Node* temp = node->next; // 先引用一下待会将要被删除的节点，防止丢失内存地址而无法真正删除node->next = node->next->next; // 实现逻辑删除free(temp); // 释放内存空间，实现了真正的删除，并且回收了资源return true;
}// 修改数据
bool modify(Node* node, dataType element, int index)
{// 检查下标是否合法 (检查左边界)if (index < 1) return false;// 根据index确定步长，将node更新(移动)对应的次数// 更新(移动)结束后，node关联的就是要被修改的节点的上一个节点while (--index){node = node->next;if (node == NULL) return false;}// 修改数据node->next->data = element;return true;
}// 查找数据
int find(Node* node, dataType element)
{int index = 0; // 头节点的下标为0，其他节点的下标可以在此基础上通过累加计算得到while (node->next){node = node->next;index++;if (node->data == element) return index; // 找到了数据，返回对应的下标号}return -1; // 找不到数据，返回-1
}// 尾部追加
bool append(Node* node, dataType element)
{// 一直循环，直到 node->next 整体为NULL为止// 循环结束后，此时的 node 关联着最后一个节点while (node->next){node = node->next;}Node* temp = (Node*)malloc(sizeof(Node)); // 申请内存空间，制作新节点if (temp == NULL) return false; // 申请失败// 将数据放到到新节点中temp->data = element;temp->next = NULL;// 尾节点指向新节点node->next = temp;return true;
}// 尾部删除
bool pop(Node* node)
{// 如果这个链表只有头节点，而没有后面的数据节点：if (node->next == NULL) return false;// 如果有数据节点：// 一直循环，直到 node->next 整体为NULL为止// 循环结束后，此时的 node 关联的是最后一个节点，而 prev 则关联着倒数第二个节点Node* prev = NULL;while (node->next){prev = node; // 先记录旧的nodenode = node->next; // 再创建新的node}// 释放最后一个节点的内存free(node);// 将倒数第二个节点的next指向NULLprev->next = NULL;return true;
}// 销毁链表
void destroy(Node* node)
{// 释放头节点以外的所有节点的内存空间，堆区的空间// 注意：不可手动释放头节点的内存空间，因为它是main主函数的变量，栈区里面的变量Node* temp = NULL;while (node->next){temp = node->next; // 先备份一下节点的指针node->next = node->next->next;free(temp);}
}
C++实现
#include<iostream>// 节点
template <class T>
class Node
{
public:T data; // 用来存放数据Node<T>* next; // 用来存放下一个节点的内存地址// 构造函数Node(){this->next = nullptr;}// 析构函数~Node(){this->next = nullptr;}
};// 链表
template<class T = int> // 默认模板参数为int类型
class Link
{
private:Node<T>* head; // 用来记录头节点指针int size; // 用来记录链表中元素的个数public:// -------------------------- 功能类内声明 --------------------------Link();~Link();int getSize();void printLink();bool insert(T, int);bool remove(int);bool modify(T, int);int find(T);bool append(T);bool pop();
};int main()
{// 创建链表 + 初始化链表Link<> myLink;// 获取链表元素个数printf("链表元素的个数：%d\n", myLink.getSize());// 输出链表中的内容myLink.printLink();// 插入数据myLink.insert(66, 1);myLink.insert(77, 1);myLink.insert(88, 1);myLink.insert(99, 1);myLink.printLink();// 删除数据myLink.remove(1);myLink.printLink();// 修改数据myLink.modify(100, 2);myLink.printLink();// 查找数据int index = myLink.find(66);(index == -1) ? printf("查找不到此数据！\n") : printf("查到此数据的下标：%d\n", index);// 尾部追加myLink.append(1024);myLink.printLink();// 尾部删除myLink.pop();myLink.printLink();// 销毁链表// 自动会调用析构函数去销毁链表，无需手动操作system("pause"); // 让程序暂停return 0;
}// -------------------------- 功能类外实现 --------------------------
// 初始化链表
template<class T>
Link<T>::Link()
{this->head = new Node<T>; // 创建一个头节点，并让 this->head 能够指向这个头节点this->size = 1; // 链表元素个数
}// 销毁链表
template<class T>
Link<T>::~Link()
{// 释放其他节点Node<T>* temp = nullptr;while (this->head->next) // 判断头节点的下一个节点是否为空，如果不为空，说明节点里面有数据，需要删除这个节点{temp = this->head->next; // 先备份好内存地址，方便待会删除这个地址所指向的节点this->head->next = this->head->next->next; // 将头节点连接"要被删除节点"的下一个节点delete temp; // 删除节点}// 释放头节点delete this->head;this->head = nullptr;// 链表元素个数置零this->size = 0;
}// 获取链表元素个数
template<class T>
int Link<T>::getSize()
{return this->size;
}// 输出链表中的内容
template<class T>
void Link<T>::printLink()
{Node<T>* temp = this->head->next; // 头节点的下一个节点std::cout << "(*) -> ";while (temp) // 如果 temp 不是 nullptr 空指针，则说明当前节点有数据，可以进入循环内部，输出数据{std::cout << temp->data << " -> ";temp = temp->next;}std::cout << std::endl;
}// 插入数据
template<class T>
bool Link<T>::insert(T data, int index)
{// 检查下标是否合法，可插入的范围是 [1, this->size]if (index < 1 || index > this->size) return false;// 获取目标节点的上一个节点Node<T>* targetNodePre = this->head;for (int i = 0; i < index - 1; i++){targetNodePre = targetNodePre->next;}// 创建新节点，并将数据存放到里面Node<T>* newNode = new Node<T>;newNode->data = data;// 将新节点插入到链表中newNode->next = targetNodePre->next;targetNodePre->next = newNode;// 更新元素个数this->size++;return true;
}// 删除数据
template<class T>
bool Link<T>::remove(int index)
{// 检查下标是否合法，可删除的范围是 [1, this->size -1]if (index < 1 || index > this->size) return false;// 获取目标节点的上一个节点Node<T>* targetNodePre = this->head;for (int i = 0; i < index - 1; i++){targetNodePre = targetNodePre->next;}// 删除节点Node<T>* temp = targetNodePre->next; // 先引用一下待会将要被删除的节点，防止丢失内存地址而无法真正删除targetNodePre->next = targetNodePre->next->next; // 实现逻辑删除delete temp; // 释放内存空间，实现了真正的删除，并且回收了资源// 更新元素个数this->size--;return true;
}// 修改数据
template<class T>
bool Link<T>::modify(T data, int index)
{// 检查下标是否合法，可修改的范围是 [1, this->size -1]if (index < 1 || index > this->size) return false;// 获取目标节点的上一个节点Node<T>* targetNodePre = this->head;for (int i = 0; i < index - 1; i++){targetNodePre = targetNodePre->next;}// 修改数据targetNodePre->next->data = data;return true;
}// 查找数据
template<class T>
int Link<T>::find(T data)
{int index = 0; // 头节点的下标为0，其他节点的下标可以在此基础上通过累加计算得到Node<T>* targetNodePre = this->head;while (targetNodePre->next) // 如果不为空指针nullptr，说明里面有数据{targetNodePre = targetNodePre->next;index++;if (targetNodePre->data == data) return index; // 找到了数据，返回对应的下标号}return -1; // 找不到数据，返回-1
}// 尾部追加
template<class T>
bool Link<T>::append(T data)
{return insert(data, this->size);
}// 尾部删除
template<class T>
bool Link<T>::pop()
{return remove(this->size - 1);
}
3.扩展
双向链表
/*C++实现双向链表：1.插入数据2.删除数据3.展示数据
*/#include<iostream>// 节点
template<class T>
class Node
{
public:T data;Node* next;Node* prev;Node(){this->next = nullptr;this->prev = nullptr;}~Node(){this->next = nullptr;this->prev = nullptr;}
};// 链表
template<class T = int>
class Link
{
private:Node<T>* head;int size;public:Link(){this->head = new Node<T>;this->size = 1;}~Link(){// 释放其他节点Node<T>* temp = nullptr;while (this->head->next){temp = this->head->next;this->head->next = this->head->next->next;delete temp;}// 释放头节点delete this->head;this->head = nullptr;this->size = 0;}bool insert(T data, int index){// 下标合法性校验if (index < 1 || index > this->size) return false;// 获取目标节点的前驱节点Node<T>* targetNodePre = this->head;for (int i = 1; i < index; i++){targetNodePre = targetNodePre->next;}// 创建新节点，并装入数据Node<T>* newNode = new Node<T>;newNode->data = data;// 将新节点插入到链表中 [...targetNodePre <===> targetNodePre->next] <--- newNodenewNode->next = targetNodePre->next;newNode->prev = targetNodePre;if (targetNodePre->next != nullptr) targetNodePre->next->prev = newNode;targetNodePre->next = newNode;// 更新节点个数this->size++;return true;}bool remove(int index){// 下标合法性校验if (index < 1 || index > this->size - 1) return false;// 获取目标节点Node<T>* targetNode = this->head;for (int i = 1; i <= index; i++){targetNode = targetNode->next;}// 删除操作 [targetNode->prev <===> targetNode <===> targetNode->next]if (targetNode->next != nullptr) targetNode->next->prev = targetNode->prev;targetNode->prev->next = targetNode->next;delete targetNode;// 更新节点个数this->size--;return true;}void printLink(){std::cout << "(*) <==> ";Node<T>* temp = this->head;while (temp->next){temp = temp->next;std::cout << temp->data << " <==> ";}std::cout << std::endl;}
};// 主函数
int main()
{// 创建链表并初始化Link<int> myLink;myLink.printLink();// 插入数据myLink.insert(10, 1);myLink.printLink();myLink.insert(20, 2);myLink.printLink();myLink.insert(30, 3);myLink.printLink();// 删除数据myLink.remove(1);myLink.printLink();myLink.remove(1);myLink.printLink();myLink.remove(1);myLink.printLink();system("pause");return 0;
}
循环链表
特殊线性表
1.栈
通过顺序表实现
// C++#include<iostream>
#include<string>
using namespace std;template<class T>
class Stack
{
public:T* arr; // 栈空间int capacity; // 栈的容量int top; // 用于记录栈顶的位置Stack(){this->arr = new T[10]; // 开辟空间this->capacity = 10;this->top = -1;}~Stack(){delete[] this->arr; // 释放空间this->capacity = 0;this->top = -1;}// 入栈Stack& push(T data){top++;this->arr[top] = data;return *this;}// 出栈Stack& pop(){top--;return *this;}// 输出栈里面的内容void show(){string symbol = "";for (int i = 0; i <= top; i++){symbol += "----";}cout << "*" << symbol << endl << "| ";for (int i = 0; i <= top; i++){std::cout << this->arr[i] << " ";}cout << endl << "*" << symbol << endl << endl;}
};int main()
{Stack<int> s;// 入栈s.push(10);s.push(20);s.push(30).show();// 出栈s.pop().show();s.pop().show();s.pop().show();system("pause");return 0;
}
通过链表实现
// C++#include<iostream>
#include<string>
using namespace std;// 节点
template<class T>
class Node
{
public:T data;Node* next;Node(){this->next = nullptr;}
};// 栈（通过链表实现的栈）
template<class T>
class Stack
{
public:Node<T>* head; // 头节点int size; // 用于记录栈中的元素个数Stack(){this->head = new Node<T>; // 创建头节点this->size = 0;}~Stack(){// 释放其他节点Node<T>* temp = nullptr;while (this->head->next){temp = this->head->next;this->head->next = this->head->next->next;delete temp;}// 释放头节点delete this->head;this->head = nullptr;this->size = 0;}// 入栈Stack& push(T data){// 创建新节点，并存放数据Node<T>* newNode = new Node<T>;newNode->data = data;// 插入新节点newNode->next = this->head->next;this->head->next = newNode;// 更新元素个数size++;return *this;}// 出栈Stack& pop(){// 删除节点Node<T>* temp = nullptr;if (this->head->next){temp = this->head->next;this->head->next = this->head->next->next;delete temp;}// 更新元素个数size--;return *this;}// 输出栈里面的内容void show(){string symbol = "";for (int i = 0; i < this->size; i++){symbol += "----";}cout << "*" << symbol << endl << "| ";if (this->size == 0){cout << endl << "*" << symbol << endl << endl;return;}Node<T>** arr = new Node<T>*[this->size];int index = 0;Node<T>* temp = this->head;while (temp->next){temp = temp->next;arr[index] = temp;index++;}for (int i = this->size - 1; i > -1; i--){std::cout << arr[i]->data << " ";}cout << endl << "*" << symbol << endl << endl;delete[] arr;}
};int main()
{Stack<int> s;// 入栈s.push(10);s.push(20);s.push(30).show();// 出栈s.pop().show();s.pop().show();s.pop().show();system("pause");return 0;
}
2.队列
通过顺序表实现
// C++#include<iostream>
#include<string>
using namespace std;// 队列所存储数据的类型
typedef int E;// 队列 (通过顺序表实现循环队列)
class Queue
{
public:E* arr; // 用于记录队列的内存地址int capacity; // 用于记录队列的容量int size; // 用于记录队列中元素的个数int front; // 用于记录队首位置int rear; // 用于记录队尾位置Queue(){this->capacity = 5;this->arr = new E[this->capacity];this->size = 0;this->front = this->rear = 0;}~Queue(){delete[] this->arr;this->arr = nullptr;this->capacity = 0;this->size = 0;this->front = this->rear = 0;}// 入队Queue& enqueue(E data){// 判断队列是否已满if (this->size == this->capacity) return *this;// 循环入队this->arr[rear] = data;this->size++;this->rear++;this->rear %= this->capacity; // 循环队列的核心算法return *this;}// 出队Queue& dequeue(){// 判断队列是否为空if (size == 0) return *this;// 循环出队this->front++;this->size--;this->front %= this->capacity; // 循环队列的核心算法return *this;}// 输出void show(){string symbol = "";for (int i = 0; i < this->size; i++){symbol += "<<<<";}if (this->size == 0) symbol = "<<<<";cout << symbol << endl;for (int i = this->front; i < this->front + this->size; i++){cout << this->arr[i % this->capacity] << " ";}cout << endl << symbol << endl << endl;}
};int main()
{Queue q; // 创建并初始化队列q.show(); // 输出队列里面的内容// 入队q.enqueue(10).show();q.enqueue(20).show();q.enqueue(30).show();// 出队q.dequeue().show();q.dequeue().show();q.dequeue().show();system("pause");return 0;
}
通过链表实现
// C++#include<iostream>
#include<string>
using namespace std;// 队列所存储数据的类型
typedef int E;// 节点
class Node
{
public:E data;Node* next;Node(){this->next = nullptr;}
};// 队列 (通过顺序表实现循环队列)
class Queue
{
public:Node* head; // 头节点（队首）Node* tail; // 尾节点（队尾）int size; // 用于记录队列中元素的个数Queue(){this->head = new Node;this->tail = this->head;this->size = 0;}~Queue(){// 释放其他节点Node* temp = nullptr;while (this->head->next){temp = this->head->next;this->head->next = this->head->next->next;delete temp;}// 释放头节点delete this->head;this->head = this->tail = nullptr;this->size = 0;}// 入队Queue& enqueue(E data){// 创建新节点，并存入数据Node* newNode = new Node;newNode->data = data;newNode->next = nullptr;// 将新节点插入到队尾this->tail->next = newNode;this->tail = newNode;// 更新数据this->size++;return *this;}// 出队Queue& dequeue(){// 回收内存空间Node* temp = nullptr;if (this->head->next){temp = this->head->next;this->head->next = this->head->next->next;delete temp;}// 更新数据this->size--;return *this;}// 输出void show(){string symbol = "";for (int i = 0; i < this->size; i++){symbol += "<<<<";}if (this->size == 0) symbol = "<<<<";cout << symbol << endl;Node* temp = this->head;while (temp->next){temp = temp->next;cout << temp->data << " ";}cout << endl << symbol << endl << endl;}
};int main()
{Queue q; // 创建并初始化队列q.show(); // 输出队列里面的内容// 入队q.enqueue(10).show();q.enqueue(20).show();q.enqueue(30).show();// 出队q.dequeue().show();q.dequeue().show();q.dequeue().show();system("pause");return 0;
}
这篇关于数据结构与算法---线性表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
