配套代码笔记仓库。

Makefile

makefile与Makefile的区别

make会优先使用makefile，发布的项目一般是一个Makefile，方便用户写自己的makefile。

参考资料

跟我一起写Makefile — 跟我一起写Makefile 1.0 文档 (seisman.github.io)

目录

数据结构

架构梳理

  • 线性（1:1)

    • 线性表

      • 顺序存储 --> arr

      • 链式存储 --> 指针 （有头，无头）

        有头是指有一个不存数据的头，始终作为这个链表的起点。

        会更加简单，无头的话，更改首部节点会麻烦。

        头节点不仅可以作为起点，还可以作为存储信息的仓库，因为头节点只有*next是必须的。

        • 单链表

          • 循环
          • 不循环

        • 双向链表

          lib四个版本，第一个最基础完善，第二个改成了变长结构体，第三个在第二个的基础上封装了函数指针，第四个在第二个的基础上隐藏了数据结构，只暴露接口。

          • 循环
          • 不循环

          学到这里可以去读一下内核有关list的实现，主要都是宏和内联函数。

    • 栈

    • 队列

      练习：

      1. 表达式计算
      2. 球钟算法
        三个栈，1h，5min，1min。27个球，过了多久队列里又是1到27的顺序。

  • 树状（1:N）

    递归。递归转非递归。

    • 深度：层数
    • 度：子树的个数
    • 叶子：边缘节点
    • 孩子：与父节点对应
    • 兄弟：相同父节点
    • 堂兄弟：相同爷节点

    • 二叉树：

      • 满二叉树：深度为k且节点为2^k-1的二叉树
      • 完全二叉树：一颗二叉树，只有倒数两层可以存在不满两个孩子的节点，且单个孩子时只能是左孩子

    • 存储：

      • 顺序：直观，但是浪费空间
        满二叉树：父节点n，左孩子2n，右孩子2n+1
      • 链式：灵活，空间利用率高

    • 遍历

      • 按行
      • 先序（根，左，右）
      • 中序（左，根，右）
      • 后序（左，右，根）

      先加中，或者，中加后，都可以逆推出树。先加后不行。

    • 平衡：

      有很多种条件判定。

      这棵树的左右子树个数差值为1。

    • 广义表

      ( root ( left ) ( right) )，进行嵌套。

    • 搜索树

      空间换时间，查找是o(1)。

      课后作业：词频统计

  • 图（N:M）

静态库与动态库

  • 静态库：

    • 私家车，可以不在标准的位置下。
    • 编译时引入，代码膨胀但是不影响运行时间。

  • 动态库（共享库）：

    • 公交车，只能在指定的路径。
    • 运行时引入，占用运行时间。

静态库

  1. libxx.a
    xx 指代库名
  2. ar -cr libxx.a yyy.o
  3. 发布到
    /usr/local/include
    /usr/local/lib
  4. gcc -L/usr/local/lib -o main main.o -lxx
    如果路径都是这个默认的，可省略。
    -l参数必须在最后，有依赖
  5. ldd -print shared libirary dependencies
    打印所用到的动态库的内容

以链式双向链表的lib2为例。

*[main][~/workspace/Linux-C-Notes/Chapter11/ds/line/list/linklist/double/lib2]$ ldd ./main 
        linux-vdso.so.1 (0x00007ffffa3d0000)
        libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007fa6c123a000)
        /lib64/ld-linux-x86-64.so.2 (0x00007fa6c142b000)
        *[main][~/workspace/Linux-C-Notes/Chapter11/ds/line/list/linklist/double/lib2]$ gcc -c llist.c
*[main][~/workspace/Linux-C-Notes/Chapter11/ds/line/list/linklist/double/lib2]$ ls
 llist.c   llist.o   Makefile
 llist.h   main.c   
*[main][~/workspace/Linux-C-Notes/Chapter11/ds/line/list/linklist/double/lib2]$ ar -cr libllist.a llist.o
*[main][~/workspace/Linux-C-Notes/Chapter11/ds/line/list/linklist/double/lib2]$ ls
 libllist.a   llist.h   main.c
 llist.c      llist.o   Makefile
*[main][~/workspace/Linux-C-Notes/Chapter11/ds/line/list/linklist/double/lib2]$ sudo cp llist.h /usr/local/include 
*[main][~/workspace/Linux-C-Notes/Chapter11/ds/line/list/linklist/double/lib2]$ sudo cp libllist.a /usr/local/lib 
*[main][~/workspace/Linux-C-Notes/Chapter11/ds/line/list/linklist/double/lib2]$ gcc -o main main.c -lllist 
*[main][~/workspace/Linux-C-Notes/Chapter11/ds/line/list/linklist/double/lib2]$ ls
 libllist.a   llist.h   main     Makefile
 llist.c      llist.o   main.c  
*[main][~/workspace/Linux-C-Notes/Chapter11/ds/line/list/linklist/double/lib2]$ ./main
6 std6 90 59
5 std5 62 27
4 std4 49 21
3 std3 86 92
2 std2 93 35
1 std1 77 15
0 std0 83 86


5 std5 62 27
4 std4 49 21
3 std3 86 92
2 std2 93 35
1 std1 77 15
0 std0 83 86

这时main.c路径下都不需要llist.c和llist.h了，#include时也从"llist.h"变为<llist.h>。

动态库

  1. libxx.so
    xx为库名
  2. gcc -shared -fpic -o libxx.so yyy.c
  3. 发布到
    /usr/local/include
    /usr/local/lib
  4. 在/etc/ld.so.conf中添加路径
  5. /sbin/ldconfig 重读/etc/ld.so.conf`
  6. `gcc -I/usr/local/include -L/usr/local/lib -o ... -lxx
    如果路径都是这个默认的，可省略。
  7. 非root用户发布，可以自己定义一个位置，例如~/lib
cp xx.co ~/lib
export LD_LIBRARY_PATH= ~/lib

还是以lib2为例。

*[main][~/workspace/Linux-C-Notes/Chapter11/ds/line/list/linklist/double/lib2]$ ls
 llist.c   llist.h   main   main.c   Makefile
*[main][~/workspace/Linux-C-Notes/Chapter11/ds/line/list/linklist/double/lib2]$ gcc -shared -fpic -o libllist.so llist.c
*[main][~/workspace/Linux-C-Notes/Chapter11/ds/line/list/linklist/double/lib2]$ ls
 libllist.so   llist.h   main.c
 llist.c       main      Makefile
*[main][~/workspace/Linux-C-Notes/Chapter11/ds/line/list/linklist/double/lib2]$ sudo mv libllist.so /usr/local/lib
*[main][~/workspace/Linux-C-Notes/Chapter11/ds/line/list/linklist/double/lib2]$ sudo vi /etc/ld.so.conf
*[main][~/workspace/Linux-C-Notes/Chapter11/ds/line/list/linklist/double/lib2]$ sudo /sbin/ldconfig
*[main][~/workspace/Linux-C-Notes/Chapter11/ds/line/list/linklist/double/lib2]$ gcc -o main main.c -lllist
*[main][~/workspace/Linux-C-Notes/Chapter11/ds/line/list/linklist/double/lib2]$ ./main
6 std6 90 59
5 std5 62 27
4 std4 49 21
3 std3 86 92
2 std2 93 35
1 std1 77 15
0 std0 83 86


5 std5 62 27
4 std4 49 21
3 std3 86 92
2 std2 93 35
1 std1 77 15
0 std0 83 86
*[main][~/workspace/Linux-C-Notes/Chapter11/ds/line/list/linklist/double/lib2]$ ldd ./main
        linux-vdso.so.1 (0x00007ffd963ee000)
        libllist.so => /usr/local/lib/libllist.so (0x00007fda74025000)
        libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007fda73e44000)
        /lib64/ld-linux-x86-64.so.2 (0x00007fda7403a000)

[!NOTE]

当动态库和静态库重名，会优先链接静态库。

以链式存储栈为例，libstack依赖libllist。

*[main][~/workspace/Linux-C-Notes/Chapter11/ds/line/stack/list]$ ls
 llist.c   main     Makefile   stack.o
 llist.h   main.c   stack.c   
 llist.o   main.o   stack.h   
*[main][~/workspace/Linux-C-Notes/Chapter11/ds/line/stack/list]$ gcc -shared -fpic -o libstack.so stack.c
*[main][~/workspace/Linux-C-Notes/Chapter11/ds/line/stack/list]$ ls
 libstack.so   llist.o   main.o     stack.h
 llist.c       main      Makefile   stack.o
 llist.h       main.c    stack.c   
*[main][~/workspace/Linux-C-Notes/Chapter11/ds/line/stack/list]$ sudo mv libstack.so /usr/local/lib 
*[main][~/workspace/Linux-C-Notes/Chapter11/ds/line/stack/list]$ sudo cp stack.h /usr/local/include 
*[main][~/workspace/Linux-C-Notes/Chapter11/ds/line/stack/list]$ code main.c         
*[main][~/workspace/Linux-C-Notes/Chapter11/ds/line/stack/list]$ ls
 llist.c   main     Makefile   stack.o
 llist.h   main.c   stack.c   
 llist.o   main.o   stack.h   
*[main][~/workspace/Linux-C-Notes/Chapter11/ds/line/stack/list]$ gcc -o main main.c -lstack
/usr/bin/ld: /usr/local/lib/libstack.so: undefined reference to `llist_create'
/usr/bin/ld: /usr/local/lib/libstack.so: undefined reference to `llist_fetch'
/usr/bin/ld: /usr/local/lib/libstack.so: undefined reference to `llist_destroy'
/usr/bin/ld: /usr/local/lib/libstack.so: undefined reference to `llist_insert'
collect2: error: ld returned 1 exit status
*[main][~/workspace/Linux-C-Notes/Chapter11/ds/line/stack/list]$ gcc -o main main.c -lstack -lllist
*[main][~/workspace/Linux-C-Notes/Chapter11/ds/line/stack/list]$ ./main
./main: error while loading shared libraries: libstack.so: cannot open shared object file: No such file or directory
*[main][~/workspace/Linux-C-Notes/Chapter11/ds/line/stack/list]$ sudo /sbin/ldconfig               
/sbin/ldconfig: Can't link /usr/lib/wsl/lib/libnvoptix_loader.so.1 to libnvoptix.so.1
/sbin/ldconfig: /usr/lib/wsl/lib/libcuda.so.1 is not a symbolic link

*[main][~/workspace/Linux-C-Notes/Chapter11/ds/line/stack/list]$ gcc -o main main.c -lstack -lllist
*[main][~/workspace/Linux-C-Notes/Chapter11/ds/line/stack/list]$ ./main                            
6 stu6 90 59
5 stu5 62 27
4 stu4 49 21
3 stu3 86 92
2 stu2 93 35
1 stu1 77 15
0 stu0 83 86

添加动态库记得重载配置文件sudo /sbin/ldconfig!