数据结构(复习)

1.串的模式匹配 KMP

2.二叉树先序遍历，后序遍历，中序遍历递归算法和非递归算法
①后续遍历递归算法

void PostOrder(BitTree T)
{
if(T!=NULL)
 PostOrder(T_>lchild);
  PostOrder(T_>rchild);
   visit(T);
}

②非递归算法中序遍历

void InOrder(BitTree T)
{
  InitStack(S);
  BiTree p=T；
  while(p|| !IsEmpty(S))
  {
  if(p)
  {
  Push(S,p);
  p=p->lchild;
  }
else{
  Pop(S，p);
  visit(p);
  p=p_>rchild;
}
}

}

③层序遍历

void LevelOrder(BiTree T)
{
InitQueue(Q);
BiTree p;
EnQueue(Q，T)；
while(!IsEmpty(Q))
{
DeQueue(Q,p);
visit(p);
if(p->lchild!=NULL)
EnQueue(Q，p->lchild)；
if(p->rchild!=NULL)
EnQueue(Q，p->rchild)；
}
}

3.树的存储结构
1.双亲表示法

#define MAX_TREE_SIZE 100
typedef struct{
ElemType data;
int parent;
} PTNode;//节点
typedef struct
{
PTNode nodes[MAX_TREE_SIZE 100];
int n;/节点个数
}PTree;//树

2.孩子表示法
3.孩子兄弟表示法

typedef struct CSNnode
{
 ElemType data;
 struct CSNode *firstchild,*nextsibling;

}CSNode,*CSTree;

4.树与二叉树的应用
哈夫曼树和哈夫曼编码带权路径长度
并查集
二叉排序树中序遍历二叉树得到一个递增序列
平衡二叉树(是二叉排序树)
5.图的存储方法

邻接矩阵法

 #define MaxVertexNum 100
 typedef char VertexType;
  typedef  int EdgeType;
  typedef struct
  {
  VertexType Vex[MaxVertexNum ];
  EdgeType Edge[[MaxVertexNum][[MaxVertexNum];
  int vexnum,arcnum;
}

邻接表存储结构

#define MaxVertexNum 100
typedef struct ArcNode
{
int adjvex;
struct ArcNode *next；

}ArcNode;
typedef struct Vnode
{
VertexType data;
 ArcNode *first;
} Vnode,AdjList[ MaxVertexNum];
typedef struct
{
AdjList vertices;
int vexnum,arcnum;
} ALGraph;

6.图的遍历
广度优先搜索(迪杰斯特拉，普利姆最小生成树)
BFS(先visit再入队)

void BFS(Graph G, int v)
{
  visit(v);
  visited[v]=TRUE;
  EnQueue(Q,v);
  while(!IsEmpty(Q))
  {
 DeQueue(Q,v);
 for(w=FirstNeighbor(G,v);w>0;w=NextNeighbor(G,v,w))
  if(!visited[w]){
    visit(w);
  visited[w]=TRUE;
   EnQueue(Q,v);
  }

}
}

深度优先搜搜(递归)
DFS

void  DFS(Graph G，int v)
{
   visit(v);
    visited[v]=TRUE;
 
 for(w=FirstNeighbor(G,v);w>0;w=NextNeighbor(G,v,w))
  if(!visited[w]){
  DFS(G，w);
  }


}

7.图的应用
最小生成树 prime kruskal
最短路径 Dijkstra算法 O(V^2) Floyd算法 O(V^3)
拓扑序列(AOV网) DFS
关键路径(AOE网)
8.查找
顺序查找 O(n)
折半查找O(log2n)
分块查找法

树型查找:
二叉排序树BST O(n)-O(log2n)
平衡二叉树 O(log2n)
B树和B+树定义和区别
B树是为实现高效的磁盘存取而设计的多叉平衡搜索树。这个概念在文件系统，数据库系统中非常重要。和二叉树相比，极大地减少了磁盘读取的次数
B+树是B树的一种变形，它更适合实际应用中操作系统的文件索引和数据库索引。
❀B+树和B树相比，主要的不同点在以下3项：
①内部节点中，关键字的个数与其子树的个数相同，不像B树中，子树的个数总比关键字个数多1个
②所有指向文件的关键字及其指针都在叶子节点中，不像B树，有的指向文件的关键字是在内部节点中。换句话说，B+树中，内部节点仅仅起到索引的作用，
③在搜索过程中，如果查询和内部节点的关键字一致，那么搜索过程不停止，而是继续向下搜索这个分支。

9.散列表哈希表
1.处理冲突的方法
拉链法开放定址法(线性探测，平方探测，伪随机序列法) 再散列法
2.散列函数的构造方法
除留取余法直接定址法平方取中法
10.排序
1.内部排序
①插入排序 O(n^2)(直接插入排序，折半插入，希尔排序)
②交换排序(冒泡排序O(n^{2)，快速排序O(nlog2n)-O(n}2) )
③选择排序(简单选择O(n^2)和堆排序O(nlog2n))
④归并排序O(nlog2n)
⑤基数排序
2.外部排序
①多路归并排序
( 败者树置换选择排序最佳归并树)