是时候面向考试复习一下数据结构了

本文只针对作者认为可能考到的知识点进行整理，存在不足，欢迎补充。

第一章 绪论

1.什么是数据结构

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

数据对象：即具有相同性质的数据元素的集合

例：英文字母数据对象：C={‘A’, ‘B’, ……, ‘Z’, ‘a’, ‘b’, ……, ‘z’}。

主要包括逻辑结构、存储结构和运算集合三部分。

逻辑结构有四种：集合、线性结构、树形结构、图状结构（网状结构）

存储结构（也称为物理结构）有两种：顺序存储结构和链式存储结构

顺序存储结构，是借助元素在存储器中的相对位置来表示数据之间逻辑关系，要求所有的元素依次放在一片连续空间中，通常借助程序设计语言的数组类型来描述。
链式存储结构
链式存储结构无需占用一整块存储空间。但为了表示结点之 间的关系， 需要给每个结点附加指针字段用于存放后继元素的储地址。所以链式结构通常借助程序设计语言指针类型来描述。

抽象数据类型的定义取决于数据类型的逻辑特性，与其在计算机内部如何表示和实现无关。

两个重要特征：数据抽象性和数据封装性。

例：试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。

答：例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。对于整个表来说，只有一个开始结点（它的前面无记录）和一个终端结点（它的后面无记录），其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元（如用数组表示）来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。即相同的逻辑结构，可以对应不同的存储结构

2.什么是算法

算法，简单来说就是解决问题的方法。它是规则的有限集合，是求解特定问题的过程描述、操作步骤或指令序列。

它具有5个重要特性：有穷性、确定性、可行性、输入、输出

算法时间复杂度的估算方法：

从算法中选取一种原操作(对于所研究的问题来说，该操作是基本操作)，将该操作重复执行的次数作为算法时间复杂度的衡量准则。

时间复杂度与原操作的执行次数之和成正比。

第二章 表结构

1.顺序表和链表

线性结构的逻辑结构特征：

​ (1)存在唯一的第1个数据元素；

　(2)存在唯一的最后1个数据元素；

　(3)第 i (>1)个数据元素有唯一的1个前驱；

　(4)第 j (<n)个数据元素有唯一的1个后继。

顺序表：顺序存储结构：用位置描述逻辑关系

链表：链式存储结构：由指针描述逻辑关系

补：链表的定义：

1
2
3
4
5
typedef struct Node
{
    Type data;
    struct Node *next;
}Node,*LinkList;

例1：综合比较顺序表和链表

答：顺序表在内存中是一段连续的存储空间， 通过头指针和偏移地址直接访问数据，访问数据的效率较高，为O（1），但是插入数据和删除数据的效率较低。
链表在内存中是不连续的，通过每一个节点保存指向下一个节点的指针的方式来存储数据，访问数据的效率较低，但同时，插入数据和删除数据的效率较高。

例2：解释链表的”头指针、头结点和首元素结点“三个概念

答：头指针：线性链表中第一个结点或头结点的存储地址，它是访问链表的起始点。

​ 头结点：附加在第一个数据元素之前的结点，该结点的数据域一般为“空”、指针域存放第一个数据元素的地址。

​ 首元素节点：链表中第一个存储着数据的节点。

例3：给定链表的头指针L和一个正整数k。试设计一个尽可能高效的算法，用于查找链表L中倒数第k个位置上的结点。

答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
LinkList LinkSearch(ListList L,int k)
{
    int k0=1;
    LinkList p=new LinkList;
    p=L->next;
    LinkList q=p;
    while(p)
    {
        if(k0<=k)++k0;
        else q=q->next;
        
        p=p->next;
    }
    return q;
}//时间复杂度为O(N)

2.栈与队列

我觉得期中考不了很难，鸽了（）

想了解的话请移步我朋友的博客：

https://linyx.tk/2020/10/04/data-structure-study-note-1/

之后会补充（大概）

3.递归

递归的特点：

（1）出口至少有一个

（2）在经过有限次的递归调用后，能够导致递归出口的出现（递归算法必需具有终止递归的条件）

例：实现Hanoi塔问题

1
2
3
4
5
6
7
8
9
10
11
void hanoi(int n,char x,char y,char z)
{
    if(n==1)
        move(x,1,z);
    else
    {
        hanoi(n-1,x,z,y);
        move(x,n,z);
        hanoi(n-1,y,x,z);
    }
}

第三章：树结构

1.树

树是有n个结点的有限集合（n>=0)

树的结点包含一个数据元素以及若干个指针

结点拥有子树的个数称为结点的度。

度=0的结点叫做叶结点

树的度=max(结点的度)

结点的层次：第l层结点的孩子定义为l+1层。

树的高度（深度）=max（结点的层次）

例： 已知一棵度为k的树中，有n1个度为1的结点，n2个度为2的结点，…，nk个度为k的结点。试计算该树的叶子结点数。

答：n0=1+0n1+1n2+2n3+…+(K-1)nK

2.二叉树

二叉树：每个结点至多只有两棵子树

即：结点的度<=2的有序树

二叉树的定义：

1
2
3
4
5
6
typedef struct TNode
{
    Type data;
    struct TNode *Lchild;
    struct TNode *Rchild;
}TNode,*Tree;

满二叉树：一棵高度为k且具有2^k-1个结点的二叉树

（k=4)

完全二叉树：高度为k，结点个数∈[2^(k-1),2^k-1]，且第k层结点都集中在左侧的二叉树。

例：如果二叉树T的叶子结点数为n0，度为2的结点数为n2，则n0=n2+1。

证明：

设二叉树T共有n个结点

度为0的结点数为n0，度为1的结点数为n1,度为2的结点数为n2，

T的分支数为m

（1）由于二叉树中所有结点的度<=2,则：n=n0+n1+n2

（2）除根节点外，其余节点都有唯一前驱，则: n-1=m

（3）由于度=i（i=0，1，2）的结点具有i个分支，则：m=0+n1+2n2

联立上式得：n0=n2+1，证毕。

3.二叉树的遍历

3.1 先序遍历

1
2
3
4
5
6
7
void preOrder(Tree T)//递归写法
{
    if(!T) return ;
    cout<<T->data;
    preOrder(T->Lchild);
    preOrder(T->Rchild);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void preOrder(Tree T)//非递归写法
{
    stack<Tree> temp;
    Tree p=T->Lchild;
    while(p)
    {
        while(p->Lchild)
        {
            cout<<p->data;
            temp.push(p);
            p=p->Lchild;
        }
        cout<<p->data;
        while(!p->Rchild)
        {
            p=temp.top();
            temp.pop();
        }
        if(p->Rchild)
            p=p->Rchild;
    }
    
}

3.2 中序遍历

1
2
3
4
5
6
7
void InOrder(Tree T)//递归写法
{
    if(!T) return;
    InOrder(T->Lchild);
    cout<<T->data;
    InOrder(T->Rchild);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void InOrder(Tree T)//非递归写法
{
    stack<Tree> temp;
    Tree p=T->Lchild;
    while(p)
    {
        while(p->Lchild)
        {
            temp.push(p);
            p=p->Lchild;
        }
        cout<<p->data;
        while(!p->Rchild)
        {
            p=temp.top();
            cout<<p->data;
            temp.pop();
        }
        if(p->Rchild)
            p=p->Rchild;
    }
}

3.3 后序遍历

1
2
3
4
5
6
7
void PostOrder(Tree T)
{
    if(!T) return ;
    PostOrder(T->Lchild);
    PostOrder(T->Rchild);
    cout<<T->data;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void PostOrder(Tree T)
{
    stack<Tree> tempL，tempR;
    Tree p=T->Lchild;
    while(p)
    {
        while(p->Lchild)
        {
            tempL.push(p);
            p=p->Lchild;
        }
        while(!p->Rchild)
        {
            cout<<p->data;
            while(tempR.top()->Rchild==p)
            {
                cout<<tempR.top()->data;//获取R栈顶部指针的数据
                tempR.pop();//弹出
            }
            p=tempL.top();
            tempL.pop();
        }
        if(p->Rchild)
        {
            tempR.push(p);
            p=p->Rchild;
        }
    }
}

例：简述由先序序列和中序序列构造二叉树的基本操作方法

答：如果前序序列和中序序列都为空，那么构造一棵空树。否则

1、根据前序可确定根。

2、根据根和中序，可以确定左子树集合和右子树集合，并得到左子树中序序列和右子树中序序列。

3、在前序序列中划分出左子树前序序列和右子树前序序列。

4、根据左子树前序序列和左子树中序序列构造左子树。

5、根据右子树前序序列和右子树中序序列构造右子树。

4.哈夫曼树

5.森林与二叉树的转换

5.1树转换为二叉树

（1）加虚线 在树的每层按从“左至右”的顺序在兄弟结点之间加虚线相连
（2）去连线。除最左的第一个子结点外，父结点与所 其它子结点的连线都去掉
（3）旋转。将树顺时针旋转45°，原有的实线左斜
（4）整型。将旋转后树中的所有虛线改为实线，并向右斜。

image-20201107155306011

image-20201107155341354

5.2二叉树转换成树

（1）加虚线 若某结点i是其父结点的左子树的根结点，则将该结点ⅰ的右子结点以及沿右子链不断地搜索所有的右子结点，将所有这些右子结点与i结点的父结点之间加虚线相连

（2）去连线 去掉二叉树中所有其右子结点之间的连线
（3）规整化 将图中各结点按层次排列且将所有的虚线变成实线

image-20201107155753914