- 博客(78)
- 收藏
- 关注
RSS订阅
原创 二叉树的创建及成员函数的实现
本文实现了二叉树的创建及其成员函数的实现成员函数包括：1)构造函数2)拷贝构造函数3)赋值运算符重载4)先序遍历（先根遍历）5)中序遍历6)后序遍历（后根遍历）7)层序遍历8)节点个数9)叶子节点个数10)二叉树深度二叉树的实现：#pragma once#include#include#includeusing namespac
2016-04-20 18:04:23
5723
原创 c++中各类继承下的对象模型
博客是从51cto迁移过来的，图片显示有问题，原文链接：https://blog.51cto.com/haipi/1753646c++中多态的实现我们都知道，c++中的多态是在虚函数的基础上实现的，用指向派生类的基类指针调用派生类（或基类）中自己的成员函数。那么，具体是怎么实现的呢？其实它是通过虚函数表来实现的，虚函数表是保存虚函数地址的一张表，若一个类中有虚函数，当程序运行时，编译器...
2016-04-11 20:04:32
700
原创 c 动态内存管理
博客是从51cto迁移过来的，图片显示有问题，原文链接：https://blog.51cto.com/haipi/1747927我们都知道在c++中可以用new/malloc动态分配内存空间用delete/free释放动态开辟的内存空间。c++中的malloc/free是继承c语言中的malloc/free，它的用法和在C语言中的用法一模一样。1.那么既然c++中有了可以动态开辟...
2016-04-11 20:04:21
1967
2
原创 数据结构 线性表—单链表
本文只要实现单链表的初始化、插入（尾插、头插、任意位置插入）、删除（尾删、头删、删除指定元素）、查找等。定义单链表typedef int DataType;typedef struct LinkNode{ DataType data; struct LinkNode *next;}LinkNode, *pLinkNode, *pList;实现单链表的所有接口：void InitLinkL
2016-04-11 20:04:00
305
转载 Linux设备模型(4)_sysfs
Linux设备模型(4)_sysfs 1. 前言 sysfs是一个基于RAM的文件系统，它和Kobject一起，可以将Kernel的数据结构导出到用户空间，以文件目录结构的形式，提供对这些数据结构（以及数据结构的属性）的访问支持。 sysfs具备文件系统的所有属性，而本文主要侧重其设备模型的特性,因此不会涉及过多的文件系统实现细节，而只介绍sysfs在Linux设备
2017-11-16 10:42:13
350
转载 Linux设备模型(3)_Uevent
Linux设备模型(3)_Uevent 1. Uevent的功能 Uevent是Kobject的一部分，用于在Kobject状态发生改变时，例如增加、移除等，通知用户空间程序。用户空间程序收到这样的事件后，会做相应的处理。 该机制通常是用来支持热拔插设备的，例如U盘插入后，USB相关的驱动软件会动态创建用于表示该U盘的device结构（相应的也包括其中的kobjec
2017-11-16 09:58:33
352
转载 Linux设备模型(2)_Kobject
Linux设备模型(2)_Kobject 1. 前言 Kobject是Linux设备模型的基础，也是设备模型中最难理解的一部分（可参考Documentation/kobject.txt的表述）。因此有必要先把它分析清楚。 2. 基本概念 由“Linux设备模型(1)_基本概念”可知，Linux设备模型的核心是使用Bus、Class、Devi
2017-11-14 12:10:05
439
转载 Linux设备模型(1)_基本概念
Linux设备模型(1)_基本概念 1. 前言 在“Linux内核的整体架构”中，蜗蜗有提到，由于Linux支持世界上几乎所有的、不同功能的硬件设备（这是Linux的优点），导致Linux内核中有一半的代码是设备驱动，而且随着硬件的快速升级换代，设备驱动的代码量也在快速增长。个人意见，这种现象打破了“简洁就是美”的理念，是丑陋的。它导致Linux内核看上去非常臃肿、杂乱、不易维护。
2017-11-07 16:29:24
315
转载 Linux内核整体架构
Linux内核的整体架构 1. 前言 本文是“Linux内核分析”系列文章的第一篇，会以内核的核心功能为出发点，描述Linux内核的整体架构，以及架构之下主要的软件子系统。之后，会介绍Linux内核源文件的目录结构，并和各个软件子系统对应。 注：本文和其它的“Linux内核分析”文章都基于如下约定： a) 内核版本为Linux 3.10.29（该版本是一个long term的版本
2017-11-02 19:24:00
388
原创 字符设备驱动程序之misc_dev方式注册字符设备
注册字符设备有三种方法：chardev、cdev、misc注册，本文介绍用misc_dev注册方法注册设备，编写简单字符设备驱动程序，实现字符设备驱动程序的基本框架。 编写字符设备驱动的基本步骤为： 1、编写对该设备的各种操作函数（open、write、ioctl） 2、定义一个file_operation结构体，该结构体用来存储驱动内核模块提供的对设备进行各种操作的函数的指针即open()、
2017-08-04 18:16:19
1246
1
原创 二叉树中两个节点的最近公共祖先节点
题目：求二叉树中两个节点的最近公共祖先节点一、该二叉树为搜索二叉树搜索二叉树的特点：任意一个节点的左子树的所有节点值都比该节点的值小，其右子树的所有节点值都比该节点的值大。解决该问题方法：从树的根节点开始和两个节点作比较，如果当前节点的值比两个节点的值都大，则这两个节点的最近公共祖先节点一定在该节点的左子树中，则下一步遍历当前节点的左子树；如果当前节点的值比两个节点的值都小
2016-08-04 23:43:47
53306
11
原创 子进程的个数
分析这段代码：分析fork() n次子进程的个数为？如下图可知，子进程的个数为2^n - 1如下图：fork()产生进程的过程就像一颗二叉树，一棵树中只有一个父进程，其他都是子进程
2016-07-29 23:36:05
939
原创 项目：文件压缩及解压缩
项目描述：实现文件的压缩及解压缩。 开发平台：VS2013 开发技术：堆，Huaffman树，文件输入输出函数 项目特点：1.统计文件中字符出现的次数，利用数据结构堆建造Huffman树，出现次数多的编码短，出现次数少的编码长。 2.根据建造好的Huffman树形成编码，以对文件进行压缩。3.将文件中出现的字符以及他们出现的次数写入配置文件，以便后续的解压缩。 4.根据
2016-07-13 23:36:20
1167
原创 没有被调用的函数其代码为什么会被执行？
现象首先我们运行下面一段代码：从以上程序中我们可以知道，main函数调用函数fun1,函数fun1和main函数都没有调用函数fun，因此，我们认为函数fun中的"fun is run.."和 "you are done.."都不会被打印。且main函数中的打印语句“begin run..”和“main: you should run here”都应该被打印让我们来
2016-06-10 19:48:08
6093
1
原创 构造哈希表之开链法（哈希桶）
上一篇博客中介绍了用闭散列法的二次探测和开链法构造哈希表的原理即实现方式。构造哈希表的闭散列法之二次探测地址：http://blog.csdn.net/xyzbaihaiping/article/details/51607770这里简单描述一下哈希桶的基本原理：哈希表中保存包含每个key值的节点，每个节点有一个_next的指针，指向产生哈希冲突的key的节点#pragma
2016-06-08 09:50:09
4953
原创 构造哈希表之二次探测法
HashTable-散列表/哈希表是根据关键字（key）而直接访问在内存存储位置的数据结构。它通过一个关键值的函数将所需的数据映射到表中的位置来访问数据，这个映射函数叫做散列（哈希）函数，存放记录的数组叫做散列表。构造哈希表的几种方法1.直接定址法（取关键字的某个线性函数为哈希地址）2.除留余数法（取关键值被某个不大于散列表长m的数p除后的所得的余数为散列地址）3.
2016-06-08 01:19:00
76628
11
转载 task_struct结构体（PCB）描述
task_struct结构描述在linux 中每一个进程都由task_struct 数据结构来定义. task_struct就是我们通常所说的PCB.她是对进程控制的唯一手段也是最有效的手段. 当我们调用fork() 时, 系统会为我们产生一个task_struct结构。然后从父进程,那里继承一些数据, 并把新的进程插入到进程树中, 以待进行进程管理。因此了解task_struct的结构对于我
2016-06-05 22:16:05
1841
原创 操作系统中常用到的进程调度算法
一、先来先服务最简单的调度算法是先来先服务（FCFS），也称为先进先出（First-In-First-Out,FIFO）或严格排队方案。当每个进程就绪后，它加入就绪队列。当前正在运行的进程停止执行时，选择在就绪队列中存在时间最长的进程运行。二、轮转法这是一种基于时钟的抢占策略，以一个周期性间隔产生时钟中断，当中断发生时，当前正在运行的进程被置于就绪队列中，然后基于FCFS策略选择下一个
2016-06-05 21:46:10
3070
原创 二叉树的线索化
线索化意义：二叉树是非线性结构，遍历二叉树都是通过递归或者用栈辅助非递归来遍历的。如果我们知道一个节点的前驱和后继，那么我们就可直接遍历二叉树设置二叉树节点的前驱和后继，就是线索化二叉树，我们利用指向左右子树的空指针存放节点的前驱和后继线索化设计思路：遍历二叉树，当遍历到一个节点的左节点或右节点为空时，设置它的前驱和后继，那么访问时直接可根据节点的前驱和后继来进行访问代
2016-05-27 23:55:40
1419
原创 广义表的创建及成员函数的实现
广义表是非线性的结构，是线性表的一种扩展，是有n个元素组成有限序列。广义表的定义是递归的，因为在表的描述中又得到了表，允许表中有表。例如：(1)A = ()(2)B = (a,b)(3)C = (a,b,(c,d))(4)D = (a,b,(c,d),(e,(f),h)) 广义表的结构：因此，广义表中包含三种节点，头节点，
2016-04-20 10:44:59
1840
原创 稀疏矩阵的存储方式及其快速转置的实现
稀疏矩阵：M*N的矩阵，矩阵中有效值的个数远小于无效值的个数，且这些数据的分布没有规律。如下图矩阵：稀疏矩阵的压缩存储方式：压缩存储极少数的有效数据。使用{row,col,value}三元组存储每一个有效数据，三元组按原矩阵中的位置，以行优先级先后顺序依次存放（以便转置打印矩阵）。稀疏矩阵的转置：（1）将存储的有效数据行优先存储改为按
2016-04-19 14:52:59
5805
原创 对称矩阵的存储方式
对于N*N的矩阵A，对于任意i和j(N-1>i>=0 && N-1>j>=0)，如果Aij=Aji那么，就称矩阵A是对称矩阵。以矩阵对角线为分界线，矩阵A分为上三角和下三角。如下图：由对称矩阵的性质，存储对称矩阵时，只需要存储对称矩阵的上三角或下三角就可以了（压缩存储），最多存储N*(N+1)/2个数据。对称矩阵和压缩存储的对应关系：下三角存储i>=j, SymmetricMat
2016-04-19 11:11:15
8065
原创 用一个数组实现两个栈
题目：用一个数组实现两个栈方案一：将数组的下标为0的位置当做第一个栈的栈底，下标为1的位置当做第二个栈的栈底，将数组的偶数位置看做第一个栈的存储空间，奇数位置看做第二个栈的存储空间。方案二：从中间分别向两边压栈将数组的中间位置看做两个栈的栈底，压栈时栈顶指针分别向两边移动，当任何一边到达数组的起始位置或是数组尾部，则开始扩容。方案三：从两边向中间压栈
2016-04-18 23:56:31
7024
3
原创 实现一个栈，实现入栈，出栈，求最小值，时间复杂度为O(1)
题目：实现一个栈，实现入栈，出栈，求栈中最小值，时间复杂度为O(1)方案一：设计栈中元素类型为一个包含元素值和当前栈中所有元素的最小值的对象入栈时，将对象入栈，当前元素的值小于栈中最小值时，就将当前元素的最小值设为当前元素的值，保持栈顶的元素对象的最小值一直是栈中所有元素的最小值出栈时，将元素对象弹出栈中元素的最小值：栈顶的元素对象的最小值方案一缺点：每次压入栈中的元素
2016-04-16 23:58:32
6943
原创 验证进栈出栈的合法性
题目：给两个序列，可以用数组来存储，一个数组存放进栈的顺序，一个数组存储出栈的顺序，要求检查这两个序列是否符合进栈和出栈匹配方法：（1）用一个辅助栈，将入栈序列的第一个元素压栈，看是否和出栈序列的第一个元素相等（2）相等则将辅助栈中的元素弹出，继续比较入栈序列的下一个元素和出栈序列的下一个元素是否相等，（3）若不想等则将继续将下一个入栈序列的元素压栈并且判断它是否与出栈序列的当
2016-04-16 23:36:46
984
原创 两个栈实现一个队列
用两个栈实现一个队列主要需要实现的是队列的入队和出队操作。针对这一问题有以下几种方案方案一用一个栈来维护队列的出队，入队操作，具体实现方法如下：入队：将元素压入第一个栈中出队：（1）将第一个栈中的元素（除栈底元素外）依次导入第二个栈中（2）将第一个栈中剩下的那个元素弹出（3）将第二个栈中的元素依次倒回到第一个栈中方案二第一个栈管理队列的入队，第二个栈管理队列的出
2016-04-16 22:43:30
482
原创 两个队列实现一个栈的两种方案
我们都知道，队列的特点是“先进先出”，而栈的特点是“先入后出”。因为栈和队列插入元素的时候都是在尾部进行插入，这个所以插入操作很好解决。而队列是从队头开始删除的，栈是从栈顶删除元素，因此，我们需要考虑怎么将元素进行弹出，解决这个问题有两种方案。方案一：我们用一个队列作为主要维护栈的队列，该队列用来插入元素和弹出元素。插入元素时，将元素直接插入到第一个队列的尾部。弹出元素时：
2016-04-16 09:10:15
487
原创 c++实现队列
队列的数据结构中一种特殊的线性表，特点是“先入先出，后入后出”，如下图：按照队列的特点我们可以自己实现队列，程序如下://Queue.hpp#pragma once#include#include#includeusing namespace std;templatestruct Node{ Node(const T& d) :_data(d) ,_next(
2016-04-13 18:44:21
757
原创 c++实现栈
栈的概念栈是数据结构中一种特殊的线性表，它的基本特性是“先入后出，后入先出”。如下图：650) this.width=650;" title="图片1.png" alt="wKiom1cJJX6QZftdAAAd2u7FNBg489.png" src="http://s5.51cto.com/wyfs02/M02/7E/D1/wKiom1cJJX6QZftdAAAd2u7FNBg489.png"
2016-04-11 20:04:46
359
原创 实现auto_ptr的两种方法
我们都知道，实现auto_ptr有两种方法：第一种方法：在上一篇博客中我已经实现了，主要思想是管理权转移。第二种方法：它是我们c++标准库中以前的一个版本，主要思想是在auto_ptr类中除了有一个指针的成员变量以外还有一个bool类型的成员变量_owner。构造函数中将_owner设为真，表示对象是指针所指向的内存的拥有者，当要赋值时(ap1=ap2)，将ap1的_owner置为true,ap2
2016-04-11 20:04:44
2216
原创 模拟实现c++标准库和boost库中的智能指针
我们知道c++标准库中定义了智能指针auto_ptr，但是我们很少用它，因为虽然它能够自动回收动态开辟的内存，不需要程序员自己去维护动态开辟的内存，但是当用它去赋值或者是拷贝构造时有一个管理权转移的过程，这样我们就不能很方便的使用auto_ptr。下面是简单的auto_ptr的实现，我们可以看到在复制和赋值时它将转移管理权。templateclass AutoPtr{public:
2016-04-11 20:04:41
425
原创 c++模板实现双向链表
#include#includeusing namespace std;templatestruct Node{ Node(const T& d) :_data(d) ,_next(NULL) , _prev(NULL) {} T _data; Node* _next; Node* _
2016-04-11 20:04:38
401
原创 C++模板实现顺序表
#include#includeusing namespace std; templateclass SeqList{public: SeqList() :_size(0) , _capacity(0) { _CheckCapacity(); } void PushBack(const T& d);
2016-04-11 20:04:35
251
原创 string类的写时拷贝
由于浅拷贝使多个对象共用一块内存地址，调用析构函数时导致一块内存被多次释放，导致程序奔溃。实现string类的时候通常显示的定义拷贝构造函数和运算符重载函数。 由于释放内存空间，开辟内存空间时花费时间，因此，在我们在不需要写，只是读的时候就可以不用新开辟内存空间，就用浅拷贝的方式创建对象，当我们需要写的时候才去新开辟内存空间。这种方法就是写时拷贝。 650) this.width=650;" ti
2016-04-11 20:04:29
1420
原创 string类的两种实现方法及string的一些成员函数的实现
string的第一种实现方法：#includeusing namespace std;class String{public: String(char *str="")//构造函数 :_str(new char[strlen(str)+1]) { strcpy(_str, str); } String(const St
2016-04-11 20:04:27
1407
原创 模拟new[]和delete[]操作符开辟内存空间及释放内存空间过程
在上一篇博客里我们知道了new[]和delete[]开辟空间和释放空间时过程，那么我们可不可以模拟实现一下它们的开辟内存和释放内存的过程呢？下面是我模拟new[]和delete[]的实现过程：650) this.width=650;" title="图片1.png" src="http://s5.51cto.com/wyfs02/M01/7C/F3/wKiom1bdHZ7hIvycAAAYY2bh
2016-04-11 20:04:24
586
1
原创 旋转数组的最小数字
题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转，输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}是数组{1,2,3,4,5}的一个旋转，该数组的最小值为1。题目分析：我们可以通过旋转以后的数组中的元素的分布方式找出其中的一些规律：数组{3,4,5,1,2}中，最左边的数字（3）大于最右边的数字（2），由于原数组是递增排序的，所以左边的
2016-04-11 20:04:19
292
原创 实现日期类
题目：实现一个日期类，主要实现日期计算功能：日期+天数=日期；日期-天数=日期；日期-日期=天数；要实现该日期类，必须熟练掌握运算符重载的概念和实现方法。以下是编写的一个日期类： 头文件：#ifndef __DATE_H__#define __DATE_H__#includeusing namespace std;class Date{public: Date(int year =
2016-04-11 20:04:16
299
原创 c++实现复数类
主要是练习用运算符重载实现复数的一些基本运算，包括：复数加法（重载的运算符：+、+=、前置++、后置++）；复数减法（重载的运算符：-、-=、前置--、后置--）；复数乘法（重载的运算符：*、*=、）；复数除法（重载的运算符：/、/=、）；代码如下：#includeusing namespace std;class Complex{public: Complex(float real =
2016-04-11 20:04:13
1442
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人