24.2.19数据结构基本概念术语（王卓）|学习笔记

一、数据类型和抽象数据类型

1、概念

参数列表：

比如power（x，y）；这个函数中，x，y就是参数列表

2、定义数据类型举例子：

带返回值的有&

3、概念小结：

用C语言真正实现抽象函数的定义：

#include<stdio.h>
typedef struct {
	/*实部*/
	float realpart;
	/*虚部*/
	float imagpart;
}Complex;
/*函数声明*/
void assign(Complex* A, float real, float imag);//赋值功能的函数
void add(Complex* A, float real, float imag);//想加
//void minus(Complex* A, float real, float imag);//想减
//void multiply(Complex* A, float real, float imag);//*
//void divide(Complex* A, float real, float imag);// \


int main() {
//函数引用等等
}
void assign(Complex* A, float real, float imag) {
	A->realpart = real;
	A->imagpart = imag;
}
void add(Complex* c, Complex A, Complex B) {
	c->realpart = A.realpart + B.realpart;
	//这行代码将A和B的实部相加，并将结果赋给c所指向的复数的实部。
	c->imagpart = A.imagpart + B.imagpart;
}
......

->的意思:

在C语言中，-> 是用来访问结构体指针的成员的操作符。当你有一个结构体的指针时，你可以使用 -> 来访问这个结构体的成员变量。

举个例子，如果你有一个结构体 struct Person 并且有一个指向这个结构体的指针 struct Person *person;，你可以通过 person->name 来访问 person 指向的 Person 结构体的 name 成员变量。

插入知识点typedef：

在C语言中，typedef关键字用于给数据类型定义一个新的名字，这样做可以让我们使用更简洁或更具描述性的名称来引用特定的数据类型。

1、是typedef的基本使用方法：

typedef 旧类型 新类型名;

这里的“旧类型”可以是任何有效的C数据类型，比如int、float、char等，或者是一个结构体、指针、数组等复合类型。“新类型名”是你想给这个类型起的新名字。例如：你想给int类型起一个新的名字MyInt，你可以这样写：

typedef int MyInt;

这样，你就可以在代码中使用MyInt来代替int了，比如

MyInt myVariable;

这行代码声明了一个int类型的变量myVariable。

2、typedef还可以用来定义复杂的数据类型，比如结构体：

typedef struct {
    int x;
    int y;
} Point;

这样，你就可以用Point来代替struct { int x; int y; }了，比如：

Point p;

这行代码声明了一个结构体类型的变量p。

3、typedef还可以用来定义指向函数的指针类型

这在定义回调函数或者函数指针时非常有用：

typedef void (*CallbackFunction)(int);

这里定义了一个名为CallbackFunction的新类型，它表示一个接受一个int参数并返回void的函数指针。

使用typedef可以让代码更加模块化，并且可以减少由于类型名称错误导致的错误。不过，过度使用typedef也可能会使代码变得难以理解，所以应该适度使用。

二、算法与算法分析

1、定义：

解决问题的方法和步骤。

2、算法的描述：

3、算法和程序关系

​​​​​

4、算法特性

5、算法设计的要求

 （1）正确性：（2）可读性：人理解，易于调试；

（3）健壮性：

（4）高效性：时间和空间

什么是好的算法？？算法分析

1、首先要具备正确性，然后是健壮性，可读性，都满足的情况下主要考虑算法的效率

算法时间效率度量：

（即为在计算机上执行所消耗的时间）有：1、事前分析（更多）2、事后分析，选择事前分析。

事前分析：

可以去掉执行一次需要的时间：

算渐进时间复杂度举例子：

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

1、步骤：

时间复杂度是由嵌套最深的语句的频度决定的，所以找嵌套层次最多的，一般就是执行次数做多的。{直接找就行了}

 2、定理1：

忽略所有低次幂项和最高次幂系数，体现出增长率的含义

未完待续。。。24.2.20

3、计算时间复杂度**例题：（考研or不会）

4、用哪一个时间复杂度：

平均时间复杂度：O(n/2);

总结

这张PPT的目的是说明：时间复杂度有多重情况

总结：这张ppt说明了，一个程序可能有这三种时间复杂度，一般考虑最坏时间复杂度

5、复杂的算法：拆分->加法法则or乘法法则

算法时间效率的比较：

四、渐进空间复杂度

1、定义：

2、分析例题

四、总结-设计好的算法的过程：