保定网站建设方案,广州网站优化服务,深圳网站设计吧,自己建网站花钱吗C数据结构与算法 目录
本文前驱课程
1 C自学精简教程 目录(必读)
2 动态数组 Vector#xff08;难度1#xff09;
其中#xff0c;2 是 1 中的一个作业。2 中详细讲解了动态数组实现的基本原理。
本文目标
1 学会写基本的C类模板语法#xff1b;
2 为以后熟练使用 S…C数据结构与算法 目录
本文前驱课程
1 C自学精简教程 目录(必读)
2 动态数组 Vector难度1
其中2 是 1 中的一个作业。2 中详细讲解了动态数组实现的基本原理。
本文目标
1 学会写基本的C类模板语法
2 为以后熟练使用 STL 打下基础
3 为更进一步的阅读和掌握更多的C库打下基础 模板语法的学习最恰当的方式就是和非模板代码对比学习。
本文的内容只是在 2 动态数组 Vector难度1的基础上把代码改造为模板语法。
除此之外不添加任何内容。
模板语法介绍
当类的成员变量是不确定的类型的时候我们使用模板类 template class来实现这样的类。
模板类的定义如下 templatetypename T struct Vector{T data;//成员变量 data 的类型不确定写成 T};解释说明
1template 表示后续代码中有类型是不确定的先用typename T当中的T表示类型
2typename表示T是一个未来才能确定的类型
3确定T的类型的方式就是创建一个Vector对象的时候在中指定 Vectorint arr; //这条语句表示用int替换代码中的T非模板语法与模板语法差异对比图 模板语法和非模板语法对比1 模板语法和非模板语法对比2 代码与注释如下
#includeiostream
#include iomanip
#include cassert
using namespace std;//------下面的代码是用来测试你的代码有没有问题的辅助代码你无需关注------
#include algorithm
#include cstdlib
#include iostream
#include vector
#include utility
using namespace std;
struct Record { Record(void* ptr1, size_t count1, const char* location1, int line1, bool is) :ptr(ptr1), count(count1), line(line1), is_array(is) { int i 0; while ((location[i] location1[i]) i 100) { i; } }void* ptr; size_t count; char location[100] { 0 }; int line; bool is_array false; bool not_use_right_delete false; }; bool operator(const Record lhs, const Record rhs) { return lhs.ptr rhs.ptr; }std::vectorRecord myAllocStatistic; void* newFunctionImpl(std::size_t sz, char const* file, int line, bool is) { void* ptr std::malloc(sz); myAllocStatistic.push_back({ ptr,sz, file, line , is }); return ptr; }void* operator new(std::size_t sz, char const* file, int line) { return newFunctionImpl(sz, file, line, false); }void* operator new [](std::size_t sz, char const* file, int line)
{ return newFunctionImpl(sz, file, line, true); }void operator delete(void* ptr) noexcept { Record item{ ptr, 0, , 0, false }; auto itr std::find(myAllocStatistic.begin(), myAllocStatistic.end(), item); if (itr ! myAllocStatistic.end()) { auto ind std::distance(myAllocStatistic.begin(), itr); myAllocStatistic[ind].ptr nullptr; if (itr-is_array) { myAllocStatistic[ind].not_use_right_delete true; } else { myAllocStatistic[ind].count 0; }std::free(ptr); } }void operator delete[](void* ptr) noexcept {Record item{ ptr, 0, , 0, true }; auto itr std::find(myAllocStatistic.begin(), myAllocStatistic.end(), item); if (itr ! myAllocStatistic.end()) { auto ind std::distance(myAllocStatistic.begin(), itr); myAllocStatistic[ind].ptr nullptr; if (!itr-is_array) { myAllocStatistic[ind].not_use_right_delete true; } else { myAllocStatistic[ind].count 0; }std::free(ptr); }}
#define new new(__FILE__, __LINE__)
struct MyStruct { void ReportMemoryLeak() { std::cout Memory leak report: std::endl; bool leak false; for (auto i : myAllocStatistic) { if (i.count ! 0) { leak true; std::cout leak count i.count Byte , file i.location , line i.line; if (i.not_use_right_delete) { cout , not use right delete. ; } cout std::endl; } }if (!leak) { cout No memory leak. endl; } }~MyStruct() { ReportMemoryLeak(); } }; static MyStruct my; void check_do(bool b, int line __LINE__) { if (b) { cout line: line Pass endl; } else { cout line: line Ohh! not passed!!!!!!!!!!!!!!!!!!!!!!!!!!! endl; exit(0); } }
#define check(msg) check_do(msg, __LINE__);
//------上面的代码是用来测试你的代码有没有问题的辅助代码你无需关注------//注意禁止修改Vector的定义包括禁止给Vector添加成员变量
//可以添加私有成员函数如果你认为需要的话templatetypename T
struct Vector
{
public:Vector();Vector(int n, T value);Vector(const Vector from);Vector(int* begin, int* end);~Vector();int size() const;//只读元素//参考 https://zhuanlan.zhihu.com/p/539451614const T operator[](int n)const { return m_data[n]; }//写入元素T operator[](int n) { return m_data[n]; }void push_back(T value);bool empty() const;// your job 1void clear();// your job 2Vector operator (const Vector from);// your job 4
private:void copy(const Vector from);// your job 3
private:int m_element_cout;int m_capacity;T* m_data;//定义一个元素类型待定的数组起始元素的指针//请忽略下面这个成员变量这个成员变量不影响你的实现当它不存在即可。
};//模板类的成员函数都要以下面的template语法开始和类声明的地方一样
templatetypename T
VectorT::Vector()
{m_element_cout 0;m_capacity 10;m_data new int[m_capacity];
}templatetypename T
VectorT::Vector(int n, T value) :Vector()
{for (int i 0; i n; i)push_back(value);
}templatetypename T
VectorT::Vector(const Vector from)
{m_element_cout from.m_element_cout;m_capacity from.m_capacity;m_data new int[m_capacity];for (int i 0; i m_element_cout; i){m_data[i] from.m_data[i];}
}templatetypename T
VectorT::Vector(int* begin, int* end) :Vector()
{for (int* p begin; p end; p){push_back(*p);}
}templatetypename T
VectorT::~Vector()
{delete[] m_data;
}templatetypename T
int VectorT::size() const
{return m_element_cout;
}templatetypename T
void VectorT::push_back(T value)
{if (m_element_cout m_capacity){m_data[m_element_cout] value;m_element_cout;}else{int* p;p new T[2 * m_capacity];for (int j 0; j m_element_cout; j){p[j] m_data[j];}p[m_element_cout] value;m_element_cout m_element_cout 1;m_capacity 2 * m_capacity;delete[]m_data;m_data p;}
}//(1) your code for : Vector empty()//(2) your code for : Vector clear()//(3) your code for : Vector copy()//(4) your code for : Vector operator void test1(void)
{Vectorint v;//创建一个存放int变量的容器vint i;check(v.size() 0);for (i 0; i 10; i){v.push_back(i);}for (int i 0; i 10; i){check(v[i] i);}check(v.size() 10);
}
void test2(void)
{int n 100000;Vectorint v;int i;check(v.size() 0);for (i 0; i n; i){v.push_back(i);}for (int i 0; i n; i){assert(v[i] i);}check(v.size() n);
}
void print(Vectorint v, const std::string msg)
{std::cout The contents of msg.c_str() are:;for (int i 0; i ! v.size(); i){std::cout v[i];}std::cout \n;
}
void test3()
{Vectorint a;Vectorint first; // empty vector of intscheck(first.empty() true first.size() 0);Vectorint second(4, 100); // four ints with value 100check(second.empty() false);check(second.size() 4);Vectorint fourth(second); // a copy of thirdcheck(fourth.size() second.size());int myints[] { 16,2,77,29 };Vectorint fifth(myints, myints sizeof(myints) / sizeof(int));check(fifth.empty() false);check(fifth[0] 16);check(fifth[3] 29);check(fifth.size() sizeof(myints) / sizeof(int));print(fifth, fifth);//The contents of fifth are:16 2 77 29 fifth.push_back(30);check(fifth[4] 30);check(fifth.size() 5);print(fifth, fifth);//The contents of fifth are:16 2 77 29 30 check(fifth.size() sizeof(myints) / sizeof(int) 1);first fifth fifth;print(first, first);//The contents of first are:16 2 77 29 30 check(first.empty() false first.size() fifth.size());Vectorint a1(myints, myints sizeof(myints) / sizeof(int));//下面大括号是作用域用来把代码分开互不干扰这样就可以创建相同的变量名字了就不用为了起很多不同的变量名而烦恼了。{Vectorint b(a1);b.push_back(2);check(b[4] 2);}{Vectorint c;c a1;}check(a1.size() sizeof(myints) / sizeof(int));{Vectorint c;c fifth;c[0] 1;check(c[0] 1);}
}int main()
{test1();test2();test3();return 0;
}预期输出 答案在此
C数据结构与算法全部答案
