请选择 进入手机版 | 继续访问电脑版

数据结构笔记(一)【绪论、算法、算法效率的度量、线性表、顺序表、链表、

[复制链接]
期待幸福 发表于 2021-1-2 19:45:23 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
数据结构条记
一、绪论

  • 顺序存储结构在物理上一定是一连的
  • 非顺序存储结构在物理上可以是离散的
  • 数据的存储结构会影响存储空间分配的方便水平
  • 运算的界说是针对逻辑结构的
  • 运算的实现是针对存储结构的
二、算法

  • 算法的五个特征
    有穷性:算法步调的运行时间是有限的
    确定性:每一条代码都有明白性的目标,对于相同的输入都有相同的输出
    大概性:算法中的步调都是可以被根本均算执行有限次
    输入:丢给算法处理处罚的数据
    输出:算法处理处罚后的效果
  • “好”算法的特质
    正确性:算法应可以或许正确地管理求解问题
    可读性:算法应有精良的可读性
    结实性:算法可以或许处理处罚一些异常
    高效率与低储存量:算法省时、省内存;时间复杂度低,空间复杂度低
三、算法效率的度量

  • 时间复杂度
    表达式T(n), T:time n:问题规模
    时间复杂度表达式只思量表达式高阶部分
    Eg:
    T(n)=3n+3≈3n
    T(n)=3n2+3n+3≈3n2
    T(n)=3n3+3n2+3n+3≈3n3
          常对幂指阶

2. 空间复杂度
表达式S(n), T:space n:问题规模
空间复杂度表达式也只思量表达式高阶部分
四、线性表

  • 线性表具有相同数据结构(每个数据元素所占空间一样大)
  • 是有限序列(有序次)
  • ai体现第i个元素,第i个位序(位序从1开始)
  • a1为表头元素、 an为表尾元素
  • 除了a1,每一个元素有且仅有一个直接前驱;除了an,每一个元素有且仅有一个直接后驱
根本利用表达形式表达形式InitList(&L)初始化表DestroyList(&L)销毁链表Listinsert(&L,i,e)插入元素ListDelete(&L,i,&e)删除元素LocateElem(L.e)按值查找Length(L)求表长PrintList(L)输出打印Empty(L)判空Tip:
什么时候要传入引用“&”——对叙述的修改效果需要“带返来”(C++中才气用“&”)
                                                                                                                                                                                                                                                                                                                                  线性表                                                                                      顺序表                                                                                      链式表                                              五、顺序表

  • 顺序表的实现——静态分配
  1. #define MaxSize 10  //界说最大长度typedef struct{   ElemType date[MaxSize];  //用静态的“数组”存放数据元素 ElemType数据范例,实际自己界说   int length;  //顺序表当前的长度}SqList;  //顺序表的范例界说(静态分配方式)
复制代码
Eg:

Tip:
Q: 静态分配的顺序表满了怎么办
A: 重建。顺序表的表长刚开始的时候就已经确定,后续无法更改

  • 顺序表的实现——静态分配
  1. #define InitSize 10  //顺序表的初始长度typedef struct{        ElemType date *date; //指示动态分配数组的指针        int MaxSize;  //顺序表的最大容量        int length;  //顺序表当前的长度}SqList;  //顺序表的范例界说(动态分配方式)
复制代码

Eg:

在IncreaseSize();中将原来的数组地点复制给p 同时新建更大的数值,在将原来的数组数值复制到新数组中,再free(p);

  • 顺序表的特点
    (1)随机访问,在O(1)时间内即可找到第i个元素
    (2)储存密度高,每个节点只能存储数据元素
    (3)扩展容量不方便
    (4)插入、删除不方便。每次都要移动大量元素
  • 顺序表的插入与删除
(1)插入

L.date[j]=L.date[j-1];将第四个元素数据放到第五个元素位置上
(2)删除


  • 顺序表的两种查找(按位、按值)
    (1)按位

    (2)按值

六、链表

  • 单链表界说

  • typedef关键字

    Eg

  • 单链表的插入与删除
    (1)插入

    (2)后插法

    (3)头插法

    Tip:将已知的前节点数据放到新建节点中,再将要插入的数据放到已知节点中
(4)删除节点

(5)删除指定结点

4. 单链表的查找
(1)按位查找

(2)按值查找


  • 求表长

  • 双链表
    (1)初始化

    (2)插入

    (2.1)在链尾插入

    (3)双链表的删除

    (4)双链表的遍历

  • 循环单链表

10.循环双链表


  • 静态链表
    (1)界说

    Tip :头结点游标为-1,寻找节点靠游标排序来实现
七、顺序表与链表的比力

  • 都属于线性表,都是线性结构
  • 顺序表:优点支持随机存储存储密度高; 缺点:开辟大量一连空间分配不方便,不方便改变存储上线
  • 链表:优点离散的小空间分配方便方便改变存储上线;缺点:不可随机存储存储密度低

来源:https://blog.csdn.net/lushixuan12345/article/details/112054632
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )