湖大计学考研系列文章目录

• 22湖南大学计算机学硕上岸经验
• 22湖南大学 866 数据结构真题（回忆版）
• 866数据结构重点内容
• 866 数据结构模拟题（一）及解析
• 866数据结构笔记 - 第一章 绪论
• 866数据结构笔记 - 第二章 线性表
• 866数据结构笔记 - 第三章 栈和队列
• 866数据结构笔记 - 第四章 串
• 866数据结构笔记 - 第五章 树和二叉树
• 866数据结构笔记 - 第六章 图 
• 866数据结构笔记 - 第七章 查找
• 866数据结构笔记 - 第八章 排序 

---

目录

重点内容

一、基本概念

二、数据结构

三、算法

四、时间复杂度和空间复杂度

时间复杂计算

循环（for + while）

递归

主定理法

参考（具体细节见原文）

---

重点内容

        22年866真题：1个选择+1个简答，共计7分

        抽象数据类型、时间复杂度计算（循环和递归）

---

一、基本概念

• 数据：信息的载体
• 数据元素：数据的基本单位
• 数据项：数据元素的最小单位
• 数据对象：性质相同的数据元素集合
• 数据结构：逻辑结构 + 物理（存储）结构 + 运算
• 抽象数据类型（ADT）：数据对象 + 数据关系 + 基本操作
• 抽象数据类型定义了一个完整的数据结构，下面给出了线性表ADT的例子。我个人理解ADT就是完成了函数的封装功能。当我们在写代码时，或者说在考试中写代码时，有很多函数我们会经常用到，比如按值获取getValue函数，但是很多情况下，我们并不需要去完全实现这些函数，因此如果给定了ADT，我们想要按值获取就可以直接调用getValue函数就可以，这样会让代码更简洁，更易懂。
• 在866数据结构中，前几年的考研中会给定ADT，让你求解问题（尤其是有关图的题目）。期末题中还有直接让你设计ADT的，所以一定要清楚ADT的概念。

template <typename E> class List { 
public:
List() {}
virtual ~List() {}
virtual void clear()=0;
virtual void insert(const E& item)=0; 
virtual void append(const E& item)=0; 
virtual E remove()=0; 
virtual void moveToStart()=0; 
virtual void moveToEnd()=0;
virtual void prev()=0; 
virtual void next()=0; 
virtual int length() const=0; 
virtual int currPos() const=0; 
virtual void moveToPos(int pos)=0; 
virtual bool getValue(Elem&) const=0; 
virtual const E& getValue() const=0; 
};

二、数据结构

​​​​​​

1. 逻辑结构：分为线性结构和非线性结构

• 线性结构（只存在一对一关系）：线性表、栈、队列、串、数组
• 非线性结构：集合、树（存在一对多关系）、图（存在多对多关系）

      2.物理结构：

• 顺序存储：逻辑相邻、物理也相邻
• 非顺序存储（链式存储）：链式、索引、散列

三、算法

1. 算法的五个特性：有穷性、确定性、可行性、输入（0个或者多个）、输出（1个或者多个）

        换句话说，算法可以没有输入，但必须有输出。

      2. 好算法的特性（算法设计的要求）：正确性、可读性、健壮性、高效与低存储

四、时间复杂度和空间复杂度

• 算法原地工作：算法所需要辅助空间是常量
• 线性时间：时间复杂度小于等于O(n)
• 比较：O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

时间复杂计算

循环（for + while）

        常用两个公式：

// eg1.
int sum = 0;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        sum++;

// eg2.
int sum = 0;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i; j++)
        sum++;

        把执行算法所需要的时间T写成输入规模n的函数，记为T(n)，T(n)计算如下公式所示，所以O(T(n))=O(n^2)

// eg3.
int sum = 0;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i; j++)
        for (int k = 1; k < j; k++)
            sum++;

        把执行算法所需要的时间T写成输入规模n的函数，记为T(n)，T(n)计算如下公式所示，所以O(T(n))=O(n^3)

// eg4.
int i = 1;
while (i <= n){
    i += 2;
}

        设循环次数为T(n)，T(n) = 1时，i=3，T(n) = 2时，i=5，T(n) = 3时，i=7，可以得出i=2T(n)+1。i <= n，可以推出T(n) <= (n-1)/2，O(T(n))=O(n^2)。

// eg5.
int i = 1;
while (i <= n){
    i *= 2;
}

//等价于
for (int i = 1; i <= n; i*=2)

        设循环次数为T(n)，T(n) = 1时，i=2，T(n) = 2时，i=4，T(n) = 3时，i=8，可以得出i=2^T(n)。i <= n，可以推出T(n) <= logn，O(T(n))=O(logn)。

        结论：初始值（i=0，i=1）和循环终止条件（j<=i，j<=n/2）并不会改变最终的时间复杂度，但是（i +=2和i *= 2）时间复杂度会变化。

递归

        不仅要写出最后结果，还要会写步骤，不然没有分。

// eg6.
int fact(int n){
    if (n <= 1) return 1;
    return n * fact(n - 1);
}

        设执行时间为T(n)，假设 n>1，T(n) = O(1) + T(n-1) = 2O(1) + T(n-2) ....... = (n-1)O(1) + T(1)，T(1) = O(1)，所以T(n) = nO(1)，O(T(n))=O(n)。

         eg7. n是2的整数次幂，求时间复杂度。

        设执行时间为T(n)，O(T(n))=O(nlogn)

主定理法

        如果用主定理法解决上面那题，则a = 2，b = 2，f(n) = n，直接用第二条，得到O(T(n))=O(nlogn)

---

参考（具体细节见原文）

参考书目：

1. 王道：《数据结构》

2. 湖大本科： 《数据结构与算法分析（ C++版）（第三版）》Clifford A. Shaffer 著，张铭、刘晓丹等译。