数据结构（导论，线性表）

导论：

与数据元素本身的形式、内容、相对位置、个数无关的是数据的逻辑结构

通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致

数据项是数据的不可分割的最小单位

数据元素是数据的基本单位

一些表面上很不相同的数据可以有相同的逻辑结构

数据的存储结构无关的术语是：有序表

数据结构中，树是非线性数据结构

算法的五个特征：输入，输出，确定性，有穷性，可行性

算法设计的基本要求：正确性、可读性、健壮性、通用性、效率与存储量的需求

时间复杂度：一个语句的频度是指该语句在算法中被重复执行的次数。

最坏时间复杂度

平均时间复杂度

最好时间复杂度

空间复杂度：对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。

简单选择、冒泡排序、插入排序的时间复杂度均为O（n的二次方）

算法原地工作是指算法所需辅助空间是常量，即O（1）。

常见的渐进时间复杂度

线性表

数据的逻辑结构

线性结构

一般线性表

受限线性表

栈和队列

串

线性表推广

数组

广义表

非线性结构

集合

树形结构

一般树

二叉树

图形结构

有向图

无向图

线性结构：

线性表：含n个相同数据类型的数据元素的有序序列，称为线性表

线性表L=(a1，a2,……an)，除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。

线性表的两种存储

顺序存储和链式存储

顺序表

优点：可以进行随机存取

缺点：插入和删除操作需要移动大量元素

求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低

顺序存储的线性表可以随机存取

由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活

插入：

在n个元素的顺序表中，第i个位置插入一个结点，共n-i+1个元素向下移动一个位置，时间复杂度为O（n）

删除：

在n个元素的顺序表中，第i个元素删除，共n-i个元素向下移动一个位置，时间复杂度为O（n）

查找：

位置和长度

链式

单链表：

数据域-指针域

用一组任意的存储单元存储线性表中的数据元素，用这种方法存储的线性表简称线性链表，而每一个结只包含一个指针域的链表，称为单链表

了解插入，删除的指向，先右后左

单列表的查找【按序号查找-按值查找】

双向链表

指针域-数据域-指针域

链接存储的存储结构所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针

线性表若采用链式存储结构时，要求内存中可用存储单元的地址连续或不连续都可以

线性表Ｌ在（需不断对Ｌ进行删除插入）情况下适用于使用链式结构实现。

单链表的存储密度小于1

将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是n

在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动（  n-i+1 ）个元素。

在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（  s->next=p->next; p->next=s; ）

大部分都是定理。

参考文章:

https://blog.csdn.net/liu17234050/article/details/106315650