数据结构第一章导图

数据结构思维导图-一.数据结构的基本概念 数据结构定义:数据结构是一种存储和组织数据的方式,以便于访问和修改。数据结构包括数据的逻辑结构、数据的存储结构以及数据的运算,

第一章：绪论（一切数据结构的基础）

1.1太简单啦

1.2.1数据结构的基础的几个元素

数据：简单来说就是能被计算机所能读到的符号总称，能够被我们所操作的符号。

数据元素：是较为完整的描述个体，假设三种数据才能描述个体那么这个总的个体被称之为数据元素。

数据项：先有数据元素这个概念才有数据项，其实是针对数据元素所言，对组成完整个体的数据元素其下的组成数据来说我们称为数据项。

数据对象：这个对象啊是指性质相同的数据元素的集合，数据元素又是指完整的个体哦。例如整数的数据对象：1，-1，2，-2还有字符的数据对象。这个概念是指性质相同的数据元素的集合

1.2.2 数据结构

数据结构：是相互之间存在一种或多种特点关系的数据元素的集合，针对完整个体的数据元素来说，只有存在特点关系的多个数据元素才有进行算法的必要。这就是数据结构！

1.逻辑结构：这种关系是独立于计算机之外，与数据怎样存储无关，是针对怎么解决问题本身提出的结构称之为逻辑结构。有两个要素：一是数据元素，二是关系。

1.集合结构：数据元素之间除了属于同一元素之外再没其他关系，类似于数据对象，例如一名学生是否为班级成员，只需将班级看成集合结构即可。

2.线性结构：犹如一条线一样，前后有关系即一一对应的关系，例如学生按照时间顺序进行排列，这个时间就是我们针对的关键点，而时间有先后顺序也即线性结构。

3.树结构：也就是针对一对多的关系的数据元素，例如：班级中班长管理多名组长，组长管理多名同学一样。

图与网：也就是多对多的关系的数据元素。

其中集合、树与图属于非线性结构，即线性结构是一对一的关系

2.存储结构：顾名思义就是对计算机存储结构的方式来定义的关系，有两种存储方式1、顺序存储结构 2、链式存储结构

1.顺序存储结构：是指元素在存储器也即地址的相对位置来确定数据元素之间的关系，通常借助数组来描述。例如数据从0号地址开始往后高地址100存储.这种以地址高低来存储的结构称为顺序存储结构，这种需要开辟一整块存储空间用来存储数据元素。

2.链式存储结构：链式存储结构不用连续开辟空间，为了表示结点的关系需要有一个引导的指针字段指向下一个数据元素的存储的地址。

1.2.3 数据类型和抽象数据类型

1.数据类型：简单来说就是整型，字符型，浮点型等等的数据类型。

2.抽象数据类型：抽象就是抽取实际问题的本质，数据结构归根结底是解决问题。一般由用户定义的，具体包括三部分：数据对象、数据对象关系上的集合、数据对象基本操作的集合。

1.3 抽象数据类型的表示与实现

（1） 预定义常量以及类型：#define ok 1 这个已经比较熟悉了#define是宏定义 ok 得值为1

typedef 是数据存储结构的表示用类型定义也就是c++的方法，typedef int status是指函数结果的返回值。 数据元素类型约定为ElemType由用户自行定义该数据类型。

以&打头的参数即为引用参数，传递引用给函数与传递指针效果一样。

内存的动态分配与释放：使用new和delete动态分配和释放内存空间 分配空间：指针变量=new 数据类型； 释放空间：delete 指针变量

输入输出语句使用C++流式输入输出形式，cin>>变量1>>.....>>变量n;

输出语句：Cout<<表达式<< 表达式n；总的来说是先有一个代码 cin>> cout<<输出。两个箭头往右是输入，往左是输出。

抽象数据类型实现过程：

定义部分：typedf struct//复数类型{ float Realpart；//实数部分float Imagepart；//虚数部分}complex是这个结构体的名称

void Create（&complex C，float x，float y）//{}引用参数&后接结构体的名称结构体定义一个名称为C，与结构体内的数据结构类型相同为float型。{C.Realpart=x；//将X赋值给结构体的实数部分以C.实现 C.image=y；//将y赋值给结构体的虚数部分以C.实现}

取复数的实部：float Getreal（complex C）{return C.Realpart//直接返回实数的值}

取复数的虚部：float Getimag（complex C//这个结构体已经被创建所以可以直接拿来用）{return C.image//直接返回虚部的值}

求两个复数c1和c2的值（第一种直接返回结构体）：complex add（complex C1 ，complex C2）//传入两个结构体，取c1、c2实数部分与虚数部分 分别进行相加，{complex sum；//创建一个全新用来存放相加部分的结构体 sum.realpart=C1.real+C2.real； sum.image=C1.image+C2,image； return sum；}

第二种方法：只是返回相加实数的值，不新创建结构体。float add（complex C1,complex C2）{float sum； sum=C1.real+C2.real； return sum；}

1.4 算法和算法分析

1.4.1 算法的定义及特性

算法：算法是为了解决某类问题而规定的一个有限长的操作序列

其具有五大特性：1.有穷性：你不能是无限计算下去是吧 2.确定性：对于每种情况算法都要有解决方案不可能产生即使这个又是哪个。3.可行性 这个没什么好说的 4.输入 多是从主调函数中获得输入值 5输出：输出多用返回值来实现 这点我要注意因为我经常不用返回值的方法。

1.4.2 算法的时间复杂度（也就是计算效率的问题时间越短越好）

时间复杂度说白了就是看有几层循环，问题规模是指算法求解问题输入量的多少这个在不同的问题所指不同，树是结点n，排序运算中n是指参加排序的计算数。

空间复杂度就是指代问题的规模

需要对其进行相除运算：例如i<n/2 在这个问题当中n是问题规模所以n/n也就是1，这个空间复杂度就是1 i<n i<n ，n2/n 也就是n这个空间复杂度就是n。