C/C++ 数据结构与算法
- 线性表(Linear List)
- 顺序存储结构
- 顺序表(Sequence List)
- 顺序栈(Sequence Stack)
- 循环队列(Circular Queue)
- 链式存储结构
- 单链表(Singly Linked List)
- 双链表(Doubly Linked List)
- 循环链表(Circular Linked List)
- 链栈(Linked Stack)
- 链队列(Linked Queue)
- 顺序存储结构
#ifndef _H_LINEARLIST #define _H_LINEARLIST #include <iostream> #include <stdexcept> using namespace std; // 线性表头文件(Linear List header file) // 导入各种数据结构头文件 // 线性表的顺序存储 #include "SequenceList.h" // 顺序表 #include "SequenceStack.h" // 顺序栈 #include "CircularQueue.h" // 循环队列 // 线性表的链式存储 #include "SinglyLinkedLIst.h" // 单链表 #include "LinkedStack.h" // 链栈 #include "LinkedQueue.h" // 链队列 #endif
LinearList.h
#ifndef _H_SEQUENCELIST #define _H_SEQUENCELIST // 顺序表定义头文件(Sequence List) namespace SequenceList { // SqList,顺序表类,成员有存储MAXSIZE个T类型数据的数组 template <typename T, size_t MAXSIZE> class SqList { private: T *data; size_t length; size_t size; public: // 初始化SqList SqList() { this->size = MAXSIZE; this->data = new T[this->size]; this->length = 0; } // 析构化SqList ~SqList() { free(this->data); } // 是否为空 bool Empty() const { return this->length == 0; } // 是否已满 bool Full() const { return this->length == this->size; } // 返回长度 size_t Length() const { return this->length; } // 返回大小 size_t Size() { return this->size; } // 清除顺序表 void Clear() { free(this->data); this->size = MAXSIZE; this->data = new T[this->size]; this->length = 0; } // 获得index上的数据 T GetElem(const size_t &index) { if (this->Empty()) { throw out_of_range("SqList<T>: List is empty!\n"); } else if (index <= 0 || index > this->length) { throw out_of_range("SqList<T>: Index out of range!\n"); } else { return this->data[index-1]; } } // 返回elem在SqList中的索引,如果找不到,返回0 size_t LocateElem(const T &elem) { size_t index = 1; for (int i = 0; i < this->length; ++i, ++index) { if (this->data[i] == elem) { return index; } } return 0; } // 在index位置上插入元素elem,所有index之后的元素向后移动一位 void InsertElem(const size_t &index, const T &elem) { if (this->Full()) { throw out_of_range("SqList<T>: List is full!\n"); } else if (index <= 0 || index > this->length + 1) { throw out_of_range("SqList<T>: Index out of range!\n"); } else { int i; for (i = this->length; i > index-1; --i) { this->data[i] = this->data[i-1]; } this->data[i] = elem; ++this->length; } } // 删除index上的元素elem,所有index之后的元素向前一位 void DeleteElem(const size_t &index) { if (this->Empty()) { throw out_of_range("SqList<T>: List is empty!\n"); } else if (index <= 0 || index > this->length) { throw out_of_range("SqList<T>: Index out of range!\n"); } else { for (int i = index-1; i < this->length - 1; ++i) { this->data[i] = this->data[i+1]; } --this->length; } } // 扩大顺序表,size += extra void Expand(size_t extra) { if (extra != 0) { T *tmp = this->data; this->data = new T[this->size + extra]; // memcpy(destination, source, size) memcpy(this->data, tmp, this->length * sizeof(T)); free(tmp); this->size += extra; } } // 打印SqList friend ostream &operator<<(ostream &os, const SqList &sql) { if (sql.Empty()) { os << "SqList<T>[0]: {}" << endl; } else { os << "SqList<T>[" << sql.length << ", " << sql.size << "]: {"; for (int i = 0; i < sql.length; ++i) { os << sql.data[i] << ", "; } os << "\b\b}" << endl; } return os; } }; } #endif
SequenceList.h
// SequenceStack.h #ifndef _H_SEQUENCESTACK #define _H_SEQUENCESTACK // 顺序栈定义头文件(Sequence Stack) namespace SequenceStack { template <typename T, size_t MAXSIZE> class SqStack { private: T *data; // 数组 size_t topPtr; // 栈顶指针 size_t length; // 长度 size_t size; // 大小 public: // 初始化 SqStack() { this->size = MAXSIZE; this->data = new T[this->size]; this->length = 0; this->topPtr = -1; } // 析构化 ~SqStack() { free(this->data); } // 是否为空 bool Empty() const { return this->length == 0; }; // 是否已满 bool Full() const { return this->length == this->size; } // 返回长度 size_t Length() const { return this->length; } // 返回大小 size_t Size() const { return this->size; } // 清除顺序栈 void Clear() { free(this->data); this->size = MAXSIZE; this->data = new T[this->size]; this->length = 0; this->topPtr = -1; } // 获取栈顶指针数据 T Top() { if (this->Empty()) { throw out_of_range("SqStack<T>: stack is empty!\n"); } else { return this->data[this->topPtr]; } } // 压入栈 void Push(const T &elem) { if (this->Full()) { throw out_of_range("SqStack<T>: stack is full!\n"); } else { ++this->topPtr; this->data[this->topPtr] = elem; ++this->length; } } // 弹出栈 void Pop() { if (this->Empty()) { throw out_of_range("SqStack<T>: stack is empty!\n"); } else { --this->topPtr; --this->length; } } // 扩大顺序栈,size += extra void Expand(const size_t &extra) { if (extra != 0) { T *tmp = this->data; this->data = new T[this->size + extra]; // memcpy(destination, source, size) memcpy(this->data, tmp, this->length * sizeof(T)); free(tmp); this->size += extra; } } // 打印栈 friend ostream &operator<<(ostream &os, const SqStack &sq) { os << "SqStack<T>[" << sq.length << ", " << sq.size << "] {"; if (sq.Empty()) { os << "}" << endl; } else { for (int i = sq.topPtr; i >= 0; --i) { os << sq.data[i] << ", "; } os << "\b\b}" << endl; } return os; } }; } #endif
SequenceStack.h
// CircularQueue.h #ifndef _H_CIRCULARQUEUE #define _H_CIRCULARQUEUE // 循环队列定义头文件(Circular Queue) namespace CircularQueue { template <typename T, size_t MAXSIZE> class CuQueue { private: T *data; // 数组 size_t head; // 头指针 size_t rear; // 尾指针 size_t length; // 长度 size_t size; // 大小 public: // 构造器 CuQueue() { this->head = 0; this->rear = 0; this->length = 0; this->size = MAXSIZE; this->data = new T[this->size]; } // 析构器 ~CuQueue() { free(this->data); } // 是否为空 bool Empty() const { return this->length == 0; } // 是否已满 bool Full() const { return this->size == this->length; } // 返回长度 size_t Length() const { return this->length; } // 返回大小 size_t Size() const { return this->size; } // 清除队列 void Clear() { free(this->data); this->size = MAXSIZE; this->data = new T[this->size]; this->length = 0; this->head = 0; this->rear = 0; } // 返回队列头元素 T Head() { if (this->Empty()) { throw out_of_range("CuQueue<T>: queue is empty!\n"); } else { return this->data[this->head]; } } // 进列 void EnQueue(const T &elem) { if (this->Full()) { throw out_of_range("CuQueue<T>: queue is full!\n"); } else { // 当head和rear指向同一个位置时,队列为空 this->data[this->rear] = elem; ++this->rear; ++this->length; if (this->rear == this->size) { this->rear = 0; } } } // 出列 void DeQueue() { if (this->Empty()) { throw out_of_range("CuQueue<T>: queue is empty!\n"); } else { ++this->head; --this->length; if (this->head == this->size) { this->head = 0; } } } // 扩大循环队列,size += extra void Expand(const size_t &extra) { if (extra != 0) { T *tmp = this->data; this->data = new T[this->size + extra]; // memcpy(destination, source, size) memcpy(this->data, tmp, this->length * sizeof(T)); free(tmp); this->size += extra; } } // 打印循环队列 friend ostream &operator<<(ostream &os, const CuQueue &cq) { os << "CuQueue<T>:[" << cq.length << ", " << cq.size << "][" << cq.head << ", " << cq.rear << "]: {"; if (cq.Empty()) { os << "}" << endl; } else { int index = cq.head; for (int i = 0; i < cq.length; ++i, ++index) { if (index == cq.size) { index = 0; } os << cq.data[index] << ", "; } os << "\b\b}" << endl; } return os; } }; } #endif
CircularQueue.h
#ifndef _H_SINGLYLINKEDLIST #define _H_SINGLYLINKEDLIST // 单链表定义头文件(Singly Linked List) namespace SinglyLinkedList { template <typename T> class SgNode { private: T elem; SgNode<T> *next; public: template <typename I> friend class SgList; T Elem() { return this->elem; } SgNode<T> *Next() { return this->next; } SgNode() {} }; template <typename T> class SgList { private: SgNode<T> *head; size_t length; public: // 初始化 SgList() { this->head = NULL; this->length = 0; } // 析构,删除每个节点 ~SgList() { SgNode<T> *tmp; for (SgNode<T> *node = this->head; node;) { tmp = node; node = node->next; delete tmp; } } // 是否为空 bool Empty() const { return this->length == 0; } // 长度 size_t Length() const { return this->length; } // 清除单链表 void Clear() { SgNode<T> *tmp; for (SgNode<T> *node = this->head; node;) { tmp = node; node = node->next; delete tmp; } this->head = NULL; this->length = 0; } // 获取index上的elem T GetElem(const size_t &index) { if (this->Empty()) { throw out_of_range("SgList<T>: List is empty!\n"); } else if (index <= 0 || index > this->length) { throw out_of_range("SgList<T>: Index out of range!\n"); } else { SgNode<T> *node = this->head; for (int i = 1; i < index; ++i) { node = node->next; } return node->elem; } } // 返回elem在单链表中的索引 size_t LocateElem(const T &elem) { size_t index = 1; for (SgNode<T> *node = this->head; node; node = node->next, ++index) { if (node->elem == elem) { return index; } } return 0; } // 在index位置插入elem void InsertElem(const size_t &index, const T &elem) { if (index <= 0 || index > this->length + 1) { throw out_of_range("SgList<T>: Index out of range!\n"); } else { SgNode<T> *node = new SgNode<T>; node->elem = elem; if (index == 1) { if (this->head == NULL) { node->next = NULL; this->head = node; } else { node->next = this->head; this->head = node; } } else { // 找到index-1上的节点 SgNode<T> *prior = this->head; for (int i = 1; i < index - 1; ++i) { prior = prior->next; } node->next = prior->next; prior->next = node; } ++this->length; } } // 删除index位置上的elem void DeleteElem(const size_t &index) { if (this->Empty()) { throw out_of_range("SgList<T>: List is empty!\n"); } else if (index <= 0 || index > this->length) { throw out_of_range("SgList<T>: Index out of range!\n"); } else { if (index == 1) { SgNode<T> *node = this->head; this->head = this->head->next; delete node; } else { // 找到index-1上的节点 SgNode<T> *prior = this->head; for (int i = 1; i < index-1; ++i) { prior = prior->next; } SgNode<T> *node = prior->next; prior->next = prior->next->next; delete node; } --this->length; } } // 打印SgList friend ostream &operator<<(ostream &os, const SgList &sg) { os << "SgList<T>[" << sg.length << "]: {"; if (sg.Empty()) { os << "NULL}" << endl; } else { for (SgNode<T> *node = sg.head; node; node = node->Next()) { os << node->Elem() << " -> "; } os << "NUll}" << endl; } return os; } }; } #endif
SinglyLinkedList.h
#ifndef _H_LINKEDQUEUE #define _H_LINKEDQUEUE // 链队列的数据结构定义 namespace LinkedQueue { template <typename T> class LiNode { private: T elem; LiNode<T> *next; public: template <typename I> friend class LiQueue; LiNode() {} T Elem() { return this->elem; } LiNode<T> *Next() { return this->next; } }; template <typename T> class LiQueue { private: LiNode<T> *head; LiNode<T> *rear; size_t length; public: // 构造器 LiQueue() { this->head = NULL; this->rear = NULL; this->length = 0; } // 析构器 ~LiQueue() { LiNode<T> *tmp; for (LiNode<T> *node = this->head; node;) { tmp = node; node = node->next; delete tmp; } } // 是否为空 bool Empty() const { return this->length == 0; } // 长度 size_t Length() const { return this->length; } // 清除链队列 void Clear() { LiNode<T> *tmp; for (LiNode<T> *node = this->head; node;) { tmp = node; node = node->next; delete tmp; } this->head = NULL; this->rear = NULL; this->length = 0; } // 返回头部元素 T Head() { if (this->Empty()) { throw out_of_range("LiQueue<T>: queue is empty!\n"); } else { return this->head->elem; } } // 入队 void EnQueue(T elem) { LiNode<T> *node = new LiNode<T>; node->elem = elem; node->next = NULL; if (this->Empty()) { this->head = node; this->rear = node; } else { this->rear->next = node; this->rear = node; } ++this->length; } // 出队 void DeQueue() { if (this->Empty()) { throw out_of_range("LiQueue<T>: queue is empty!\n"); } else { if (this->length == 1) { delete this->head; this->head = NULL; this->rear = NULL; } else { LiNode<T> *node = this->head; this->head = this->head->next; delete node; } --this->length; } } // 打印链队列 friend ostream &operator<<(ostream &os, LiQueue &li) { os << "LiQueue<T>[" << li.length << "]: {"; if (li.Empty()) { os << "}" << endl; } else { for (LiNode<T> *node = li.head; node; node = node->Next()) { os << node->Elem() << ", "; } os << "\b\b}" << endl; } return os; } }; } #endif
LinkedQueue.h
- 算法(Algorithms)
- 斐波那契数列(Fibonacci)
#ifndef _H_ALGORITHMS #define _H_ALGORITHMS // 斐波那契数列 size_t Fibonacci(size_t i) { if (i < 2) return i == 0 ? 0 : 1; else return Fibonacci(i-1) + Fibonacci(i-2); } #endif
Algorithms.h
相关推荐
shenwenjie 2020-09-24
xiesheng 2020-08-02
mingyunxiaohai 2020-07-28
Cypress 2020-07-08
xhao 2020-05-05
Cypress 2020-06-28
Dyancsdn 2020-06-27
Masimaro 2020-06-21
waitwolf 2020-06-21
Jasmineyaoyao 2020-06-16
OldBowl 2020-06-16
alicelmx 2020-06-16
Masimaro 2020-06-14
waitwolf 2020-06-08
nurvnurv 2020-06-05
ustbfym 2020-06-04
ziruoxiangyi 2020-06-03
范范 2020-06-03