C语言_链表

发表于2024-01-17更新于2025-09-28阅读次数

链表

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

节点定义

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

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

push_back

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

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;
}

测试

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

void traversal()
{
    PNode current = header;
    while(current != NULL)
    {
        printf("id: %u, val: %c\n", current->id, current->val);
        current = current->next;
    }
}

`insert_after_id`

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);
    }
}

测试

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`

自己写的版本

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);
    }
}

测试

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

双指针法

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

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;
    }
}

测试

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

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。

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

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

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

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

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

保存到文件

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

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

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

int save(char const * const filename)
{
    return 0;
}

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

int load(char const * const filename)
{
    return 0;
}

C语言_结构体_sizeof_分段

发表于2024-01-16更新于2025-09-28阅读次数

结构体

关于;的问题：

一般来说，大括号{}结尾后不用再加;。但是结构体的定义中的大括号{}后面要加;。因为结构体的定义属于数据的定义，只是有了大括号的形式而已，而数据的定义后面都要加;，因此结构体的定义中的大括号{}后面要加;。

函数、if语句、for语句中的{}是语句的定义，则不用加;。

struct Stu
{
    unsigned id;
    unsigned char age;
    char name[10];
};

C语言中，struct和结构体名字是一体的，共同才能合成一个类型，不能只写Stu。

结构体的定义

int main()
{
    struct Stu stu;
    stu.age = 17;
    stu.id = 123456;
    strcpy(stu.name, "xcg");
    printf("Age: %u, ID: %u, Name: %s\n", stu.age, stu.id, stu.name);
}

结构体的大小

struct Test
{
    int a;          // 4
    char b;         // 1  --> 实际: 4
};
int main()
{
    printf("%u\n", sizeof(struct Test));
}// 8

字节对齐

为了效率，即使char只占用一个字节，也会以结构体中大的数据类型为参考多占一些空间。如此在传输过程中就无需再去一个一个找分量，而是可以直接按照整体处理。一个时钟周期，64位数据都会一次性传输完成，所以说虽然浪费了一些空间，但换来了提高效率。

每一个元素的偏移量（相对0），都是自身类型大小的整数倍（0也算）。
结构体的整体大小，是内部最大的基础数据类型大小的整数倍。
我们控制不了的：结构体的首地址，是体内最大基本数据类型大小的整数倍。

struct Test
{
    int a;          // 4
    char b;         // 1  --> 实际: 2
    short c;        // 2
};//8
struct Test
{
    int a;          // 4
    char b;         // 1  --> 实际: 2
    short c;        // 2
    char d;         // 1  --> 实际: 4
};//12
struct Test
{
    int a;          // 4
    char b;         // 1
    char d;         // 1
    short c;        // 2
    short e[10];    // 10 --> 12
};//20

有办法关闭字节对齐特性：#pragma comment package 1

typedef

typedef struct _Stu
{
    unsigned id;
    unsigned char age;
    char name[11];
}Stu;

结构体指针类型

typedef struct _Stu
{
    unsigned id;
    unsigned char age;
    char name[11];
}*PStu;

如此定义，则效果为：PStu相当于Stu*

Stu* stu = (Stu*)malloc(sizeof(Stu));就可以写为

PStu stu = (PStu)malloc(sizeof(Stu));

星号的结合问题

1	typedef int * PMyInt;

如此定义，PMyInt相当于int*，即是一个int指针类型。但是，实际上，*星号是跟着名字PMyInt结合的。int*这种写法只是大多数人的习惯而已。

因此，typedef int MyInt, *PMyInt;才解释得通。如果typedef int * MyInt, PMyInt，则就变成了MyInt是指针类型，而PMyInt变成了int类型！

堆创建结构体

stdlib

C Standard General Utilities Library

malloc

分配指定字节数的内存块，返回一个无类型指针，需要强制转换类型。此空间的伸缩不受限制，因此需要显式分配、释放。

在小型设备上如果内存不够，则有可能会返回NULL。

#include<stdlib.h>
int main()
{
    Stu* stu = (Stu*)malloc(sizeof(Stu));
}

free

#include<stdlib.h>
int main()
{
    Stu* stu = (Stu*)malloc(sizeof(Stu));
    free(stu);
    stu = NULL;
}

为什么要置空？不成文的规定：指针是否有效？由指针是否为空决定。如果指针不空则认为是指向的内容有效。

如果不置空，即在释放指向的内容后依旧保留此指针，就成为了无意义的乱指。称为“野指针”或“迷途指针”。

如果反过来：空间内容有效，但指针值丢失，则叫做内存泄漏。

怎么解决？

小心编程

关闭进程，让操作系统收回所有内存

结构体指针访问成员

(*stu).age - *优先级是2，.优先级是1
stu->age - arrow运算符。

分段

结构体不仅可以把小类型组合成大类型，还能把基本数据类型拆成小块。

使用“位域”运算符（bit field operator）。

struct Test
{
    int a : 2;
};
int main()
{
    struct Test test;
    test.a = 1;
    printf("%i\n", test.a);
}// 1

给test.a赋值1是可以的。但给test.a赋值2则会打印成-2

int main()
{
    struct Test test;
    test.a = 2;
    printf("%i\n", test.a);
}// -2

因为：a是有符号int型，但只有2位的空间。除去符号位，则只有1位空间。那么，把2这个int字面常量给了a，就相当于：(10)2给了a。那么，a实际空间存的是(10)2，因为它是有符号int，而又因为当前符号位是1，所以实际表达的值为：(10)2的补码，算出无符号值后，再加个负号，即 $(01)_2+1=(10)_2$ 得出2，再加个负号，即-2。

此时的sizeof大小为多少呢？

struct Test
{
    int a : 2;
};// 4  -->  整个int的大小

//a、b一起分了12个字节，还有20个没分配。因此还是1个int的大小
struct Test
{
    int a : 2;
    int b : 10;
};// 4  -->  1个int的大小

分隔符

//a先分了2个字节，但是a剩下的空间不想再用，加个separator分隔符。
//在分隔符后定义b。此时是第2个int空间。
struct Test
{
    int a : 2;
    int : 0;     // separator  //无名
    int b : 10;
};// 8  -->  2个int的大小

下面这个分隔符的意义在于，虽然实际有效的是int类型，但是long long分隔符的作用在于在第一个和第二个int之间划分了8字节的位置，即a实际被提升为8字节大小，b也被提升为8字节大小。

//a先分了2个字节，但是a剩下的空间不想再用，加个separator分隔符。
//在分隔符后定义b。此时是第2个int空间。
struct Test
{
    int a : 2;
    long long : 0;     // separator  //无名
    int b : 10;
};// 16  -->  2个long long的大小

实际用处

如果小于8 bits，则用位域运算符。如果是8 bits，则直接用char。
separator一般不用，直接占满上面的空位即可，然后紧接着定义下一个类型。