数据结构基础知识+结构体指针函数+时间复杂度

1、数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

2、数据：所有能输入到计算机中并被计算机程序所处理的符号的总称。

3、数据元素：数据的基本单位。

4、数据对象：性质相同的数据元素集合。

5、集合：数据元素相互之间的关系。

6、逻辑结构：描述数据之间的逻辑关系。

集合：结构中的数据元素之间除了同属于一个集合关系外，没有其他关系了，称为集合关系。

线性：一对一。

树：一对多。

图：多对多。

7、物理结构/存储结构：数据结构在计算机中的表示。最小的单位：bit，叫做位。

顺序结构：一串连续的地址。（定义一个数据即可，适合存储线性结构）

链式结构:链(link),存储单元并不是连续的紧密的联系在一起，而实靠指针来连接的，每个存储结构不仅有存储单元，还有下一个存储单 元的地址。

//c语言实现链式存储
typedef struct LNode{	//LNode意为节点，这个结构体里面存放着一个数据data和指向下一个节点的指针next
    int data;	//一个节点中存放的数据。
    struct LNode *next;	//指向下一个节点的指针
}LNode;	//名字，同上一个LNode
LNode *L;	//定义指针L。
//malloc函数：根据你的指定，动态的给你分配一个空间，并且给你返回这个空间的地址。
L = (LNode*)malloc(sizeof(LNode));	//为结构类型为LNode的节点分配一片空间,并把这片空间的地址存储在L内。
//光有L没有*，就代表L存储的是一片地址，加上了*才是取的地址中的值。
//sizeof()计算空间大小，sizef(LNode)计算LNode这个结构体空间的大小，以便进行分配。
//LNode*是进行了一次强制类型转化。
1 -> next = 2;	//通过指向结构体的一个指针来取结构体的分量不能用.，必须用箭头符号。
2 -> next = 3;	

1、数值类型：short,int,long,float,double。

2、指针类型：存放变量地址的变量类型。

p1 = &D			//&是去D的地址，然后p1的值就是&的地址了。又称p1指向D。
int *p1 = &A	//用int * 表示p1，p1就只能用来定义整形变量的地址（后面只能接整形变量地址），加了个int *类型就是说p1这个指针指向了A中的值(*p就相当于A)。
//&的意思是取地址符号，意思是去整形变量A的地址。
E = *p1			//用变量E来去指针p1指向的地址中的值。

#include	//输入输出功能
using namespace std;	//优化代码

int main()
{
	int a = 11;
	int b = 10;
	int *p = &a;	//指针p加了个*就能直接去变量a中拿值 
	cout<<"*p: "<<*p< 
输出结果:*p = 11
		a = 12
		p = 0
 
3、构造类型
 
数组的定义
 
int B[100];	//长度100,范围0~99。
int A[5] = {9,3,2,1,5};//数据的初始化。
 
结构体：不同变量类型结合在一起构成的变量。
 
 
 
为什么要用到结构体：比如要统计一个学校学生的所有信息，姓名，性别，学号，电话等等，定义的变量过于松散，需要整合一下，就用到了结构体，可以定义一个学生的结构体，使其内部包含这些信息。
 
 
//第一种定义方法:
typedef struct	//固定形式
{
    int a;
    float b;
    char c;
}student;		//student是结构体名
 
//第二种定义方法:结构体套结构体
typedef struct student	//固定形式
{
    int a;
    float b;
    char c;
    struct student *d;
}student;
 
//结构体的赋值
//类似于java定义一个学生类
#include
	//第一种定义方法:
	typedef struct //固定形式
	{
	    int number;
	    float age;
	    char name[10];
	}student;		//student是结构体名
int main(){
	student zhangsan = {10086,18.5,"zhangsan"};	//第一种赋值法
	
    printf("number: %d nage: %f nname: %s",zhangsan.number,zhangsan.age,zhangsan.name);
    return 0;
}
 
void:用来定义没有返回值的函数。
 
void F(){
    return ;	//返回值为空
}
 
三、函数 
int a(int b,int c){		//返回值类型，函数名，括号里是参数定义列表
    //函数体
}
 
//简单函数的写法和调用
#include
int add(int a,int b){
	return a+b; 
}
int main(){
	int result; 
	result = add(1,2);		//调用函数 
	printf("%dn",result);
	printf("%dn",add(10,20));	//调用函数 
	return 0;
}
 
定义引用型参数**(让外面的变量参与到函数的运算中来)**(c++写法)
 
#include
void getResult(int r){
		r++;
	}
void a(int &r){
	r++;
}
int main(){
	int result = 0;
	getResult(result);
	printf("result = %dn",result);	//result = 0 
	a(result);
	printf("result = %dn",result);	//result = 1
	return 0;
}

 
输出结果：
result = 0
result = 1
 
定义指针型变量的引用**（让外面的指针型变量参与到函数体的运算中去）**(c++写法)
 
#include

void getResult(int *&p){	 
	int q = 10;
	p = &q;	//3、相当于指针a指向p的地址 
}
int main(){
	int* a = NULL;	//1、定义一个空指针a 
	getResult(a);	//2、把a传入函数getResult中，因为有&的存在，a就相当于p了。 
	printf("%d",*a);//4、将指针a加个*号，就是取q所在地址中的值，输出10。 
	return 0;
}
 
输出结果:10
 
纯粹的c语言下定义引用型参数的函数写法
 
#include

void getResult(int *r){	//这里的*也不再是指针了，而是为了外部变量能进入函数体，必须添加的符号。 
	++(*r);	//相当于外部变量result的变化，至于(*)，可以理解成固定形式。 
}

int main(){
	int result = 0;
	getResult(&result); //加了&就可以进入函数体内来实现result自身的变化了。 
	printf("%d",result);	//输出结果:1 
}
 
输出结果:1
 
纯粹的c语言下定义引用形变量来引用指针型变量的写法（函数体外的指针型变量可以直接进入函数体进行运算）
 
#include
void getResult(int **p){	//2、第一个*是让外部变量进入函数体的，就是a就变成了p，而第二个*是指针。 
	int q = 10;
	*p = &q;	//3、*(拿走)p = &q(q的地址)，中的值 
}
int main(){
	int* a = NULL;
	getResult(&a);	//1、想把a传进函数体就得在a前面加一个&。 
	printf("%d",*a);	//10 
}
 
输出结果:10
 
四、时间复杂度和空间复杂度 
1、时间复杂度：随着时间的增长，在某个时间之后，程序执行需要耗费的时间或许有一个上限或一个下限，上限称为cf(N)，下限称为cg(N)，时间复杂度T(N),处于二者之间。（大O表示法，通常用cf(N)。就是把程序耗时T(N)当成最耗时的cf(N)来计算。
 
 
时间复杂度
 
 
 
时间复杂度的运算：循环语句就看内部执行了几次再乘个n，两层循环就再乘个n，几层循环乘几个n，要是时间复杂度是n²＋n那么就取n方，谁大取谁。