Featured image of post 一生一芯预学习
一生一芯

一生一芯预学习

ysyx

Learn C The Hard Way

ex1

在你的文本编辑器中打开ex1文件，随机修改或删除一部分，之后运行它看看发生了什么。

删除了一些\00\00\00

plutoisy@plutoisy-ubuntu:~/lcthw$ ./ex1
./ex1: line 1: syntax error near unexpected token `('
./ex1: line 1: `ELF\00\00\00\00\00\00\00\00\...

再多打印5行文本或者其它比"Hello world.“更复杂的东西。

#include <stdio.h>
int main(int argc, char *argv[])
{
	puts("Hello world.");
	puts("Hello NJU.");
	puts("Hello ICS.");
	puts("Hello OS.");
	puts("Hello YSYX.");
	puts("Hello.");
	return 0;
}

执行man 3 puts来阅读这个函数和其它函数的文档。

int puts(const char *s);

puts() writes the string s and a trailing newline to stdout.

ex2

编写makefile

CFLAGS=-Wall -g

all:ex1

clean:
	rm -f ex1

-Wall 和 -g

-Wall 可以启用一系列常见警告。

-g 为程序添加调试信息

ex3

更新makefile

CFLAGS=-Wall -g

all:ex1 ex3

clean:ex1 ex3
	rm -f $^

常用的内置变量

常用的内置变量

ex6

printf格式化

printf格式化

ex7

改变universe_of_defects

改变universe_of_defects

巨大的数字实际上打印成了什么

字符串

unsigned long 在 C 语言中的最大值取决于具体的实现和平台。在大多数 32 位和 64 位系统上，unsigned long 的最大值通常是

  • 32 位系统：$2^{32} - 1 = 4294967295$
  • 64 位系统：$2^{64} - 1 = 18446744073709551615$

unsigned 关键字用于什么

声明无符号整数类型。

char 和 int 为什么可以相乘

char 和 int 可以相乘是因为 char 类型在进行算术运算时会被自动转换为 int 类型。这是因为 C 语言中的整数提升规则。

ex8

尝试替换

areas[0] = 100;
name[0] = 'A';
full_name[0] = 'A';
areas[1] = name[0];

尝试替换

上网搜索在不同的CPU上整数所占的不同大小

  • LP64（Linux/Unix 64-bit）：int 为 4 字节，long 和 long long 为 8 字节。
  • ILP32（32-bit）：int、long 为 4 字节，long long 为 8 字节。
  • LLP64（Windows 64-bit）：int 为 4 字节，long 为 4 字节，long long 为 8 字节。

ex9

将一些字符赋给numbers的元素，之后用printf一次打印一个字符，你会得到什么编译器警告？

并无warring

并无warring

对names执行上述的相反操作，把names当成int数组，并一次打印一个int，Valgrind会提示什么？

Valgrind没有报错

没有报错

如果一个字符数组占四个字节，一个整数也占4个字节，你可以像整数一样使用整个name吗？你如何用黑魔法实现它？

可以使用int指针

尝试

int *intPtr = (int *)name;
int nameAsInt = *intPtr;
printf("name: %d\n", nameAsInt);

将name转换成another的形式，看看代码是否能正常工作。

name转换成another的形式也可以用int指针转为int型

ex10

将i初始化为0看看会发生什么。是否也需要改动argc，不改动的话它能正常工作吗？为什么下标从0开始可以正常工作？

argc是参数个数，程序名是第一个参数

将num_states改为错误的值使它变大，来看看会发生什么。

num_states变大后会发生Segmentation fault (core dumped)

弄清楚在for循环的每一部分你都可以放置什么样的代码。

for (initialization; condition; increment) {
    // loop body
}

  • Initialization: 可以包含多个初始化语句，用逗号分隔。

  • Condition: 循环继续执行的条件，可以是任意表达式。

  • Increment: 每次循环结束后要执行的语句，可以包含多个语句，用逗号分隔。

查询如何使用’,’（逗号）字符来在for循环的每一部分中，’;’（分号）之间分隔多条语句。

for (int i = 0, j = 0; i < 10; i++, j += 2) {
    // loop body
}

查询NULL是什么东西，尝试将它用做states的一个元素，看看它会打印出什么。

NULL 是一个宏，表示空指针常量。在数组中使用 NULL 可以表示一个未初始化或空的元素。作为states元素会打印：state 4: (null)

看看你是否能在打印之前将states的一个元素赋值给argv中的元素，再试试相反的操作。

可以进行赋值

ex11

让这些循环倒序执行，通过使用i–从argc开始递减直到0。你可能需要做一些算数操作让数组的下标正常工作。

int i = argc;
while(i > 0) {
    printf("arg %d: %s\n", i, argv[i]);
    i--;
}

当时没改i++,发现他会打印不少东西，直到段错误

打印内容

使用while循环将argv中的值复制到states。

int j = 0;
int tmpargc;
if (argc > 4){
	tmpargc = 4;
}
else{
	tmpargc = argc;
}
while(j < tmpargc){
	states[j] = argv[j];
	j++;
}

研究你是否真正复制了这些字符串。答案可能会让你感到意外和困惑。

没有复制，只是改变了states里存放的指针

ex12

移除else部分，使它不能处理边界情况。

移除else也不会报错，超过范围不进行处理

将&&改为||，于是你会把“与”操作变成“或”操作，并且看看会发生什么。

将&&改为||：else if处理了除argc是1外的所有情况

布尔运算符

在 C 语言中，除了 &&（逻辑与）之外，还有其他几个重要的布尔运算符：

  • ||（逻辑或）：如果任一操作数为真，结果为真。
  • !（逻辑非）：用于取反，将真变为假，假变为真。

回到练习10和11，使用if语句使循环提前退出。你需要break语句来实现它，搜索它的有关资料。

break 语句用于提前退出循环。可以结合 if 语句来实现条件判断，从而在特定条件下退出循环。break 语句只会退出其所在的最内层循环。对于嵌套的两层循环，break 仅会退出当前的内层循环，而不会影响外层循环。

第一个判断所输出的话真的正确吗？由于你的“第一个参数”不是用户输入的第一个参数，把它改正。

...
if(argc == 1) {
    printf("You dont have argument. You suck.\n");
}
else if(argc == 2) {
    printf("You only have one argument. You suck.\n");
} 
...

ex13

编写另一个程序，在字母上做算术运算将它们转换为小写

#include <stdio.h>
int main(int argc, char *argv[])
{
    for(int i = 1; i < argc; i++){
        for(int j = 0; argv[i][j] != '\0'; j++) {
            char letter = argv[i][j];
            if (letter >= 'A' && letter <= 'Z') {
                letter = letter + ('a' - 'A');
            }
            printf("%c",letter);
        }
        printf("\n");
    }
    return 0;
}

使用','（逗号）在for循环中初始化letter。

for(char letter = argv[1][i]; argv[1][i] != '\0'; i++, letter = argv[1][i])

使用另一个for循环来让它处理你传入的所有命令行参数。

for(int j = 1; j < argc; j++){
    int i = 0;
    for(i = 0; argv[j][i] != '\0'; i++) {
       char letter = argv[j][i];
       ...
    }
}

使用 if 和 else if 语句来替代 switch 语句。

if (letter == 'a' || letter == 'A') {
    printf("%d: 'A'\n", i);
} else if (letter == 'e' || letter == 'E') {
    printf("%d: 'E'\n", i);
} else if (letter == 'i' || letter == 'I') {
    printf("%d: 'I'\n", i);
} else if (letter == 'o' || letter == 'O') {
    printf("%d: 'O'\n", i);
} else if (letter == 'u' || letter == 'U') {
    printf("%d: 'U'\n", i);
} else if ((letter == 'y' || letter == 'Y') && i > 2) {
    // it's only sometimes Y
    printf("%d: 'Y'\n", i);
} else {
    printf("%d: %c is not a vowel\n", i, letter);
}

if代码块外面写了个break，这样会产生什么效果？

由于break的存在，在识别到y时不会进入到default，而放在里面的break似乎没有起作用，还是会运行default

ex14

其它相似的函数

  1. isdigit(ch): 检查字符是否为数字（0-9）。
  2. ispunct(ch): 检查字符是否为标点符号。
  3. isspace(ch): 检查字符是否为空白字符（空格、制表符、换行符等）。
  4. isalnum(ch): 检查字符是否为字母或数字。

使用strlen函数，重写print_letters，让它只处理固定的长度

下面的代码合并了print_letters

void print_arguments_one(int argc, char *argv[]){
    int i = 0;
    for(i = 0; i < argc; i++) {
        int j = 0;
        int len = strlen(argv[i]);
        for(j = 0; j < len; j++) {
            char ch = argv[i][j];

            // if(isalpha(ch) || isblank(ch)) {
            //     printf("'%c' == %d ", ch, ch);
            // }
            if(isdigit(ch) || !isalpha(ch)) {
                printf("'%c' == %d ", ch, ch);
            }
        }

        printf("\n");
    }
}

ex15

将cur_age指向names

就是把names里面存放的5个地址理解成int值

int *cur_age = (int *)names;

用一些古怪的方式使计算发生错误

让cur_name不自增

试着重写循环，让它们从数组的最后一个元素开始遍历到首个元素。这比看上去要困难

for(cur_name = names+count-1, cur_age = ages+count-1;
        (cur_age - ages) >=0;
        cur_name--, cur_age--)
{
    printf("%s lived %d years so far.\n",
            *cur_name, *cur_age);
}

使用指针来处理命令行参数

for(int k = 0; k < argc; k++){
    printf("%s\n", *(argv+k));
}

打印出这些指针所指向的地址

for(int g = 0; g < count; g++){
    printf("---\n");
    printf("cur_name: %p\n",cur_name+g);
    printf("cur_age: %p\n",cur_age+g);
    printf("name: %p\n",names+g);
    printf("age: %p\n",ages+g);
}

使用函数来重写程序

void printfunc(int *cur_age, char **cur_name, int count){
    for(int i = 0; i < count; i++) {
        printf("%s is %d years old.\n",
                *(cur_name+i), *(cur_age+i));
    }
}

将for循环改为while循环

int i = 0;
while(i < count){
    printf("%s is %d years old.\n",
            *(cur_name+i), *(cur_age+i));
    i++;
}

ex16

传递NULL给Person_destroy来看看会发生什么

会触发assert0

void Person_destroy(struct Person *who)
{
    assert(who != NULL);
    free(who->name);
    free(who);
}

你应该向valgrind传递什么参数来让它向你报告内存如何泄露。

应该向valgrind传递--leak-check=full来让它向你报告内存如何泄露。

报告内存泄露

忘记在Person_destroy中释放who->name，并且对比两次的输出。同时，使用正确的选项来让Valgrind告诉你哪里错了。

没有释放who->name

这一次，向Person_print传递NULL，并且观察Valgrind会输出什么。

向Person_print传递NULL

不使用指针

#include <stdio.h>
#include <string.h>

struct Person {
    char name[50];  
    int age;
    int height;
    int weight;
};


struct Person Person_create(char *name, int age, int height, int weight) {
    struct Person who;

    strncpy(who.name, name, sizeof(who.name) - 1); 
    who.name[sizeof(who.name) - 1] = '\0'; 
    who.age = age;
    who.height = height;
    who.weight = weight;

    return who;
}


void Person_print(struct Person who) {
    printf("Name: %s\n", who.name);
    printf("\tAge: %d\n", who.age);
    printf("\tHeight: %d\n", who.height);
    printf("\tWeight: %d\n", who.weight);
}

int main(int argc, char *argv[]) {
    
    struct Person joe = Person_create("Joe Alex", 32, 64, 140);
    struct Person frank = Person_create("Frank Blank", 20, 72, 180);

    
    printf("Joe is:\n");
    Person_print(joe);

    printf("Frank is:\n");
    Person_print(frank);

    
    joe.age += 20;
    joe.height -= 2;
    joe.weight += 40;
    Person_print(joe);

    frank.age += 20;
    frank.weight += 20;
    Person_print(frank);

    
    return 0;
}

ex17

bug修复

...
res = strncpy(addr->name, name, MAX_DATA - 1); 
addr->name[MAX_DATA - 1] = '\0'; 
...
res = strncpy(addr->email, email, MAX_DATA - 1);
addr->email[MAX_DATA - 1] = '\0';
...

fix func die

void die(const char* message, struct Connection* conn)
{
    if (errno) {
        perror(message);
    } else {
        printf("ERROR: %s\n", message);
    }

    if (conn != NULL) {
        Database_close(conn);
    }
    else{
        printf("conn is NULL\n");
    }

    exit(1);
}

如何计算结构体的大小

如何计算结构体的大小

自动化测试

#!/bin/bash
set -e
commands=(
    "echo '-----Running test create-----'"
    "./ex17 db.dat c 512 100"

    "echo '-------Running test set------'"
    "./ex17 db.dat s 1 zed zed@zedshaw.com 120"
    "./ex17 db.dat s 2 frank frank@zedshaw.com 110"
    "./ex17 db.dat s 3 joe joe@zedshaw.com 119"

    "echo '------Running test list------'"
    "./ex17 db.dat l"

    "echo '-------Running test get------'"
    "./ex17 db.dat g 1"
    "./ex17 db.dat g 2"
    "./ex17 db.dat g 3"

    "echo '-----Running test delete-----'"
    "./ex17 db.dat d 1"
    "./ex17 db.dat l"

    "echo '------Running test find------'"
    "./ex17 db.dat f zed@"
    "./ex17 db.dat f frank"
    "./ex17 db.dat f 119"
)
for cmd in "${commands[@]}"; do
    eval $cmd
done
echo "All tests completed successfully."

使用单一的全局变量来储存数据库连接

开头声明conn全局变量，把所有指针都去掉，malloc和free也删掉

struct Connection conn;

栈

栈是一种后进先出（LIFO）的数据结构。主要操作包括：

  • Push: 将元素添加到栈顶。
  • Pop: 移除并返回栈顶元素。
  • Peek/Top: 返回栈顶元素但不移除。
  • IsEmpty: 检查栈是否为空。

Python 实现

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        raise IndexError("pop from empty stack")

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        raise IndexError("peek from empty stack")

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

ex18

find func

find func

修改二进制文件

把ERROR改成ABCDE无法运行，段错误

把ERROR改成ABCDE

把错误的函数传给compare_cb

错误的函数传给compare_cb

将NULL传给它

会找不到函数

将NULL传给它

编写另一个排序算法，修改test_sorting使它接收任意的排序函数和排序函数的比较回调。并使用它来测试两种排序算法。

typedef int* (*compare_func)(int *numbers, int count, compare_cb cmp);
...
void test_sorting(int *numbers, int count, compare_cb cmp, compare_func cmpf)
...
int *sorted = cmpf(numbers, count, cmp);

ex32

一些bug

makefile有问题,要删掉tests: CFLAGS += (TARGET)并加入以下内容，cc编译要先写.c后写.a

$(TESTS): %: %.c
	$(CC) $(CFLAGS) $< $(TARGET) -o $@

以下给指针赋值有问题，这些字符串字面量通常存储在只读数据段 (.rodata)，也就是程序的静态存储区的一部分。它们的内容是只读的，不能被修改。当然也不能free，lcthw作者采用的测试方法没有触发这个bug，他每次销毁list都是在list清空的情况下销毁的。

valgrind疑似在这里判断出错，我使用原有方法，全部弹出后销毁（strdup malloc的空间并没有删除），但valgrind却没有报内存泄漏，我手动free之后他依然没有报内存泄漏，并且也没有报错free了多次

char *test1 = "test1 data";
char *test2 = "test2 data";
char *test3 = "test3 data";
...
test1 = strdup("test1 data");
test2 = strdup("test2 data");
test3 = strdup("test3 data");
...

使List_clear_destroy更高效

void List_clear_destroy(List * list)
{
    check(list, "list can't be NULL");
    //List_clear(list);
    //List_destroy(list);
    LIST_FOREACH(list, first, next, cur) {

        free(cur->value);
        
        if (cur->prev) {
            free(cur->prev);
        }
    }

    free(list->last);
    free(list);
error:
    return;
}

为一些先决条件添加断言，使其部结构NULL值作为List *list的参数。

为所有函数加入check(list, "list can't be NULL");并设置好error后的返回值

检查列表的内容始终正确

void List_check(List * list)
{
    check(list, "list can't be NULL");
    check(!(list->count < 0), "count < 0");
    if(list->count > 0){
        check(list->first, "count > 0, first should not be NULL");
    }
error:
    return;
}

单向链表与双向链表优劣

  • 单向链表在内存有限且只需单向遍历的情况下更优。双向链表在需要频繁进行插入、删除操作和双向遍历时更优。

  • 双向链表的内存消耗更大,每个节点需要额外的指针来指向前驱节点。

加入复制功能

由于不知道复制void*指向的空间，所以直接使用了同一个指针，test_copy放在test_unshift下一个测试

List *List_copy(List * list)
{
    check(list, "list can't be NULL");
    List* new_list =  List_create();
    LIST_FOREACH(list, first, next, cur) {
        List_push(new_list, cur->value);
    }
    return new_list;
error:
    return;
}

char *test_copy()
{
    listcopy = List_copy(list);
    mu_assert(list != NULL, "Failed to create list.");
    mu_assert(List_first(listcopy) == test3, "Wrong last value.");
    mu_assert(List_count(listcopy) == 3, "Wrong count on unshift.");
    List_check(listcopy);
    List_pop(listcopy);
    List_pop(listcopy);
    List_pop(listcopy);
    List_clear_destroy(listcopy);
    return NULL;
}

无内存泄漏

无错误无内存泄漏

ex33

归并排序做了大量的链表复制和创建操作，寻找减少它们的办法

添加List_split函数，此函数接受list，按pos切开，返回右边，输入list储存左边。这样就可以减少一个List_create()

List* List_split(List *list, int pos) {
    if (!list || List_count(list) == 0 || pos <= 0 || pos >= List_count(list)) {
        return NULL; 
    }

    List *right = List_create(); 
    int total_count = List_count(list);

    int i = 0;
    LIST_FOREACH(list, first, next, cur) {
        if (i == pos) {
            
            right->first = cur;
            right->last = list->last;
            right->count = total_count - pos;

            
            list->last = cur->prev;
            list->count = pos;

            
            if (cur->prev) {
                cur->prev->next = NULL;
            }
            cur->prev = NULL;

            return right;
        }
        i++;
    }

    return NULL; 
}

创建一个可选的调试级别的不变量，在排序后实现is_sorted的功能。

check(is_sorted_debug(list), "Failed to sort");

添加函数计时

  • clock() 函数：返回程序自启动以来处理器时钟的计数。
  • CLOCKS_PER_SEC：每秒的时钟计数，用于将时钟计数转换为秒。
  • 时间计算：通过 (end - start) / CLOCKS_PER_SEC 计算函数的运行时间。
char *all_tests()
{
    mu_suite_start();

    clock_t start, end;
    double cpu_time_used;

    start = clock(); 
    mu_run_test(test_bubble_sort);
    end = clock(); 
    printf("Function test_bubble_sort execution time: %f seconds\n", ((double) (end - start)) / CLOCKS_PER_SEC);


    
    start = clock(); 
    mu_run_test(test_merge_sort);
    end = clock(); 
    printf("Function test_merge_sort execution time: %f seconds\n", ((double) (end - start)) / CLOCKS_PER_SEC);


    return NULL;
}

时间结果

创建不同长度的随机链表

for (i = 0; i < rand() % NUM_VALUES + 1; i++)

链表排序比较麻烦的原因

无随机访问：链表不支持随机访问，无法像数组一样通过索引直接访问元素。这意味着不能通过简单的索引交换来排序元素。

节点操作复杂：链表中的元素是通过指针连接的，排序时需要频繁调整这些指针，容易出错且操作复杂。

效率问题：常用的排序算法如快速排序和堆排序依赖于随机访问，效率不高。链表排序通常使用归并排序，因为它适合链表的结构，但实现起来复杂。

内存管理： 链表节点的动态内存管理增加了排序的复杂性，需要小心处理内存分配和释放。

实现List_insert_sorted（有序链表）

void List_insert_sorted(List *list, void *value, List_compare cmp){
    
    check(is_sorted_debug(list), "Failed to sort");
    if( list->first == NULL){
        List_push(list, value);
    }
    else if(cmp(value, list->first->value) < 0){
        List_unshift(list, value);
    }
    else{
        ListNode *node = calloc(1, sizeof(ListNode));
        check_mem(node);
        node->value = value;
        node->next = NULL;


        
        ListNode *current = list->first;
        while(current->next != NULL && cmp(value, current->next->value) > 0) {
            current = current->next;
        }
        
        node->next = current->next;
        current->next = node;
        //node->prev = node->next->prev;
        //node->next->prev = node;

        if(current->next == NULL) {
            list->last = node;
        }

        list->count++;
    }
    
    check(is_sorted_debug(list), "Failed to sort");
error:
    return;
}

实现“自底向上”的归并排序

List *List_merge_sort_bottom_up(List *list, List_compare cmp){
    if(List_count(list) <= 1){
        return list;
    }
    int len = List_count(list);
    List *work = list;
    List *temp = List_create();
    int width;

    for (width = 1; width < len; width = width * 2) {
        //printf("width: %d\n", width);
        while (List_count(work) > 0) {
            List *left = List_get_first_n_node(work, width);
            List *right = List_get_first_n_node(work, width);
            List *merged = List_merge(left, right, cmp);

            while (List_count(merged) > 0) {
                List_push(temp, List_shift(merged));
            }
            //List_print(temp);
        }

        List *swap = work;
        work = temp;
        temp = swap;
    }
    List_destroy(temp);

    return work;
}

无内存泄漏

无错误无内存泄漏

ex42

无内存泄漏

无错误无内存泄漏

ex44

available_data的bug

连续读写满两次发现错误，发现available_data和available_space的计算是有问题的,没有考虑环绕的情况，

bug

// #define RingBuffer_available_data(B) (\
//         (B)->end % (B)->length - (B)->start)

#define RingBuffer_available_data(B) (\
    ((B)->end >= (B)->start) ? \
    ((B)->end - (B)->start) : \
    ((B)->end + (B)->length - (B)->start))

// #define RingBuffer_available_space(B) (\
//         (B)->length - (B)->end - 1)

#define RingBuffer_available_space(B) (\
    ((B)->end >= (B)->start) ? \
    ((B)->length - (B)->end + (B)->start - 1) : \
    ((B)->start - (B)->end - 1))

无内存泄漏

无错误无内存泄漏

PA

尝试理解计算机如何计算

计算机通过把复杂算数拆解成数个自身指令集支持的操作来完成复杂计算。

从状态机视角理解程序运行

(0, x, x) -> (1, 0, x) -> (2, 0, 0) -> (3, 0, 1) -> (4, 1, 1) -> (2, 1, 1) -> (3, 1, 2) -> (4, 3, 2) -> (2, 3, 2) -> (3, 3, 3) -> (4, 6, 3) -> … -> (4, 4950, 99) -> (2, 4950, 99) -> (3, 4950, 100) -> (4, 5050, 100) -> (5, 5050, 100)

riscv32有哪几种指令格式?

4种基础(R/I/S/U),2种变体(B/J)

详见riscv-spec-20191213.pdf page33,34

riscv32的指令格式

LUI指令的行为是什么?

UI(上立即加载)用于构建32位常量，使用U型格式。LUI将U-mediate值放入目标寄存器rd的最高20位，并在最低12位填0。

详见riscv-spec-20191213.pdf page37

LUI指令的行为

mstatus寄存器的结构是怎么样的?

mstatus 寄存器是一个MXLEN位读/写寄存器，其格式如图3.6(RV32)和图3.7(RV64)所示。图3.6(RV32)和图 3.7(RV64)所示。mstatus寄存器跟踪并控制hart 的当前运行状态。运行状态。在S级ISA中，mstatus的限制视图显示为sstatus寄存器。

详见riscv-privileged-20211203.pdf page34

mstatus寄存器的结构

shell命令

PA1统计所有行数:267503

PA1统计所有行数:266809

find . -name "*.c" -o -name "*.h" | xargs wc -l

PA1统计非空行数:231035

PA0统计非空行数:230385

find . -name "*.c" -o -name "*.h" | xargs grep -v '^\s*$' | wc -l

RTFM

-Wall可以启用一系列常见警告。

-Werror可以将所有警告视为错误。

在编译时刻把潜在的fault直接转变成failure

Licensed under CC BY-NC-SA 4.0
© 2023 - 2024 Plutoisy
Built with Hugo
主题 Stack 由 Jimmy 设计