- 数据结构复习
- @[toc]
- 第0章绪论
- 第1章线性表
- 分类:顺序表和链表
- 1.顺序表(数组存储)
- 1)(数据类型)
- 2.链表(链式存储)
- 1)(数据类型)
- 2)head和头结点
- 3)主要操作
- 4)分类
- 循环链表 (将表尾的指针指向'头结点'
- 双向链表 (方便查询前一个结点
- 第2章栈和队列
- 栈 **(有后进先出的特性**
- **1)'栈的定义:**
- 2)数据类型
- 顺序栈 (以数组为格式存储
- 链式栈 (以链表形式存储
- 3)主要操作
- 队列 (有先进先出的特性
- 1)队列的定义:
- 2)数据类型
- 顺序队列(以数组为格式存储
- 链式队列 (以链表形式存储
- 3)主要操作
- 第2章栈和队列
- 串 (主要为BF、KMP算法
- 1)定义
- 2)**'串的模式匹配算法'**
- 2)实际代码
- 数组
- 二维数组
- 广义表(LS) 线性表内存储的数据不一定为相同类型
- 第3章树和二叉树
- 树
- 1)定义
- 二叉树
- 1)定义
- 2)数据类型
- **'顺序存储':**按照满二叉树的编号放入数组,没有的空出填0即可
- '链式存储':data,lchild,rchild
- 3)算法
- 二叉树的遍历
- 线索二叉树(方便查询前驱和后继结点
- 哈夫曼树 (带权路径长度最短的二叉树
- 1)定义
- 2)构造哈夫曼树
- 3)哈夫曼编码
- 第4章图
- 1)定义
- 2)数据类型
- **'数组表示法(邻接矩阵)':**用二维数组表示元素之间的关系
- '链式存储结构(邻接表)':
- 3)图的遍历
- 深度优先搜索(DFS) 递归思想
- 广度优先搜索(BFS) 使用队列
- 4)图的应用
- 图的生成树:
- 最小生成树 (各边权值和最小)
- 最短路径
- 有向无环图':通常用来描述一个工程或系统的进度
- 第5章查找与排序
- 查找
- 1)概念
- 2)线性表的查找
- 3)树表的查找
- '二叉排序树':
- '平衡二叉树'(AVL):
- 4)散列表的查找(哈希表)
- '开放地址法':
- '链地址法'(java中HashSet的存储方式):
- 排序
- 1)插入排序
- 直接插入排序(按照顺序法定位插入位置,运用数组从后往前进行比较)
- 二分插入排序(按照二分法定位位置)
- 希尔排序(缩小增量、多遍插入排序)
- 2)交换排序
- **冒泡排序 O(n²)**
- **快排 O(n*log2 n) 递归**
- 3)选择排序
- **简单选择排序:**
- **堆排序:**
- 4)归并排序
- 5)基数排序
- 排序时间汇总:
1.抽象数据类型
ADT 抽象数据类型名 {
'Data'
数据对象:〈数据对象的定义〉
数据关系:〈数据关系的定义>
'Operation'
操作1:
初始化操作
结果描述
操作2:
...
操作3:
...
} ADT 抽象数据类型名
2.计算时间复杂度(离散数学)
O(n)的相关计算
第1章线性表 分类:顺序表和链表 1.顺序表(数组存储)线性表里面存储内容的类型必须相同
因为线性表里内容为:数组(存放数据),长度(记录大小)
1)(数据类型) struct{
elem[100];//不一定是一维数组,可以根据需求改变 如自定义结构类型
int length
}L
2.链表(链式存储)
结构:数据 和指针(指向下一个数据)
注:最后一个结点指针域为NULL
1)(数据类型)typedef struct LNode{
ElemType data;
struct LNode *next;//作为接收下一个链表地址的指针(next=&a1) next类型和当前类型一致
}LNode,*Linklist//Linklist是结构体的指针类型名
2)head和头结点
head:指向链表中第一个结点的指针
头结点:不储存任何信息的结点,其指针指向第一个真正结点
3)主要操作‘初始化操作’:
在带头结点的情况下,则需建立一个其指针域的指针为NULL的头结点,并令头指针指向该结点
void InitList(Linklist &L){//传入一个指针变量 L
L = new LNode; //给指针L分配空间 大小为下一个LNode
if (!L) exit(1);// 存储空间分配失败
L->next = NULL; //头结点的指针next指向空
}
删除:
q=p->next;//引入一个q结点便于free掉 p->next=q->next;//相当于将p的next 跳过 delete q;
‘建立链表’:
‘头插法’:插入头结点的后一位即可(数据插入顺序为逆序
void CreateList_H(Linklist &L,int n){//n个元素
L=new LNode;
L->next=NULL;//建立一个带头结点的单链表
for(i=n;i>0;--i){//逆序
p=new LNode; //生成新的结点p
scanf(&p->data); //手动输入插入的元素值
p->next=L->next; //插入到表头
L->next=p;
}
}
‘尾插法’:插入尾结点的后一位 要引入尾指针’r’(数据插入为顺序
void CreateList_R(Linklist &L,int n){#n个元素
L=new LNode;
L->next=NULL;//建立一个带头结点的单链表
r=L; //将尾指针指向头结点
for(i=n;i>0;i++){
p=new LNode;//生成新的结点p
scanf(&p->data); //手动输入插入的元素值
p->next=NULL;
r->next=p; //插入到表尾部
r=p; //r指向新的尾结点
}
}
4)分类
循环链表 (将表尾的指针指向’头结点’
‘特点’:
从任一结点出发,沿着链可访问全部结点;
运算与单链表基本一致,仅是循环结束条件为P->next==L (L为头指针);
判断是否是表尾结点:p->next==L ;
双向链表 (方便查询前一个结点:结构中多了一个前趋指针,方便对前一个进行查询
第2章栈和队列注意进栈出栈那种排序题,见作业2
栈 (有后进先出的特性 1)'栈的定义:可以在表尾进行插入和删除的线性表
表尾称为栈顶:top, 表头称为栈底:base
stacksize:栈的最大存储上限
2)数据类型 顺序栈 (以数组为格式存储 typedef struct{
int stacksize;//栈的大小
SElemType *top;//指向栈顶元素的上一个的位置
SElemType *base;//指向栈底元素
}SqStack;
链式栈 (以链表形式存储
typedef struct{
SElemType data;
struct StackNode *next;
}StackNode,*LinkStack;
3)主要操作
‘入栈’:给top指针所值的区域赋值,top指针上移一个
‘出栈’:top指针下移,返回top现在所指的元素
队列 (有先进先出的特性 1)队列的定义:
可以在表尾进行插入 在表头进行删除的线性表,队头(Front) 队尾(Rear)
解决上溢的办法:引入循环队列,求余数(%)即可
解决队满的办法:少用一个元素空间
(rear+1)%maxsize==front;2)数据类型 顺序队列(以数组为格式存储
typedef struct{
Qelementtype *base;//指向数组的首元素
int front;//指向队头的下标
int rear; //指向队尾的下标
}SqQuence;
链式队列 (以链表形式存储
typedef struct QNode{
Qelementtype data;
struct Qnode *next;
}QNode,*QuenePtr;/
}
}
快排 O(n*log2 n) 递归
1.找一个中心形成两个子表’左子表’小’右子表’大
2.对各子表重新选择中心(方法同上)
3.如果只有一个中心点结束
‘子表的形成’:
1.将第0号位置空下,存储中心点,'low’变为空
2.前后两指针’low’&‘high’,如果’high’小于中心点,'high’和’low’值交换从两头向中间交替逼近的思想
3.递归调用,直到表剩1个
int L[100];//定义顺序表
int length=0;
void Qsort(int *L,int low,int high){
int center;
if (low
center=Partition(L,low,high);//找到中心点
Qsort(L,low,center-1);//对左子表排序
Qsort(L,center+1,high);//对右子表排序
}
}
int Partition(int *L,int low,int high){
int key;
L[0]=L[low];key=L[low];//将中心点调整到0处
while (low
while (low=key)
--high;
L[low]=L[high];
while (low
3)选择排序
简单选择排序:
1.从所有的数据元素中挑一个最小的与第一个进行交换
2.第二次从第二个开始找最小值
3.依次排序
堆排序:
堆定义:若n个元素的序列满足(实际为完全二叉树)
‘小根堆’:ai
‘大根堆’:ai>a2i&&ai>a(2i+1)
‘输出堆顶元素对其余元素进行调整’:
1.输出堆顶后,以堆中最后一个元素代替它
2.将其与左右子树的结点进行比较,小了交换
3.重复,直到叶子结点
‘堆的建立’:
1.所有非叶子结点(n/2–1)进行排序即可(顶点和自己的左右子树进行比较)
2.根节点需要从上往下对比完全
‘堆排序’:
1.进行堆排序
2.输出根
3在进行调整、输出
4)归并排序
‘思路’:
1.两两排序合并成一个有序的
2.四四合并
…
5)基数排序
方法:
分配+收集(数字根据实际情况而定)
'0-9’数字,第一次按照’个位’分配,分配后按照顺序取出
'0-9’数字,第二次按照’十位’分配后,按照顺序取出
排序时间汇总:



