【数据结构】第1章绪论

蔚落 2023-02-25 12:28 12阅读 0赞

## 1.1 数据结构的研究内容 ##

## 1.2 基本概念和术语 ##

**1、术语关系**：数据 > 数据对象 > 数据元素（基本单位） > 数据项（最小单位）  
数据结构 (Data Structure) 是相互之间存在一种或多种特定关系的数据元素的集合。换句话 说，数据结构是带 ”结构＂ 的数据元素的集合，“结构” 就是指数据元素之间存在的关系。  
**2、数据结构形式定义**：数据结构是一个二元组(D, R)，D是数据元素的有限集，R是D上关系的有限集  
注：<a, b>有序a前b后，(a, b)无序  
例1：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic_center]

T = (D, R)  
D = \{A, B, a, b, c\}  
R = \{R1, R2\}  
R1 = \{<A, a>, <A, b>, <A, c>\}  
R2 = \{<B, a>, <B, b>, <B, c>\}

例2：复数(a + bi)的数据结构  
T = (D, R)  
D = \{a, b\}  
R = \{R1\}  
R1 = \{<a, b>\}  
**3、逻辑结构**：集合、线性、树、图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70 1]  
**4、储存结构**：顺序（数组）、链式（指针）  
**5、数据类型**：  
**6、抽象数据类型**：

## 1.3 抽象数据类型的表示与实现 ##

【补】C++数据结构中的&后面的变量能带回返回值，例：

#include<bits/stdc++.h>
    using namespace std;
    int a = 1;
    int b = 2;
    void fun(int &c,int d) //&后面的变量能带回返回值
    {
        
        c = 3;
        d = 4;
    }
    int main()
    {
        
        fun(a, b);
        printf("%d\n", a); //a = 3, 被改变了
        printf("%d\n", b); //b = 2, 没变
        return 0;
    }

## 1.4 算法和算法分析 ##

**1、定义**：算法 (Algorithm) 是为了解决某类问题而规定的一个有限长的操作序列  
**2、特性**：有穷性、确定性、可行性、输入、输出  
**3、优劣标准**：正确性、可读性、健壮性、高效性  
**4、时间复杂度**：算法的渐近时间复杂度， 简称时间复杂度  
计算方法：  
1、用常数1取代运行时间中的所有加法常数  
2、在修改后的运行次数函数中，只保留最高阶项  
3、如果最高阶项存在且不是1，则删掉与这个项相乘的常数  
4、得到的最后结果就是大O阶  
例1：选择排序、冒泡排序，O(n ^ 2)  
例2：下面程序，常数阶O(1)

#include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        
        int x = 90, y = 100;
        while(y > 0)
        {
        
            if(x > 100)
            {
        
                x -= 10;
                y--;
            }
            else x++;
        }
        cout<<x<<' '<<y<<'\n'; //91 0
        return 0;
    }

大小关系：O(1) < O(log n) < O(n) < O(n \* log n) < O(n ^ 2) < O(n ^ 3) < O(2 ^ n) < O(n!) < O(n ^ n)  
**5、空间复杂度**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic_center]: /images/20230209/d262bcf0be534c419993012bb9221de4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200713084042732.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200713084059569.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky,size_16,color_FFFFFF,t_70