yummy_alice-CSDN博客

转载排序算法时间复杂度、空间复杂度、稳定性比较

排序算法分类排序算法比较表格填空 **注： 1 归并排序可以通过手摇算法将空间复杂度降到O（1），但是时间复杂度会提高。 2 基数排序时间复杂度为O（N*M），其中N为数据个数，M为数据位数。**辅助记忆原理理解1 冒泡排序1.1 过程冒泡排序从小到大排序：一开始交换的区间为0~N-1，将第1个数和第2个数进行比较，前面大于后面，交换两...

2018-08-13 15:41:47 276 2

原创 malloc/free与new/delete区别

malloc函数malloc的全称是memory allocation，中文叫动态内存分配。原型：extern void *malloc(unsigned int num_bytes); 说明：分配长度为num_bytes字节的内存块。如果分配成功则返回指向被分配内存的指针，分配失败返回空指针NULL。当内存不再使用时，应使用free()函数将内存块释放。void *malloc(...

2018-08-11 09:57:02 142

原创题型——[LeetCode] Remove Nth Node From End of List 移除链表倒数第N个节点

Given a linked list, remove the nth node from the end of list and return its head. For example, Given linked list: 1->2->3->4->5, and n = 2.After removing the second node from the e...

2018-08-09 15:02:06 131

原创题型——rotate-list

Given a list, rotate the list to the right by k places, where k is non-negative. For example: Given 1-&gt;2-&gt;3-&gt;4-&gt;5-&gt;NULL and k = 2, return 4-&gt;5-&gt;1-&gt;2-&gt;3-&a

2018-08-09 10:38:18 127

此题我们可以先定义两个指针，p和q。让p和q都指向头结点。在定义一个i，i的初始值为0。然后进入一个for循环，直到p走到链表结尾，每次i++。当i &amp;lt; k 的我们让p走，q不走。当i &amp;gt;= k 的时候我们让p和q同时走一步。当p走到结尾的时候，那么q走的值就是倒数k的位置，我们返回这个值就好了。我们在用图来说明一下我们假设k = 3，即输出链表中倒数第3个结点的值。一...

2018-08-02 14:52:59 7020

原创题型——合并两个排序的链表

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。此题我们可以public class Solution { public ListNode Merge(ListNode pHead1,ListNode pHead2) { if(pHead1 == NULL) { retur...

2018-08-01 16:46:57 91

原创题型——复杂链表的复制

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空此题是一个复杂链表的复制，我们的思路分为三部分。1、根据原始链表的每个结点N创建对应的N’，再把N’放到N的后面。2、设置复制出来的结点的random结点，假设原始链表上的...

2018-08-01 16:19:28 106

原创 sizeof和strlen的用法及区别

通常我们计算一个数组的长度都喜欢用sizeof和strlen来计算。今天就来说说sizeof和strlen具体的用法以及他们之间的区别。sizeof首先sizeof(…)是运算符，在头文件中typedef为unsigned int，其值在编译时即计算好了，参数可以是数组、指针、类型、对象、函数等。由于在编译时计算，因此sizeof不能用来返回动态分配的内存空间的大小。实际上，用si...

2018-07-27 16:09:46 466

原创 Linux——进程的优先级

进程优先级基本概念 * CPU资源分配的先后顺序，就是进程的优先权 * 优先权高的进程有优先执行的权利。配置进程优先权对多任务环境的Linux很有用，可以改善系统性能。 * 还可以吧进程运行到指定的CPU上，这样一来，把不重要的进程安排到某个CPU，可以大大改善系统的整体性能。查看系统进程在Linux或者nuix系统中，用ps-l命令则会类似输出一下几个内容: 在...

2018-07-27 11:00:28 289

原创 Linux——TCP的粘包问题

TCP面向字节流创建一个TCP的socket，同时在内核中创建一个发送缓冲区和一个接收缓冲区； *调用write，数据会先写入发送缓冲区中； *如果发送的字节数太长，会被拆分成多个TCP的数据包发出； *如果发送的字节数太短，就会现在缓冲区里等着，等到缓冲区长度差不多了，或者其他合适的时机发送出去；接收数据的时候，数据也是从网卡驱动程序到达内核的接收缓冲区；然后应用程序...

2018-07-27 10:42:44 307 1

原创 static总结

今天来总结一下static。首先变量和函数的属性包括数据类型和数据的存储类别，存储类别指数据在内存中存储方式（静态和动态），包含auto，static，register，extern四种。具体点来说内存分为三块:静态区，堆区，栈区。外部变量和全局变量存放在静态区，局部变量存放在栈区，动态开辟的内存存在堆区。extern 外部变量声明，是指这是一个已在别的地方定义过的对象，这里只是对变量...

2018-07-26 16:28:37 188

原创题型——末尾0的个数

此题选C，Telnet协议是TCP/IP协议族中的一员，是Internet远程登录服务的标准协议和主要方式。它为用户提供了在本地计算机上完成远程主机工作的能力。在终端使用者的电脑上使用telnet程序，用它连接到服务器。终端使用者可以在telnet程序中输入命令，这些命令会在服务器上运行，就像直接在服务器的控制台输入一样。可以在本地就能控制服务器。要开始一个telnet会话，必须输入用户名和密...

2018-07-26 14:34:08 352

原创 C++——Vector和List

1、vector连续存储结构，每个元素在内存上是连续的；支持高效的随机访问和在尾端插入/删除操作，但其他位置的插入/删除操作效率低下；相当于一个数组，但是与数组的区别为：内存空间的扩展。vector支持不指定vector大小的存储，但是数组的扩展需要程序员自己写。vector的内存分配实现原理：STL内部实现时，首先分配一个非常大的内存空间预备进行存储，即capacity（）函数返回的...

2018-07-25 15:07:24 217

原创 C++——日期类实现

头文件#pragma once#include <iostream>using namespace std;class Date{public: Date(int year = 1900,int month = 1,int day = 1); Date(const Date& d); void Dateshow(); int Ge...

2018-07-25 11:23:59 582

原创 C++——类和对象（二）

隐含的this指针 1、每个成员函数都有一个指针形参，它的名字是固定的，称为this指针，this指针是隐式的。（构造函数比较特殊，没有这个隐含this形参） 2、编译器会对成员函数进行处理，在对象调用成员函数时，对象地址作实参传递给成员函数的第一个形参this指针。 3、this指针是成员函数隐含指针形参，是编译器自己处理的，我们不能在成员函数的形参中添加this指针的参数定义，也不能在调...

2018-07-19 16:00:37 159

原创 C++——类和对象（一）

面向对象概念：面向对象是一种程序设计范型，同时也是一种程序开发的方法。对象指的是类的实例，将对象作为程序的基本单元。将程序和数据封装其中，以提高软件的重用性，灵活性和扩展性。三大特性：封装，继承，多态类（class/struct)：数据（成员变量）、程序（成员函数）三种访问限定符：public（共有）、protected（保护）、private（私有）。 1、public成员可...

2018-07-18 15:35:37 144

原创 C++——引用和指针

1、引用的概念及用法引用不是定义一个新的变量，而是给一个已经定义的变量重新起一个别名。定义的格式为：类型&引用变量名 = 已定义过的变量名；引用的特点： 1、一个变量可取多个别名 2、引用必须初始化 3、引用只能在初始化的时候引用一次，不能改变为再引用其他的变量。引用作为参数 1、值传递，如果形参为非引用的传值方式，则生成局部临时变量接收实参的值void S...

2018-07-18 13:31:28 107

原创 C++——初识C++

简介C++是C语言的继承，它既可以进行C语言的过程化程序设计，又可以进行以抽象数据类型为特点的基于对象的程序设计，还可以进行以继承和多态为特点的面向对象的程序设计。C++擅长面向对象程序设计的同时，还可以进行基于过程的程序设计，因而C++就适应的问题规模而论，大小由之。 C++不仅拥有计算机高效运行的实用性特征，同时还致力于提高大规模程序的编程质量与程序设计语言的问题描述能力。发展历史...

2018-07-06 10:44:59 428

原创 Linux-网络编程套接字

理解源IP地址和目的IP地址在IP数据报头部中，有两个IP地址，分别叫做源IP地址和目的IP地址。认识端口号端口号是传输层协议的内容端口号是一个2字节十六位的整数端口号用来标识一个进程，告诉操作系统，当前的这个数据要交给哪一个进程来处理； IP地址+端口号能被标识网络上的某一台主机的某一个进程一个端口号只能被一个进程占用一个进程可以绑定多个端口号，但是一个端口号不能被...

2018-06-29 16:40:24 137

原创数据结构之二叉搜索树

二叉搜素树，又名二叉查找树，二叉排序树。它具有以下特点： 1、若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 2、若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 3、它的左、右子树也分别为二叉排序树。下面我们实现以下二叉搜索树的一些基本操作： 1、初始化 2、销毁 3、插入 4、删除 5、查找 ...

2018-06-06 17:27:03 167

原创 Linux - 初识网络

网络发展独立模式：计算机之间相互独立；网络互连：多台计算机连接在一起，完成数据共享；网络间通信局域网LAN：计算机数量更多了，通过交换机和路由器连接在一起；广域网WAN：将远隔千里的计算机都连在一起。网络协议初识 TCP/IP五层模型 TCP/IP是一组协议的代名词，它还包括许多协议，组成了TCP/IP协议簇。 TCP/IP通讯协议采用了5层的层级结构，每层都呼叫它的...

2018-06-02 10:53:15 235

原创数据结构之堆的基本操作

今天我们来说一说堆，堆是一个完全二叉树，堆分大堆和小堆。小堆：这个树的根节点是这个树中的最小的元素对于任意一个子树来说, 子树的根节点, 小于左右孩子节点的值. 大堆：这个树的根节点是这个树种的最大元素对于任意一个子树来说, 子树的根节点, 大于左右孩子节点的值. 下面我们画图来说明一下。下面我们实现堆的基本操作1、定义一个堆我们定义一个堆的结构体，将堆...

2018-05-26 14:20:51 411

原创数据结构之哈希变形（位图）

Bitmap.h#pragma once#include <stdio.h>#include <stdlib.h>#include <string.h>#include <stdint.h>typedef uint64_t BitmapType;typedef struct Bitmap{ BitmapType* data;...

2018-05-25 10:04:23 156

原创进程组/作业/会话以及守护进程

1、进程组每个进程除了有一个进程ID之外，还属于一个进程组。进程组是一个或多个进程的集合。通常，它们与同一个作业相关联，可以接受来自同一终端的各种信号。每个进程组有一个唯一的进程组ID。每个进程组都可以有一个组长进程。组长进程的标识是，其进程组ID等于其进程ID。组长进程可以创建一个进程组，创建该组中的进程，然后终止。只要在某个进程组中的一个进程存在，则该进程组就存在，这与其组长进程是否终止无...

2018-05-19 14:15:44 152

原创迷宫

void MazeInit(Maze* maze)//初始化地图{ if(maze == NULL) { return; } int map[ROW][COL] = { {0,1,0,0,0,0}, {0,1,1,1,0,0}, {0,1,0,1,1,0}, {1,1,0,0,1,0}, {0,0,0,0,0,0}, {0,0...

2018-04-27 09:03:46 158

原创二叉树

一、二叉树的概念一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树组成。二、二叉树的特点 1、每个结点最多有两棵子树，即二叉树不存在度大于2的结点。 2、二叉树的子树有左右之分，其子树的次序不能颠倒。三、二叉树的表示方法 1、双亲表示法 2、孩子表示法 3、双亲孩子表示法 4、孩子兄弟表示法四、二叉树的遍历遵循某种次序，...

2018-04-26 19:55:38 164

原创线程死锁

1、什么是线程死锁？线程死锁是指由于两个或多个线程互相持有对方所需要的资源，导致这些线程处于等待状态，无法前往执行。当线程互相持有对方所需要的资源时，会互相等待对方释放资源，如果线程都不主动释放所占有的资源，将产生死锁。2、产生死锁的4个必要条件（1）互斥条件：进程对所分配到的资源具有排他性，即一个资源只能被一个进程所占有，直到该进程被释放。（2）请求和保持条件：一个进程在请求被占...

2018-04-23 18:33:25 366

原创栈和队列笔试题

1、最小栈#include <stdio.h>#include "seqstack.h"typedef struct Min_SeqStack { SeqStack stack; }Min_SeqStack;void Min_SeqStackPrint(Min_SeqStack* s){ if(s == NULL) { return; } ...

2018-04-22 21:24:27 192

原创线程的同步与互斥

线程是存在同步和互斥的。我们先来看一个操作共享变量会有问题的售票系统代码#include <stdio.h>#include <stdlib.h>#include <string.h>#include <unistd.h>#include <pthread.h>int ticket = 100;void *route...

2018-04-22 19:09:56 124

原创线程的基本概念

线程的概念： 1、在一个程序里的一个执行路线就叫做线程。更准确的定义为：线程是“一个进程内部的控制序列”。 2、一切进程至少都有一个执行线程。进程和线程的区别： 1、进程是资源竞争的基本单位。 2、线程是程序执行的最小单位。 3、线程共享进程数据，但也拥有自己的一部分数据。线程的优点： 1、创建一个新线程的代价要比创建一个新进程的...

2018-04-21 10:00:51 220

原创 POSIX信号量——生产者消费者模型

今天我们来写一个基于固定大小的环形队列的生产者消费者模型。首先来画图说明一下这是一个环形队列的生产者消费者模型。生产者用P表示，消费者用C表示。这个环形队列的每一段空间我们用semBlank表示，放入的内容我们用semData表示。生产者首先要申请一个semBlank，然后放入semData。消费者则是要先拿一个semData，然后释放一个semBlank。在这个环形队列中我们...

2018-04-20 22:26:53 508

原创顺序队列

SeqQueue.h#pragma once#include <stdio.h>#include <stddef.h>#define SQUEUEMAX 1000typedef char SeqQueueType;typedef struct SeqQueue{ SeqQueueType data[SQUEUEMAX]; size_t he...

2018-04-20 15:32:16 86

原创顺序栈

SeqStack.h#pragma once#include <stdio.h>#include <stddef.h>#include <stdlib.h>typedef char SeqStackType;typedef struct SeqStack{ SeqStackType* data; size_t capacity;/...

2018-04-20 15:23:43 147

原创常见面试题

1、strlen 和 size of 的区别通常我们计算一个数组的大小用strlen和size of 来计算，那么两者有什么区别呢？（1）strlen是一个函数，而size of 是一个运算符。（2）size of计算的是这个数组所存储的内存数（字节大小），可以用类型做参数，而strlen相当一个计数器，只能用char*做参数，计算的是字符串数组的元素个数，以 \n 结尾。2 ...

2018-04-18 15:26:54 125

原创静态库动态库

我们使用ls-l的时候看到的除了看到文件名，还看到文件的元数据拥有的权限硬链接数文件所有者组大小文件最后修改时间文件名ls-l读取存储在磁盘上的文件信息，然后显示出来其实这个信息除了通过这种方式来读取，还有一个sata命令能够看到更多的信息这里写图片描述上面的执行结果有几个信息需要解释一下 inode 为了能解释清楚inode我...

2018-04-18 15:11:08 102

原创常见链表面试题

头文件以及定义的节点都在上一篇的单链表功能实现里面有写逆序打印单链表递归方式简洁明了void linklist_reverseprintf(linklist *head){ if(head == NULL) { return;//空链表 } linklist_reverseprint(head->next); pr...

2018-04-09 16:21:06 119

原创实现一个有头结点有环的双链表

在之前的博客里我们讲到了不带头节点不带环的单向链表，今天我们来实现一个有头结点有环的双向链表。我们首先设置一个头结点，这个头结点的数据是无意义的，我们再设置一个环，让这个链表的尾巴指向头称为一个带环链表。相比于之前的单向链表，这次我们多加了一个prev指针，成为双向链表。如图就是我们的有头有环的双向链表。画的太丑了.... 话不多说，直...

2018-04-06 16:27:41 221

原创 popen、system函数和fork的区别

首先我们先来说一说我们熟知的fork函数。 fork（）一个程序一调用fork函数，系统就为一个新的进程准备了前述三个段，首先，系统让新的进程与旧的进程使用同一个代码段，因为它们的程序还是相同的，对于数据段和堆栈段，系统则复制一份给新的进程，这样，父进程的所有数据都可以留给子进程，但是，子进程一旦开始运行，虽然它继承了父进程的一切数据，但实际上数据却已经分开，相互之间...

2018-03-28 14:08:15 211

原创自主实现一个简单的myshell

#include <stdio.h>#include <stdlib.h>#include <unistd.h>#include <sys/wait.h>#include <string.h>void dasan(char buf[],char *argv[]){ int argc = 0; char *p...

2018-03-28 12:47:12 397

原创完成单链表的后续操作（实现一个无头无环的单链表）

之前我们完成了顺序表的一些操作，今天我们就来说一说链表。链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要开辟内存单元。链表有一个“头指针”变量，以head表示，它存放一个地址。该地址指向一个元素。链表中每一个元素称为“结点”，每个结点都应包括两个部分：一为用户需要用的实际数据，二为下一个结点的地址。因此，head指向第一个元素：第一...

2018-03-27 19:55:25 211

空空如也

空空如也