数据结构整理笔记
数据结构与算法
数据结构：数据的组成形式（数据是以什么样的形式组织起来的，数组、链表、队列、树、图等）
算法（注：强调的是数据结构与算法中的算法，狭义算法）：对所存储数据的操作（操作指的是对于所存数据有关问题，求解最终答案的过程）的⽅法，例：[1、2、3、4、5]中的最⼤值，求得最⼤值的⽅法（⼀系列操作）就是算法
书籍推荐
数据结构概述（教材选⽤严蔚敏、吴伟民，该书程序是伪算法具体的程序是⾼⼀凡，西电的，⼤⽜，只有程序。还有⼀本书，台湾的黄国瑜⾃⼰写的只有思路，程序是另外⼀个合作的清华的写的，可惜很多错的。）学完数据结构之后会对⾯向过程的函数有⼀个更深的了解，有本通俗易懂的数据结构的书《⼤话数据结构》⽤来⼊门很不错。
数据结构的概述
定义
我们如何把现实中⼤量⽽反复的问题以特定的数据类型（个体的数据类型）和特定的存储结构（个体间的相互关系）保存到主存储器(内存)中，以及在此基础上为实现某个功能（⽐如查某个元素，删除某个元素，对所有元素进⾏排序）⽽执⾏的相应的操作，这个相应的操作也叫做算法。
数据结构=个体+个体的关系
算法=对存储数据的操作
狭义：
数据结构是专门研究数据存储的问题
数据的存储包含两⽅⾯：个体的存储 + 个体关系的存储
⼴义：
数据结构既包含数据的存储也包含数据的操作
对存储数据的操作就是算法
算法
狭义：
算法是和数据的存储⽅式密切相关
⼴义：
算法和数据的存储⽅式⽆关，这就是泛型思想
算法的真正学法：
很多算法你根本解决不了因为很多都属于数学上的东西，所以我们把答案出来，如果能看懂就⾏，但是⼤部分⼈⼜看不懂，分三步，按照流程，语句，试数。这个过程肯定会不断地出错，所以不断出错，不断改错，这样反复敲很多次，才能有个提⾼。实在看不懂就先背会。
衡量算法的标准：
（1） 时间复杂度
⼤概程序要执⾏的次数，⽽并⾮是执⾏的时间（因为同⼀程序在不同机器上执⾏的时间是不⼀样的，有差异）
（2） 空间复杂度
算法执⾏过程中⼤概所占⽤的最⼤内存
（3） 难易程度（主要是应⽤⽅⾯看重）
（4） 健壮性（不能别⼈给⼀个⾮法的输⼊就挂掉）
数据结构的地位：
数据结构是软件中最核⼼的课程
程序 = 数据的存储 + 数据的操作 + 可以被计算机执⾏的语⾔
泛型
对于同⼀种逻辑结构，⽆论该逻辑结构的物理存储是什么样⼦的，我们可以对它执⾏相同的操作。
    泛型：（给你⼀种假象，只不过⽜⼈从内部都弄好了）利⽤某种技术达到的效果就是：不同的存储⽅式，执⾏的
操作是⼀样的
预备知识
指针
指针的重要性：（内存是可以被CPU直接访问的，硬盘不⾏；cpu访问内存主要靠地址总线，数据总线，控制总线。）
指针是C语⾔的灵魂
定义
地址：
地址就是内存单元的编号
从0开始的⾮负整数
范围：0--FFFFFFFF[0-4G-1]（地址线是32位，刚好控制2的32次）
指针：
指针就是地址  地址就是指针
指针变量是存放内存单元地址的变量
指针的本质是⼀个操作受限的⾮负整数（不能加乘除，只能减）
分类：
1、基本类型的指针
2、指针和数组的关系
结构体（C++中⽤类也能实现）
为什么会出现结构体
为了表⽰⼀些复杂的数据，⽽普通的基本类型变量⽆法满⾜要求
什么叫结构体
结构体是⽤户根据实际需要⾃⼰定义的复合数据类型
如何使⽤结构体
两种⽅式：
struct Student st = {1000, "zhangsan", 20}
struct Student * pst = &st;
st.sid
pst->sid
pst所指向的结构体变量中的sid这个成员
注意事项：
结构体变量不间能加减乘除，但可以相互赋值
普通结构体变量和结构体指针变量作为函数参数的传递
（病毒就是靠访问正在运⾏的那些程序所占⽤的内存。Java中规定局部变量必须初始化，因为这些变量⼀开始都是垃圾值，但是属性不是必须初始化的，因为已经默认初始化为0）动态内存分配和释放（动态分配的内存⼀定要⼿动释放，否则造成内存泄露。）（java中A aa = new A()；其实就是 A *p = (A *)m
alloc(sizeof(A))）
数据存储结构
线性结构【把所有的结点⽤⼀根直线穿起来】
数组和链表
栈和队列是数组和链表这两种线性结构的应⽤
连续存储【数组】
1、什么叫做数组
元素类型相同，⼤⼩相等（数组传参，只要传进去⾸地址和长度就⾏）
2、数组的优缺点：
优点：
存取速度快
缺点：
事先必须知道数组的长度
插⼊删除元素很慢
空间通常是有限制的
需要⼤块连续的内存块
插⼊删除元素的效率很低
离散存储【链表】（我们搞底层的开发，类似于SUN公司的类）
定义：
n个节点离散分配
彼此通过指针相连
每个节点只有⼀个前驱节点，每个节点只有⼀个后续节点
⾸节点没有前驱节点，尾节点没有后续节点。
专业术语：
⾸节点：
第⼀个有效节点
尾节点：
最后⼀个有效节点
头节点：
头结点的数据类型和⾸节点的类型⼀样
没有存放有效数据，最最前⾯的，是在
⾸节点之前的，主要是为了⽅便对链表
的操作。
头指针：（指向头）
指向头节点的指针变量
尾指针：
指向尾节点的指针
（头结点有可能很⼤，占的内存可能⼤，假设我想造⼀个函数输出所有链表的值，那你如果不⽤头指针类型做形参，那由于不同链表的头节点不⼀样⼤⼩，这样就没办法出形参）
确定⼀个链表需要⼏个参数：（或者说如果期望⼀个函数对链表进⾏操作我们⾄少需要接收链表的那些信息）      只需要⼀个参数：头指针，因为通过它我们可以推出链表的所有信息。
（链表的程序最好⼀定要⾃⼰敲出来）
分类：
单链表
双链表：
每⼀个节点有两个指针域
循环链表
能通过任何⼀个节点到其他所有的节点
⾮循环链表
（java中变成垃圾内存则会⾃动释放，但是C和C++则不会，所以要⼿动释放，否则会引起内存泄露。delete等于
free）
算法：
遍历
查
清空
销毁
求长度
排序
删除节点
插⼊节点
链表的优缺点：
优点：
空间没有限制
插⼊删除元素很快
缺点：
存取速度很慢。
栈和队列是⼀种特殊的线性结构，是连续存储或离散存储的⼀种应⽤
线性结构的应⽤------栈
定义：⼀种可以实现“先进后出“的存储结构，类似于箱⼦
分类：
  静态栈
动态栈
算法：
数组和链表出栈
压栈
应⽤：
函数调⽤
中断
表达式求值
内存分配
缓冲处理
迷宫
int main(void)
{
int p;
int * m = (int *)malloc(100);
}
如静态变量p和m是在栈中分配，有操作系统⾃动分配和释放。⽽(int *)malloc(100)；执⾏后，将在堆中分配⼀块100字节的内存，由程序员⼿动分配。
栈的⽰意图

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。