数据结构和算法

启

数据结构

逻辑结构：集合，线性结构，树形结构，图状（网状）结构

存储结构：顺序储存，链式储存，索引储存，散列储存

算法

时间复杂度

计算时间复杂度主要看循环，加法就保留高阶的，乘法就相乘

空间复杂度

算法的空间复杂度主要看循环，数据类型的变量，递归，同样加法就保留高阶的，乘法就相乘

空间复杂度=递归调用的深度

线性表

定义：相同数据类型的n个数据元素的有限序列

表示：L=（a1,a2,a3….,an）

位序：从1开始，不是从0开始，除了第一个元素外，每个元素都有1个直接前驱，直接后续同理

操作：

顺序表

顺序表：使用顺序储存的方式实现的线性表（物理位置）

实现方式——静态分配（数组）,创建包含数组和数组当前长度的变量的结构体来实现

注意：如果不初始化为0，那么打印的时候可能会打印脏数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<iostream>
#include<string>
using namespace std;
#define MaxSize 10    //定义最大长度

typedef struct SqList { int data[MaxSize]; int length; };  //定义结构体

//初始化一个顺序表
void List(SqList& L) {
	for ( int i=0; MaxSize <i ; i++)
	{
		L.data[i] = 0; //将所以元素初始化为0
		L.length = 0;//初始化长度为0
	}
}

int main() {
	SqList L;//声明一个顺序表
	List(L); //初始化一个顺序表
    for (int i = 0; i < L.length; i++)
	{
	printf("data[%d]=%d\n", i, L.data[i]);
	}
	return 0;
}

动态分配

开辟新的空间，并将原来空间的数据复制过去

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
#include<string>
using namespace std;
#define MaxSize1 10    //定义最大长度

typedef struct SqList {
	int *data; //动态数组的地址
	int MaxSize; //最大长度
	int length;//当前长度
};  //定义结构体

//初始化一个顺序表
void List(SqList& L) {
	L.data = (int*)malloc(MaxSize1 * sizeof(int));//(int*)将返回值转化为int类型的指针，malloc申请所需要的连续的空间
	L.length = 0;//当前长度设置为0
	L.MaxSize = MaxSize1;//设置数组最大长度

}

//动态添加顺序表长度
void addList(SqList& L,int len) {
	int* p = L.data;//将顺序表数组的地址传给p
	L.data = (int*)malloc((L.MaxSize+len) * sizeof(int));//malloc申请用来最大空间加上需要新增加的连续的空间给顺序表的数组指针
	for (int i = 0; i < L.length; i++) {
		L.data[i] = p[i];//复制顺序表原来地址的数据给新地址的数组
	}
	L.MaxSize = L.MaxSize + len;//设置一下最大长度
	free(p);//释放掉原来地址

}

int main() {
	SqList L;//声明一个顺序表
	List(L); //初始化一个顺序表
	addList(L, 5);
	L.data[0] = 100;
	L.length = 1;
	for (int i = 0; i < L.length; i++)
	{
		printf("data[%d]=%d\n", i, L.data[i]);
	}
	return 0;
}