数据结构_绪论

1.数据结构的研究内容

研究数据的特性和数据之间的关系

 用计算机解决一个问题的步骤

1.具体问题抽象成数学模型

实质:

分析问题--->提取操作对象--->找出操作对象之间的关系(数据结构)--->用数学语言描述

操作对象+对象之间的关系

2.设计算法

3.编程,调试,运行

早期计算机主要用于计算数值计算(数据对象关系简单,但计算复杂)

例:

求解梁架结构的应力(线性方程组)

预报人口增长的情况(微分方程)

当今

计算more often 的用于非数值计算

例1,

学生表

操作对象:每位学生的信息(学号,姓名,性别等)

操作算法:增删改查

关系:线性关系

数据结构:线性表/线性数据结构

例2:

人机对弈问题

操作对象:各种器具状态,即描述棋盘的格局信息

算法:走棋,即选择一种策略使棋局状态发生变化

关系:非线性关系,树

数据结构:树形结构

例3:

地图最短路径问题

操作对象:各个地点

算法:方向选择

关系,非线性关系,图

数据结构:图形结构

综上

以上都是一些非数值计算问题

描述非数值计算问题的数学模型不是数学方程,而是表,树,图之类的具有逻辑关系的数据

数据结构是一门研究非数值计算的程序设计中计算机的操作对象以及他们之间的关系和操作的学科额

数据结构的基本概念和基本术语

数据

是能输入计算机且能被计算机处理的各种符号的集合

(信息的载体

对客观事物符号化的表示

能够被计算机识别存储和加工

)

包括

数值型的数据:整数,实数

非数值型的数据:文字,图像,声音等

数据元素:

数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理

元素/记录/结点/顶点/(如棋盘的格局)

数据项

构成数据元素的不可分割的最小单位

数据>数据元素>数据项

例

学生表>个人记录>学号/姓名

数据对象

是性质相同的数据元素的集合,是数据的一个子集.

例如

整数数据对象 集合N={0,(-/+)1,(-/+)2,(-/+)3...}

字母字符数据对象是集合C={A,B,C...Z}

学生表也可以看做一个数据对象

数据元素与数据对象

数据元素是数据的基本单位 是集合的个体

数据对象是性质相同的数据元素的集合 是集合的子集

数据结构

数据元素不是孤立存在的,他们之间存在着某种关系,数据元素相互之间的关系称之为结构

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

也可以说,数据结构是带结构的数据元素的集合

包括三个内容

1.数据元素之间的逻辑关系,也成为逻辑结构

2.数据元素及其关系在计算机内存中的表示(又称为映像),称为数据的物理结构或数据的存储结构

3.数据的运算和实现,即对数据元素可以施加的操作以及这些操作在相应的存储结构上的实现

逻辑结构

描述数据元素之间的逻辑关系

与数据的存储无关,独立于计算机

是从具体问题抽象出来的数学模型

存储结构

数据元素及其关系在计算机存储器中的结构(存储方式)

是数据结构在计算机中的表示

逻辑结构与数据结构之间的关系

存储脚骨是逻辑关系的映像与元素元素本身的映像

逻辑结构是数据结构的抽象,存储结构是数据结构的实现

两种综合起来建立了数据元素之间的结构关系

逻辑结构分类

线性结构

有且仅有一个开始和一个终端结点,每个结点只有一个直接前趋和直接后继

例:线性表,栈,队列,串

非线性结构

一个节点可能有多个直接前趋和直接后继

例如:树,图

第二种分类

集合机构: 同属一个集合

线性结构 一对一

树形结构 一对多

图状结构/网状结构 多对多

存储结构

顺序存储结构

用一组连续的存储单元依次存储数据元素,数据元素之间的逻辑关系由元素的存储位置来表示

c语言中用数组来实现顺序存储结构

例: int numbers[5] = {1, 2, 3, 4, 5};

链式存储结构

用一组任意的存储单元存储数据元素,数据之间的逻辑关系用指针来表示

c语言中用指针来实现链式存储结构

链表

索引存储结构

在存储结点信息的同时,还建立附加的索引表

散列存储结构

根据结点的关键字直接结算出该结点的存储地址

数据类型和抽象数据类型

在使用高级程序设计语言编写程序时,必须对程序中出现的每个变量,常量或表达式,明确说明他们所属的数据类型

例如:

c语言中,int char,float, double 等基本数据类型

数组,结构,共用体,枚举等构造数据类型

还有指针,空(void)类型

用户也可以typedef自己定义数据类型

一些最基本数据结构可以用数据类型来实现,如数组,字符串等

而另一些常用的数据结构,如栈,队列,树,图等,不能直接用数据类型来表示

高级语言中的数据类型明显地或隐含地规定了在程序执行期间变量和表达的所有可能的取值范围,以及在这些数值范围上所允许进行的操作

c语言中定义i 为int类型,就表示i的范围是整数, 这个整数可以进行+-*\%等操作

数据类型的作用

约束变量或常量的取值范围

约束变量或常量的操作 

数据类型

定义:数据类型是一组性质相同的值的集合,以及定义于这个值集合上的一组操作的总称

数据类型=值的集合+值集合上的一组操作

抽象数据类型

是指一个数学模型以及定义在此数学模型上的一组操作

由用户定义,从问题抽象出数据模型(逻辑结构)

还包括定义在数据模型上的一组抽象运算(相关操作)

不考虑计算机内具体的存储结构,与运算的具体实现算法

抽象数据类型的形式定义

抽象数据类型可用(D,S,P)三元组表示

其中D是数据对象,S是D上的关系集,P是对D的基本操作

定义格式

ADT 抽象数据类型名{

        数据对象:<数据对象的定义>

        数据关系:<数据关系的定义>

        基本操作:<基本操作的定义>

} ADT 抽象数据类型名

基本操作定义格式

基本操作名(参数表)

初始条件:<初始条件描述>

操作结果:<操作结构描述>

参数表

赋值操作:只为操作提供输入值.

引用参数 以& 打头,除可提供输入值外,还讲返回操作结构

scak(&G,n)

初始条件 

描述操作执行之前数据结构和参数应满足的条件,若不满足,则操作失败,并返回相应出错信息.若初始条件为空,则省略

操作结果

说明操作完成之后,数据结构的变化状况和应返回的结果

圆 抽象数据类型

ADT Circle {

        数据对象:D={r,x,y| r,x,y均为实数}

        数据关系:R={<r,x,y>|r是半径,<x,y>是圆心坐标}

        基本操作:

        Circle(&C,r,x,y)

                操作结果:构造一个圆

        double Area(C)

                初始条件:圆已经存在

                操作结果:计算面积

        double Cirumference(C)

                初始条件:圆已经存在

                操作结构:计算周长

}ADT Circle

ADT Complex{

        D={r1,r2|r1,r2都是实数}

        S={<r1,r2>|r1是实部,r2是虚部}

        assign(&C,v1,v2)

                初始条件:空的复数C已经存在

                操作结果:构造复数C,r1,r2分别被赋值参数v1,v2的值

        destroy(&C)

                初始条件:复数C已经存在

                操作结果:复数C被销毁

}ADT complex

小结

数据-(个体)->数据元素 -(性质相同的构成集合)->数据对象-(数据元素之间的关系)->

数据结构->

映像到内存->存储结构(顺序/链式/索引/散列)

逻辑模型->逻辑结构(集合/线性/树形/图状)

操作-> 抽象数据类型(数据对象/数据关系/基本操作)

抽象数据类型的实现

抽象数据类型可以通过固有的数据类型来表示和实现

例

c语言实现复数 抽象数据类型

定义结构体,声明操作函数

#pragma once
typedef struct {float realpart;float imagpart;
}Complex;
void assign(Complex* c, float real, float image);
void add(Complex* c, Complex A, Complex B);
void subtract(Complex* c, Complex A, Complex B);
void multiply(Complex* c, Complex A, Complex B);
void divide(Complex* c, Complex A, Complex B);
void print_complex(Complex A);

定义函数

#include "demo2.h"
#include<stdio.h>
void assign(Complex* c, float real, float image) {c->realpart = real;c->imagpart = image;
};
void add(Complex* c, Complex A, Complex B) {c->realpart = A.realpart + B.realpart;c->imagpart = A.imagpart + B.imagpart;
};
void subtract(Complex* c, Complex A, Complex B) {c->imagpart = A.imagpart - B.imagpart;c->realpart = A.realpart - A.realpart;
}
void multiply(Complex* c, Complex A, Complex B) {c->realpart = A.realpart * B.realpart - A.imagpart * B.imagpart;c->imagpart = A.realpart * B.imagpart + A.imagpart * B.realpart;
}
void divide(Complex* c, Complex A, Complex B) {float denominator = B.realpart * B.realpart + B.imagpart * B.imagpart;c->realpart = (A.realpart * B.realpart + A.imagpart * B.imagpart) / denominator;c->imagpart = (A.imagpart * B.realpart - A.realpart * B.imagpart)/ denominator;}
void print_complex(Complex A) {printf("%.2f + %.2fi\n", A.realpart, A.imagpart);}

实现复数计算

[(8+6i)(4+3i)]/[(8+6i)+(4+3i)]

#include<stdio.h>
#include "demo2.h"int main() {Complex a1;Complex* a=&a1;assign(a, 8, 6);print_complex(*a);Complex b1;Complex* b=&b1;assign(b, 4, 3);Complex d1;Complex* d=&d1;multiply(d, *a, *b);Complex e1;Complex* e=&e1;add(e, *a, *b);Complex f1;Complex* f=&f1;divide(f, *d, *e);print_complex(*f);}

                                          算法和算法分析

算法的定义

对特定问题求解方法和步骤的一种描述,他是指令的有限序列,其中每个指令表述一个或多个操作

简而言之,算法就是解决问题的方法和步骤

算法的描述

例:求解一元二次方程的根

自然语言:英语,中文

1.输入方程的系数a,b,c

2.判断a是否等于0,如果等于,提示不是一元二次方程,反之,执行下一步

3.计算d = b^2 -4ac

4.判断d 如果d等于0,计算并输出两个相等的实根,小于零没有实根,大于0,输出两个实根

5.结束

流程图:传统流程图,NS流程图

略

伪代码:类语言:类C语言

程序代码:C语言程序,java 程序,python

算法与程序

算法是解决问题的一种方法和过程,考虑如何将输入转换成输出,一个问题可以有多种算法.

程序是用某种程序设计语言对算法的具体实现

程序=数据结构+算法

数据结构通过算法实现操作

算法根据数据结构设计程序

算法的特性:

有穷性:一个算法必须总是在执行有穷步之后结束,且在有穷时间内完成

确定性:算法种每一条指令必须有确切的含义,没有二义性(相同的输入只能得到相同的输出)

可行性:算法是可执行的,算法描述的操作可以通过已经实现的基本操作执行有限次来实现

输入:一个算法有零个或多个输入

输出:一个算法有一个或多个输出

算法设计的要求

正确性

程序对于精心选择的,典型,苛刻且带有刁难性的几组输入数据能够得出满足要求的结果(就认为算法是正确的)

可读性

易于阅读和交流,晦涩难懂的算法容易隐藏错误,不易调试

健壮性(鲁棒性)

当输入非法数据时,算法恰当的做出反应或进行相应处理,而不是产生莫名奇妙的输出结果

处理出错的方法,不应是中断程序的执行,而应该是返回表示错误或错误性质的值,以便再更高的抽象层次进行处理

高效性

要求少的时间,少的存储要求

一个好的算法首先要具备正确性,健壮性,可读性,在这些方面都满足的情况下,主要考虑算法的效率,通过算法的效率评判算法的优劣程度

算法效率的两个方面:

时间效率:算法耗费的时间

空间效率:算法执行过程中耗费的存储空间

时间效率和空间效率有时候是矛盾的

算法时间效率的度量

算法时间效率可以用依据该算法编制的程序在计算机上执行所消耗的时间来度量

两种度量方法

事后统计

将算法实现,测算其时间和空间开销

缺点:编写程序实现算法将花费较多的时间和精力,所得实验结构依赖于计算机的软硬件等环境因素,掩盖算法本身的优劣

事前分析

对算法所消耗资源的一种估算方法

事前分析方法

算法运行时间=一个简单操作所需要的时间  *  简单操作次数

也即算法中每条语句的执行时间之和

算法运行时间=Σ每一条语句的执行次数(语句频度) * 该语句执行一次所需要的时间

每条语句执行一次所需的时间一般是由机器决定的和算法无关

可以可以考虑假设执行每条语句所需要的时间均为单位时间,对算法的运行时间就变成讨论该算法中所有语句的执行次数,即频度之和

这就可以独立于不同机器的软硬件环境来分析算法的时间性能了

例:

在python中实现两个N阶矩阵相乘

def func(n, a, b):"""两个n阶矩阵相乘,返回计算结果:param n: 矩阵的阶数:param a: 矩阵a:param b: 矩阵b:return:"""c = [[0 for _ in range(n)] for _ in range(n)]  # 初始化结果矩阵Cfor i in range(n):for j in range(len(b)):for k in range(n):c[i][j] += a[i][k] * b[k][j]  # 计算C的元素值return ca = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]  # 矩阵A
b = [[10, 11, 12], [13, 14, 15], [16, 17, 18]]  # 矩阵B
print(func(3, a, b))

类C语言

#include <stdio.h>void matrix_multiply(int n, int a[n][n], int b[n][n], int c[n][n]) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {c[i][j] = 0;for (int k = 0; k < n; k++) {c[i][j] += a[i][k] * b[k][j];}}}
}void print_matrix(int n, int matrix[n][n]) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {printf("%d ", matrix[i][j]);}printf("\n");}
}int main() {int n = 3;int a[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};int b[3][3] = {{10, 11, 12}, {13, 14, 15}, {16, 17, 18}};int c[3][3];matrix_multiply(n, a, b, c);print_matrix(n, c);return 0;
}

我们把算法所耗费的时间定义为该算法中每条语句的频度之和,则上述算法的时间消耗T(n)为

T(n)= 2n³ + 3n² + 2n +1

为了便于比较不同算法的时间效率,我们仅比较他们的数量级

例如两个不同的算法,时间消耗分别是:

T(n)=10n²  与Tn(n)= fn³

若有某个辅助函数f(n),使得当n趋于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数记作T(n)=O(f(n))

称O(f(n))为算法的渐进时间复杂度(O是数量级的符号),简称时间复杂度.

对于求解矩阵相乘问题,算法耗费时间:

        T(n)= 2n³ + 3n² + 2n +1

n趋于无穷大,T(n)/ n³--->2,则T(n)与n³同阶/同数量级,记作

                                T(n)=O(n³)

这就是求解矩阵相乘问题的算法的渐进时间复杂度

一般情况下,不必计算所有操作的执行次数,而只考虑算法中基本操作执行次数,它是问题规模n的某个函数,用T(n)表示

算法中基本语句重复执行的次数是问题规模n的某个函数f(n),算法的时间量度记作T(n)=O(f(n))

它表示随着n的增大,算法执行的时间的增长率和f(n)的增长率相同,称渐进时间复杂度

基本语句

算法中重复执行次数和算法的执行时间成正比的语句

对算法运行时间的贡献最大

执行次数最多

问题规模n

n越大算法的执行时间越长

排序:n为记录数

juzheng:n为矩阵的阶数

多项式:n为多项式的项数

集合:n为元素个数

树,n为树的结点个数

图:n为图的顶点数或边数

计算定理

分析算法时间复杂度的基本方法

1.找出语句频度最大的那条语句作为基本语句

2.计算基本语句的频度得到问题规模n的某个函数f(n)

3.取其数量级用符号O表示

例1

类c

x = 0;
y = 0;
for (int k = 0; k < n; k++)x++;
for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)y++;

f(n)= n(n+1)  第6行代码执行次数

T(n)=O(n²)

python

x = 0
y = 0
n = int(input("请输入循环的次数:"))
for k in range(0, n):x += 1
for i in range(0, n):for j in range(0, n):y += 1
print(x, y)

T(n)=O(n²)

例2

类c

void exam(float x[][], int m, int n) {float sum[];for (int i = 0; i < m; i++) {sum[i] = 0.0;for (int j = 0; j < n; j++)sum[i] += x[i][j];}for (i = 0; i < m; i++)cout << i << ":" << sum[i] << endl;
}

python实现

def exam(x, m, n):sum_l = [0 for i in range(m)]for i in range(m):for j in range(n):sum_l[i] += x[i][j]for i in range(m):print(f"{i}:{sum_l[i]}")x = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
m, n = len(x), len(x[0])
exam(x, m, n)

f()= m*n

T(n) = f(m*b)

时间复杂度是由嵌套最深语句的频度决定的

例3

矩阵相乘

类c

for(i=1;i<=n;i++)for (j = 1; j <= n; j++) {c[i][i] = 0for (k = 1; k <= n; k++)c[i][j] = c[i][j] + a[i][k] * b[k][j];
}

python

def func(n, a, b):"""两个n阶矩阵相乘,返回计算结果:param n: 矩阵的阶数:param a: 矩阵a:param b: 矩阵b:return:"""c = [[0 for _ in range(n)] for _ in range(n)]  # 初始化结果矩阵Cfor i in range(n):for j in range(len(b)):for k in range(n):c[i][j] += a[i][k] * b[k][j]  # 计算C的元素值return ca = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]  # 矩阵A
b = [[10, 11, 12], [13, 14, 15], [16, 17, 18]]  # 矩阵B
print(func(3, a, b))

算法中的基本操作语句

c[i][j] += a[i][k] * b[k][j]  # 计算C的元素值

T(n)=O(n³)

例4

类c

for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;

python

def func(n):  # 定义函数 func，接受一个参数 nglobal x  # 声明全局变量 xfor i in range(len(n)):  # 遍历 n 的第一层for j in range(len(n[i])):  # 遍历 n 的第二层for k in range(len(n[i][j])):  # 遍历 n 的第三层x += 1  # x 加 1n = [[[6, 4, 2], [1, 2]], [[23, 4]]]  # 定义一个嵌套列表 n
x = 0  # 初始化 x 为 0
func(n)  # 调用函数 func，传入参数 n
print(x)  # 打印 x 的值

T(n)=f(n³)

例5

类c

i = 1;
while(i<=n)i=i*2

python

def func(n):i = 1num = 0while i <= n:i = i * 2num +=1print(f"基本语句执行次数:{num}")
func(12)

做题的关键:找出次数x与n的关系

循环一次 i=1*2 =2

循环两次i=1*2*2 =

循环3次i=1*2*2*2 = 

归纳法可知循x次 i=

有循环条件可知:i<=n,<=n,

当毕业的钟声悠然回荡，青春的乐章轻盈飘扬，愿你的未来如盛开的百花，人生旅程如诗篇般韵味深长。每一阵钟响都镌刻着成就，每一段旋律都寄托着梦想，愿你在前行的道路上，繁花满径，诗意盎然。