C语言数据结构

C语言数据结构，有顺序表、链表、栈、队列的知识，线性表是一种广泛的数据结构，常用的线性表有:顺序表,链表,盏,队列,字符串。

C语言数据结构

• 数据结构
  • 线性表
    • 线性表是一种广泛的数据结构 常用的线性表有:顺序表,链表,盏,队列,字符串
    • 顺序表
      • 顺序表实质上就是数组 概念:存储空间在中物理上是连续的链表 优点:缓存利用率和命中率高,支持随机访问O(1). 缺点:需要动态扩容,任意位插入需要搬数据, 应用场景:元素高效存储,频繁访问
      • 静态顺序表
      • 动态顺序表
    • 链表
      • 概念:逻辑上连续但是物理上不一定连续的链表 优点:插入数据只需要修改指向,没有容量概念,按需释放内存 缺点:不支持随机访问,缓存利用率和命中率低存储的指针有一定的消耗 应用场景:任意位置插入和删除频繁的场景
      • 单向链表
        • 概念:单向访问结构简单,一般不会单独存储数据适应其他结构的子结构儒哈希表和图的邻表
      • 双向链表
        • 概念:双向访问结构复杂,一般用来单独存储数据(带头双向环形链表)
      • 环形链表
        • 概念:从某个节点开始进入循环的节点,进入循环前还可能会有其它节点
      • 哨兵卫链表
        • 概念:带哨兵卫的链表,链表头存储的数据值是抛弃的,只用其next指针来统一整个链表结构 优点:方便链表尾删尾插
    • 栈与队列
      • 栈
        • 概念;栈是一种特殊的线性表，其只能在固定的一端进行插入和删除操作，这是栈顶，而另一端叫栈底。 栈的数据元素遵循LIFO即后进先出（Last In First Out ）的规则 压栈:栈的插入操作为入栈/压栈,入数据在栈顶 出战:栈的删除叫出栈,出数据也在栈顶 栈也分数组栈和链式栈(一般使用顺序表实现栈) --使用链式的话一般head做栈顶效率更高
      • 队列
        • 概念:只允许在一端进行插入操作,在另一端进行删除操作的特殊线性表,队列具有现金先去FIFO(Frist In Frish Out) 入队列:进行插入操作的一段称队尾 出队列:进行删除的一端称队头 队列分数组队列和链式队列(一般使用链式队列) --使用数组队列需要挪动数据
        • 环形队列
          • 概念:环形队列也是一种循环队列线性数据结构,基于FIFO原则因为形成一个循环说一被称为环形缓冲器. 特点:环形队列的好处是可以利用之前用过的空间但是一旦队列满了就不能插入下一个数据. 其实现方式也可以用数组和链表的方式实现 但是需要多开一个空间来给环形队列判满所以K(存储个数)要开K+1个. 判空:front==tail 判满:(tail+1)%k+1==front
• 算法
  • 算法复杂度
    • 可使用大O渐进表示法来表示O(N^M) (极限取大头思想)
    • 空间复杂度
      • 临时额外占用空间大小的量度为空间复杂度 冒泡排序复杂度:O(1) 二分查找复杂度O(1) 斐波拉契复杂度O(N)
    • 时间复杂度
      • 算法的基本操作的执行次数为时间复杂度 冒泡排序复杂度O(N^2) 二分查找复杂度O(log2^N) 斐波拉契复杂度O(N)或者O(2^N)
  • 顺序表
    • 顺序表接口函数
  • 链表
    • 单向链表
      • 单链表接口函数
      • 含随机指针单链表函数
        • 单独的试题:把一个含有三个成员的链表完整复制到新链表中
    • 双向链表
      • 双向链表接口函数
    • 环形链表
      • 环形单链表求入口点问题 使用快慢双指针追击解决 slow指针走1步,fast指针走2步 如果快指针走大于2步以上则不一定能追上 如fast走3走,则N(指针之间的距离)为偶数才能追上 如fast走4步则N为3的倍数才能追上 L为入口前距离 C为环形距离 X为环形相遇点到入口点距离 N为慢指针入口点前快指针的圈数 求入口点公式 2(L+X)=L+N*C+X L+X=N*C L=N*C-X L=(N-1)*C+C-X
      • 环形单链表接口函数
    • 哨兵卫链表
      • 哨兵卫链表接口函数
  • 栈与队列
    • 栈
      • 栈接口函数
    • 队列
      • 队列接口函数
      • 环形队列函数
• 缓存访问相关
• 课堂小知识
  • 1.用异或来抵消相同的值找出单独值 2.用三个节点地址索引来翻转单链表 3.用两个指针地址来查找链表指定地方(中值或指定倒数k个)(先走k个或走的个数两倍) 4.检查单链表相交节点遍历得到节点相差值 5.回文结构就是对称结构