842数据结构复习之数据类型

2018-10-26 | 阅读：次

数据类型

主要掌握基本概念，存储结构，基本操作（查找，插入，删除）, 可能结合时间复杂度来考，知道一些应用场景。

1. 表

有由A1,A2,…,AN组成的表，表的大小为N，称Ai−1是Ai的前驱，Ai+1是Ai的后继。大小为0的表为空表。

表ADT上的操作常见的包括：插入、删除、索引、查找、清空、打印。这是些基本的操作，根据需要可以再添加。

逻辑&物理

数组实现

数组实现的表，索引为O(1)，插入和删除的最坏情况为O(N)，查找、清空和打印为O(N)。
链表实现

链表由一系列在内存中可以不相连的结构组成，每个结构含有表元素和指向后继结构的指针，最后一个结构的指针为NULL。

创建头节点

手动new一个新的Node，将Node的next置为NULL即可。

head = new Node(0);head->next = NULL;

从头插入一个新的节点

手动new出一个新的节点p，使p的next的指向head->next所指向的地址,然后将head->next从新指向p即可。

Node * p = new Node(int); p->next = head->next; head->next = p;

删除指定节点

先遍历到指定节点的前一个节点,然后通过将前一个节点的next指针指向指定节点的下一个节点,达到悬空指定节点的效果,然后删除指定节点即可。

修改指定节点

遍历到指定节点的位置,将其data修改为要修改的值即可。

链表反转

方法1：使用3个指针遍历单链表，逐个链接点进行反转。
```
定义三个临时节点指向头结点之后的第1个节点p，第2个节点q和第3个节点m。将p->next置为空,然后将q->next = p,然后将p向后移动一个节点,即p = q,最后将q向后移动一个节点,即q = m,最后把m向后移动一个节点,即m = m->next;依此类推直到m等于NULL,然后将q->next = p,最后将head->next指向q(即目前第一个节点疑,也就是原本最后的一个节点)。
```
通过三个节点达到从头开始逐个逆序的目的。

方法2：从第2个节点到第N个节点，依次逐节点插入到第1个节点(head节点)之后，最后将第一个节点挪到新表的表尾。

从图上观察，方法是：对于一条链表，从第2个节点到第N个节点，依次逐节点插入到第1个节点(head节点)之后，(N-1)次这样的操作结束之后将第1个节点挪到新表的表尾即可。

代码如下:
应用
- 逆转链表
```
public  void  inverse( ListNode f )
 {  if ( f = = NULL ) return;
     ListNode  p = f . link ;  pr = NULL; 
     while ( p ! = NULL )
    {   f . link = pr ;
         pr = f ;
         f = p ;
         p = p . link ;
    }
     f . link = pr ;
  }
```
- 多项式相加
  
  参考网址：
  
  https://blog.csdn.net/bingjianIT/article/details/60779641
  
  http://data.biancheng.net/view/90.html
  
  https://blog.csdn.net/u014492609/article/details/39453481
- 约瑟夫问题
  
  参考网址：
  
  http://maskray.me/blog/2013-08-27-josephus-problem-two-log-n-solutions
  
  https://www.nowcoder.com/questionTerminal/11b018d042444d4d9ca4914c7b84a968
  
  https://blog.csdn.net/zhang5476499/article/details/52432870
- 双链表的插入，删除
  
  参考网址：
  
  https://blog.csdn.net/lisayh/article/details/79216796
  
  https://juejin.im/post/5b5d1a9af265da0f47352f14
  
  https://segmentfault.com/a/1190000002519828
- 特殊矩阵的压缩存储（南大PPT讲解很详细）
  
  数列掌握等差数列！
参考网址 https://www.jianshu.com/p/ad56483a7cdb

2 字符串

3 栈

应用
- 对表达式求值。
  
  中缀—-后缀—-对后缀表达式求值
- 递归函数的实现。
- PPT：第4章中用非递归实现中序,后序遍历

4 队列

4.1 优先队列概念

4.2 堆

4.4 堆排序

可以试着做一下这个题目

4.3 应用

已知队尾元素的位置与元素的个数，求队头元素的位置。

5 树

5.1 二叉树

二叉树的定义

包含n个节点的有限集合，该集合或者为空集（此时，二叉树称为空树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。

满二叉树
完全二叉树

二叉树的一些性质
二叉树的存储
- 顺序存储
  
  顺序存储结构是指用一维数据存储二叉树中的节点，其中，数组的下标要能体现节点之间的逻辑关系，对于上述的二叉树，其顺序存储结构为：
  
  在顺序存储结构中，“^”表示的是没有节点，从顺序存储可以看出，若出现大量“^”，则对空间是一种极大的浪费。
- 链式存储
  
  data 称为数据域，lchild和rchild称为指针域，分别指向左孩子和右孩子。
```
typedef struct BiNode{
        int data;// 数据域的值 
        struct BiNode *left;// 左孩子
        struct BiNode *right;// 右孩子
}binode;
```

二叉树的遍历

前序遍历

// 先序遍历
void pre_order(binode *p){
        if (p != NULL){
                printf("%d\t", p->data);
                pre_order(p->left);
                pre_order(p->right);
        }
}

中序遍历

// 中序遍历
void in_order(binode *p){
        if (p != NULL){
                in_order(p->left);
                printf("%d\t", p->data);
                in_order(p->right);
        }
}

后序遍历

// 后序遍历
void post_order(binode *p){
        if (p!= NULL){
                post_order(p->left);
                post_order(p->right);
                printf("%d\t", p->data);
        }
}

层次遍历

// 层次遍历
void lever_order(binode *p){
        // 使用队列
        list<binode *> t;
        if (p != NULL){
                t.push_back(p);
        }
    
        while (t.size() > 0){
                printf("%d\t", (t.front())->data);
                if ((t.front())->left != NULL){
                        t.push_back((t.front())->left);
                }
    
                if ((t.front())->right != NULL){
                        t.push_back((t.front())->right);
                }
                t.pop_front();
        }

最后的遍历结果
深度优先遍历，广度优先遍历

线索二叉树
- 存储
二叉排序树
二叉搜索树
1. 通过将字段leftSize添加到每个树节点，从普通二进制搜索树导出索引二进制搜索树。
2. Leftsize字段中的值=节点左子树+1中元素的数量
平衡二叉树
B- 树

定义：m阶的B树是m路搜索树。如果B树不为空，则相应的扩展树满足以下属性： 1）根至少有两个孩子 2）除根之外的所有内部节点都有至少[m/2]的孩子 3）所有外部节点处于同一级别

B-TREES属性： 1）所有外部节点都在同一级别 2）外部节点数=关键字数+1

1）搜索B树使用与之相同的算法搜索B树用于m路搜索树。算法分析：磁盘访问的数量是最多h（h是B树的高度）。证明：T是高度为h的阶数为m的B树，T中的元素数为n，每次我们将一个节点读入内存。 n + 1个外部节点在级别h上。
1. 插入具有m个子节点（也称为完整节点）的节点，如在最后一个示例中将B插入到B树中，整个节点被分成两个节点。
2. 新指针将添加到完整节点的父节点。因为k[m/2]被插入到父节点中，所以可能导致新的拆分。如果根被拆分，树的高度将增加1。
算法分析：
1. 如果插入操作导致s节点分裂，磁盘访问的数量是 h（读入搜索路径上的节点）
2. +2s（写出拆分的每个节点的两个分割部分）
3. +1 (写出新的结点)
3）从B树中删除两种情况：
1. 要删除的元素位于其子节点是外部节点的节点中（即元素位于叶子中）
2. 该元素将从非叶子中删除。
参考网址：

https://blog.csdn.net/google19890102/article/details/53926704

5.2 森林

森林与二叉树的转换
森林的遍历

5.3 树的应用

等价类问题
- 概念解释
  
  https://www.jianshu.com/p/da2c1deee1ae
- 其他参考网址
  
  https://blog.csdn.net/fangxin205/article/details/25650767
  
  https://www.coder4.com/archives/3217
  
  https://www.cnblogs.com/kangjianwei101/p/5242859.html
哈夫曼树&哈夫曼编码
- 参考网址
  
  https://www.jianshu.com/p/2c931286f060
  
  https://blog.csdn.net/ns_code/article/details/19174553
  
  https://blog.csdn.net/google19890102/article/details/54848262
  
  http://www.cnblogs.com/mcgrady/p/3329825.hml
  
  https://www.jianshu.com/p/95fba425be44
- 哈夫曼树与字符编码
  
  https://www.jianshu.com/p/2c931286f060

6 图

6.1 知识点大纲

6.2 图的概念

6.3 图的存储

6.3.1 邻接矩阵

digraphs: 有向图

a symmetric matrix: 对称矩阵

vertex :顶点

6.3.2 邻接表

6.4 图的遍历

从图的某个顶点出发访问遍图中所有顶点，且每个顶点仅被访问一次。（连通图与非连通图）

6.4.1 DFS 深度优先

步骤:

1、访问指定的起始顶点；

2、若当前访问的顶点的邻接顶点有未被访问的，则任选一个访问之；反之，退回到最近访问过的顶点；直到与起始顶点相通的全部顶点都访问完毕；

3、若此时图中尚有顶点未被访问，则再选其中一个顶点作为起始顶点并访问之，转 2；反之，遍历结束。

连通图的深度优先遍历类似于树的先根遍历

具体细节见：http://www.cnblogs.com/kubixuesheng/p/4399705.html
例子：

具体细节见：https://blog.csdn.net/zhangxiangDavaid/article/details/38323633

6.4.2 BFS 广度优先

步骤：

从图的某一结点出发，首先依次访问该结点的所有邻接顶点 Vi1, Vi2, …, Vin 再按这些顶点被访问的先后次序依次访问与它们相邻接的所有未被访问的顶点，重复此过程，直至所有顶点均被访问为止。

例子：

强烈推荐：
- https://blog.csdn.net/qq_38499859/article/details/79113284
- https://zhuanlan.zhihu.com/p/26987139

6.5 图的基本应用

6.5.1 最小生成树

Prim算法

普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克（英语：Vojtěch Jarník）发现；并在1957年由美国计算机科学家罗伯特·普里姆（英语：Robert C. Prim）独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。
Kuscal算法

Kruskal算法是一种用来寻找最小生成树的算法，由Joseph Kruskal在1956年发表。用来解决同样问题的还有Prim算法和Boruvka算法等。三种算法都是贪婪算法的应用。和Boruvka算法不同的地方是，Kruskal算法在图中存在相同权值的边时也有效。
强烈推荐：