Krocz's Blog

数据结构模板

发表于 2023-11-10 更新于 2024-04-26 分类于算法和数据结构
本文字数： 24k 阅读时长 ≈ 44 分钟

1.链表

1.1 静态链表（数组模拟）

1.1.1 单链表

#include <iostream>
using namespace std;
const int N = 100010;
int e[N], ne[N], idx, head = -1;

void add_head(int v)
{
    e[idx] = v, ne[idx] = head, head = idx++;
}

void add(int k, int v)
{
    e[idx] = v, ne[idx] = ne[k], ne[k] = idx++;
}

void remove(int k)
{
    if(~k) ne[k] = ne[ne[k]];
    else head = ne[head];
}

int main()
{
    int m;
    cin >> m;
    while(m --)
    {
        int k, v;
        char c;
        cin >> c;
        switch(c)
        {
            case 'H':
                cin >> v;
                add_head(v);
                break;
            // 题中对于k的计数从1开始，但是存储下标从0开始，因此需要k - 1
            case 'I':
                cin >> k >> v;
                add(k - 1, v);
                break;
            case 'D':
                cin >> k;
                remove(k - 1);
        }
    }
    for(int i = head; ~i; i = ne[i])
        cout << e[i] << " ";
    return 0;
}

注1：为了逻辑清晰代码简洁，无论是静态链表还是动态链表都最好加上头节点，但是仅在数组模拟单链表时没有头节点，因为算法题中使用单链表时一般仅使用在头插入新节点，不涉及其他操作，所以没有必要加入头节点

阅读全文 »

算法模板

发表于 2023-10-31 更新于 2024-04-26 分类于算法和数据结构
本文字数： 6.2k 阅读时长 ≈ 11 分钟

1.快速排序

时间复杂度：$O(nlogn)$

void quick_sort(int l, int r)
{
    if(l >= r) return;
    int x = a[l + r >> 1], i = l - 1, j = r + 1;
    while(i < j)
    {
        do i++; while(a[i] < x);
        do j--; while(a[j] > x);
        if(i < j) swap(a[i], a[j]);
    }
    quick_sort(l, j), quick_sort(j + 1, r);
}

1.1 选择第K大的数字(quick_select)

时间复杂度：$O(n)$

阅读全文 »

简单的LED驱动程序

发表于 2023-10-30 更新于 2024-04-26 分类于韦东山Linux驱动开发笔记
本文字数： 8.2k 阅读时长 ≈ 15 分钟

1.学会看芯片手册

1.1 GPIO的通用操作方法

参考stm32的GPIO引脚的使用过程：

使能GPIOx时钟
设置GPIOx引脚的工作模式（输入、输出、复用、重定向）
读取/设置GOPIOx引脚的电平

一般的，芯片GPIO引脚使能的操作如下：

阅读全文 »

编写第一个驱动程序

发表于 2023-10-23 更新于 2024-04-26 分类于韦东山Linux驱动开发笔记
本文字数： 12k 阅读时长 ≈ 23 分钟

1. 编写驱动程序的框架

1.1 APP 打开的文件在内核中如何表示

APP 打开文件时，可以得到一个整数，这个整数被称为文件句柄。对于 APP 的每一个文件句柄，在内核里面都有一个struct file结构体与之对应:

struct file {
	union {
		struct llist_node	fu_llist;
		struct rcu_head 	fu_rcuhead;
	} f_u;
	struct path		f_path;
	struct inode		*f_inode;	/* cached value */
	const struct file_operations	*f_op;
	/*
	 * Protects f_ep_links, f_flags.
	 * Must not be taken from IRQ context.
	 */
	spinlock_t		f_lock;
	atomic_long_t		f_count;
	unsigned int 		f_flags;
	fmode_t			f_mode;
	struct mutex		f_pos_lock;
	loff_t			f_pos;
	struct fown_struct	f_owner;
	const struct cred	*f_cred;
	struct file_ra_state	f_ra;