数据结构和算法

启

数据结构

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

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

算法

时间复杂度

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

空间复杂度

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

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

线性表

定义：相同数据类型的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;
}

添加数据

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

//内容插入顺序表
bool add_content(SqList& L, int i, int e) {
	//判断插入的位置是否合法形成顺序表
	if (i>=L.length+1 || i < 1) {
		return false;
	};
	//判断插入的位置是超过最大值
	if (i == L.MaxSize) {
		return false;
	};
	//循环将插入位置后面的向后移动一位
	for (int j =L.length;i<=j; j--) 
		L.data[j] = L.data[j-1];
	L.data[i - 1] = e;
	L.length++;
	return true;
	
}

int main() {
	SqList L;//声明一个顺序表
	List(L); //初始化一个顺序表
	addList(L, 5);
	L.data[0] = 100;
	L.data[1] = 200;
	L.data[2] = 300;
	L.data[3] = 400;
	L.data[4] = 500;
	L.length = 5;
	add_content(L, 1, 1);
	add_content(L, 6, 2);
	add_content(L, 6, 3);
	add_content(L, 6, 4);
	add_content(L, 6, 5);
	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
//删除顺序表内容
bool deleteList(SqList& L, int i, int  &e) {
	//判断删除的位置是否合法形成顺序表
	if (i >= L.length || i < 1) {
		return false;
	};
	//判断删除的位置是超过最大值
	if (i == L.MaxSize) {
		return false;
	};
	//将删除的赋值给e带回去，循环将删除位置后面的向前移动一位
	e = L.data[i - 1];
	//将后一位的值覆盖要删掉的值，并循环
	for (int j = i; j < L.length;j++)
	{
		L.data[j - 1] = L.data[j];
	}
	
	L.length--;
	return true;

专升本

绪论

考点：

  1. 数据结构相关概念和术语
  2. 数据结构的三要素：逻辑结构，物理结构，数据运算
  3. 时间和空间复杂度的计算和分析

数据结构基本概念

  • 数据：是信息的载体，能被计算机识别和处理

  • 数据元素：是数据的基本单位，数据项是构成数据元素的最小单位：如学生信息是数据元素，由学号，姓名等数据项组成

  • 数据对象：是相同性质的数据元素组成，是数据的一个子集，如：全班学生

  • 数据类型：

    原子类型：值不可再分的数据类型

    结构类型：值可以再分的数据类型

    抽象数据类型：描述数据的逻辑结构和抽象运算，常用（数据对象，数据关系，基本操作集）这样的三元组表示，构成一个完整的数据结构定义

  • 数据结构：

    1. 逻辑结构：线性结构，非线性结构（集合，树，网）

    2. 物理（储存）结构：数据元素和关系，是用计算机语言实现的逻辑结构

      顺序储存：内存是是连续的（顺序表，循环队列）

      链式储存：内存上不一定连续，但是可以指向下一个的地址（单链表)

      索引储存：有索引表，通过key索引到内容的地址

      散列储存：通过函数计算出地址（哈希表）

    3. 数据运算

顺序表

数组