一、绪论
TARGET
掌握数据结构中涉及的基本概念
掌握算法的时间、空间复杂度及其简易分析方法
1、复杂现实问题
涉及线性表、树、图之类的数据结构
2、研究内容：：研究非数值计算的程序设 计问题中计算机的操作对象以及它们之间的关系和操作
3、基本概念
数据：能输入到计算机中去的描述客观事物的符号
包括数值型数据和非数值型数据
数据元素：数据的基本单位，也称节点或记录
数据项：有独立含义的数据最小单位，也称域
数据对象：相同特性数据元素的集合，是数据的一个子集
数据结构：相互之间存在的一种或多种特定关系的数据元素的集合
4、数据结构的内涵
数据逻辑结构：与计算机无关，包括集合、线性结构、树形结构、图形结构
数据存储结构：
顺序结构：使用相对位置（ps:可以看成相对于基址偏移）来表示数据元素间的逻辑关系（随机存储）
链式结构：用指针来表示数据元素间的逻辑关系
数据的运算
a、逻辑结构和存储结构相同，但运算不同，则数据结构不同，如栈和队列
问题：栈和队列是两种数据结构，他们的不同体现在哪里？
b、数据结构本身的运算：增、删、查、改、排序
5、数据类型和抽象数据类型
数据类型：即变量所具有的的数据种类，可以看做计算机已经实现的数据结构
抽象数据结构：用户自定义，由基本数据类型组成，包括一组相关的操作，类似c语言中的结构体
ADT = （D，S，P）
6、算法与算法分析
算法定义：求解某类问题所使用的一系列清晰的操作序列
特性：
- 输入 0或多个输入项
- 输出 至少一个输出项
- 有穷性 算法步骤和执行时间都是有限的
- 确定性 每一步都有明确的意义
- 可行性 能达到语气目标
算法的评价方法
正确性、可读性、健壮性、高效性
高效性:时间复杂度、空间复杂度
时间复杂度
算法在计算机上执行的时间，两种度量方法
-
事后统计
-
事前分析估计
取决于：算法选用的策略、问题规模，用O（）表示
求解方法：时间复杂度由最深层嵌套语句的重复执行次数决定
ps：有的情况下，算法中基本操作重复执行的次数随问题的输入实例不同而不同
空间复杂度
算法所需存储空间的度量，记作: S(n)=O(f(n))
算法执行要占据的空间 包括
- 算法本身要占据的空间，输入/输出，指令，常数，变量等
- 算法要使用的辅助空间
二、线性表
线性结构：
只有一个开始节点和一个终端节点
最多只有一个直接前驱和后继
反映的逻辑关系是一对一
TARGET
掌插顺序表的定义、查找、插入和删除
掌插链表的定义、创建、查找、插入和删除
1、线性表：
n（n>=0）个数据元素的有限序列
ps：n=0时称为空表
同一线性表中的元素必定具有相同特性
2、线性表的顺序表示
（又称顺序存储结构或顺序映像）和实现
定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的 存储结构。即：逻辑上相邻，物理上也相邻
方法：用一组地址连续的存储单元依次存储线性表的元素，可通过 数组V[n]来实现
实现：
初始化：
两种方式：参数用引用、参数用指针
代码部分
插入：
算法描述：
（1）判断揑入位置i 是否合法；
（2）判断顺序表的存储空间是否已满；
（3）将第n至第i 位的元素依次向后移动
一个位置，空出第i个位置；
（4）将要揑入的新元素e放入第i个位置；
（5）表长加1，返回OK。
代码
时间复杂度
最差：O(n)
最好：O(1)
平均：O(n/2)
删除：
算法描述：
算法描述：
（1）判断删除位置i 是否合法；
（2）将第i+1至第n 位的元素依次向前移
动一个位置；
（3）表长减1,返回OK。
代码
最差：移动n-1次
最好：不用移动
平均：移动（n-1）/ 2
查找：
随机存取，时间复杂度为O(1)
销毁：
if(L.elem) delete[]L.elem;
清空：
L.length=0
求长度
return L.length
判读是否为空
if (L.length == 0) return true;
else return 0;
特点：
逻辑结构与存储结构一致
访问每个元素花的时间相等
优点：
存储密度大（结点本身所占存储量/结点结构所占存储量）
可以实现随机存取
缺点：
在插入、删除某一元素时需要移动大量元素
当元素数量大且变化多时，浪费存储空间
属于静态存储模式，数据元素不能*扩充
3、线性表的链式表示
又称为非顺序映像或链式映像
定义：结点在存储器中的位置是任意的，即逻辑上相邻的数据元素 在物理上不一定相邻。
方法：指针
相关术语：
单链表或线性链表、双链表、循环链表
头指针、首元结点、头结点
思考：在链表中设置头结点有什么好处？
将非空表、空表、首元结点的操作统一
typedef struct LNode{
ElemType data; //数据域
struct LNode *next; //指针域
}LNode,*LinkList;
// *LinkList为LNode类型的指针
LNode *p <<——>> LinkList p
初始化：
ps:注意区分有无头结点
代码
代码后续补充，未完待续……
双链表、循环链表
头指针、首元结点、头结点
思考：在链表中设置头结点有什么好处？
将非空表、空表、首元结点的操作统一
typedef struct LNode{
ElemType data; //数据域
struct LNode *next; //指针域
}LNode,*LinkList;
// *LinkList为LNode类型的指针
LNode *p <<——>> LinkList p
初始化：
ps:注意区分有无头结点
代码
代码后续补充，未完待续……