squack-CSDN博客

原创数据结构---并查集

这段时间自己做了几次笔试题，好几次都遇到了有关于并查集求解的问题。然而因为自己对于并查集的不熟悉导致的结果都很不美好，所以决定深入学习一下并查集。1、并查集的概念并查集是由一个数组、两个函数（查找一个数的根、合并路线）组成，常用来解决一些不相交集合的合并与查找问题。2.并查集实现原理（下文给的图的n都取值为10）（1）元素初始化给定n个元素组成的一个数组，数组的下标依次为0,1...

2018-09-04 15:54:59 293

原创动态内存管理

1、了解内存 2.C语言动态内存管理C语言使用malloc/calloc/realloc在堆上进行空间开辟，使用free进行空间释放； malloc和free都声明在头文件 stdlib.h 中2.1malloc（1）函数原型：void* malloc(size_t size)（2）参数：内存空间的长度（3）返回值：返回值是一个指向开辟空间的起始地址的一个指针如...

2018-09-01 16:26:44 204

原创三种页面置换算法

1、为什么要有页面置换算法程序运行过程中，有时要访问的页面不在内存中，而需要将其调入内存。但是内存已经无空闲空间存储页面，为保证程序正常运行，系统必须从内存中调出一页程序或数据送到磁盘对换区，此时需要一定的算法来决定到低需要调出那个页面。通常将这种算法称为“页面置换算法”。2.页面置换算法的分类2.1 最佳置换算法（OPT）（1）实现原理：每次选择未来长时间不被访问的或者以后永不使...

2018-08-31 10:47:39 24452 10

原创进程间通信---信号量

1.基本概念（1）临界资源：系统内某些资源一段时间内只能被一个进程使用，称这样的资源为临界资源。（2）临界区：在进程中涉及到互斥资源的程序段称为临界区。（3）进程互斥：某些资源在被一个进程访问时，其他进程要想访问就必须等待，当资源被访问完了之后才可以被其他进程访问。（4）进程同步：多个进程相互配合共同完成一项工作。（5）互斥实例火车票售票例子：有两个进程A进程、B进程，...

2018-08-30 21:15:57 549

原创死锁

1. 死锁的定义（1）概念一个进程组内的每一个进程都在等待仅由该组进程内的其他进程才能引发的事件，那么该进程是死锁的。如：小A与小B一起去吃饭，桌子上只有两根筷子。小A拿一根筷子，小B拿起另一根筷子，当菜上桌时，小A需要小B的那根筷子才能够迟到饭，小B需要小A的那根筷子才能吃到饭，但是他们彼此又都不愿意将自己的筷子给对方，从而两人就会无休止的等下去，都吃不了饭。这种现象就是死锁。...

2018-08-30 16:23:48 211

原创面向对象特性之继承

1.继承的概念1.1 为什么要有继承在C++中，每一个类都有属于自己的成员函数与成员变量，但有的时候有两个类的成员函数与成员变量相同，为了避免对此重复定义相同的类，引入继承，子类只需继承父类的成员函数与变量即可1.2 继承的定义在创建一个类时，不需要重新编写成员函数与成员变量，只需要指定新建的类继承了一个已有的类即可；已有的类是父类（基类），新建的类是子类（派生类）；继承是...

2018-08-29 15:17:53 273

原创 C语言---小算法

题目：1元钱一瓶汽水，喝完后两个空瓶换一瓶汽水，问：你有20元钱，最多可以喝到几瓶汽水？分析：一元钱一瓶水，则N元钱就可以买N瓶水；假设有N个空瓶，则可以换的N/2瓶水，则此时有空瓶N/2+N%2; 当空瓶的数量小于2的时候，无法再换水int main(){ int money = 20; int s = money; while (money >...

2018-08-28 15:06:55 302

原创 C++---引用的基础知识

1.引用1.1 定义引用就是变量的别名（并没有重新定义一个变量），通过将声明符写成&d的形式来定义引用类型。需注意的是：一个变量可以有多个别名；引用的变量必须初始化；引用只能在初始化的时候使用一次，不能再引用改变其他变量如下所示，已定义变量a,b与c相当于a的别名，即a可以叫b，也可以叫c；b、c与a指向同一块空间，当其中一个改变时，其他的值也跟着改变in...

2018-08-28 11:39:49 164

原创 C++基础知识（命名空间、重载、缺省参数）

一、类型分类类型分类：基础类型自定义类型二、命名空间1.命名空间相当于全局域，用{}括起来一个文件，用namespace给这个文件命名。 std是C++库里的文件，它的使用有两种方法，一种是using namespace std，一种是std::cout<<i<<std::endl（::是域作用解析符）。2....

2018-08-27 21:34:13 242

原创应用层---HTTP协议

应用层应用层是TCP/IP协议分层的最顶层模型，它的作用是维持好应用程序之间的沟通，维护好特定的协议。如简单电子邮件传输（SMTP），文件传输协议（FTP），网络远程访问协议（Telnet）等。应用层协议分为两种，一种是根据客户要求自己对数据格式约定的自定制应用层协议；另一种是应用层知名协议，即已被他人定义好且十分好用的应用层协议，其中HTTP协议就是其中一种。HTTP协议-超文本传...

2018-08-27 17:44:30 5755

原创 TCP与UDP的比较

TCP与UDP的对比1、协议段格式不同（1）UDP的报头有8字节，TCP的报头有20个字节，UDP比TCP更为简单（2）UDP有16位UDP长度能确认报文长度，而TCP只有4位首部长度，无法确认报文长度，容易发生粘包问题（3）UDP的报头有源端口号、目的端口号、16位UDP长度、16位校验和；而TCP的报头不仅有源端口号、目的端口号、16位校验和，还有32位序号和确认序号、4位首部...

2018-08-26 11:26:36 353

原创进程间通信---共享内存

1.什么是共享内存在物理空间申请一块内存，这块内存通过页表映射到对个进程的共享存储映射区，一进城可通过页表向这个内存里写数据，一进城可通过页表从这块内存中拿数据。这个可被多个进程所能利用的内存称为共享内存。内存映射到共享他们的进程的地址空间，则数据的传输不再涉及内核，所以共享内存是最快的IPC方式。2.共享内存的特点（1）共享内存是双向通信（全双工）。（2）共享内存是IPC...

2018-08-21 17:34:32 338

原创传输层---TCP协议

1.TCP协议段格式源端口号/目的端口号：知道数据从哪进程中来，要到哪个进程中去32位序号/32位确认序号：传输数据时按字节进行编号，序号保证数据按序到达，而双方都需要确认，所以有序号和确认序号4位首部长度：将报头与有效载荷进行分离。4位表示的最大数据是15，则头部最大长度=15*4=60。6位标志位： URG:紧急指针标志位 ACK：确认标志位。ACK=1...

2018-08-19 15:14:39 3572

原创进程间通信-消息队列

1.消息队列的概念消息队列其实就是一个链表，往消息队列写数据解释向链表里插入一个消息节点，从消息队列里拿数据就是访问该节点，访问完删除该节点。一个消息队列由标识符来标识2.消息队列函数2.1 msgget函数---打开或创建消息队列头文件：#include<sys/ipc.h> #include<sys/ipc.h>函数实现 ...

2018-08-18 23:00:32 361

原创进程间通信---管道

1.进程间通信介绍 (1) 进程间通信(IPC)：多个进程间进行信息交流 (2) 进程间通信的方式：管道、消息队列、共享内存、信号量、socket等； (3) 进程间通信的目的：数据传输：一个进程将他的数据发给另一个进程资源共享：多个进程间共享同样的资源通知事件：一个进程给另一个进程发消息，通知他发生了什么事...

2018-08-18 11:34:34 211

原创 TCP协议客户端与服务器端一般的通信过程

服务器初始化（1）调用socket,创建文件描述符（2）调用bind,将文件描述符与ip/port连接起来。若端口号已被占用，则bind失败（3）调用listen，声明该文件描述符是服务器的一个文件描述符，为之后的accept做准备（4）调用accept,并处于阻塞状态，等待客户端连接建立连接（1）调用socket，创建文件描述符 ...

2018-08-17 23:22:51 30190 3

原创异常

处理错误的方法传统处理异常的方法1.中断程序 2.返回错误码 3.调用一个预先设置的出现错误时需要调用的函数—-回调函数 #include<iostream> #include<stdio.h> #include<errno.h> void Test() { FILE* fout=fopen("test.c","...

2018-08-17 07:45:44 184

原创排序算法的比较

插入排序直接插入排序void insertsort1(int* a, int n){ assert(a); int i = 0; int end = 0; int tmp = 0; for (i = 0; i < n-1; ++i) { end =...

2018-08-14 17:55:10 194

原创 vector的基本使用

vector是STL最常见的容器，它是一种顺序容器，可以随机访问。vector是一块连续分配的内存，与数组较为相似。不同之处在于数组是静态分配内存，确定大小之后不能改变；vector是动态分配内存，可根据自身元素的不断增多而进行的增容。1.声明头文件要使用vector，必须添加头文件，而且如果没有命名空间using namespace std的声明，每次在使用vector时vector的前...

2018-07-27 11:49:53 322

原创面向对象的特性---多态

多态 1.虚函数：在类的成员函数前加virtual即构成虚函数。作用是通过基类的指针与引用调用派生类的成员函数 2.多态的概念多态即多种形态，通过调用不同的函数实现不同的功能。如买票机制，不同的对象买票的制度也不同，如普通人买全票，学生可买半价票等。 3.多态的条件（1）虚函数的...

2018-07-27 08:49:24 6363

原创使用shell脚本打印9*9乘法表

1.for循环打印9*9乘法#！/bin/bashfor (( i=1;i<=9;++i ))do for (( j=1;j<=i;++j )) do echo -n "${i}*${j}=$((i*j)) " done echo " " #换行done输出结果：2.while循环打印9*9乘法...

2018-07-26 21:12:46 1499

原创 shell的循环语句

输出1-10个数，依次用循环实现1.for循环（类似C语言）2.for in循环3.while循环4.until循环5.命令行循环6.死循环#！ /bin/bashfor (( ;; ))do echo "haha"done#！/bin/bashwhile true;do echo "haha"done上面的两...

2018-07-26 20:56:03 1685

原创 shell脚本初学

1.基本概念shell脚本是一门解释非编译、弱类型的脚本语言，意思是说shell是命令行解释器，它在执行时不需要编译，且shell中的变量不需要定义类型。shell执行命令的方式有两种：（1）交互式：用户输入一条命令，shell就解释执行一条；（2）批处理：用户事先写一个Shell脚本，其中有很多条命令，让Shell一次把这些命令执行完，而不必一条一条的敲命令。shell的开头...

2018-07-26 20:26:13 192

原创传输层—UDP协议

UDP协议端格式（1）源端口号与目的端口号：都是16位，指数据从的进程来源与进程去向。（2）16位UDP长度：指整个数据报（UDP首部+UDP数据）的长度，UDP首部固定为8字节，UDP数据最大为65535-8=65527字节。（3）16位UDP校验和：检验整个数据报、UDP首部等在数据传输中是否出错...

2018-07-10 16:24:28 501

原创套接字

套接字--IP地址+端口号 1.IP地址----确认插入互联网中的某一台主机 IP数据包头中有两个IP地址：源IP地址与目的IP地址，源MAC地址与目的MAC地址 2.端口号=进程号，确定某台主机上的某一个进程 3.套接字确定了互联网中某台主机上的某一个进程。 4.PID表示惟一的一个进程，在任何场景都适用，而端口号也表示唯一一个进程，在网络场景下适用。 5.一个进程可能绑定多...

2018-07-10 10:28:19 1067

原创结构体在内存中的对其原则

类对象存储模型一个结构体定义完了之后，其在内存中的存储并不等于所有元素宽度之和。基本数据类型结构体遵循原则一：结构体中的元素是按照定义的顺序一个个放到内存中去的，并不紧密排布。从内存存储单元的首地址（0）开始，每一个元素都认为内存根据它的大小来划分，所以每一个元素存放的位置从自己宽度的整数倍开始。原则二：经原则一后，计算出结构体的存储单元是否是宽度最长元素的...

2018-07-07 16:55:24 308

原创堆的实现

堆数据结构是一种数组对象，它可以被视为一颗完全二叉树结构。堆结构的二叉存储是最大堆：每个父节点大于左右孩子节点最小堆：每个父节点小于左右孩子节点实现的基本接口#include<vector>template<class T>class Heap{public: Heap()//无参构造函数,若开始堆是空的则调用 {} Heap(T* a,...

2018-04-04 23:01:47 363

原创 map和set的使用

set的使用set集合是C++ STL库中自带的容器，常用的操作有： begin（）----返回set容器的第一个元素地址 end（）----返回set容器的最后一个元素地址 clear（）---删除set容器中所有元素 empty（）---判断set容器是否为空 size（）--...

2018-04-04 22:46:36 707

原创大端存储与小端存储

大小端小端：数据的低字节存到内存的低地址处，数据的高字节存到内存的高地址处大端：数据的低地址存到内存的高地址处，数据的高地址存到内存的低地址处大小端判断例题一般的解法：利用联合解决大小端判断int check_sys(){ union Un//联合类 { char c;...

2018-03-25 12:06:46 196

原创模拟实现strcat

strcat,字符串连接，其连接原理如下图所示：直接调用strcat的代码#include<stdio.h>#include<stdlib.h>#include<string.h>int main(){ char arr[20] = "this is "; char *arr2 = "cool"; strcat(arr, arr2); prin...

2018-03-15 19:27:56 119

原创模拟实现库函数strcpy

strcpy-字符串拷贝，即需要将源字符串的内容拷贝到需要拷贝的空间中调用库函数strcpy代码实现#include<stdio.h>#include<stdlib.h>#include<string.h>int main(){ char arr[20] = { 0 }; char *p = "this is cool"; strcpy...

2018-03-14 21:16:02 168

原创 Linux的基本指令

1.了解Linux的权限管理(1)文件访问者的分类文件和文件目录的所有者：u--user文件及目录所有者所在的组用户：g--group其他用户：o--others(2)文件访问权限的种类基本权限：读（r）:read对文件而言，具有读取文件内容的权限；对目录而言，具有浏览该目录信息的权限。写（w）:write对文件而言，具有修改文件内容的权限；对目录而言，具有删除移动...

2017-12-03 22:21:58 215

原创 C++类和对象--四个默认函数+运算符重载

C++类的基本点（1）类的定义在C++中，用“类”描述“对象”。对象是构成系统的基本单位，可以是自然物体，也可以是一种逻辑结构等。类是所有面向对象的语言的共同特征，类是对象的抽象，而对象是类的具体实例。可以说类是对象的模板，用来定义对象的抽象类型。（2）成员访问限定符 public（公有的）：既可以被本类中的成员函数引用，也可以被类的作用域的其他函数所用。 pr...

2017-10-10 19:53:04 304

原创 C++入门基础知识

命名空间命名空间，就是根据需要指定的一些有名字的内存区域。把一些全局实体分别放在各个命名空间中，从而与全局实体分隔开。如namespace MY{ int a = 0;}namespace YOU{ int a = 1;} 其中namespace是定义命名空间所必须写的关键字，MY和YOU是自己定义的命名空间的名字（可用任意合法的标识符），花括号里的是命名空间...

2017-09-26 21:40:21 212

原创数组的简单解析

数组是最基本的构造类型，它是一组相同类型数据的有序集合。数组中的元素在内存中连续存放，每个元素都属于同一数据类型，用数组名和下标可以唯一确定数组元素。

2017-07-14 10:57:34 2601

原创交换两个变量a与b的值

很多编程的初学者都会遇到交换两个变量的值的问题，而我最近也遇到了并有了自己的一些想法，所以在此记录下来，希望能对于我一样的初学者们有所帮助。问题：交换两个变量a与b的值，并输出交换后的值。一开始遇到这道题，我的基本想法就是定义一个新的变量c作为中间变量，让c=a,a=b.b=c就可任意完成这个问题了。程序代码如下： #include<stdio.h>#i...

2017-07-07 16:25:54 7860

qq_39290490的博客