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;
}
};
}
#endifSequenceList.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;
}
};
}
#endifSequenceStack.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;
}
};
}
#endifCircularQueue.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;
}
};
}
#endifSinglyLinkedList.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;
}
};
}
#endifLinkedQueue.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);
}
#endifAlgorithms.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