数据结构——第一章绪论小结

1.1什么是数据结构

数据结构包括（一）数据的逻辑结构（二）数据的存储结构。（三）运算

1.逻辑结构

（1）逻辑结构的表示

a.图表表示

b.?二元组表示如下B=（D，R）D是数据元素，R是数据元素之间的关系

(2)逻辑结构的类型

a.集合

b.线性结构

c.树形结构

d.图形结构

2.存储结构

（1）顺序存储结构

（2）链式存储结构

（3）索引存储结构

（4）哈希存储结构

接着是数据类型和抽象数据类型

数据类型主要涉及到内存空间的分配问题。

数据结构重点讲抽象数据类型类似结构体抽象结构体类型的基本描述格式如下

ADT抽象数据类型名

{
数据对象

数据关系

基本运算

}

1.2算法分析（重点时间复杂度和空间复杂度）

1时间复杂度

一个算法的执行时间可以由其中原操作的执行次数来计量

例如

#include <stdlib.h>
int main()
{
	int a[10][10];
	int b[10][10];
	int c[10][10];
	int i, j;
	for (i = 0; i < 10; i++)
		for (j = 0; j < 10; j++)
			c[i][j] = a[i][j] + b[i][j];
}

其原操作就是c[i][j] = a[i][j] + b[i][j];

其全部频度之和为T（n） = n+1+n（n+1）+n^2.

n+1是因为第一个for循环i会加到n+1次下面类似。

我们都是用简化的算法时间复杂度分析。

及在计算时间复杂度和空间复杂度时只取最高项且无关其系数系数直接取1即可。

故上述的时间复杂度为n^2

用O（n^2）表示

求和求积定理

接着就是非常重要的时间复杂度的求和求积定理

求和定理：对于多个循环不是嵌套而是并列的取其复杂度最大的那个

例如

#define  _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>
int main()
{
	int a[10][10];
	int b[10][10];
	int c[10][10];
	int sum = 0;
	int i, j;
	for (i = 0; i < 10; i++)
		for (j = 0; j < 10; j++)
			c[i][j] = a[i][j] + b[i][j];
	for (i = 0; i < 10; i++)
	{
		sum += a[1][i];

	}
}

上下两个for循环并列c的时间复杂度为O（n ^2）而sum的时间复杂度为O（n）故二者的时间复杂度取O（n^2）j

求积定理也是上述代码其实求积定理就是循环的嵌套像上述的原操作c第一个for执行n次里面嵌套的for循环也是n次故时间复杂度为两者的乘机为O（n*n）.

空间复杂度和时间复杂度类似就是改成创建这里就不过多描述。

如果对时间复杂度还不知道怎么算的话推荐取b站上学习一下找播放量高的（本蒟蒻就是这么过来的）

小结

上述其它概念只要了解即可，但要知道时间复杂度和空间复杂度怎么算，因为这是重点。

最后就是计算机大佬的名言数据结构+算法=程序。

?