数据结构复习
基础知识
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)
线性表
- 掌握顺序表的存储结构以及基本操作操作的代码实现以及它的优缺点——代码级
- 掌握顺序表的存储方式和基本操作的代码实现——代码级
- 掌握单链表的存储方式和基本操作的代码实现——代码级
链表头是整个链表的第一个节点，它不存放任何数据信息，不过它可以告诉我们第一个数据是从哪一个开始
单链表所需函数：
//正常插入
void insert(int k,int x){
e[idx] = x,ne[idx] = ne[k],ne[k] = idx,idx++;
}
//头插
void insert_head(int x){
e[idx] = x,ne[idx] = head,head = idx,idx++;
}
//删除
void del(int k){
ne[k] = ne[ne[k]];
}
- 单链表初始创建等的区别——由于头节点存在
- 循环链表和双向循环链表，掌握插入与删除
- 约瑟夫问题——循环链表
- 顺序栈和链式栈的实现——代码级
- 双向栈不需要看
- 给一个序列要知道可能的出战序列和不可能的情况以及出栈序列的个数
出栈序列的个数=
$$ \frac{1}{n+1}C_{2n}^{n} $$
- 括号匹配：
for(int i=0;i<length;i++)
{
if(str[i]=='('||str[i]=='{'||str[i]=='[')
{
Push(S,str[i]);
}
else{
if((str[i]==')'||str[i]=='}'||str[i]==']')&&StackEmpty(S))return false;
char topElem;
Pop(S,topElem);
if(str[i]==')'&&topElem!='(')return false;
if(str[i]=='}'&&topElem!='{')return false;
if(str[i]==']'&&topElem!='[')return false;
}
}
return StackEmpty(S);
- 后缀表达式的求值
int main() {
string s;
cin>>s;
stack<int>st;
for(int i=0;i<s.size();i++){
if(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/'){
int num1=st.top();
st.pop();
int num2=st.top();
st.pop();
if(s[i]=='+')st.push(num2+num1);
if(s[i]=='-')st.push(num2-num1);
if(s[i]=='*')st.push(num2*num1);
if(s[i]=='/')st.push(num2/num1);
}else{
char ch=s[i];
string s2;
char s1[2]={ch,0};
s2=s1;
st.push(stoi(s2));
}
}
- 已知中缀表达式求后缀和前缀
先从右向左遍历中缀表达式，找到从右到左的第一个优先级最低的运算符来做二叉树的根，确定根之后那么它的左右子树基本确定，然后第二次遍历中缀表达式找第二优先级最低的运算符，然后根据刚刚的大致位置确定第二最低优先级运算符的位置
- 循环队列的顺序结构和链式结构--代码级
队头指针进1: front = (front + 1) % maxSize;
队尾指针进1: rear = (rear + 1) % maxSize;
队列初始化：front = rear = 0;
队空条件：front == rear;
队满条件：(rear + 1) % maxSize == front
-
了解对称矩阵的压缩存储过程
-
稀疏矩阵的存储结构
-
理解字符串的存储表示和提取子串简单模式匹配算法
树
- 基本术语要知道
- 树的逻辑结构
每个节点就只有唯一的前驱有零个或多个后继
- 二叉树———代码级
- 带空节点的先序建二叉树的方法
int BinTreeCreate(BitTree &BT)
{
char ch;
scanf("%c", &ch);
if(ch == '#') BT = NULL;
else{
BT = new BT;
BT->data = ch;
BinTreeCreate(BT->lchild);
BinTreeCreate(BT->rchild);
}
return 0;
}
- 给你一个先序列给你一个中序，要能够把这个二叉树画出来(不涉及到代码)
或者慢慢推（中左右，左中右）也行 - 二叉树遍历
void BinTraverse(BitTree BT)
{
if(BT == NULL) return;
printf("%c",BT->data);
if(BT->lchild != NULL)
BinTraverse(BT->lchild);
if(BT->rchild != NULL);
BinTraverse(BT->rchild);
}
//更换printf的位置即可得到中/后序遍历
- 一颗完全二叉树也要会非常熟练地算出杜为零。杜维一杜为二的节点个数以及他的深度，甚至于他的非叶子节点的个数都能算出来、
$$ n_{0} = n_{2} + 1 $$
- 树的子女兄弟存储方法，不需要代码理解
左指孩子，右指兄弟
-
树和二叉树和森林的相互转换，不需要代码
-
树/森林的深度优先
-
哈夫曼数和哈夫曼编码的过程(图有误，左0右1)
索引和散列
所有内容不需要代码级
- 散列查找技术的原理
散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f (key)
- 哈希函数的构建方法，重点掌握除留余数
线性探测。要会算查找成功和查找不成功，二次探测和双反，也只要会算查找成功就可以了
- 理解处理冲突开放定制法
当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。
Hi=（H（key）+di）% m i=1，2，…，n
-
了解列地址法处理冲突的过程
-
理解决定哈希表查找ASL就是平均查找长度的因素：饱和因子Alpha
查找
- 顺序查找时间复杂度分析以及代码O（n）
- 折半查找也的代码以及时间复杂度分析(二分査找就是 折半查找 )
- 折半查找判定树
- 二叉排序树的定义
任何节点的键值一定大于其左子树中的每一个节点的键值，并小于其右子树中的每一个节点的键值。
- 掌握二叉排序树的搜索插入删除代码
搜索与插入代码：
BST_P SearchMin(BST_P root)
{
if (root == NULL)
return NULL;
if (root->lchild == NULL)
return root;
else //一直往左孩子找，直到没有左孩子的结点
return SearchMin(root->lchild);
}
BST_P SearchMax(BST_P root)
{
if (root == NULL)
return NULL;
if (root->rchild == NULL)
return root;
else //一直往右孩子找，直到没有右孩子的结点
return SearchMax(root->rchild);
}
BST_P Search_BST(BST_P root, DataType key)
{
if (root == NULL)
return NULL;
if (key > root->data) //查找右子树
return Search_BST(root->rchild, key);
else if (key < root->data) //查找左子树
return Search_BST(root->lchild, key);
else
return root;
}
void Insert_BST(BST_P *root, DataType data)
{
//初始化插入节点
BST_P p = (BST_P)malloc(sizeof(struct BST_Node));
if (!p) return;
p->data = data;
p->lchild = p->rchild = NULL;
//空树时，直接作为根节点
if (*root == NULL)
{
*root = p;
return;
}
//是否存在，已存在则返回，不插入
if (Search_BST(root, data) != NULL) return;
//进行插入，首先找到要插入的位置的父节点
BST_P tnode = NULL, troot = *root;
while (troot)
{
tnode = troot;
troot = (data < troot->data) ? troot->lchild : troot->rchild;
}
if (data < tnode->data)
tnode->lchild = p;
else
tnode->rchild = p;
}
值得一提的二叉排序树删除操作:
void DeleteBSTNode(BST_P *root, DataType data)
{
BST_P p = *root, parent = NULL, s = NULL;
if (!p) return;
if (p->data == data) //找到要删除的节点了
{
/* It's a leaf node */
if (!p->rchild && !p->lchild)
*root = NULL;
// 只有一个左节点
else if (!p->rchild&&p->lchild)
*root = p->lchild;
// 只有一个右节点
else if (!p->lchild&&p->rchild)
*root = p->rchild;
//左右节点都不空
else
{
s = p->rchild;
/* the s without left child */
if (!s->lchild)
s->lchild = p->lchild;
/* the s have left child */
else
{
/* find the smallest node in the left subtree of s */
while (s->lchild)
{
/* record the parent node of s */
parent = s;
s = s->lchild;
}
parent->lchild = s->rchild;
s->lchild = p->lchild;
s->rchild = p->rchild;
}
*root = s;
}
free(p);
}
else if (data > p->data) //向右找
DeleteBSTNode(&(p->rchild), data);
else if (data < p->data) //向左找
DeleteBSTNode(&(p->lchild), data);
}
- 堆swift和down
void up(int x){
while(x/2 > 0 && h[x/2] > h[x]){
swap(x/2,x);
x/=2;
}
}
void down(int x){
int p = x;
if(2*x <= idx && h[p] > h[2*x]) p = 2*x;
if(2*x + 1 <= idx && h[p] > h[2*x + 1]) p = 2*x + 1;
if(p != x){
swap(x,p);
down(p);
}
}
图论
图这一块的东西呢都代码记得很少
- 第一个理解什么是图理解什么是图以及它的逻辑结构
- 理解图的基本术语
什么是路径，什么是连接顶点了，什么是联通图了什么是非连通图的连通分量了，还有这个叫强连通图以及强连通分量还有生成树
- 掌握图的两种存储结构邻接矩阵和邻接表
public int getFirstneighbor(int i){
for (int j=0;j<vertexNum;j++){
if (isVisited[j]==false && edgeMatrix[i][j]!=0){
return j;
}
}
return -1;
}
public int getNextNeighbor(int i,int j){
for(int k=j+1; k<vertexNum; k++){
if (isVisited[k]==false && edgeMatrix[i][k]!=0){
return k;
}
}
return -1;
}
- 重点掌握树的深度优先遍历和广度优先遍历——非代码级
深度优先：利用栈
广度优先：利用队列
-
最小树生成算法：Prim和Kruskal,一个是顶点归并成集合，一个是边排序后归并
-
AOE不看
排序
只靠二分插入排序，希尔排序，冒泡排序，快速排序以及堆排序
一方面是代码，第二个是时间复杂度分析以及稳定性分析
- 折半插入排序
最好时间复杂度O(n)平均时间复杂度O(n²)最坏时间复杂度O(n²)是一种稳定的排序算法。
- 其他排序算法
