目录存储形式
目录在文件系统中的存储方式与常规文件类似,常规文件包括了inode节点以及文件内容数据存储块。
目录是由inode节点和目录块构成,目录块记录了哪些文件组织在目录下,记录它们的文件名以及inode编号。
目录块中有多个目录项,每一个目录项都会对应到该目录下的某一个文件,目录项记录了该文件的文件名以及inode节点。
- 普通文件由inode节点和数据块组成。
- 目录由inode节点和目录块组成。
rmdir只能删除空目录,连软链接也不能删除。
puts()函数输出字符串并换行,把字符串输出到标准输出设备上,并将\0’转为换行符’‘\n’。
但fputs没有输出换行符。
scanf会将空格作为字符串的分隔符,但是gets()不会
字符串拼接
char* strcat(char* dest, const char* src);
字符串拷贝strcpy
把字符串转化为十进制数atoi atol atoll
将数字转化为字符串
sprintf(str, "%d", 500);
随机数与伪随机数
通过rand()可以得到[0,RAND_MAX]之间的伪随机数,但是每次运行的序列是相同的,通过srand()设置随机数种子。
中断服务程序与普通程序区别
中断服务程序是一种特殊的程序,它在计算机系统中用于处理硬件中断。
当硬件设备需要引起处理器注意时,会发出中断信号,这时处理器会立即暂停当前任务,转而执行与中断号相关联的中断服务程序。
与普通任务的不同点包括:
- 响应时间:中断服务程序必须立即响应中断信号,因为它们处理的是硬件设备发出的请求,而不是按照程序设计顺序执行的任务。
- 优先级:中断服务程序通常具有较高的优先级,因为快速响应和处理硬件问题对系统的正常运行至关重要。
- 执行方式:中断服务程序在执行时暂时中断正在运行的普通任务,完成中断后,会恢复被中断的任务继续执行。
- 环境要求:由于中断服务程序可能在任何时刻被触发执行,因此需要设计为尽可能短小高效,以保证系统的实时性和稳定性。
实时操作系统和分时操作系统的区别
响应时间要求不同
- 实时操作系统要求系统能够在严格的时间限制内完成任务响应,通常以毫秒甚至微妙为单位。这意味着RTOS需要确保在预定的时间内完成任务,以避免系统失效或产生严重后果(如飞行控制系统)。
- 分时操作系统更注重资源共享和公平性,通过时间片轮转机制来分配处理器时间,以便多个用户或多个任务共享系统资源。
任务调度方式不同
- RTOS的调度算法通常基于优先级,以确保高优先级任务可以立即得到处理器的响应。
- 分时操作系统使用轮转或优先级调度,但更注重公平性和资源的合理利用,确保每个用户或任务都能够得到适当的处理器时间。
应用场景不同
- 实时操作系统适用于对时间要求极高的应用,如航空航天,医疗设备,工业自动化等领域。
- 分时操作系统则广泛用于桌面计算机、服务器和大多数一般用途的计算机设备中,能够同时处理多个任务和用户的需求。
Windows操作系统不是一个严格意义上的实时操作系统,虽然能够处理实时任务,但设计更多考虑多任务处理和用户体验,响应时间通常更长。
Windows操作系统会使用更复杂的调度算法,如多级反馈队列调度。
进程与线程的区别
进程
- 进程是程序的执行实例,是资源分配的基本单位。
- 每个进程都有自己独立的内存空间,包括代码、数据、堆栈等。
- 进程之间通常是独立的,彼此不会直接共享内存,通信需要通过特定的机制,如管道、套接字等。
线程
- 线程是进程中的一个指向单元,是操作系统能够进行调度的最小单位。
- 同一进程的多个线程共享相同的内存空间和资源,包括代码段和数据段。
- 线程可以高效地完成多任务处理,因为线程间的切换比进程间的切换开销小。
关键区别
- 进程是资源分配的单位,线程是操作系统调度的单位。
- 每个进程都有独立的内存空间,线程共享所属进程的内存。
- 进程之间 通信复杂且开销较大,线程之间可以通过共享内存等方式方便地进行通信。
分割链表
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* partition(ListNode* head, int x) {ListNode* p = head;ListNode* left = nullptr;ListNode* leftHead = nullptr;ListNode* right = nullptr;ListNode* rightHead = nullptr;while(p){if(p->val < x){if(left == nullptr){leftHead = p;left = p;}else{left->next = p;left = left->next;}}else{if(right == nullptr){rightHead = p;right = p;}else{right->next = p;right = right->next;}}p = p->next;}if(leftHead != nullptr){if(rightHead != nullptr){right->next = nullptr;left->next = rightHead;}else{left->next = nullptr;}return leftHead;}return head;}
};
LRU缓存
请设计并实现一个满足LRU约束的数据结构。
实现LRUCache类:
哈希表+双向链表
LRU缓存机制可以通过哈希表辅以双向链表实现,我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。
struct DLinkedNode {int key, value;DLinkedNode* prev;DLinkedNode* next;DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};class LRUCache {
private:unordered_map<int, DLinkedNode*> cache;DLinkedNode* head;DLinkedNode* tail;int size;int capacity;public:LRUCache(int _capacity): capacity(_capacity), size(0) {// 使用伪头部和伪尾部节点head = new DLinkedNode();tail = new DLinkedNode();head->next = tail;tail->prev = head;}int get(int key) {if (!cache.count(key)) {return -1;}// 如果 key 存在,先通过哈希表定位,再移到头部DLinkedNode* node = cache[key];moveToHead(node);return node->value;}void put(int key, int value) {if (!cache.count(key)) {// 如果 key 不存在,创建一个新的节点DLinkedNode* node = new DLinkedNode(key, value);// 添加进哈希表cache[key] = node;// 添加至双向链表的头部addToHead(node);++size;if (size > capacity) {// 如果超出容量,删除双向链表的尾部节点DLinkedNode* removed = removeTail();// 删除哈希表中对应的项cache.erase(removed->key);// 防止内存泄漏delete removed;--size;}}else {// 如果 key 存在,先通过哈希表定位,再修改 value,并移到头部DLinkedNode* node = cache[key];node->value = value;moveToHead(node);}}void addToHead(DLinkedNode* node) {node->prev = head;node->next = head->next;head->next->prev = node;head->next = node;}void removeNode(DLinkedNode* node) {node->prev->next = node->next;node->next->prev = node->prev;}void moveToHead(DLinkedNode* node) {removeNode(node);addToHead(node);}DLinkedNode* removeTail() {DLinkedNode* node = tail->prev;removeNode(node);return node;}
};
同一个程序可以被运行多次,从而产生多个不同的进程。
使用ps命令查看系统中所有进程。
kill函数用于发送一个信号,在发送信号的时候需要指定接收信号的进程。
信号是发生事件时对进程的一种通知机制。
信号的目的是用来通信的。
产生信号的情况
- 硬件发送异常,硬件检测到错误条件并通知内核,再由内核发送相应的信号给相关进程。硬件检测到异常的例子包括执行一条异常的机器语言指令,诸如,除数为0、数组访问越界导致引用了无法访问的内存区域等,这些异常情况都会被硬件检测到,并通知内核,然后内核为该异常情况发生时正在运行的进程发送适当的信号以通知进程。
- 在终端下输入了能够产生信号的特殊字符。在终端上按下Ctrl+C可以产生中断信号,这个方法可以终止在前台运行的程序,按下Ctrl+z产生暂停信号,这个方法可以暂停当前前台运行的进程。
- 进程调用kill()系统调用可以将任意信号发送给另一个进程或进程组。但是接收信号的进程和发送的进程的所有者必须相同,或发送信号的进程的所有者是root超级用户。
- 用户可以通过kill命令将信号发送给其他进程。通常我们会通过kill命令来杀死一个进程,在终端执行kill -9 xxx杀死PID为xxx的进程。kill命令其内部的实现原理也是通过kill()系统调用来完成的。
关键字static
在函数内部声明的静态变量会保持其值,直到程序结束,它们在内存中位置固定,不会随着函数的调用而销毁和重新创建。
当函数被声明为静态时,它的作用域仅限于声明它的文件内部,不可见于其它文件中的代码。
静态全局变量:当全局变量被声明为静态时,它的作用域仅限于声明的文件内部。
静态数据成员:属于整个类,而不是类的实例。
回调函数
回调函数是一种常见的编程模式,特别是在处理事件驱动或异步操作时非常有用。回调函数允许将一个函数作为函数参数传递给另一个函数,从而在某个特定事件发生时调用这个函数。
C语言中,回调函数通过函数指针实现。函数指针是指向函数的指针变量,可以作为函数参数传递给其他函数。
struct可以有无参构造。
C++中不能重载的是.*以及::。
#pragma pack(2)强制设定为2字节对齐。
typedef只是类型,不加typedef才算指针,enum枚举类型,4字节。
无参构造是A a;不加括号。