链表：
#ifndef LINKEDLIST_H_
#define LINKEDLIST_H_
#include <stdexcept>
using namespace std;
template<typename T>
class Node {
public:
T element;
Node<T> *next;
Node() {
next = NULL;
}
Node(T element) {
this->element = element;
next = NULL;
}
};
//----------------- Iterator -----------------
template<typename T>
class Iterator {
public:
Iterator(Node<T> *p) {
current = p;
}
Iterator &operator++() {
current = current->next;
return *this;
}
Iterator &operator++(int) {
return ++(*this);
}
T operator*() {
return current->element;
}
bool operator==(const Iterator<T> &iterator) {
return current == iterator.current;
}
bool operator!=(const Iterator<T> &iterator) {
return current != iterator.current;
}
private:
Node<T> *current;
};
//----------------- Iterator -----------------
template<typename T>
class LinkedList {
public:
LinkedList();
void addFirst(T element);
void addLast(T element);
T getFirst();
T getLast();
T get(int index);
T removeFirst() throw (runtime_error);
T removeLast() throw (runtime_error);
void add(T element);
void add(int index, T element);
void remove(T element);
T removeAt(int index) throw (runtime_error);
void clear();
int getSize();
bool isEmpty();
//----------------- Iterator -----------------
Iterator<T> begin();
Iterator<T> end();
//----------------- Iterator -----------------
private:
Node<T> *head, *tail;
int size;
};
template<typename T>
LinkedList<T>::LinkedList() {
size = 0;
head = tail = NULL;
}
template<typename T>
void LinkedList<T>::addFirst(T element) {
Node<T> *newNode = new Node<T> (element);
newNode->next = head;
head = newNode;
size++;
if (tail == NULL)
tail = head;
}
template<typename T>
void LinkedList<T>::addLast(T element) {
if (tail == NULL)
tail = head = new Node<T> (element);
else {
tail->next = new Node<T> (element);
tail = tail->next;
}
size++;
}
template<typename T>
T LinkedList<T>::getFirst() {
if (size == 0)
throw runtime_error("Index out of range.");
return head->element;
}
template<typename T>
T LinkedList<T>::getLast() {
if (size == 0)
throw runtime_error("Index out of range.");
return tail->element;
}
template<typename T>
T LinkedList<T>::get(int index) {
if (index < 0 || index > (size - 1))
throw runtime_error("Index out of range.");
else if (index == 0)
return getFirst();
else if (index == (size - 1))
return getLast();
else {
Node<T> *current = head;
for (int i = 0; i < index; i++)
current = current->next;
return current->element;
}
}
template<typename T>
T LinkedList<T>::removeFirst() throw (runtime_error) {
if (size == 0)
throw runtime_error("No elements in the list.");
Node<T> *temp = head;
head = head->next;
if (head == NULL)
tail = NULL;
size--;
T element = temp->element;
delete temp;
return element;
}
template<typename T>
T LinkedList<T>::removeLast() throw (runtime_error) {
if (size == 0)
throw runtime_error("No elements in the list.");
else if (size == 1) {
Node<T> *temp = head;
head = tail = NULL;
size = 0;
T element = temp->element;
delete temp;
return element;
} else {
Node<T> *current = head;
for (int i = 0; i < size - 2; i++)
current = current->next;
Node<T> *temp = tail;
tail = current;
tail->next = NULL;
size--;
T element = temp->element;
delete temp;
return element;
}
}
template<typename T>
void LinkedList<T>::add(T element) {
addLast(element);
}
template<typename T>
void LinkedList<T>::add(int index, T element) {
if (index == 0)
addFirst(element);
else if (index >= size)
addLast(element);
else {
Node<T> *current = head;
for (int i = 1; i < index; i++)
current = current->next;
Node<T> *temp = current->next;
current->next = new Node<T> (element);
(current->next)->next = temp;
size++;
}
}
template<typename T>
void LinkedList<T>::remove(T element) {
}
template<typename T>
T LinkedList<T>::removeAt(int index) throw (runtime_error) {
if (index < 0 || index > (size - 1))
throw runtime_error("Index out of range.");
else if (index == 0)
return removeFirst();
else if (index == (size - 1))
return removeLast();
else {
Node<T> *previous = head;
for (int i = 1; i < index; i++)
previous = previous->next;
Node<T> *current = previous->next;
previous->next = current->next;
size--;
T element = current->element;
delete current;
return element;
}
}
template<typename T>
void LinkedList<T>::clear() {
while (head != NULL) {
Node<T> *temp = head;
delete temp;
head = head->next;
}
tail = NULL;
}
template<typename T>
int LinkedList<T>::getSize() {
return size;
}
template<typename T>
bool LinkedList<T>::isEmpty() {
return head == NULL;
}
//----------------- Iterator -----------------
template<typename T>
Iterator<T> LinkedList<T>::begin() {
return Iterator<T> (head);
}
template<typename T>
Iterator<T> LinkedList<T>::end() {
return Iterator<T> (tail->next);
}
//----------------- Iterator -----------------
#endif /* LINKEDLIST_H_ */
栈：
#ifndef STACKWITHLINKEDLIST_H_
#define STACKWITHLINKEDLIST_H_
#include "LinkedList.h"
template<typename T = int>
class Stack {
public:
Stack();
bool isEmpty();
T peek();
void push(T value);
T pop();
int getSize();
private:
LinkedList<T> list;
};
template<typename T>
Stack<T>::Stack() {
}
template<typename T>
bool Stack<T>::isEmpty() {
return list.isEmpty();
}
template<typename T>
T Stack<T>::peek() {
return list.getLast();
}
template<typename T>
void Stack<T>::push(T value) {
list.addLast(value);
}
template<typename T>
T Stack<T>::pop() {
return list.removeLast();
}
template<typename T>
int Stack<T>::getSize() {
return list.getSize();
}
#endif /* STACKWITHLINKEDLIST_H_ */
队列：
#ifndef QUEUE_H_
#define QUEUE_H_
#include "LinkedList.h"
using namespace std;
template<typename T>
class Queue {
public:
Queue();
void enqueue(T element);
T dequeue() throw (runtime_error);
int getSize();
private:
LinkedList<T> list;
};
template<typename T>
Queue<T>::Queue() {
}
template<typename T>
void Queue<T>::enqueue(T element) {
list.addLast(element);
}
template<typename T>
T Queue<T>::dequeue() throw (runtime_error) {
return list.removeFirst();
}
template<typename T>
int Queue<T>::getSize() {
return list.getSize();
}
#endif /* QUEUE_H_ */
分享到：
相关推荐
顺序表、链表、栈、队列、树、Hashmap等数据结构；排序、二分法查找、树遍历等常见算法实现...单向链表 双向链表 单向循环链表 栈 队列 FIFO队列 LIFO队列 优先队列（Priority Queue） 双端队列（double-ended queue）
主要介绍了Python单向链表和双向链表原理与用法,结合实例形式详细分析了单向链表与双向链表的概念、原理以及创建、添加、删除等相关操作技巧,需要的朋友可以参考下
假定一个单向循环链表来表示队列
假定一个单向循环链表来表示队列（即循环链队），该队列只设一个队尾指针，不设队首指针，试编写下列各种运算的算法： 1） 向循环链队插入一个元素值为x的结点。 2） 从循环链队中删除一个结点。 3） 访问队列
4-12 单向循环链表删除元素复习及链表扩展 4-13 双向链表及添加元素 4-14 双向链表删除元素 五、排序与搜索 5-01 排序算法的稳定性 5-02 冒泡排序及实现 5-03 选择排序算法及实现 5-04 插入算法 5-05 插入...
//链表节点类型 //不安全的遍历 #define list_for_each(head, pos) for(pos=head->next; pos!=head; pos=pos->next) //安全的遍历 #define list_for_each_safe(head, pos, n) for(pos=head->next, n=pos->next; ...
单向链表 双向链表 循环链表 静态链表 栈（Stack） 队列（Queue） 双端队列（Deque） 循环队列 哈希表（HashTable） 树形数据结构 二叉树（BinaryTree）、二叉搜索树（BinarySearchTree、BST） 平衡二叉搜索树...
单向链表的数据结构及其相关算法：单向链表结构包含两个要素，即头结点head和链表大小size，具体操作包括： 链表的增删 链表是否为空 链表的大小 链表的打印输出 删除链表重复节点 链表倒数第K个元素 链表的反转 ...
5、编写在非递减有序链表中插入一个元素使链表元素仍有序的函数，并利用该函数建立一个非递减有序单向链表。 6、利用算法5建立两个非递减有序单向链表，然后合并成一个非递增链表。 7、利用算法5建立两个非递减有序...
java 算法：包括数组，哈希表，队列，栈，链表（双端，单向，双向），二叉树（普通二叉树，哈夫曼树，二叉查找树，平衡二叉树，二叉线索树），图这些数据结构的实现以及多种排序算法和其他一些算法的实现（递归，二...
单向链表、栈和队列、二叉树
C语言 表、栈和队列详解 表ADT 形如A1,A2,A3…An的表，这个表的大小为n，而大小为0的表称为空表，非空表中，Ai+1后继Ai，Ai-1前驱Ai，表ADT的相关操有...链表的结构有很多种，单向链表、双向链表、循环链表、有无表
队列和堆栈都是使用单向链表实现的。 安装 像安装任何其他软件包一样安装： go get github.com/fabioberger/data-structures 将要使用的数据结构添加到项目的导入中： import "github....
1、 定义栈的存储结构。 2、 编写程序实现双向栈的基本操作：1）初始化；2）判断栈是否为空；3）判断栈是否已满；4）入栈；5）出栈；6）清空栈；7）取栈顶元素。 3、 所写源代码编程风格良好，有详细注释。 4、 程序...
队列基本操作 两种情况
1．把数据存储到计算机中,...设有一个头指针为head的单向链表，p指向表中某一个结点，且有p->next= =NULL,通过操作p->next=head ，就可使该单向链表构造成单向循环链表。 8．循环队列的最大存储空间为MaxSize，队头指针
C实现一个链表类【代码】，作者 tr0217 （尧思齐 齐尧），是一个通用的C链接表，可以在TC2.0、vc6.0和gcc5.4.3中编译成功，释放链表所占用的资源，在链表使用结束后必须调用，本链表为单向链表，非常有效。...
9、栈和队列逻辑上都是线性表。（ ） 10、单链表从任何一个结点出发，都能访问到所有结点 （ ） 11、删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。（ ） 12、快速排序是排序算法中最快...