队列类链式存储

代码：

linkqueue.hpp

// 队列类 #pragma once #include "linklist.hpp" template <typename T> class LinkQueue { public: LinkQueue(); ~LinkQueue(); public: int clear(); int append(T &t); int retieve(T &t); int header(T &t); int length(); protected: LinkList<T> *m_list; }; template <typename T> LinkQueue<T>::LinkQueue() { m_list = new LinkList < T > ; } template <typename T> LinkQueue<T>::~LinkQueue() { clear(); delete m_list; m_list = NULL; } template <typename T> int LinkQueue<T>::clear() { T t; while (m_list->getLen() > 0) { m_list->del(0, t); } return 0; } template <typename T> int LinkQueue<T>::append(T &t) { return m_list->insert(t, m_list->getLen()); } template <typename T> int LinkQueue<T>::retieve(T &t) { return m_list->del(m_list->getLen() - 1, t); } template <typename T> int LinkQueue<T>::header(T &t) { return m_list->get(0, t); } template <typename T> int LinkQueue<T>::length() { return m_list->getLen(); }

main.cpp

// 队列类测试程序 #include <iostream> #include <cstdio> #include "linkqueue.hpp" using namespace std; struct Student { char name[32]; int age; }; void play() { Student s1, s2, s3; s1.age = 21; s2.age = 22; s3.age = 23; LinkQueue<Student> lq; // 创建队列 lq.append(s1); // 入队列 lq.append(s2); lq.append(s3); Student tmp; lq.header(tmp); cout << "header of queue: " << tmp.age << endl; cout << "length of queue: " << lq.length() << endl; while (lq.length() > 0) { lq.retieve(tmp); cout << tmp.age << " "; } cout << endl; lq.clear(); } int main() { play(); return 0; }

栈类链式存储

linkstack.hpp

// 栈类 #pragma once #include "linklist.hpp" template <typename T> class LinkStack { public: LinkStack(); ~LinkStack(); public: int clear(); int push(T &t); int pop(T &t); int top(T &t); int size(); protected: LinkList<T> *m_list; }; template <typename T> LinkStack<T>::LinkStack() { m_list = new LinkList < T > ; } template <typename T> LinkStack<T>::~LinkStack() { clear(); delete m_list; m_list = NULL; } template <typename T> int LinkStack<T>::clear() { T t; while (m_list->getLen() > 0) { m_list->del(0, t); } return 0; } template <typename T> int LinkStack<T>::push(T &t) { return m_list->insert(t, 0); } template <typename T> int LinkStack<T>::pop(T &t) { return m_list->del(0, t); } template <typename T> int LinkStack<T>::top(T &t) { return m_list->get(0, t); } template <typename T> int LinkStack<T>::size() { return m_list->getLen(); }

main.cpp

// 链式存储栈类的测试程序 #include <iostream> #include <cstdio> #include "linkstack.hpp" using namespace std; struct Student { char name[32]; int age; }; void play() { Student s1, s2, s3; s1.age = 21; s2.age = 22; s3.age = 23; LinkStack<Student> ls; // 创建栈 // 入栈 ls.push(s1); ls.push(s2); ls.push(s3); // 获取栈顶元素 Student tmp; ls.top(tmp); cout << "top of stack: " << tmp.age << endl; cout << "size of stack: " << ls.size() << endl; // 出栈 while (ls.size() > 0) { ls.pop(tmp); } ls.clear(); } int main() { play(); return 0; }

linklist.h

// 链表类 #pragma once #include <iostream> #include <cstdio> using namespace std; template <typename T> struct Node { T t; Node<T> *next; }; template <typename T> class LinkList { public: LinkList(); ~LinkList(); public: int clear(); int insert(T &t, int pos); int get(int pos, T &t); int del(int pos, T &t); int getLen(); protected: Node<T> *header; int length; }; template <typename T> LinkList<T>::LinkList() { header = new Node < T > ; header->next = NULL; length = 0; } template <typename T> LinkList<T>::~LinkList() { Node<T> *tmp = NULL; while (header) { tmp = header->next; delete header; header = tmp; } } template <typename T> int LinkList<T>::clear() { ~LinkList(); LinkList(); return 0; } template <typename T> int LinkList<T>::insert(T &t, int pos) { Node<T> *cur = NULL; // 对pos的容错处理 if (pos >= length) { pos = length; } cur = header; for (int i = 0; i < pos; ++i) { cur = cur->next; } // 把上层应用的t结点缓存到容器中 Node<T> *node = new Node < T > ; node->next = NULL; node->t = t; // 把t缓存到容器中 node->next = cur->next; cur->next = node; ++length; return 0; } template <typename T> int LinkList<T>::get(int pos, T &t) { Node<T> *cur = NULL; if (pos >= length) { return -1; } cur = header; for (int i = 0; i < pos; ++i) { cur = cur->next; } t = cur->next->t; // 把pos位置的结点赋值给t return 0; } template <typename T> int LinkList<T>::del(int pos, T &t) { Node<T> *cur = NULL; if (pos >= length) { return -1; } cur = header; for (int i = 0; i < pos; ++i) { cur = cur->next; } Node<T> *ret = NULL; ret = cur->next; t = ret->t; // 把缓存的结点给上层应用t // 删除操作 cur->next = ret->next; --length; delete ret; // 注意释放内存，因为insert的时候new Node<T> return 0; } template <typename T> int LinkList<T>::getLen() { return length; }