C语言模拟实现C多态基类指针/引用指向子类的实例通过基类指针/引用调用子类成员函数。typedef void(*SoundFunc)(void*); //虚函数表 typedef struct { SoundFunc makesound;//叫声 }Vtable; //基类 typedef struct { const char* name; Vtable* table; }Animal; //实现子类虚函数(cat) void Catsound(void *self){ Animal* am(Animal*)self; printf(%s:喵喵~;\n,am-name); } //Cat 虚函数表 Vtable CatVtable{ .makesoundCatsound }; //dog void Dogsound(void *self){ Animal* am(Animal*)self; printf(%s:汪汪汪~~\n,am-name); } //Dog 虚函数表 Vtable DogVtable{ .makesoundDogsound }; // 6. 子类构造函数初始化基类属性和虚函数表 Animal* CatCreate(const char* name) { Animal* cat(Animal*)malloc(sizeof(Animal)); cat-namename; cat-tableCatVtable; return cat; } Animal* DogCreate(const char* name) { Animal* dog(Animal*)malloc(sizeof(Animal)); dog-namename; dog-tableDogVtable; return dog; } // 7. 统一调用接口核心多态实现 // 无需区分子类类型直接通过基类指针调用虚函数表中的函数 void AnimalMakesound(Animal* animal) { if(animalanimal-tableanimal-table-makesound) { animal-table-makesound(animal); } } int main() { Animal* catCatCreate(小猫); Animal* dogDogCreate(小狗); //统一调用接口 AnimalMakesound(cat); AnimalMakesound(dog); free(cat); free(dog); return 0; }单例模式所谓单例模式就是要确保一个类仅仅有一个实例并且提供全局访问点。C实现单例模式需要解决线程安全问题、内存泄漏、对象销毁等问题。设计要点1、私有构造函数禁止外部new创建实例2、私有拷贝/赋值运算符3、提供全局访问点通常是静态方法4、线程安全多线程环境下避免创建多个实例5、自动销毁避免内存泄漏class Singleton { public: //禁用拷贝 和赋值 Singleton(const Singleton)delete; Singleton operator(const Singleton)delete; //全局访问点 唯一返回值 static Singleton Getinstance() { //局部静态变量 线程安全初始化 程序结束自动销毁 static Singleton instance; return instance; } //测试接口 void showtest(const string msg) { cout[Singleton:]msgendl; } private: //私有构造函数 禁止外部创建实例 Singleton(){ cout实例创建成功endl; } ~Singleton(){ cout销毁成功endl; } }; int main() { Singleton s1Singleton::Getinstance(); Singleton s2Singleton::Getinstance(); s1.showtest(s1实例); s1.showtest(s1 s2都是同一个实例!); couts1地址:s1endl; couts2地址:s2endl; }归并排序输入nums[5,2,3,1]输出[1,2,3,5]图解归并class Solution { vectorinttmp; public: vectorint MySort(vectorint arr) { // write code here tmp.resize(arr.size()); merage(arr,0,arr.size()-1); return arr; } void merage(vectorint arr,int l,int r) { if(lr) return ; int mid(lr)1; // merage(arr,l,mid); merage(arr,mid1,r); //合并 int cur1l,cur2mid1,i0; while(cur1midcur2r) { tmp[i]arr[cur1]arr[cur2]?arr[cur1]:arr[cur2]; } //处理剩下没有遍历的 while(cur1mid) tmp[i]arr[cur1]; while(cur2r) tmp[i]arr[cur2]; for(int il;ir;i) { arr[i]tmp[i-l]; } } };智能指针shared_ptr#pragma once #includeatomic using namespace std; templatetypename T class sharedPtr { private: T* ptr; atomicsize_t* ref_count; void release() { if (ref_count ref_count-fetch_sub(1)1) { delete ptr; delete ref_count; } } public: //默认构造 sharedPtr():ptr(nullptr),ref_count(nullptr) {} //构造 防止隐式类型强转化 explicit sharedPtr(T* p):ptr(p), ref_count(p?new atomicsize_t(1):nullptr) { } //析构 ~sharedPtr() { } //拷贝构造 sharedPtr(const sharedPtrT other) :ptr(other.ptr), ref_count(other.ref_count) { if(ref_count) { ref_count-fetch_add(1,memory_order_relaxed); } } //拷贝赋值 sharedPtrT operator(const sharedPtrT other) { if (this ! other) { ptr other.ptr; ref_count other.ref_count; if (ref_count) { ref_count-fetch_add(1,memory_order_relaxed); } } return *this; } //移动构造 sharedPtr(sharedPtrT other)noexcept:ptr(other.ptr),ref_count(other.ref_count) { ptrother.ptr; ref_countother.ref_count; } //移动赋值 noexcept不会抛异常 sharedPtrT operator(const sharedPtrT other)noexcept { if(this!other) { release(); ptrother.ptr; ref_countother.ref_count; other.ptrnullptr; other.ref_countnullptr; } return *this; } T operator*()const{ return *ptr; } T* operator-()const{ return ptr; } //获取引用计算 size_t use_count()const { return ref_count?ref_count-load(memory_order_acquire); } T* get()const{ return ptr; } //重置指针 void reset(T* pnullptr) { release(); ptrp; ref_countp? new atomicsize_t(1):nullptr; } };链表oj排序链表原题链表的中间节点 合并两个有序链表双指针,如果快指针指向空或者快指针下一节点指向空那么慢指针就在中间节点。ps:因为这里我们需要找到中间节点并断开找到链表中间节点head1的前一个结点并断开head1与前一个结点的连接。这样就把链表分成俩部分。分治递归调用sortlist函数。分别排序head(只有前一段)和head1.排序后得到两个有序链表然后合并得到排序后的链表链表返回头节点。class Solution { //中间节点 ListNode* middleSort(ListNode* head) { ListNode* prenullptr; ListNode* fasthead,*slowhead; while(fastfast-next) { preslow; slowslow-next; fastfast-next-next; } pre-nextnullptr; return slow; } //合并两个有序链表 ListNode* mergeTwo(ListNode* l1,ListNode* l2) { ListNode dummy; ListNode* curdummy; while(l1l2) { if(l1-vall2-val) { cur-nextl1; l1l1-next;//向后移动 } else { cur-nextl2; l2l2-next; } curcur-next; } //拼接剩余的链表 cur-nextl1?l1:l2; return dummy.next; } public: ListNode* sortList(ListNode* head) { if(headnullptr||head-nextnullptr) { return head; } ListNode dummy; ListNode* head1middleSort(head);//找到中间链表 //分治 head1sortList(head1); headsortList(head); return mergeTwo(head1,head); } };反转链表输入一个链表反转链表后输出新链表的表头详解1、因为链表结尾时nullpre是nullp指向头部2、p的next成员马上要指向pre不保存p的下一节点就会使其丢失所以让t来存储它。3、class Solution { public: ListNode* ReverseList(ListNode* head) { // write code here ListNode* newnodenullptr; while(head) { ListNode* nxthead-next; head-nextnewnode; newnodehead; headnxt; } return newnode; } };
C++复习篇
C语言模拟实现C多态基类指针/引用指向子类的实例通过基类指针/引用调用子类成员函数。typedef void(*SoundFunc)(void*); //虚函数表 typedef struct { SoundFunc makesound;//叫声 }Vtable; //基类 typedef struct { const char* name; Vtable* table; }Animal; //实现子类虚函数(cat) void Catsound(void *self){ Animal* am(Animal*)self; printf(%s:喵喵~;\n,am-name); } //Cat 虚函数表 Vtable CatVtable{ .makesoundCatsound }; //dog void Dogsound(void *self){ Animal* am(Animal*)self; printf(%s:汪汪汪~~\n,am-name); } //Dog 虚函数表 Vtable DogVtable{ .makesoundDogsound }; // 6. 子类构造函数初始化基类属性和虚函数表 Animal* CatCreate(const char* name) { Animal* cat(Animal*)malloc(sizeof(Animal)); cat-namename; cat-tableCatVtable; return cat; } Animal* DogCreate(const char* name) { Animal* dog(Animal*)malloc(sizeof(Animal)); dog-namename; dog-tableDogVtable; return dog; } // 7. 统一调用接口核心多态实现 // 无需区分子类类型直接通过基类指针调用虚函数表中的函数 void AnimalMakesound(Animal* animal) { if(animalanimal-tableanimal-table-makesound) { animal-table-makesound(animal); } } int main() { Animal* catCatCreate(小猫); Animal* dogDogCreate(小狗); //统一调用接口 AnimalMakesound(cat); AnimalMakesound(dog); free(cat); free(dog); return 0; }单例模式所谓单例模式就是要确保一个类仅仅有一个实例并且提供全局访问点。C实现单例模式需要解决线程安全问题、内存泄漏、对象销毁等问题。设计要点1、私有构造函数禁止外部new创建实例2、私有拷贝/赋值运算符3、提供全局访问点通常是静态方法4、线程安全多线程环境下避免创建多个实例5、自动销毁避免内存泄漏class Singleton { public: //禁用拷贝 和赋值 Singleton(const Singleton)delete; Singleton operator(const Singleton)delete; //全局访问点 唯一返回值 static Singleton Getinstance() { //局部静态变量 线程安全初始化 程序结束自动销毁 static Singleton instance; return instance; } //测试接口 void showtest(const string msg) { cout[Singleton:]msgendl; } private: //私有构造函数 禁止外部创建实例 Singleton(){ cout实例创建成功endl; } ~Singleton(){ cout销毁成功endl; } }; int main() { Singleton s1Singleton::Getinstance(); Singleton s2Singleton::Getinstance(); s1.showtest(s1实例); s1.showtest(s1 s2都是同一个实例!); couts1地址:s1endl; couts2地址:s2endl; }归并排序输入nums[5,2,3,1]输出[1,2,3,5]图解归并class Solution { vectorinttmp; public: vectorint MySort(vectorint arr) { // write code here tmp.resize(arr.size()); merage(arr,0,arr.size()-1); return arr; } void merage(vectorint arr,int l,int r) { if(lr) return ; int mid(lr)1; // merage(arr,l,mid); merage(arr,mid1,r); //合并 int cur1l,cur2mid1,i0; while(cur1midcur2r) { tmp[i]arr[cur1]arr[cur2]?arr[cur1]:arr[cur2]; } //处理剩下没有遍历的 while(cur1mid) tmp[i]arr[cur1]; while(cur2r) tmp[i]arr[cur2]; for(int il;ir;i) { arr[i]tmp[i-l]; } } };智能指针shared_ptr#pragma once #includeatomic using namespace std; templatetypename T class sharedPtr { private: T* ptr; atomicsize_t* ref_count; void release() { if (ref_count ref_count-fetch_sub(1)1) { delete ptr; delete ref_count; } } public: //默认构造 sharedPtr():ptr(nullptr),ref_count(nullptr) {} //构造 防止隐式类型强转化 explicit sharedPtr(T* p):ptr(p), ref_count(p?new atomicsize_t(1):nullptr) { } //析构 ~sharedPtr() { } //拷贝构造 sharedPtr(const sharedPtrT other) :ptr(other.ptr), ref_count(other.ref_count) { if(ref_count) { ref_count-fetch_add(1,memory_order_relaxed); } } //拷贝赋值 sharedPtrT operator(const sharedPtrT other) { if (this ! other) { ptr other.ptr; ref_count other.ref_count; if (ref_count) { ref_count-fetch_add(1,memory_order_relaxed); } } return *this; } //移动构造 sharedPtr(sharedPtrT other)noexcept:ptr(other.ptr),ref_count(other.ref_count) { ptrother.ptr; ref_countother.ref_count; } //移动赋值 noexcept不会抛异常 sharedPtrT operator(const sharedPtrT other)noexcept { if(this!other) { release(); ptrother.ptr; ref_countother.ref_count; other.ptrnullptr; other.ref_countnullptr; } return *this; } T operator*()const{ return *ptr; } T* operator-()const{ return ptr; } //获取引用计算 size_t use_count()const { return ref_count?ref_count-load(memory_order_acquire); } T* get()const{ return ptr; } //重置指针 void reset(T* pnullptr) { release(); ptrp; ref_countp? new atomicsize_t(1):nullptr; } };链表oj排序链表原题链表的中间节点 合并两个有序链表双指针,如果快指针指向空或者快指针下一节点指向空那么慢指针就在中间节点。ps:因为这里我们需要找到中间节点并断开找到链表中间节点head1的前一个结点并断开head1与前一个结点的连接。这样就把链表分成俩部分。分治递归调用sortlist函数。分别排序head(只有前一段)和head1.排序后得到两个有序链表然后合并得到排序后的链表链表返回头节点。class Solution { //中间节点 ListNode* middleSort(ListNode* head) { ListNode* prenullptr; ListNode* fasthead,*slowhead; while(fastfast-next) { preslow; slowslow-next; fastfast-next-next; } pre-nextnullptr; return slow; } //合并两个有序链表 ListNode* mergeTwo(ListNode* l1,ListNode* l2) { ListNode dummy; ListNode* curdummy; while(l1l2) { if(l1-vall2-val) { cur-nextl1; l1l1-next;//向后移动 } else { cur-nextl2; l2l2-next; } curcur-next; } //拼接剩余的链表 cur-nextl1?l1:l2; return dummy.next; } public: ListNode* sortList(ListNode* head) { if(headnullptr||head-nextnullptr) { return head; } ListNode dummy; ListNode* head1middleSort(head);//找到中间链表 //分治 head1sortList(head1); headsortList(head); return mergeTwo(head1,head); } };反转链表输入一个链表反转链表后输出新链表的表头详解1、因为链表结尾时nullpre是nullp指向头部2、p的next成员马上要指向pre不保存p的下一节点就会使其丢失所以让t来存储它。3、class Solution { public: ListNode* ReverseList(ListNode* head) { // write code here ListNode* newnodenullptr; while(head) { ListNode* nxthead-next; head-nextnewnode; newnodehead; headnxt; } return newnode; } };
