队列类链式存储

代码：
linkqueue.hpp

? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 // 队列类 #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

? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 // 队列类测试程序 #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

? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 // 栈类 #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

? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 // 链式存储栈类的测试程序 #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

? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 // 链表类 #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; }