第一章 绪论
1.1、基本概念
1.1.1、数据、数据元素、数据项、数据对象
数据(Data):是客观事物的符号表示,是所有能输入到计算机中并被计算机程序处理的符号的总称。
- 数值型数据:整数、实数等
- 非数值型数据:文字图像、图形声音等
数据元素(Data Element):是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。
数据项(Data Item):是组成数据元素的、有独立含义的、不可分割的最小单位。
数据对象(Data Object):是性质相同的数据元素的集合,是数据的一个子集。
1.1.2、数据结构
数据元素之间的关系称为结构
数据结构(Data Structure):是相互之间存在一种或多种特定关系的数据元素的集合。
数据结构包括以下三个方面的内容:
- 逻辑结构:数据元素之间的逻辑关系
- 物理结构(数据的存储结构):数据元素及其关系在计算机中的表示
- 运算和实现:即对数据元素可以施加的操作以及这些操作在相应存储结构上的实现。
逻辑结构与存储结构的关系:
- 存储结构是逻辑关系的映像与元素本身的映像
- 逻辑结构是数据结构的抽象,存储结构是数据结构的实现
- 两者综合起来建立了数据元素之间的结构关系
- 逻辑结构的种类:
- 集合结构:结构中的数据元素之间除了同属于一个集合的关系外,无任何其他关系
- 线性结构:结构中的元素之间存在着一对一的线性关系
- 树形结构:结构中的元素之间存在一对多的层次关系
- 图状结构或网状结构:结构中数据元素之间存在着多对多的任意关系
- 存储结构
- 顺序存储结构:用一组连续的存储单元依次存储数据元素,数据元素之间的逻辑关系由元素的存储位置来表示。
- 链式存储结构:用一组任意的存储单元存储数据元素,数据元素之间的逻辑关系用指针来表示。
- 索引存储结构:在存储点信息的同时,还建立附加的索引表,索引表中的项称为索引项,索引项一般是:(关键字, 地址)
- 散列存储结构:根据结点的关键字直接计算出该结点的存储地址
1.1.3、数据类型和抽象数据类型
数据类型(Data Type):是高级程序设计语言中的基本概念,是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称
C语言中的数据类型:
- 基本数据类型:
- int(4个字节)
- short(2个字节)
- long(4个字节)
- float(单精度,4个字节,精确的字数和位数6~7)
- double(双精度,8个字节,精确的数字和位数16-17位)
- char(1个字节)
- 数据存储大小:
char | short | int | long | long long | float | double | |
16位 | 1 | 2 | 2 | 4 | 8 | 4 | 8 |
32位 | 1 | 2 | 4 | 4 | 8 | 4 | 8 |
64位 | 1 | 2 | 4 | 8 | 8 | 4 | 8 |
- 数组、结构、共用体、枚举等构造数据类型
- 指针、空(void)类型以及typedef自己定义数据类型
抽象数据类型:是指一个数学模型以及定义在此数学模型上的一组操作。
- 由用户定义,从问题抽象出数据模型(逻辑结构)
- 还包括定义在数据模型上的一组抽象运算(相关操作)
- 不考虑计算机内的具体存储结构与运算的具体实现算法
抽象数据类型的形式定义:
抽象数据类型可用(D, S, P)三元组表示
- D是数据对象;
- S是D上的关系集;
- P是对D的基本操作集。
定义格式:
ADT抽象数据类型名 {
数据对象:<数据对象的定义>
数据关系:<数据关系的定义>
基本操作:<基本操作的定义>
}ADT抽象数据类型名
基本操作定义格式:
基本操作名(参数表)
初始条件:<初始条件描述>
操作结果:<操作结果描述>
基本操作参数:
- 赋值参数只为操作提供输入值
- 引用参数以"&"打头,可提供输入值外,还将返回操作结果
抽象数据类型(ADT)定义举例:
Circle的定义:
ADTCircle { 数据对象: D={r, x, y|r, x, y均为实数}; 数据关系: R={<r, x, y>|r是半径, <x, y>是圆心坐标} 基本操作: Circle(&C, r, x, y) 操作结果: 构造一个圆。doubleArea(C); 初始条件: 圆已存在操作结果: 计算面积doubleCircumference(C) 初始条件: 圆已存在操作结果: 计算周长 ...... } ADTCircle
复数的定义:
ADTComplex{ D= {r1, r2|r1, r2都是实数} S= {<r1, r2>|r1是实部, r2是虚部} assign(&C, v1, v2) 初始条件: 空的复数C已存在操作结果: 构造复数C, r1, r2分别被赋予以参数v1, v2的值destroy(&C) 初始条件: 复数C已存在操作结果: 复数C被销毁getReal(Z, &realPart) 初始条件: 复数已存在。操作结果: 用realPart返回复数Z的实部值getImag(Z, &imagPart) 初始条件: 复数已存在。操作结果: 用imagPart返回复数Z的虚部值Add(z1, z2, &sum) 初始条件: z1, z2是复数操作结果: sum返回两个复数z1,z2的和} ADTComplex
1.2、抽象数据类型的表示与实现
C语言实现复数:
typedefstruct { floatr; // 实部floati; // 虚部} Complex; voidAssign(Complex*A, floata, floatb); /* 赋值 */voidOutComplex(ComplexA); voidAdd(Complex*A, ComplexB,ComplexC); /* B+C */voidSub(Complex*A, ComplexB,ComplexC); /* B-C */voidMul(Complex*A, ComplexB,ComplexC); /* C*B */voidDiv(Complex*A, ComplexB,ComplexC); /* B/C */voidAssign(Complex*A, floatx, floaty) { // 构造一个复数A->x=r; A->y=i; } voidOutComplex(ComplexA) { // 输出复数if(A.v>0) printf("%f+%fi",A.r, A.v); elseprintf("%f%fi",A.r, A.v); } voidAdd(Complex*A, ComplexB,ComplexC) { // 求两个复数c1 和 c2的和sumA->r=B.r+C.r; A->i=B.i+C.i; } ComplexSub(Complex*A, ComplexB,ComplexC) { // 求两个复数c1 和 c2 的差differenceA->r=B.r-C.r; A->i=B.i-C.i; } voidMul(Complex*A, ComplexB,ComplexC) { A->r=B.r*C.r-B.i*C.i; A->v=B.i*C.r+B.r*C.i; } voidDev(Complex*A, ComplexB,ComplexC) { A->r=B.r*C.r-B.v*C.v; A->v= (B.i*C.r-B.r*C.i) / (C.r*C.r+C.i*C.i); } voidmain() { inti; Complexz, z1, z2; floata1, a2, b1, b2; while(i!=0) { printf("请分别输入复数z1的实部和虚部:"); scanf("%f%f", &a1, &b1); printf("请分别输入复数z2的实部和虚部:"); sacnf("%f%f", &a2, &b2); Assign(&z1, a1, b1); Assign(&z2, a2, b2); printf("复数在z1 = "); OutComplex(z1); printf("\n复数z2 = "); OutComplex(z2); Add(&Z, z1, z2); printf("\n复数z1 + z2 = "); OutComplex(z); Sub(&Z, z1, z2); printf("\n复数z1 - z2 = "); OutComplex(z); Mul(&Z, z1, z2); printf("\n复数z1 * z2 = "); OutComplex(z); Dev(&Z, z1, z2); printf("\n复数z1 / z2 = "); OutComplex(z); printf("按任意按键结束\n"); System("cls"); } }
java实现复数类:
packagestruct; importjava.math.BigDecimal; importjava.util.Objects; /*** @author java小豪* @version 1.0.0* @description 复数类*/publicclassComplex { /**实部*/privatedoublereal; /**虚部*/privatedoubleimag; /**get/set方法*/publicdoublegetReal() { returnreal; } publicdoublegetImag() { returnimag; } publicvoidsetReal(doublereal) { this.real=real; } publicvoidsetImag(doubleimag) { this.imag=imag; } publicComplex() {} publicComplex(doublereal, doubleimag) { this.real=real; this.imag=imag; } /**** 两个复数相加* @param other* @return 复数相加*/publicComplexadd(Complexother) { returnadd(this, other); } publicstaticComplexadd(Complexcomplex, Complexother) { doubler=complex.getReal() +other.getReal(); doublei=complex.getImag() +other.getImag(); returnnewComplex(r, i); } /*** 两个复数相减* @param other* @return 复数相减*/publicComplexsub(Complexother) { returnsub(this, other); } publicstaticComplexsub(Complexcomplex, Complexother) { doubler=complex.getReal() -other.getReal(); doublei=complex.getImag() -other.getImag(); returnnewComplex(r, i); } /*** 两复数相乘* @param other* @return 复数相乘*/publicComplexmul(Complexother) { returnmul(this, other); } publicstaticComplexmul(Complexcomplex, Complexother) { doubler=complex.getReal() *other.getReal() -complex.getImag() *other.getImag(); doublei=complex.getImag() *other.getReal() +complex.getReal() *other.getImag(); returnnewComplex(r, i); } publicComplexdiv(Complexother) { returndiv(this, other); } publicstaticComplexdiv(Complexcomplex, Complexother) { //如果为0,表示除以0, 产生除0异常。if(other.getReal() ==0&&other.getImag() ==0){ thrownewArithmeticException("除 0 异常"); } doubler=complex.getReal() *other.getReal() -complex.getImag() *other.getImag(); doublei= (complex.getImag() *other.getReal() -complex.getReal() *other.getImag()) / (complex.getReal() *complex.getReal() +complex.getImag() *complex.getImag()); returnnewComplex(r, i); } /*** 比较两个复数是否相等* @param o* @return true 或 false*/publicbooleanequals(Objecto) { if (this==o) { returntrue; } if (o==null||getClass() !=o.getClass()) { returnfalse; } Complexcomplex= (Complex) o; returnDouble.compare(complex.real, real) ==0&&Double.compare(complex.imag, imag) ==0; } publicinthashCode() { returnObjects.hash(real, imag); } publicStringtoString() { StringBuildersb=newStringBuilder(); //保留四位小数,并且去0.StringtempR=newBigDecimal(this.real). setScale(4, BigDecimal.ROUND_HALF_UP).stripTrailingZeros().toString(); sb.append(tempR); //如果虚部为正,需要添加一个+号。 为-时,不需要添加if(this.imag>0){ sb.append("+"); } //如果为0,返回实部if(this.imag==0){ returnsb.toString(); } //添加虚部, 复数后面的 i是固定的StringtempI=newBigDecimal(this.imag). setScale(4, BigDecimal.ROUND_HALF_UP).stripTrailingZeros().toString(); sb.append(tempI); sb.append("i"); returnsb.toString(); } } /*** @author java小豪* @version 1.0.0* @description 复数运算测试类*/publicclassComplexTest { publicstaticvoidmain(String[] args) { //1. 第一个复数, 实部为3,虚部为8Complexc1=newComplex(3, 8); //2. 第二个复数, 实部为3,虚部为-6Complexc2=newComplex(4, -9); //3. 第三个复数,实部为2,虚部为-7.Complexc3=newComplex(5, -9); //4. 第四个复数,看是否相同Complexc4=newComplex(23, 8); System.out.println("c1打印输出:"+c1.toString()); System.out.println(c1.toString() +"+"+c2.toString() +"="+Complex.add(c1, c2)); System.out.println(c1.toString() +"-"+c2.toString() +"="+Complex.sub(c1, c2)); System.out.println(c1.toString() +"*"+c2.toString() +"="+Complex.mul(c1, c2)); System.out.println(c1.toString() +"/"+c2.toString() +"="+Complex.div(c1, c2)); System.out.println(c1.toString()+"与"+c4.toString()+"是否相同:"+c1.equals(c4)); } }
1.3、算法和算法分析内容
1.3.1、算法
⚫️算法的定义:对特定问题求解方法和步骤的一种描述,他的指令的有限序列。
⚫️算法的描述:
- 自然语言:英语、中文
- 流程图:传统流程图、NS流程图
- 伪代码:类C语言
- 程序代码:JAVA、C语言
⚫️算法的特性:一个算法必须具备以下五个重要的特性
◾️有穷性:一个算法必须总是在执行有穷步之后结束,且每一步都在又有穷时间内完成
◾️确定性:对于每种情况下所应执行的操作,在算法中有确切的规定,不会产生二义性
◾️可行性:算法中所有的操作都可以通过以实现的基本操作运算执行有限次来实现
◾️输入:一个算法有零个或多个输入
◾️输出:一个算法有一个或多个输出
⚫️算法设计的要求:
◾️正确性
算法转化为程序后要注意:
1、程序中不含语法错误
2、程序对于机组输入数据能够得出满足要求的结果
3、程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果
4、程序对于一切合法的输入数据都能得出满足要求的结果
◾️可读性
◾️健壮性
◾️高效性
⚫️算法的效率:
- 时间效率:算法所耗费的时间。
- 该算法编制的程序在计算机上执行所消耗的时间来度量
- 度量方法:事后统计法、事前分析估算法
- 空间效率:算法执行过程中所耗费的存储空间。
算法运行的时间 = 每条语句频度 * 该语句执行一次所需的时间
n * n矩阵相乘的算法可描述为:
for (inti=1; i<=n; i++) // 频度n + 1次for (intj=1; j<=n; j++) { // 频度n * (n + 1)次c[i][j] =0; // 频度n * n次for (intk=0; k<n; k++) { // 频度n * n * (n + 1)次c[i][j] =c[i][j] +a[i][k] *b[k][j]; // 频度n * n * n次 } }
算法的渐进时间复杂度:T(n) = O(n3)
1.3.2、分析算法时间复杂度的基本方法
- 找出语句频度最大的那条语句作为基本语句
- 计算基本语句的频度得到问题规模n的某个函数
- 取其数量级用符号"O"表示
举例分析:
例一:
x=0; y=0; for (inti=1; i<=n; i++) x++; for (intj=1; j<=n; j++) for (intk=1; k<=n; k++) y++;
时间复杂度为:y++的频度为f(n) = n^2,所以时间复杂度为:T(n) = O(n^2)
例二:
voidexam(floatx[][], intm, intn) { floatsum[]; for (inti=0; i<m; i++) { sum[i] =0.0; for (intj=0; j<n; j++) { sum[i] +=x[i][j]; } } for (inti=0; i<m; i++) System.out.println("%d", sum[i]); }
时间复杂度:sum[i] += x[i][j]的频度为f(n) = m * n,时间复杂度为:T(n) = O(m * n)
例三:
for (inti=1; i<=n; i++) for (intj=1; j<=n; j++) { c[i][j] =0; for (intk=0; k<n; k++) { c[i][j] =c[i][j] +a[i][k] *b[k][j]; } }
时间复杂度:c[i][j] = c[i][j] + a[i][k] * b[k][j]的频度为f(n) = n^3,时间复杂度为:T(n) = O(n3)
例四:
inti=1, j=1, k=1; for (i=1; i<=n; i++) for (j=1; j<=i; j++) for (k=0; k<=j; k++) x=x+1;
时间复杂度为:x = x + 1 的频度为f(n) = \sum i * (i + 1) / 2,时间复杂度为: T(n) = O(n * (n + 1) * (n + 2) / 6) = O(n3)
例五:
i=1; while(i<=n) i=i*2;
时间复杂度为:i = i * 2 的频度为:f(n) = log2 n,时间复杂度为:T(n) = log2 n
1.3.3、算法时间复杂度的计算
- 最好时间复杂度:指在最好情况下,算法的时间复杂度
- 最坏时间复杂度:指在最坏情况下,算法的时间复杂度
- 平均时间复杂度:指在所有的输入实例在等概率出现的情况下,算法的期望运行时间
注意:对于复杂的算法,可以分成几个容易估算的部分,然后利用大O加法法则和乘法法则计算
- 加法法则:T(n) = T_1(n) + T_2(n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n)))
- 乘法法则:T(n) = T_1(n) * T_2(n) = O(f(n)) * O(g(n)) = O(f(n) * g(n))
复杂度T(n)按数量级递增顺序为:
越向右算法的复杂度越高
常数阶 | 对数阶 | 线性阶 | 线性对数阶 | 平方阶 | 立方阶 | K次方阶 | 指数阶 |
O(1) | O(logn) | O(n) | O(n * log n) | O(n2) | O(n3) | O(nk) | O(2n) |
1.3.4、算法的空间复杂度
◼️空间复杂度:算法所需存储空间的度量,记作:S(n) = O(f(n))其中n为问题的规模(或大小)
◼️算法要占据的空间:
- 算法本身要占据的空间,输入/输出,指令,常数,变量等
- 算法要使用的辅助空间
分析例题:
例一:将一维数组a中的n个数逆序存放到原数组中
for (inti=0; i<n; i++) { t=a[i]; a[i] =a[n-i-1]; a[n-i-1] =t; }
空间复杂度:仅借用临时变量t,与问题规模n大小无关,所以空间复杂度为O(1)
for (inti=0; i<n; i++) b[i] =a[n-i-1]; for (inti=0; i<n; i++) a[i] =b[i];
空间复杂度为:借用大小为n的辅助数组b,所以空间复杂度为O(n)