C/CPP与数据结构-C++模板类与数据结构基础
概念理解
- C++模板类就相当于一个容器
- 把一个元素添加到模板类中，相当于模板类定义一个对象，往这个对象中插入元素，实际上内部是使用了拷贝的动作。
- 核心思想： 所有容器提供的都是值（value）语意，而非引用（reference）语意。容器执行插入元素的操作时，内部实施拷贝动作。所以STL容器内存储的元素必须能够被拷贝（必须提供拷贝构造函数）。
- 加入到容器中的元素，应该可以被加入才行。
- 因此要加入的节点类如下特征：
- 保证节点能够插入到容器中
- 提供无参构造函数
- 拷贝构造函数
- 重载“=”操作符
模板类设计与实现
-
链表类_链式存储设计与实现
//linkList.hpp文件 #include<iostream> using namespace std; #pragma once //定义节点类 template <typename T> struct Node { T t; //数据域 Node<T> *next; //指针域 }; //定义链表类 template <typename T> class LinkList { public: //无参构造函数 LinkList(); ~LinkList();//析构函数 //成员函数 void clear(); int length(); int insert(T &t, int pos); int del(int pos, T &t); int get(int pos,T &t); private: Node<T> *m_header;//链表内部要创建一个链表的头结点 int m_len;//记录链表的长度 }; template <typename T> LinkList<T>::LinkList() { //1. 创建链表的头部结点 m_header = new Node<T>; m_header->next = NULL; //链表长度初始化 m_len = 0; } template <typename T> LinkList<T>::~LinkList()//析构函数 { //清空链表中的所有元素 clear(); //销毁头部结点 delete m_header; m_len = 0; } //成员函数 template <typename T> void LinkList<T>::clear() { //添加一个辅助指针变量 Node<T> *tem = NULL; //从头部结点开始清空 while (m_header != NULL) { //暂存头部结点的下一个节点 tem = m_header->next; //清空头部结点 delete m_header; //m_header 指向下一个节点 m_header = tem; } //清空完重新创建一个头部结点 m_header = new Node<T>; m_header->next = NULL; //链表长度初始化 m_len = 0; } template <typename T> int LinkList<T>::length() { return m_len; } template <typename T> int LinkList<T>::insert(T &t, int pos) { //1. 引入辅助指针变量 Node<T> *current = NULL; //2. 辅助指针变量指向链表头部结点 current = m_header; //3.辅助指针变量跳到要插入位置的前一个结点 for (int i = 0; i < pos; i++) { current = current->next; } //4. 插入操作 //4.1 创建新节点,缓存要插入的数据 Node<T> *node = new Node<T>; node->t = t;//把用户的节点缓存到容器中，t应该可以使用“=”操作符 node->next = NULL; //2. 连接链表 node->next = current->next; current->next = node; //5. 改变长度 m_len++; return 0; } template <typename T> int LinkList<T>::del(int pos, T &t) { //1. 引入辅助指针变量 Node<T> *current = NULL; Node<T> *ret = NULL; //用于暂存要删除的节点 //2. 辅助指针变量指向链表头部结点 current = m_header; //3.辅助指针变量跳到要插入位置的前一个结点 for (int i = 0; i < pos; i++) { current = current->next; } //4. 拿到要删除的节点 ret = current->next; t = ret->t; //5. 连接要删除节点的下一个节点 current->next = ret->next; //6. 销毁要删除的节点，回收内存 delete ret; //7. 修改链表长度 m_len--; return 0; } template <typename T> int LinkList<T>::get(int pos, T &t) { //1. 引入辅助指针变量 Node<T> *current = NULL; //2. 辅助指针变量指向链表头部结点 current = m_header; //3.辅助指针变量跳到要插入位置的前一个结点 for (int i = 0; i < pos; i++) { current = current->next; } t = current->next->t; return 0; } //main.cpp #include<iostream> using namespace std; #include"linkList.hpp" //定义数据类 class Teacher01 { public: char name[32]; int age; }; int main() { Teacher01 t1, t2,t3,temp; t1.age = 31; t2.age = 32; t3.age = 33; //1. 创建链表类对象 LinkList<Teacher01> list; //2. 插入元素 list.insert(t1, 0); list.insert(t2, 0); list.insert(t3, 0); //3. 遍历 for (int i = 0; i < list.length(); i++) { list.get(i,temp); cout << temp.age << " "; } //4. 删除 while (list.length()>0) { cout << temp.age << " "; list.del(0, temp); } list.clear(); cout << "hello world !" << endl; system("pause"); return 0; } -
栈类_链式存储设计与实现
//linkstack.hpp #pragma once #include<iostream> using namespace std; #include"linkList.hpp" template <typename T> class LinkStack { public: LinkStack(); ~LinkStack(); int clear(); int push(T &t); int pop(T &t); int top(T &t); int size(); private: 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->length()>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->length(); } //main.cpp文件 Teacher01 t1, t2, t3, temp; t1.age = 31; t2.age = 32; t3.age = 33; //创建 LinkStack <Teacher01> stack; //入栈 stack.push(t1); stack.push(t2); stack.push(t3); //遍历 stack.top(temp); cout << "top：" << temp.age << endl; //出栈 while (stack.size()>0) { stack.pop(temp); cout << temp.age << " "; } stack.clear(); -
队列类_链式存储设计与实现
//linkqueue.hpp #pragma once #include<iostream> using namespace std; #include"linkList.hpp" template <typename T> class LinkQueue { public: LinkQueue(); ~LinkQueue(); int clear(); int append(T &t); int retieve(T &t); int header(T &t); int length(); private: 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 (length()>0) { retieve(t); } return 0; } template <typename T> int LinkQueue<T>::append(T &t) { return m_list->insert(t, m_list->length()); } template <typename T> int LinkQueue<T>::retieve(T &t) { return m_list->del(0,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->length(); } //main.cpp Teacher01 t1, t2, t3, temp; t1.age = 31; t2.age = 32; t3.age = 33; //创建队列 LinkQueue<Teacher01> queue; // queue.append(t1); queue.append(t2); queue.append(t3); queue.header(temp); cout << "header:" << temp.age << endl; while (queue.length()>0) { queue.retieve(temp); cout << temp.age << " "; } queue.clear(); -
链表类_顺序存储设计与实现
//seqList.hpp #pragma once #include<iostream> using namespace std; template<typename T> class SeqList { public: SeqList(int capacity = 20); ~SeqList(); int clear(); int length(); int capacity(); int insert(T &t, int pos); int get(int pos, T &t); int del(int pos, T &t); private: int m_capacity; int m_length; T *m_array; }; template<typename T> SeqList<T>::SeqList(int capacity ) { m_capacity = capacity; m_length = 0; m_array = new T[m_capacity]; return; } template<typename T> SeqList<T>::~SeqList() { delete[]m_array; m_array = NULL; m_length = 0; m_capacity = 0; } template<typename T> int SeqList<T>::clear() { m_length = 0; return 0; } template<typename T> int SeqList<T>::length() { return m_length; } template<typename T> int SeqList<T>::capacity() { return m_capacity; } template<typename T> int SeqList<T>::insert(T &t, int pos) { int i = 0; for (i = m_length; i > pos; i--) { m_array[i] = m_array[i - 1]; } m_array[i] = t; //把上层应用的t缓存在数组中，若t是对象，则要保证能被拷贝（=）,避免深拷贝、浅拷贝问题 m_length++; return 0; } template<typename T> int SeqList<T>::get(int pos, T &t) { t = m_array[pos]; return 0; } template<typename T> int SeqList<T>::del(int pos, T &t) { t = m_array[pos]; for (int i = pos+1; i < m_length; i++) { m_array[i - 1] = m_array[i]; } m_length--; return 0; } //main.cpp Teacher01 t1, t2, t3, temp; t1.age = 31; t2.age = 32; t3.age = 33; //创建一个顺序链表 SeqList<Teacher01> seqlist; seqlist.insert(t1, 0); seqlist.insert(t2, 0); seqlist.insert(t3, 0); for (int i = 0; i < seqlist.length(); i++) { seqlist.get(i, temp); cout << temp.age << " "; } cout << "删除：" << endl; while (seqlist.length()>0) { seqlist.del(0, temp); cout << temp.age << " "; } seqlist.clear(); -
栈类_顺序存储设计与实现
#pragma once #include<iostream> using namespace std; #include"seqList.hpp" template<typename T> class SeqStack { public: SeqStack(int capacity = 20); ~SeqStack(); int clear(); int push(T &t); int pop(T &t); int top(T &t); int size(); int capicity(); private: SeqList<T> *m_seqlist; }; template<typename T> SeqStack<T>::SeqStack(int capacity) { m_seqlist = new SeqList<T>(capacity); } template<typename T> SeqStack<T>::~SeqStack() { clear(); delete m_seqlist; m_seqlist = NULL; } template<typename T> int SeqStack<T>::clear() { T t; while (size()>0) { pop(t); } return 0; } template<typename T> int SeqStack<T>::push(T &t) { return m_seqlist->insert(t, m_seqlist->length()); } template<typename T> int SeqStack<T>::pop(T &t) { return m_seqlist->del(m_seqlist->length() - 1, t); } template<typename T> int SeqStack<T>::top(T &t) { m_seqlist->get(m_seqlist->length()-1, t); return 0; } template<typename T> int SeqStack<T>::size() { return m_seqlist->length(); } template<typename T> int SeqStack<T>::capicity() { return m_seqlist->capacity(); } //main.cpp Teacher01 t1, t2, t3, temp; t1.age = 31; t2.age = 32; t3.age = 33; SeqStack<Teacher01> seqstac; seqstac.push(t1); seqstac.push(t2); seqstac.push(t3); seqstac.top(temp); cout <<"top"<< temp.age << " "; while (seqstac.size()>0) { seqstac.pop(temp); cout << temp.age << " "; } seqstac.clear(); -
队列类_顺序存储设计与实现
//seqqueue.hpp #pragma once #include<iostream> using namespace std; #include"seqList.hpp" template<typename T> class SeqQueue { public: SeqQueue(int capacity = 20); ~SeqQueue(); int clear(); int append(T &t); int retrieve(T &t); int header(T &t); int length(); int capacity(); private: SeqList<T> *m_seqlist; }; template<typename T> SeqQueue<T>::SeqQueue(int capacity) { m_seqlist = new SeqList<T>(capacity); } template<typename T> SeqQueue<T>::~SeqQueue() { delete m_seqlist; } template<typename T> int SeqQueue<T>::clear() { return m_seqlist->clear(); } template<typename T> int SeqQueue<T>::append(T &t) { return m_seqlist->insert(t,m_seqlist->length()); } template<typename T> int SeqQueue<T>::retrieve(T &t) { return m_seqlist->del(0,t); } template<typename T> int SeqQueue<T>::header(T &t) { return m_seqlist->get(0,t); } template<typename T> int SeqQueue<T>::length() { return m_seqlist->length(); } template<typename T> int SeqQueue<T>::capacity() { return m_seqlist->capacity(); } //main.cpp Teacher01 t1, t2, t3, temp; t1.age = 31; t2.age = 32; t3.age = 33; SeqQueue<Teacher01> seqqueue; seqqueue.append(t1); seqqueue.append(t2); seqqueue.append(t3); seqqueue.header(temp); cout << "Header:" << temp.age << endl; while (seqqueue.length()>0) { seqqueue.retrieve(temp); cout << temp.age << " "; } seqqueue.clear();