大话数据结构1

数据结构：是相互之间存在的一种或者多种特定关系的数据元素的集合。

数据: 是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。数据不仅仅包括整型、实型等数值类型，还包括字符及声音、图像、视频等非数值类型。

数据元素：是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。也被称为记录。

数据项：一个数据元素可以由若干个数据项组成。

数据对象：是性质相同的数据元素的集合，是数据的子集。

算法：算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

在进行算法分析时，语句总的执行测试T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n)=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。其中f（n）是问题规模n的某个函数。

常见的时间复杂度

线性表顺序存储结构的优缺点

优点

• 无需为表示表中元素之间的逻辑关系而增加额外的存储空间
• 可以快速的存取表中任一位置的元素

缺点

• 插入和删除操作需要移动大量元素
• 当线性表长度变化较大时，难以确定存储空间的容量
• 造成储存空间的”碎片“

单链表结构和顺序储存结构优缺点

• 储存分配方式
  • 顺序存储结构用一段连续的存储单元依次储存线性表的数据元素。
  • 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素
• 时间性能
  • 查找
    • 顺序储存结构O(1)
    • 单链表O(n)
  • 插入和删除
    • 顺序储存结构需要平均移动表长一半的元素，时间为O(n)
    • 单链表在先出某位置的指针后，插入和删除时间仅为O(1)
• 空间性能
  • 顺序储存结构需要预分配储存空间，分大了，浪费，分小了易发生上溢
  • 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制