数据：
数据元素：
数据项：
关键字：
数据对象：
数据结构：
内容：
逻辑结构：抽象的数据模型。用户视图，面向问题
存储结构（物理）：逻辑结构在计算机中的表示。面向计算机，实现视图
性质：
形式定义：（D，R）
D：数据元素有限集
R：D上的关系有限集
D = { a , b , c , d }
R = { ( a , b ) , ( a , c ) , ( b , d ) }
数据类型：（值 + 操作）DT
抽象数据类型：（数据结构 + 操作）ADT
数据结构
其结构上的操作
可用（D，S，P）表示
D：数据对象
S：D上关系集
P：对D的操作集
ADT Complex{ //ADT 类型名{
D = { e1 , e2 }, // 数据对象
R = {< e1 , e2 >}, // 数据关系
InitComplex( &Z , v1 , v2 ) // 基本操作
}ADT Complex // }ADT 类型名算法：指令的有限序列
算法分析:
算法分析-----大"O"符号
若两个正常数 c , n0 ,对任意n >= n0 都有T(n)<= c × f(n), 则称T(n) = O(f(n))
若
A
(
n
)
=
a
m
n
m
+
a
m
−
1
n
m
−
1
+
.
.
.
a
0
A(n) = a_mn^m + a_{m-1}n^{m-1} + ...a_0
A(n)=amnm+am−1nm−1+...a0
是一个m次多项式,则A(n) = O(n^m).
算法执行时间 = Σ(基本操作(i)的执行次数x基本操作(i)的执行时间)
算法空间复杂度: 算法执行所需空间的增长率
定义:
长度:
特征:
线性表链式存储
任意存储单元存放线性表元素,无连续性(淡化"位序")
便于插入,删除的操作
逻辑相邻,物理未必相邻,即"链式存储"
节点:
| data(数据域) | Next(指针域) |
|---|
单链表:表节点中只包含一个指针域
查找（按位查找）
templateT linklist::GetElem(int i){
P = Head->next; //工作指针（首节点），也可头节点
j = 1; //计数器，初始为1（首节点），若头节点，为0
while(p && j< i){ //顺位工作指针，直至i
P = P->next;
j++;
}
if(!P || j >i){ //空表或i<0或i>表长
throw "位置" //查找位置不合理
}else{
return P->data;
}
} //O(n) 插入
头插法：每次新申请节点放在“头节点”后
templatevoid LinkList::CreatList(int n){
for(int i = 1;i<= n;i++){
s = new Node;
cin>>s->data;
s->next = head->next
head->next = s;
}
} 尾插法：保证工作指针指向最后节点，方便插入
templatevoid LinkList::CreatList(int n){
Node*P,*S; //工作指针，P指向尾节点
P = Head;
for(int i =1，i<= n;i++){
s = new Node;
cin>>s->data;
s->next = p->next; //新节点链插入表尾
p->next = s;
p = s;
}
} 循环链表：终点指针指向head
双向链表
单链中每个节点再设置一个指向其前驱节点的指针域
静态链表
用数组描述链表，包括：
缺点：
间接寻址
顺序存储
链式存储
常用操作
- InitStack(&S) //初始化
- DestroyStack(&S) //销毁
- Push(&S,e) //入栈
- Pop(&S) //出栈
- GetTop(S) //获取栈顶元素
- StackEmpty(S) //测栈空
- ClearStack(&S) //清空栈顺序栈
templateclass SqStack{
Private:
T *base; //栈底指针
int top; //栈顶
int stackSize; //栈容量
public:...
} 链栈
不带头结点
templatestruct Node{
T data;
Node*next;
} 顺序栈vs链栈
时间：出入栈均为常数级
时间：
链栈特点
基本操作
- T* base; //存储空间基址
- int front; //队头指针
- int rear; //队尾指针
- queueSize; //队容量
- InitQueue(&Q) //初始化
- DestroyQueue(&Q) //销毁
- GetQueue(Q) //获取头元素
- EnQueue(&Q,e) //入队
- DeQueue(&Q,e) //出队
- QueueEmpty() //判断队空
- QueueFull() //判断队满
- ClearQueue(); //清空队列
- QueueTranverse(); //遍历队列**特点: **
链队
仅在表头删除和表尾插入的单链表
循环队列
循环栈
概念
串匹配
类型
根的元素，分叉为左子树，右子树。子树数量<=2（大二分叉）
满二叉树
完全二叉树
平衡二叉树
性质
遍历
线索二叉树
赫夫曼（哈夫曼）树
赫夫曼编码
树转二叉树：
树遍历
森林遍历
邻接点：
有向完全图：
无向完全图
度：
权：
子图：
连通图：
连通分量：
强连通图：
图生成树
图的存储
图的遍历
关节点
重连通图
最小生成树
最短路径
DAG图
AOV网与拓扑算法
关键路径：
有序折半查找
哨兵顺序查找
动态查找
散列函数
特点：
常用哈希函数
处理冲突
哈希表查找分析
内排序
三大经典排序方法
快速排序
堆排序
前缀表达式
后缀表达式
哈希表查找分析
内排序
三大经典排序方法
快速排序
堆排序
前缀表达式
后缀表达式
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
