数据结构学习2

2023-08-03 20:58 由优秀还天籁发表于 #其他

功能受限的表结构
1、队列：
只有两个口进出数据，一个专门进入数据，另一个专门出数据，先进先出，FIFO表。
顺序队列：
存储元素的连续内存的首地址
容量
队头位置（出队）
队尾位置（入队）
[元素数量]（可有可无）
运算：创建、销毁、清空、出队、入队、队空、队满、队头、队尾、元素数量

需要注意的问题
1、存储的元素是有一维数组+队头位置front+队尾位置rear来表示，入队rear+1，出队front+1，为了让队列能够反复使用。我们需要
把一维数组想象成一个环，因此+1之后需要对容量cal+1求余
            front=（front+1）%cal；
            rear=（front+1）%cal；
2、判断队空和队满问题
    如果不处理该问题，那么队空和队满的条件都是front=rear，就无法区分是队空还是队满
    方法1：存储元素的内存多增加一个位置空间（常考）
        队空：front==rear
        队满：：（real+1）%cal == front （其中的cal是相对于前面创建的内存数+1）
        代价：需要额外申请存储一个元素的内存
        计算数量；（rear-front+cal）%cal；
        队尾数据下标：（rear-1+cal）%cal
    方法2:顺序队列结构中增加一个记录数量的数据项，通过数量和容量对比判断队空、队满。

链式队列
    由若干个节点组成的队列结构，只能操作队头节点，队尾节点
    链式队列结构：
        队头指针
        队尾指针
        节点数量
    运算：创建、销毁、队空、入队、出队、队头、队尾、数量
    
队列的应用：
    1、数据排队处理：-消息排队
    2、树的层序遍历
    3、图的广度优先遍历BFS
    4、封装线程池、数据池

1、封装链表：
1、单链表
由于不封装链表结构时，链表的尾添加效率低
其次非法位置的判断效率也很低，只能通过遍历来判断
节点：
数据域
指针域next
链表结构：
头指针
尾指针
节点数量（好处：只是判断非法位置效率变高）

    注意：单链表的删除节点，无论是按位置，按值删除，都需要找到待删除节点的前一个。

2、静态链表
节点：
数据域
游标
特点：
1、静态链表的节点存储在一段连续的内存中，通过游标来访问下一个节点
2、插入、删除节点时，只需要修改游标的值即可，不需要动态申请、释放节点，因此得名静态链表
3、虽然能实现效果，但是也牺牲了随机访问的功能，对内存的要求高，只是给没有指针的编程语言提供实现链表的方式。

3、循环链表
链表的最后一个节点的next不指向NULL，而是指向第一个节点，这样的链表称为循环链表，如果是单链表则称为单循环链表，好处是可以
在任意一个节点开始遍历整个链表。

4、双向链表
注意：双向链表一般会实现为双向循环链表，最后一个节点的next指向第一个节点，第一个节点的prev指向最后一个。
节点：
前趋指针：prev
数据域 data
后继指针 next
封装双循环链表结构：
节点数量
头节点指针
注意：封装的是带头节点的双链表，不然的话插入、删除操作可能会改变head的指向，处理起来就需要分情况，很麻烦，因此带头节点不需要考虑以上情况
注意：
1、删除操作时，不再需要找待节点的前一个位置
2、因为是双向循环链表，所以可以根据需要从前往后遍历，也可以从后往前遍历，从而提高查找的效率。

5、Linux内核链表
既然节点中不能包含万物，那么就让万物来包含节点
6、通用链表
能够存储并操作任意类型的数据到链表中，并提供对应的操作
万能指针 void*
c语言中任意类型的指针可以转换成void类型
void类型指针可以转换成任意类型的指针
节点：
void*ptr; //数据域
指针域；
链表结构；
头指针
数量

核心点：
1、void* 确保能存储任意类型的数据；
2、普通操作可参考双链表即可
2、通过回调模式来实现一些特殊操作，例如：遍历、按值操作、排序（这些操作都是需要用户来制定规则）

数组与矩阵
数组：存储空间连续的表结构
矩阵：带有二维信息的数据，一般使用二维数组来存储矩阵,矩阵中存储数据的元素个数一般都少于所申请的内存个数，如果直接以二维数组存储会浪费内存
因此可以通过压缩矩阵成为一维数组的方式来节约内存。

特殊矩阵：行数、列数 n 行号i 列号j
    上三角矩阵：
    [x] [x] [x] [x]
    [ ] [x] [x] [x] 
    [ ] [ ] [x] [x]
    [ ] [ ] [ ] [x]
    压缩方法：使用一维数组压缩，一维数组长度：（n+1）*n/2
    下标的对应关系：（j+1）*j/2+1
     == 一维数组的下标。
    要求：j>=i ；
    例子：
        1 3 4 5 
        0 2 9 6
        0 0 6 3 
        0 0 0 7 对于这个二维数组中，存储的一维数组为 1 3 2 4 9 6 5 6 3 7

    下三角矩阵：
        压缩方法：使用一维数组压缩，一维数组长度：（n+1）*n/2
        下标的对应关系：（i+1）*i/2+j == 一维数组的下标。
        要求：j<=i时，才有有效数据，才能进行压缩；

    对称矩阵：
    对角矩阵：沿左上-右下对角线两边有数据
    [0] [1] [ ] [ ]
    [2] [3] [4] [ ] 
    [ ] [5] [6] [7]
    [ ] [ ] [8] [9]
    压缩方法：使用一维数组压缩
    一维数组的长度：3n-2
    下标的对应关系：2*i+j；
    要求：abs（i-j）<=1时，才有有效数据，才进行压缩

稀疏矩阵：有效数据不多且位置无规律，绝大多数位置都是无效数据不需要进行表示使用的，但是数据没有具体标准，全凭感觉。
    压缩方式：使用三元组来进行压缩。
    三元组：有三个数据项：
        行、列、值
        构成一个整体，该整体即可顺序存储，也可链式存储。
    优点：节约存储空间
    缺点：矩阵具备随机访问功能，但是压缩成三元组后，失去了随机访问的效果，只能遍历查找某行某列的数据