C语言_文件

发表于2024-01-17更新于2025-11-04阅读次数

文件

FILE

1
2
3
4
5
typedef struct _iobuf
{
    void * _Placeholder;
}FILE;
_ACRTIMP _ALT FILE* __cdecl __acrt_iob_func(unsigned _Ix);

实际就是一个无符号整型ID值，当做了形式为指针来用了。

为什么要用指针，是为了防止单纯的整型随意被赋值，而不同类型的指针不可以随意赋值，因此可以用指针来阻挡一下，出错概率就小了。

mode

mode是以内存视角来说的：

  1. 从设备写入到内存中是input，是"r"；
  2. 从内存中写出到磁盘是output，是"w"。如果文件存在，则删掉内容，从0开始写。

fopen

1
2
3
4
5
int main()
{
    FILE * file = fopen("e:\\aa.txt", "w");  //绝对路径
    fclose(file);
}

\是转义字符，所以，\\表示\。如果不想写\\，也可以只写一个/

写东西

文件中有两个流，输出流和输入流，两个流的指针位置互相独立、互不干扰。指针位置可以用fseek、fsetpos等改变。

在这里用fwrite写入文件：Write block of data to stream.

1
2
3
4
5
6
size_t fwrite(const void * ptr, size_t size, size_t count, FILE * stream);
// ptr指示缓冲区的起始位置；Pointer to the array of elements to be written, converted to a const void *
// size是要写入的元素类型的大小
// count是有多少个元素
// stream是哪个文件
// 返回值是指写入了多少个元素，而不是字节数。
1
2
3
4
5
6
7
8
9
10
int main()
{
    int val = 24;
    FILE * file = fopen("e:\\aa.txt", "w");  //绝对路径
    if(NULL == file) return 0;
    // 写入一个int。
    size_t byte_written = fwrite(&val, sizeof val, 1, file);
    fclose(file);
    file = NULL;
}

程序中读文件

如果已经有存在的文件，则就不要再执行写入的部分。需要用宏条件语句来控制程序。

fread是Read block of data from stream.

1
size_t fread(void * ptr, size_t size, size_t count, FILE * stream);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int main()
{
    FILE * file = NULL;
#ifdef _CREATE_FILE__
    int val = 24;
    file = fopen("e:\\aa.txt", "w");
    if(!file)
        return 0;
    size_t num_written = fwrite(&val, sizeof val, 1, file);
#else
    int val = 0;
    file = fopen("e:\\aa.txt", "r");
    size_t size_to_read = sizeof val;
    if(!file)
        return 0;
    // 返回的是元素个数，为1个
    size_t num_read = fread(&val, sizeof val, 1, file);
    if(num_read == size_to_read)
        printf("%i\n", val);
#endif // _CREATE_FILE__
    fclose(file);
    file = NULL;
    return 0;
}// 24

实际上

默认暂时在缓存区中存放内容，比如向磁盘中写入东西，直到缓冲区满时，才会真正开始写入磁盘。也可以中途调用fflush进行立即刷新缓存区。

C语言_链表

发表于2024-01-17更新于2025-11-04阅读次数

链表

  1. 不要求地址连续，因此可以建立在堆上。
  2. 插入的时间复杂度低。

节点定义

以下为无头节点的单链表。

1
2
3
4
5
6
7
8
typedef struct _Node
{
    unsigned id;
    char val;
    struct _Node * next;
}Node, *PNode;
// 指向链表中第1个有效元素的指针，不是教科书上的头节点（头节点是无效值，仅代表标识）
PNode header = NULL;

push_back

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void push_back(PNode node)
{
    PNode current = header;
    if(current == NULL)
    {
        header = node;
        return;
    }
    while(current->next != NULL)
    {
        current = current->next;
    }
    current->next = node;
    return;
}

make_node

1
2
3
4
5
6
7
8
9
10
11
PNode make_node(unsigned id, char val)
{
    PNode node = (PNode)malloc(sizeof(Node));
    if (node != NULL)
    {
        node->id = id;
        node->val = val;
        node->next = NULL;
    }
    return node;
}

测试

1
2
3
4
5
6
7
8
9
int main()
{
    PNode node = make_node(1, 'a');
    push_back(node);
    node = make_node(2, 'b');
    push_back(node);
    node = make_node(3, 'c');
    push_back(node);
}

traversal

1
2
3
4
5
6
7
8
9
void traversal()
{
    PNode current = header;
    while(current != NULL)
    {
        printf("id: %u, val: %c\n", current->id, current->val);
        current = current->next;
    }
}

insert_after_id

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void insert_after_id(unsigned id, PNode node)
{
    PNode current = header;
    while(current != NULL)
    {
        if(id == current->id) break;
        current = current->next;
    }
    if(current != NULL)
    {
        node->next = current->next;
        current->next = node;
    }
    else
    {
        push_back(node);
    }
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main()
{
    PNode node = make_node(1, 'a');
    push_back(node);
    node = make_node(2, 'b');
    push_back(node);
    node = make_node(3, 'c');
    push_back(node);
    traversal();
    node = make_node(4, 'd');
    insert_after_id(2, node);
    traversal();
}
//第一次遍历：1 2 3
//第二次遍历：1 2 4 3

insert_before_id

自己写的版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void insert_before_id(unsigned id, PNode node)
{
    PNode current = header;
    if(current == NULL)
    {
        push_back(node);
        return;
    }
    if(current->id == id)
    {
        header = node;
        node->next = current;
        return;
    }
    while(current->next != NULL)
    {
        if(id == current->next->id) break;
        current = current->next;
    }
    if(current->next != NULL)
    {
        node->next = current->next;
        current->next = node;
    }
    else
    {
        push_back(node);
    }
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main()
{
    PNode node = make_node(1, 'a');
    push_back(node);
    node = make_node(2, 'b');
    push_back(node);
    node = make_node(3, 'c');
    push_back(node);
    traversal();
    node = make_node(4, 'd');
    insert_before_id(1, node);
    traversal();
}
//第一次遍历：1 2 3
//第二次遍历：4 1 2 3

双指针法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void insert_before(unsigned id, PNode node)
{
    PNode p = header, pp = NULL;
    while(p)
    {
        if(p->id == id)
        {
            break;
        }
        pp = p;
        p = p->next;
    }
    if(!p)//插入的位置为空
    {
        push_back(node);
        return;
    }
    // 找到id，且p不为空
    if(p != NULL && pp == NULL)//第一次while循环即找到了id，即id在首元素，需要插到首位置，要换头。
    {
        header = node;
        node->next = p;
        return;
    }
    // 剩下就是在中间插入的情况了。
    pp->next = node;
    node->next = p;
}

remove_node

删除指定id

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void remove_node(unsigned id)
{
    PNode current = header;
    if(header != NULL && header->id == id)
    {
        free(header);
        header = NULL;
        return;
    }
    PNode prev = NULL;
    while(current != NULL)
    {
        if(id == current->id) break;
        prev = current;
        current = current->next;
    }
    if(current != NULL)
    {
        prev->next = current->next;
        free(current);
        current = NULL;
    }
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
int main()
{
    PNode node = make_node(1, 'a');
    push_back(node);
    node = make_node(2, 'b');
    push_back(node);
    node = make_node(3, 'c');
    push_back(node);
    traversal();
    node = make_node(4, 'd');
    insert_before_id(1, node);
    traversal();
    remove_node(1);
    traversal();
    remove_node(2);
    traversal();
    remove_node(3);
    traversal();
    remove_node(4);
    traversal();
    remove_node(5);
    traversal();
}
/* 结果：
id: 1, val: a
id: 2, val: b
id: 3, val: c

id: 4, val: d
id: 1, val: a
id: 2, val: b
id: 3, val: c

id: 4, val: d
id: 2, val: b
id: 3, val: c

id: 4, val: d
id: 3, val: c

id: 4, val: d

空
*/

环

制造环

标记一个id，之后让尾节点next指向该id

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
PNode find_id(unsigned id)
{
    PNode current = header;
    while(current != NULL)
    {
        if(current->id == id) break;
        current = current->next;
    }
    return current;
}
void make_cycle(unsigned id)
{
    // 确保有两个节点
    if(header == NULL || header->next == NULL) return;
    PNode cycle_begin = find_id(id);
    // 确保有这个id  并且  确保cycle_begin不是尾节点
    if(cycle_begin == NULL || cycle_begin->next == NULL) return;
    PNode current = header;
    while(current->next != NULL)
    {
        current = current->next;
    }
    current->next = cycle_begin;
}

如何判断是否有环？快慢指针

一个指针走一步，一个指针走两步。

如果两个指针重合则有环，如果无环的话，快指针肯定能到终点NULL。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
int has_cycle()
{
    if (header == NULL || header->next == NULL) return 0;
    PNode fast = header;
    PNode slow = header;
    while (fast != NULL)
    {
        fast = fast->next;
        if(fast != NULL)
            printf("fast1: -> %i\n", fast->id);
        if (fast != NULL)
        {
            fast = fast->next;
            if (fast != NULL)
                printf("fast2: -> %i\n", fast->id);
            slow = slow->next;
            printf("slow: -> %i\n\n", slow->id);
            if (fast == slow && fast != NULL)
            {
                fast = header;
                while (fast != slow)
                {
                    fast = fast->next;
                    slow = slow->next;
                }
                printf("有环: %i\n", slow->id);
                return 1;
            }
        }
        else
        {
            printf("无环");
            return 0;
        }
    }
}
int main()
{
    PNode node = make_node(7, '7');
    push_back(node);
    node = make_node(5, '5');
    push_back(node);
    node = make_node(6, '6');
    push_back(node);
    node = make_node(8, '8');
    push_back(node);
    node = make_node(2, '2');
    push_back(node);
    node = make_node(0, '0');
    push_back(node);
    node = make_node(4, '4');
    push_back(node);
    traversal();
    make_cycle(6);
    has_cycle();
}
// 有环：6

让一个快指针和一个慢指针再次相遇当然可以说明此链表有环。但，难点在于如何找到环的入口？

设xx为头节点到循环入口处的距离，yy为循环入口处到相遇点的距离，zz为相遇点到尾节点的距离（即该节点下一个是循环口）。并结合fastfast指针和slowslow指针的步数关系fast=2slowfast=2slow，得出在相遇点：fast=x+n(y+z)+yfast=x+n(y+z)+y，slow=x+yslow=x+y（慢指针肯定不会在圈内转完一圈，可以想想，是合理的，因为快指针总比慢指针快nn圈，肯定在慢指针走完一圈前和它相遇！），则

\begin{align} x+n(y+z)+y&=2(x+y)\\ x&=n(y+z)-y\\ x&=n(y+z)-(y+z)+z\\ x&=(n-1)(y+z)+z\\ x&=z \end{align}

y+zy+z是圈长，我们可以想到，如果快指针要和慢指针相遇，nn必须要大于等于11。至于nn，即圈数具体为几，实际上无所谓，因为快指针在里面转了nn圈和11圈，效果是一样的！所以我们可以得出，x=zx=z！于是，已知zz为相遇点到尾节点的距离（尾节点下一个是循环口），并且已知z=xz=x（xx为头节点到循环入口处的距离）。那么，让一个指针在相遇点，另一个指针在头节点，同时步进，直到相遇，就是循环入口处！

参考：https://www.bilibili.com/video/BV1if4y1d7ob

保存到文件

保存所有节点信息到文件中。成功返回1，失败返回0。

不应当把结构体作为整体完全保存到一行。

而是每个属性一行一行地保存。因为next指针在下次运行失效的。需要按照每个属性重新构建每个节点。

1
2
3
4
int save(char const * const filename)
{
    return 0;
}

加载的时候，next指针的信息已经是失效的，需要重新make_node。

1
2
3
4
int load(char const * const filename)
{
    return 0;
}