数据结构-01-引言

发表于 更新于 分类于 / 阅读次数： 本文字数： 2.6k 阅读时长 ≈ 9 分钟

本博文基于C语言的内容引入数据结构的时间、空间复杂度概念，并补充等差数列、累加和数列、等比数列等数学理论。

数据结构可以拆分为两个内容，即数据+结构。

是什么？

  • 首先，数据从哪儿来？到哪儿去？

    数据从生活各处中来，而目的是用数据驱动业务。

  • 结构又是什么？

    即数据的组织形式，比如数组、比如链表。

    在特定的情境下，以往所用的数据类型无法基于需求合理地组织数据，此时需要自己设计一套新的数据组织形式来解决问题。

    数据结构是一种存储、组织数据的方式，旨在方便访问和修改。任何一致数据结构都有各自的优劣。

C基础

函数

  • 实现某个具体功能的代码块
  • 增加代码复用性
  • 降低编程难度
  • 函数不被调用就不会执行
  • 对内隐藏细节，对外暴露接口

基于需求对函数设定参数、设定返回值。

字符串

C语言中的字符串是按照字符数据进行存储的，并没有这种数据类型。

C#中有string类型

  • 存储时字符串尾部带有 \0结束符

  • 可在定义时直接初始化赋值，也可在定义后使用strcpy()赋值

1
2
3
char arr1[11] = "HelloWorld";
char arr2[11];
strcpy(arr2,"HelloWorld");

地址

依据冯诺伊曼结构，计算机操作系统通常包括输入/输出设备，主存储器、辅存储器、控制器、运算器。

内存条、显卡、适配卡都各自有其存储地址空间。操作系统将设备的存储地址空间抽象为一个巨大的一维数组空间，如常说的32位/64位机。

数组

  • 相同数据类型的集合
  • 数组长度在定义时已经确定
  • n元素的数组下标为0~n-1
1
2
char a[11];
char b[10][10];

例如以上变量a：

  • a：数组变量
  • *a：数组首元素

再比如变量b：

  • b:数组地址
  • *b:数组首个行向量地址
  • **b：数组首个行向量中首个元素地址

指针

指针与数据在某种程度上可以实现相同的功能，比如 :

1
2
int arr[4] = {1,3,5,7};
int *p = arr;

则arr[i]和*(p+i)是一致的。指针在进行算术运算时，移动的是i与指针指向数据类型字节长度的乘积。

p+i的实际地址为p向后移动sizeof(int)*i。

有符号 无符号 32位 64位
char unsigned char 1 1
short unsigned short 2 2
int unsigned int 4 4
long unsigned long 4 8
float 4 8
double 8 8

结构体

结构体是一个或多个变量的集合，变量可以是不同的类型。

1
2
3
4
struct point{
    int x;
    int y;
}

通常来说，结构体之间的传递也使用指针以提高效率。

1
2
3
struct point *p;
p->x = 1;
(*pp).y = 2;

有些情况下，为了更清晰的表明结构体的功能，通常会使用别名：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef unsigned int uint32_t;
typedef unsigned short uint16_t;

//如果后续需要用作链表，需要结构体名和别名
typedef struct Point
{
    int a;
    int b;
} point_t;

//如果不需要用作链表，可以直接省区结构体名
typedef struct
{
    int a;
    int b;
}point_t;

内存分配

  • 静态/全局内存

    静态声明的变量和全局变量使用这部分内存，程序开始运行时分配，程序结束才消失

  • 自动内存（栈）

    函数内局部变量，函数被调用时才创建

  • 动态内存（堆）

    根据需求写代码动态分配内存，需要程序主动释放。

数学基础

等差数列

假设有n项元素，其中a1至an中每两项之间的差值为d，则其前n项和 由于 an = a1 + (n − 1)d 所以前n项和也可表示为： 当a1与d均为1时:

累加和数列

累加和数列是在等差数列的基础上再度累加。即

  • b1 = S1 = a1
  • b2 = S2 = a1+a2
  • b3 = S3 = a1+a2+a3
  • …
  • bn = Sn = a1+a2+… + an = n(a1+an)/2

我们假设，数列b的前n项和为Tn，则有 展开后可得：

利用求和公式计算得：

整理可得：

合并同类项得： 我们假设，a1 和d均为1，则数列的前n项和为：

等比数列

数列{an}满足相邻项的比值为常数q，其通项式为 an = a1qn − 1 因此Sn的表达式为： Sn = a1 + a1q + a1q2 + ..a1qn − 1 两端同时成q以后减去上式： (q − 1)Sn = a1(qn − 1) 可得：

算法分析

  • 时间复杂度
  • 空间复杂度
  • 抽象数据类型ADT

数据结构与算法存在本质联系。在研究某一类型的数据结构时，总要涉及其上施加的运算，只有通过对定义运算的研究，才能真正理解数据结构的定义与作用。

时间复杂度

时间复杂度，也称渐进复杂度，T(n) = O(f(n))。随问题规模n增大，算法执行时间增长率和f(n)增长率成正比。

程序运行时间主要和执行每条语句的耗时、每条语句的执行频率有关。

语句执行要由源程序翻译为目标代码，目标代码再装配执行。每个语句执行一次需要的具体时间和机器的软/硬件环节有关。因此，算法分析并非是实际执行时间，而是针对算法中语句执行次数做出估计，得到算法执行时间的信息。

例如：

1
2
3
4
5
6
7
8
9
10
for(int i = 1; i<=n; i++) //循环n次，额外1次判断频度为n+1
{
    for(int j = 1; j<=n; j++)//同上
    {
        for(int k =1; k<=n; k++)//同上
        {
            c[i][j] += a[i][k]* b[k][j]; 
        }
    }
}

上方代码的f(n) = n^3，当n=1时，f(n) = O(1)。

有以下区分：

  • 最好时间复杂度：算法再最好情况下的时间复杂度
  • 最坏时间复杂度：算法在最坏情况下的时间复杂度
  • 平均时间复杂度：算法在所有可能的情况下，按输入实例等概率出现时的加权平均值

通常只讨论最坏时间复杂度。

常量阶

1
2
x++; //频度为1
s = 0; //频度为1

f(n) = 1+1;复杂度为O(1)。

1
2
3
4
5
for(int i=0; i<10000; i++)
{
    x++;
    s = 0;
}

算法执行时间不随问题的规模增长而增长，尽管执行了上万次，其仍然是常量。

线性阶

1
2
3
4
5
for(int i=0; i<n; i++)
{
	x++; //频度为n
    s=0; //频度为n
}

f(n)=(n+1)+n+n = 3n+1，即复杂度T(n) = O(n)。

平方阶

1
2
3
4
5
6
7
8
9
x++; //频度为n
s=0; //频度为n	
for(int i=0; i<=n; i++)
{
    for(int j=0; j<=n; j++)//频度为n	
    {
        y++;//频度为n	
    }
}

f(n)=(n+1)*n = n^2+n，即复杂度T(n) = O(n^2)。

立方阶

1
2
3
4
5
6
7
8
9
10
11
x=1;
for(int i=0; i<=n; i++)//频度为n
{
    for(int j=0; j<=i; j++) //频度为1+2+..+i	
    {
        for(int k =0; k<=j;k++ )//频度为1+(1+2)+(1+2+3)..+n*(n+1)/2
        {
        	y++;//频度为n*(n+1)*(n+2)/6	
        }
    }
}

f(n)=n*(n*(n+1)/2) = n^2+n，即复杂度T(n) = O(n^2)。

对数阶

1
2
3
4
5
for(int i=0; i<=n; i=i*2)
{
	x++; 
    s=0; 
}
次数 1 2 3 4 t
i 1 2 4 8
i 2^0 2^1 2^2 2^3 2^(t-1)

2^t-1 > n时循环退出，可得t>log2n + 1

即T(n) = O(log2n)，故也可以推导出倍数为其他值时的时间复杂度。

题目

1.例如：设n是描述问题规模的非负整数，下面程序片段的时间复杂度是();

1
2
3
x = 2;
while(x<n/2)
    x = 2*x;

实现复杂度的核心目的是找到语句的执行频次，也即什么时候退出循环，把每次x的值列出

次数 1 2 3 4 t
i 2^2 2^3 2^4 2^5 2^t+1

即2t+1 > n/2，可得t>log2n - 2，时间复杂度为O(log2n)。

2.再如：

1
2
3
4
5
6
int fun(int n)
{
    int i=0, sum =0;
    while(sum < n) sum += ++i;
    return i;
}

同样的思路，列i与sum的变化表格：

次数 1 2 3 4 t
i 1 2 3 4 t
sum 1 1+2 1+2+3 1+..+4 t(t+1)/2

即t(t+1)/2 >= n，推知t > n1/2，时间复杂度为O (n1/2)。

此处曾出现一处误解，即在t次将sum的值计算为n(n+1)/2 > n，从而得出复杂度为O(n)。根本原因在于将循环次数与问题规模混用一个n值。

3.再如：

1
2
3
4
5
6
7
8
int sum = 0;
for(int i=1; i<n; i*=2)
{
	for(int j=0; j<i; j++)
    {
        sum++;
    }
}
次数 1 2 3 4 t
i 2^0 2^1 2^2 2^3 2^(t-1)
内层次数 2^0 2^1 2^2 2^3 2^(t-1)

其中外层函数的执行次数为2^(t-1) >=n ，可得t>log2n + 1。

而内层每次执行执行的次数与外圈i相等，故最内层语句总执行频度为： 带入t=log2n得f(n) = 2n，故T(n) = O(n)；

空间复杂度

空间复杂度主要描述某个算法对应的程序想在计算机上执行，除去用来存储代码和输入数据的内存空间外，还需要额外的空间。

S(n) = O(f(n))。

抽象数据类型ADT

ADT是一种编程概念，用于定义数据类型及其操作，不涉及实现细节。优势是对外隐藏细节，对内隐藏接口。

在C中，ADT通常通过结构体和函数实现。

————————— End —————————

算法 + 数据结构 = 程序