数据结构知识点复习.txt

数据结构
-数据的逻辑结构：在数据结构中,从逻辑上可以将其分为线性结构和非线性结构
-线性结构
-线性表
-顺序表
-特点
-储存地址连续
-逻辑上相邻的数据元素其物理位置也相邻
-存储密度大（存储空间全部用于存储元素）
-可以随机访问任意元素
-优点
-不需要额外的存储空间来表示元素间的逻辑关系
-可以随机地存取表中的任意一个元素
-缺点
-插入和删除元素时要移动大量的元素
 -必须事先分配足够的空间，内存分配固定不灵活
-顺序表的基本运算的复杂度
 -插入
 -时间复杂度：O(n)
-空间复杂度：O(1)
 -删除
 -时间复杂度：O(n)  
-空间复杂度：O(1)
-链表
-特点
-不要求储存地址连续
-逻辑上相邻的数据元素其物理位置不一定相邻。
-在存储每个结点值的同时，还必须存储指示其后继结点的地址
-不需要事先估计存储空间大小。
-不能随机访问任意元素，要按顺序查找