![[郝斌老师]自学数据结构大纲笔记](https://img.doczj.com/img11/0ifa9g01pdz4496w7qh-11.webp)
![[郝斌老师]自学数据结构大纲笔记](https://img.doczj.com/img11/0ifa9g01pdz4496w7qh-02.webp)
数据结构概述（教材选用严蔚敏、吴伟民，该书程序是伪算法
具体的程序是高一凡，西电的，大牛，只有
程序。还有一本书，台湾的黄国瑜自己写的
只有思路，程序是另外一个合作的清华的写
的，可惜很多错的。）
学完数据结构之后会对面向过程的函数有一个更深的了解
定义
我们如何把现实中大量而复杂的问题以特定的数据类型（单
个数据怎样存储？）和特定的存储结构（个体的关系）
保存到主存储器（内存）中，以及在此基础上为实现某个功能
（比如查找某个元素，删除某个元素，对所有元素进行排序）
而执行的相应操作，这个相应的操作也叫算法。（比如班里有
15个人，其信息量也许一个数组就搞定了，但是假如10000个，怎么办？内存也许没有这么多连续的空间，所以我们改用链表，
you see这就是与存储有关系。又比如，人事管理系统的信息存储，因为存在着上下级的关系，所以数组和链表就无能为力了，
这时候我们用树，再比如我们做的是交通图，站和站之间肯定要连通，这
时候以上的存储方式又无能为力了，所以我们又有了图。图
就是每个结点都可以和其他结点产生联系。所以当我们要解决
问题时，首先要解决的是如何把这些问题转换成数据，先保存
到我们的主存中，）
数据结构 = 个体的存储 + 个体的关系的存储
算法 = 对存储数据的操作
算法
解题的方法和步骤
衡量算法的标准
1、时间复杂度
大概程序要执行的次数，而非执行的时间。
2、空间复杂度
算法执行过程中大概所占用的最大内存
3、难易程度（主要是应用方面看重）
4、健壮性（不能别人给一个非法的输入就挂掉）
数据结构的地位
数据结构是软件中最核心的课程
程序 = 数据的存储＋数据的操作＋可以被计算机执行的语言（已经提供）
（学完数据结构，想用一种语言去实现它，必须有指针，数据结构java
版，就胡扯，变味，因为我们要讲链表，就是通过指针链在一起的。比如
在java中A aa = new A();本质上，aa是个地址）
预备知识
指针
指针的重要性：（内存是可以被CPU直接访问的，硬盘不行
主要靠地址总线，数据总线，控制总线。）
指针是C语言的灵魂
定义
地址
地址就是内存单元的编号
从0开始的非负整数
范围：0--FFFFFFFF[0-4G-1]（地址线是32位，刚好控制2的32次）指针：
指针就是地址地址就是指针
指针变量是存放内存单元地址的变量
指针的本质是一个操作受限的非负整数（不能加乘除，只能减）分类：
1、基本类型的指针
2、指针和数组的关系
结构体（C++中用类也能实现）
为什么会出现结构体
为了表示一些复杂的数据，而普通的基本类型变量无法满足要求
什么叫结构体
结构体是用户根据实际需要自己定义的复合数据类型
如何使用结构体
两种方式：
struct Student st = {1000, "zhangsan", 20}
struct Student * pst = &st;
1.
st.sid
2.
pst->sid
pst所指向的结构体变量中的sid这个成员
注意事项：
结构体变量不能加减乘除，但可以相互赋值
普通结构体变量和结构体指针变量作为函数参数的传递
（病毒就是靠访问正在运行的那些程序所占用的内存。Java中规定局部
变量必须初始化，因为这些变量一开始都是垃圾值，但是属性不是必须
初始化的，因为已经默认初始化为0）
动态内存分配和释放（动态分配的内存一定要手动释放，否则造成内存
泄露。）
（java中A aa = new A();其实就是 A *p = (A *)malloc(sizeof(A))）
模块一：线性结构【把所有的结点用一根直线穿起来】
连续存储【数组】
1、什么叫做数组
元素类型相同，大小相等（数组传参，只要传进去首地址和长度就行）
2、数组的优缺点：
优点：
存取速度快
缺点：
事先必须知道数组的长度
插入删除元素很慢
空间通常是有限制的
需要大块连续的内存块
插入删除元素的效率很低
离散存储【链表】（我们搞底层的开发，类似于SUN公司的类）
定义：
n个节点离散分配
彼此通过指针相连
每个节点只有一个前驱节点，每个节点只有一个后续节点
首节点没有前驱节点，尾节点没有后续节点。
专业术语：
首节点：
第一个有效节点（有效节点就是存放有效数据的节点）
尾节点：
最后一个有效节点
头节点：
头结点的数据类型和首节点的类型一样
没有存放有效数据，放在最前面的，是在
首节点之前的，主要是为了方便对链表
的操作。
头指针：（指向头）
指向头节点的指针变量
尾指针：
指向尾节点的指针
（头结点有可能很大，占的内存可能大，假设我想造一个函数
输出所有链表的值，那你如果不用头指针类型做形参，那由于
不同链表的头节点不一样大小，这样就没办法找出形参）
在学数据结构之前，我们确定数组的信息就是数组的长度和数组名，那么学完数据结构后就有三个了，长度，有效个数，数组名
确定一个链表需要几个参数：（或者说如果期望一个函数对链表进行操作
我们至少需要接收链表的那些信息？？？）
只需要一个参数:头指针，因为通过它我们可以推出
链表的所有信息。
（链表的程序最好一定要自己敲出来）
分类：
单链表
每个节点的指针域只能指向下一个节点
双链表：
每一个节点有两个指针域
循环链表
能通过任何一个节点找到其他所有的节点
非循环链表
（java中变成垃圾内存则会自动释放，但是C和C++则不会，所以要
手动释放，否则会引起内存泄露。delete等于free）
算法：
遍历
查找
清空
销毁
求长度
排序
删除节点
插入节点
算法：狭义的算法是与数据的存储方式密切相关
广义的算法是与数据的存储方式无关
泛型：（给你一种假象，只不过牛人从内部都弄好了）
利用某种技术（比如C++里面函数重载）达到的效果就是：不同的存储方式，执行的操作是一样的
算法的真正学法：很多算法你根本解决不了！！！！！！因为很多都属于
数学上的东西，所以我们把答案找出来，如果能看懂就
行，但是大部分人又看不懂，分三步，按照流程，语句，
试数。这个过程肯定会不断地出错，所以不断出错，不断
改错，这样反复敲很多次，才能有个提高。实在看不懂
就先背会。
链表的优缺点：
优点：
空间没有限制
插入删除元素很快
缺点：
存取速度很慢。
# include
# include
void f(int k)
{
int i;
double * q = (double *)malloc(200);
}
int main(void)
{
int i = 10;
int * p = (int *)malloc(100);
return 0;
}
//f 函数和main 函数里面的i,q,p 都是栈里面分配的，由操作系统分配的
栈和堆表示的是一种分配数据的方式，静态的和局部变量是以压栈和出栈的方式分配内存的
//malloc(200),malloc(100)是在堆里面分配的，由程序员自己手动分配的，动态的是以一种堆排序的方式分配内存的
线性结构的两种常见应用之一 栈 (存储数据的结构)
定义
一种可以实现“先进后出” 的存储结构
栈类似于箱子
分类
静态栈 （类似于用数组实现）
动态栈 （类似于用链表实现）
算法（往里放，从里取）
出栈
压栈（参看Java 中线程的例子，成产消费的例子）
左边生成东西，右边往出取（消费）生产和取出必须要平衡，不平衡的话生产就会满了，或者取出的是空的，取空了就是不能再取了，再取就是垃圾数据了 生产往底部一直往上放，取出就从顶部一直往下取
应用
函数调用（压栈和出栈是现实的）
中断
表达式求值（用两个栈，一个存放数字，一个存放符号）
内存分配
缓冲处理
迷宫
线性结构的两种常见应用之二 队列
定义：
一种可是实现“先进先出”的存储结构
分类：
栈
链式队列：用链表实现
静态队列：用数组实现
静态对流通常都必须是循环队列，为了减少
内存浪费。
循环队列的讲解：
1、静态队列为什么必须是循环队列
2、循环队列需要几个参数来确定及其含义
需要2个参数来确定
front
rear
3、循环队列各个参数的含义
2个参数不同场合不同的含义 ?
建议初学者先记住，然后慢慢体会
1）队列初始化
front和rear的值都是零
2）队列非空
front代表队列的第一个元素
rear代表了最后一个有效元素的下一个元素
3）队列空
front和rear的值相等，但是不一定是零
4、循环队列入队伪算法讲解
两步完成：
1）将值存入r所代表的位置
2）将r后移，正确写法是 rear = (rear+1)%数组长度
错误写法：rear=rear+1;
5、循环队列出队伪算法讲解
front = (front+1) % 数组长度
6、如何判断循环队列是否为空
如果front与rear的值相等，
则队列一定为空
7、如何判断循环队列是否已满
预备知识：
front的值和rear的值没有规律，
即可以大，小，等。
两种方式：
1、多增加一个表标识的参数
2、少用一个队列中的元素（才一个，不影响的）
通常使用第二种方法
如果r和f的值紧挨着，则队列已满
用C语言伪算法表示就是：
if( (r+1)%数组长度 == f )
已满
else
不满
队列算法：
入队
出队
队列的具体应用：
所有和时间有关的操作都有队列的影子。
（例如操作系统认为先进来的先处理）
专题：递归【这对你的编码能力是个质的飞跃，如果你想成为一个很厉害的
程序员，数据结构是必须要掌握的，因为计算机专业的本科生也达不到这水
平！计算机特别适合用递归的思想来解决问题，但是我们人类用递归的思想
来考虑问题就会感到十分困扰，这也是很多学过递归的人一直都搞不明白的
地方！那是不是递归可以随便写，当然不是，有些同学一用递归程序就死翘
翘了。递归的思想是软件思想的基本思想之一，在树和图论上面，几乎全是
用递归来实现的，最简单，像求阶乘这种没有明确执行次数的问题，都是用
递归来解决】
定义：
一个函数自己直接或间接调用自己(一个函数调用另外
一个函数和他调用自己是一模一样的，都是那三步，
只不过在人看来有点诡异。)
递归用栈实现
递归满足的三个条件：
1、递归必须得有一个明确的终止条件
2、该函数处理的数据规模必须在递减
3、这个转化必须是可解的。
递归的调用
1、当在一个函数的运行期间调用另一个函数时，在运行被调用函数之前，系统需要完成三件事：
A 将所有的实际参数，返回地址等信息传递给被调函数保存
B 为被调函数的局部变量（也包括形参）分配存储空间
C 将控制转移到被调函数的入口
2、从被调函数返回主调函数之前，系统也要完成三件事：
A 保存被调函数的返回结果
B 释放被调函数所占的存储空间
C 依照被调函数保存的返回地址将控制转移到调用函数
3、当有多个函数相互调用时，按照“后调用先返回”的原则，上述函数之间信息传递和控制转移必须借助“栈”
来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就在栈顶分配一个存储区，进行压栈操作，每当一个函数退出时，就释放它的存储区，就进行出栈操作，当前运行的函数永远都在栈顶位置
A函数调用A函数和A函数调用B函数在计算机看来是没有任何区别的，只不过用我们日常的思维方式理解比较怪异而已！
循环和递归：
理论上循环能解决的，肯定可以转化为递归，但是这个
过程是复杂的数学转化过程，递归能解决不一定能转化
为循环，我们初学者只要把经典的递归算法看懂就行，
至于有没有能力运用看个人。
递归：
易于理解(学完汉诺塔，树，图后就会发现递归很容易理解)
速度慢
存储空间大
循环
不易于理解
速度快
存储空间小
举例：
1.求阶乘
2.1+2+3+4+。。。+100的和
3.汉诺塔
【汉诺塔】这不是线性递归，这是非线性递归！
n=1 1
n=2 3
n=3 7
.........
.........
n=64 2的64次方减1【这是个天文数字，就算世界上最快的计算机
也解决不了，汉诺塔的负责度是2的n次方减1】问题很复杂，但真正解决
问题的编码只有三句。
4.走迷宫(CS的实现)
递归的运用：
树和森林就是以递归的方式定义的
树和图的很多算法都是以递归来实现的
很多数学公式就是以递归的方式定义的
斐波拉契序列
1 2 3 5 8 13 21 34。。。用递归思想写出代码
为何数据结构难学：因为计算机内存是线性一维的，而我们要处理的数据
都是比较复杂的，那么怎么把这么多复杂的数据保存在计算机中来保存本
身就是一个难题，而计算机在保存线性结构的时候比较好理解，尤其是数
组和链表只不过是连续和离散的问题，线性结构是我们学习的重点，因为
线性算法比较成熟，无论C++还是Java中都有相关的工具例如Arraylist.
Linkedlist,但是在Java中没有树和图，因为非线性结构太复杂了，他的
操作远远大于线性结构的操作。即使SUN公司也没造出来。
小复习一下：^_^
逻辑结构：（就是在你大脑里面能产生的，不考虑在计算机中存储）
线性（用一根直线穿）
在计算机中存储用：
数组
链表
栈和队列是一种特殊的线性结构，是具体应用。
（操作受限的线性结构，不受限的应该是在任何地方可以增删改查
可以用数组和链表实现。只要把链表学会，栈和队列都能搞定，数
组稍微复杂一些。）
非线性：
树
图
物理结构：
数组
链表
模块二：非线性结构(现在人类还没有造出一个容器，能把树和图
都装进去的，因为他们确实是太复杂了)
（都要靠链表去实现）
树
树定义
专业定义：
1、有且只有一个称为根的节点
2、有若干个互不相交的子树，这些子树本身也是一棵树
通俗定义：
1、树是由节点和边组成
2、每个节点只有一个父节点但可以有多个子节点
3、但有一个节点例外，该节点没有根节点，此节点称为根节点
专业术语
节点父节点子节点
子孙堂兄弟
深度：
从根节点到最底层节点的层数称之为深度
根节点是第一层
叶子节点；（叶子就不能劈叉了）
没有子节点的节点
非终端节点：
实际就是非叶子节点。
根节点既可以是叶子也可以是非叶子节点
度：
子节点的个数称为度。（一棵树看最大的）
树分类：
一般树
任意一个节点的子节点的个数都不受限制
二叉树（有序树）
任意一个节点的子节点的个数最多两个，且子节点
的位置不可更改。
分类：
一般二叉树
满二叉树
在不增加树的层数的前提下。无法再多
添加一个节点的二叉树就是满二叉树。
完全二叉树
如果只是删除了满二叉树最底层最右边的
连续若干个节点，这样形成的二叉树就是
完全二叉树。
森林
n个互不相交的树的集合
一般的二叉树要以数组的方式存储，要先转化成完全二叉树，因为如果你
只存有效节点（无论先序，中序，后序），则无法知道这个树的组成方式
是什么样子的。
树的存储（都是转化成二叉树来存储）
二叉树的存储
连续存储【完全二叉树】
优点：
查找某个节点的父节点和子节点（也包括判断有咩有）速度很快
缺点：
耗用内存空间过大
链式存储
一般树的存储
双亲表示法
求父节点方便
孩子表示法
求子节点方便
双亲孩子表示法
求父节点和子节点都很方便
二叉树表示法
把一个普通树转化成二叉树来存储
具体转换方法：
设法保证任意一个节点的
左指针域指向它的第一个孩子
有指针域指向它的下一个兄弟
只要能满足此条件，就可以把一个普通树转化成二叉树
一个普通树转化成的二叉树一定没有右子树
森林的存储
先把森林转化为二叉树，再存储二叉树，具体方式为：根节点
之间可以当成是兄弟来看待
二叉树操作
遍历
先序遍历【先访问根节点】
先访问根节点
再先序访问左子树
再先序访问右子树
中序遍历【中间访问根节点】
中序遍历左子树
再访问根节点
再中序遍历右子树
后序遍历【最后访问根节点】
先后序遍历左子树
再后序遍历右子树
再访问根节点
已知两种遍历序列求原始二叉树
通过先序和中序或者中序和后续我们可以
还原出原始的二叉树
但是通过先序和后续是无法还原出原始的二叉树的
换种说法：
只有通过先序和中序，或通过中序和后序
我们才可以唯一的确定一个二叉树
应用
树是数据库中数据组织的一种重要形式（例如图书馆
的图书分类一层一层往下分。）
操作系统子父进程的关系本身就是一棵树
面向对象语言中类的继承关系本身就是一棵树
赫夫曼树（树的一个特例）
图
模块三：查找和排序
折半查找
排序：
冒泡
插入
选择
快速排序
归并排序
排序和查找的关系
排序是查找的前提
排序是重点
Java中容器和数据结构相关知识
Iterator接口
Map
哈希表（与Java关系比较大）
再次讨论什么是数据结构：
数据结构研究是数据结构的存储和数据的操作的一门学问
数据的存储分为两部分：
个体的存储
个体关系的存储
从某个角度而言，数据的存储最核心的就是个体关系
的存储，个体的存储可以忽略不计。
再次讨论到底什么是泛型：
同一种逻辑结构，无论该逻辑结构物理存储是什么样子的
我们都可以对它执行相同的操作（例如都是线性结构或者
用数组实现的树和用链表实现的树。利用重载技术。）
判断： 1.线性表的链式存储结构优于顺序存储错误 2.单链表的每个节点都恰好包含一个指针域错误 3.线性表中的元素都可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因 此属于同一数据对象正确 4.在线性表的顺序存储结构中，逻辑上相邻的两个元素在屋里位置上并不一定紧邻。错 误 5.在线性表的数据结构中，插入和删除元素时，移动元素的个数和该元素的位置有关。正 确 6.顺序存储的线性表可以实现随机存取正确 7.栈一定是顺序存储的线性结构错误 8.一个栈的输入序列为A，B,C,D，可以得到输入序列为C,A,B,D 错误 9.队列是一种后进先出的线性表错误 10.树结构中每个节点最多只有一个直接前驱正确 11.二叉树的前序遍历中，任意一个节点均处于其子树节点的前面正确 12.在栈空的情况下，不能做出出栈操作，否则产生溢出正确 13.在前序遍历二叉树的序列中，任何节点的子树的所有节点都是直接跟在该节点之后正 确 填空： 1.在N个节点的顺序表中删除一个节点平均需要移动（（N-1）/2）个节点，具体的移 动次数取决于（表长N和删除位置） 2.在单链表中除首节点外，任意节点的存储位置都由（直接前驱）节点中的指针指示 3.树中节点的最大层次称为树的（度） 4.由一颗二叉树的前序序列和（中）序列可唯一确定这棵二叉树 5.哈弗曼树的带权路径长度（最小）的二叉树 6.二插排序树任意节点的关键字值（大于）其左子树中各节点的关键字值（小于）其 右子树中的各节点关键字值 7.二分查找法，表中元素必须按（关键字有序）存放 选择： 1.用单链表方式存储的线性表，储存每个节点需要两个域，一个数据域，另一个是（B 指针域） 2.设A1，A2，A3为三个节点；P，10，,2代表地址，则如下的链表存储结构称为（B 单链表） 3.单链表的存储密度（C 小于1） 4.在线性表中（B 中间元素）只有一个直接前驱和一个直接后续 5.两个指针P和Q，分别指向单链表的两个元素P所指元素时Q所指元素前驱的条 件是（D P==Q） 6.在栈中存取数据的原则是（B 后进先出） 7.顺序栈判空的条件是（C top==-1） 8.串是一种特殊的线性表，其特殊性体现在（B 数据元素是一个字符） 9.求字符串T和字符串S中首次出现的位置的操作为（C 串的模式匹配） 10.深度为H的二叉树至多有（B 2H-1）个节点
郝斌数据结构自学笔记 --知识点+程序源代码 By-HZM 1_什么叫做数据结构 数据结构概述 定义 我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器（内存）中，以及在此基础上为实现某个功能（比如查找某个元素，删除某个元素，对所有元素进行排序）而执行的相应操作，这个相应的操作也叫算法。 ~ 数据结构=个体的存储+个体的关系存储 算法=对存储数据的操作 2_衡量算法的标准 算法 解题的方法和步骤 ~ 衡量算法的标准 1）时间复杂度：大概程序执行的次数，而非执行的时间 2）空间复杂度：算法执行过程中大概所占用的最大内存 3）难易程度 4）健壮性 3_数据结构的特点 【 数据结构的地位 数据结构是软件中最核心的课程 程序=数据的存储+数据的操作+可以被计算机执行的语言 4_预备知识_指针_1 5_预备知识_指针_2 * 指针的重要性： 指针是C语言的灵魂 定义：
地址： 地址是内存单元的编号,从0开始的非负整数，范围：0-FFFFFFFF【0-4G-1】 CPU=====地址线，控制线，数据线=====内存 指针： … 指针就是地址，地址就是指针。 指针变量是存放内存单元地址的变量。 指针的本质是一个操作受限的非负整数。 分类： 1.基本类型的指针 2.指针和数组的关系 ? 变量并不一定连续分配，随机分配内存。 内存： 内存是多字节组成的线性一维存储空间。 内存的基本划分单位是字节。 每个字节含有8位，每一位存放1个0或1个1. 内存和编号是一一对应的。 （ 软件在运行前需要向操作系统申请存储空间。在软件运行期间，该软件所占空间不再分配给其他软件。当软件运行完毕后，操作系统将回收该内存空间（操作系统并不清空该内存空间中遗留下来的数据）。 NOTE：1）指针变量也是变量，普通变量前不能加*，常亮和表达式前不能加&。 2）局部变量只在本函数内部使用。 如何通过被调函数修改主调函数中普通变量的值。 1）实参为相关变量的地址； < 2）形参为以该变量的类型为类型的指针变量； 3）在被调函数中通过 *形参变量名的形式的形式就可以修改主函数。 CASE 1 #include<> int main(void) { |
数据结构复习笔记 作者: 网络转载发布日期: 无 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，有时一个数据元素可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。如整数这个集合中，10这个数就可称是一个数据元素.又比如在一个数据库(关系式数据库)中，一个记录可称为一个数据元素，而这个元素中的某一字段就是一个数据项。 数据结构的定义虽然没有标准，但是它包括以下三方面内容：逻辑结构、存储结构、和对数据的操作。这一段比较重要，我用自己的语言来说明一下，大家看看是不是这样。 比如一个表(数据库)，我们就称它为一个数据结构，它由很多记录(数据元素)组成，每个元素又包括很多字段(数据项)组成。那么这张表的逻辑结构是怎么样的呢? 我们分析数据结构都是从结点(其实也就是元素、记录、顶点，虽然在各种情况下所用名字不同，但说的是同一个东东)之间的关系来分析的，对于这个表中的任一个记录(结点)，它只有一个直接前趋，只有一个直接后继(前趋后继就是前相邻后相邻的意思)，整个表只有一个开始结点和一个终端结点，那我们知道了这些关系就能明白这个表的逻辑结构了。 而存储结构则是指用计算机语言如何表示结点之间的这种关系。如上面的表，在计算机语言中描述为连续存放在一片内存单元中，还是随机的存放在内存中再用指针把它们链接在一起，这两种表示法就成为两种不同的存储结构。(注意，在本课程里，我们只在高级语言的层次上讨论存储结构。) 第三个概念就是对数据的运算，比如一张表格，我们需要进行查找，增加，修改，删除记录等工作，而怎么样才能进行这样的操作呢? 这也就是数据的运算，它不仅仅是加减乘除这些算术运算了，在数据结构中，这些运算常常涉及算法问题。 弄清了以上三个问题，就可以弄清数据结构这个概念。 -------------------------------------------------------------------------------- 通常我们就将数据的逻辑结构简称为数据结构，数据的逻辑结构分两大类：线性结构和非线性结构(这两个很容易理解) 数据的存储方法有四种：顺序存储方法、链接存储方法、索引存储方法和散列存储方法。-------------------------------------------------------------------------------- 下一个是难点问题，就是算法的描述和分析，主要是算法复杂度的分析方法及其运用。首先了解一下几个概念。一个是时间复杂度，一个是渐近时间复杂度。前者是某个算法的时间耗费，它是该算法所求解问题规模n的函数，而后者是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 当我们评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度，因此，在算法分析时，往往对两者不予区分，经常是将渐近时间复杂度T(n)=O(f(n)简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。 此外，算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的情况下的时间复杂度。以保证算法的运行时间不会比它更长。 常见的时间复杂度，按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)。 时间复杂度的分析计算请看书本上的例子，然后我们通过做练习加以领会和巩固。 数据结构习题一 --------------------------------------------------------------------------------
数据结构学习总结 经过一学期的学习，我对数据结构有了我自己的认识。一开始，我以为它和C语言和C++一样，都是讲一门语言。但学习之后，发现事实并不是这样，在数据结构的学习中，有线性表，有队，有栈，有树，有图等等。这些看起来没有关系，其实之间有着千丝万缕的联系。线性表是其中最简单的，所以在前几章学习，后面依次逐章变难，学起来也很吃力。 《数据结构与算法》以基本数据结构和算法设计策略为知识单元，系统地介绍了数据结构的知识与应用、计算机算法的设计与分析方法，主要内容包括线性表、树、图和广义表、算法设计策略以及查找与排序算法等。 线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。线性表具有如下的结构特点：均匀性：虽然不同数据表的数据元素可以是各种各样的，但对于同一线性表的各数据元素必定具有相同的数据类型和长度。有序性：各数据元素在线性表中的位置只取决于它们的序号，数据元素之前的相对位置是线性的，即存在唯一的“第一个“和“最后一个”的数据元素，除了第一个和最后一个外，其它元素前面均只有一个数据元素直接前驱和后面均只有一个数据元素（直接后继）。在实现线性表数据元素的存储方面，一般可用顺序存储结构和链式存储结构两种方法。链式存储结构将在本网站线性链表中介绍，本章主要介绍用数组实现线性表数据元素的顺序存储及其应用。另外栈、队列和串也是线性表的特殊情况，又称为受限的线性结构。 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生
C 语言概述： 1、为什么学习C 语言 1). C 的起源和发展 2).C 的特点 优点 代码量小速度快功能强大 缺点 危险性高 开发周期长 可移植性不强 3）.c 的应用领域 主要是系统领域 4）.c 的重要性 2、怎样学习C 语言 3、学习的目标 了解程序语言及发展历史熟 练掌握c 语言的语法规则掌 握简单的算法 理解面向过程的思想，这非常有助于将来对面向对象思想的学习能看懂程序 会调试程序 掌握将大问题转化为一系列小问题来求解的思想 为学习c++、数据结构、c#、java 打下良好的基础 4、常见的学习问题 1、学习java 为什么建议先学习C 语言 2、没学过计算机专业的课程能够学懂C 语言 3、英语和数学不好能学好C 吗 32 个关键词：（有系统定义，不能重做其他定义） auto break case char const continue default do double else enum extern float for goto if int long register return short signed sizeof static struct switch typedef unsigned unsigned union void volatile while 5、课程规划 c 语言简介 第一讲、基本编程知识 第二讲、数据类型 第三讲、运算符和表达式 第四讲、流程控制（所有语言都一样的） 第五讲、函数（体现出面向过程和面向对象的区别） 第六讲、数组 第七讲、指针（c 语言的灵魂） 第八讲、变量的作用域和存储方式 第九讲、扩展数据类型 第十讲、专题： 字符串的处理 进制转换 补码 动态内存分配（java、数据结构必学） 综合应用：链表的使用
数据结构概述（教材选用严蔚敏、吴伟民，该书程序是伪算法 具体的程序是高一凡，西电的，大牛，只有 程序。还有一本书，台湾的黄国瑜自己写的 只有思路，程序是另外一个合作的清华的写 的，可惜很多错的。） 学完数据结构之后会对面向过程的函数有一个更深的了解 定义 我们如何把现实中大量而复杂的问题以特定的数据类型（单 个数据怎样存储？）和特定的存储结构（个体的关系） 保存到主存储器（内存）中，以及在此基础上为实现某个功能 （比如查找某个元素，删除某个元素，对所有元素进行排序） 而执行的相应操作，这个相应的操作也叫算法。（比如班里有 15个人，其信息量也许一个数组就搞定了，但是假如10000个，怎么办？内存也许没有这么多连续的空间，所以我们改用链表， you see这就是与存储有关系。又比如，人事管理系统的信息存储，因为存在着上下级的关系，所以数组和链表就无能为力了， 这时候我们用树，再比如我们做的是交通图，站和站之间肯定要连通，这 时候以上的存储方式又无能为力了，所以我们又有了图。图 就是每个结点都可以和其他结点产生联系。所以当我们要解决 问题时，首先要解决的是如何把这些问题转换成数据，先保存 到我们的主存中，） 数据结构 = 个体的存储 + 个体的关系的存储 算法 = 对存储数据的操作 算法 解题的方法和步骤 衡量算法的标准 1、时间复杂度 大概程序要执行的次数，而非执行的时间。 2、空间复杂度 算法执行过程中大概所占用的最大内存 3、难易程度（主要是应用方面看重） 4、健壮性（不能别人给一个非法的输入就挂掉） 数据结构的地位 数据结构是软件中最核心的课程 程序 = 数据的存储＋数据的操作＋可以被计算机执行的语言（已经提供） （学完数据结构，想用一种语言去实现它，必须有指针，数据结构java 版，就胡扯，变味，因为我们要讲链表，就是通过指针链在一起的。比如 在java中A aa = new A();本质上，aa是个地址） 预备知识 指针
C语言概述： 1、为什么学习C语言 1). C的起源和发展 2).C的特点 优点 代码量小速度快功能强大 缺点 危险性高 开发周期长 可移植性不强 3）.c的应用领域 主要是系统领域 4）.c的重要性 2、怎样学习C语言 3、学习的目标 了解程序语言及发展历史 熟练掌握c语言的语法规则 掌握简单的算法 理解面向过程的思想，这非常有助于将来对面向对象思想的学习能看懂程序 会调试程序 掌握将大问题转化为一系列小问题来求解的思想 为学习c++、数据结构、c#、java打下良好的基础 4、常见的学习问题 1、学习java为什么建议先学习C语言 2、没学过计算机专业的课程能够学懂C语言 3、英语和数学不好能学好C吗 32个关键词：（有系统定义，不能重做其他定义） auto break case char const continue default do double else enum extern float for goto if int long register return short signed sizeof static struct switch typedef unsigned unsigned union void volatile while 5、课程规划 c语言简介 第一讲、基本编程知识 第二讲、数据类型 第三讲、运算符和表达式 第四讲、流程控制（所有语言都一样的） 第五讲、函数（体现出面向过程和面向对象的区别） 第六讲、数组 第七讲、指针（c语言的灵魂） 第八讲、变量的作用域和存储方式 第九讲、扩展数据类型 第十讲、专题： 字符串的处理 进制转换 补码 动态存分配（java、数据结构必学） 综合应用：链表的使用 文档大全
{数据结构1~5笔记} Array_point 1 # include
int * p; //p是个变量名字, int * 表示该p变量只能存储int类型变量的地址 int i = 10; int j; // p = &i; j = *p; // 等价于j = i; printf("i = %d, j = %d, *p = %d\n", i, j, *p); //p = 10; //error return 0; } Point 2 # include
第一章概论 1.数据：信息的载体,能被计算机识别、存储和加工处理。 2.数据元素：数据的基本单位，可由若干个数据项组成，数据项是具有独立含义的最小标识单位。 3.数据结构：数据之间的相互关系，即数据的组织形式。 它包括：1）数据的逻辑结构，从逻辑关系上描述数据，与数据存储无关，独立于计算机； 2）数据的存储结构，是逻辑结构用计算机语言的实现，依赖于计算机语言。 3）数据的运算，定义在逻辑结构上，每种逻辑结构都有一个运算集合。常用的运算：检索/插入/删除/更新/排序。 4.数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的存储结构是逻辑结构用计算机语言的实现。 5.数据类型：一个值的集合及在值上定义的一组操作的总称。分为：原子类型和结构类型。 6.抽象数据类型：抽象数据的组织和与之相关的操作。优点：将数据和操作封装在一起实现了信息隐藏。 7. 抽象数据类型ADT：是在概念层上描述问题；类：是在实现层上描述问题；在应用层上操作对象（类的实例）解决问题。 8.数据的逻辑结构，简称为数据结构，有： （1）线性结构，若结构是非空集则仅有一个开始和终端结点，并且所有结点最多只有一个直接前趋和后继。 （2）非线性结构，一个结点可能有多个直接前趋和后继。 9.数据的存储结构有： 1）顺序存储，把逻辑相邻的结点存储在物理上相邻的存储单元内。 2）链接存储，结点间的逻辑关系由附加指针字段表示。 3）索引存储，存储结点信息的同时，建立附加索引表，有稠密索引和稀疏索引。 4）散列存储，按结点的关键字直接计算出存储地址。 10.评价算法的好坏是：算法是正确的；执行算法所耗的时间；执行算法的存储空间（辅助存储空间）；易于理解、编码、调试。
专题： 动态内存分配(所有高级语言，没有C里深刻) 传统数组的缺点： 1.数组长度必须事先指定，而且只能是常整数，不能是变量 例子int a[5];//必须事先指定，而且只能是常整数 int len = 5; int a[len];//error 2.传统形式定义的数组，该数组的内存程序员无法手动释放 数组一旦定义，系统为数组分配的内存空间就会一直存在，除非数组所在的函数运行终止。 在一个函数运行期间，系统为该函数中的数组分配的空间会一直存在。 直到该函数运行完毕时，数组的空间才会被系统自动释放。 例子：void f(void){int a[5]={1,2,3,4,5};....} //数组a 占20个字节的内存空间，程序员无法手动编程释放它，数组a只能在f()函数结束被系统释放 3. 数组的长度一旦定义，数组长度就不能再更改。 数组的长度不能在函数运行的过程中动态的扩充或缩小 4. 传统方式定义的数组不能跨函数使用 A函数定义的数组，只有在A函数运行期间才可以被其他函数使用， 但A函数运行完毕后，A函数中的数组将无法在被其他函数使用。 #include
数据结构及算法知识 1.字典树构造及其优化与应用 字典树的核心就是空间换时间，利用字符串的公共前缀来避免无谓的字符串比较，降低查询时间 性质： - 根结点不包含字符，除了根结点每个结点都包含一个字符 - 从根结点到某一结点的路径经过的字符连接起来就是该结点对于的字符串 - 查询和建树可以同时进行 有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。 思路：首先要求得每个词的频率，1G无法放入内存，需要分成多个小文件，对每个小文件的词进行统计 （1）散列分治：顺序读取文件，对每个词，可以hash(x)P00(只要不小于1024个文件，是为了保证每个小文件可以放入内存)，这样被映射为5000个小文件，每个文件大概200K，每个文件最少1250个单词 （2）对于每个小文件，利用hash_map/字典树记录每个单词出现的频率，（3）用100个元素的最小堆，选出每个文件中的频率最大的100个单词 （4）对这5000个小文件进行归并排序，选出最大的100个。 2.大规模文本文件，全是单词，求前10词频的单词（Top k问题是热门问题）
3.如何判断时间，空间复杂度是否为O（logn） 最直观的判断就是程序中采用了二分，且二分后只运算数据的一半。但如果两部分都运算的话，时间复杂度就是O(nlogn)了。其实不一定是二分，只不过二分比较常用罢了 4.各个算法的时间和空间复杂度 5.M个有序链表取前k大个元素
6.红黑树的调整 红黑树是一种近似平衡的二叉查找树，它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一倍 1.每个节点要么是红色，要么是黑色。 2.根节点必须是黑色 3.红色节点不能连续（也即是，红色节点的孩子和父亲都不能是红色）。 4.对于每个节点，从该点至null（树尾端）的任何路径，都含有相同个数的黑色节点。 在树的结构发生改变时（插入或者删除操作），往往会破坏上述条件3或条件4，需要通过调整使得查找树重新满足红黑树的条件。 调整可以分为两类：一类是颜色调整，即改变某个节点的颜色；另一类是结构调整，即改变检索树的结构关系。结构调整过程包含两个基本操作：左旋（Rotate Left），右旋（RotateRight）。
郝斌老师的C语言：课堂讲解全程动手敲代码，讲解细致，对于重要知识点的讲解不厌其烦，是一个难得的C语言入门教程。在这里对老师的辛勤付出表示感谢。 郝斌c语言视频教程 · 概述： 课程计划 为什么学习c语言： Fortran语言主要用于科学计算，在第三代语言中，以1980年为分水岭，分为结构化和面向对象语言。Basic语言是vb的前生，pascal语言一般是用于教学。C语言是最重要的，其他的语言一般很少用了。结构化的代表语言是c语言。结构化语言的数据和操作是分离的，导致在写大项目的时候，会出现各种各样莫名其妙的问题。 在面向对象的语言中c++是最复杂的语言。由于c++语言太复杂，sun公司对c++进行了改装，产生了java语
言。而c#是由微软开发的，和java相似，几乎一模一样。 在高级语言的执行速度上，c是最快的，c++其次，而java 和c#是最后的。Java和c#流行，主要的一个原因是可以跨平台。 C语言的发展和过程：
C语言的特点： ·优点：代码量小，速度快，功能强大。 ·缺点：危险性高，开发周期长，可移植性弱。 危险性高：写同一个程序，在java中会报错，而在c中不会报错，为什么呢，因为c认为程序你想怎么写就怎么写，c语言认为你写的程序不是很离谱，他都认为你写的这个程序有特殊的含义。可以直接通过，而java 则不可以。 开发周期长：c语言是面向过程的语言，面向过程的语言的特点就是在开发大项目的时候，很容易崩溃，好比盖大楼，C语言还要造大量的砖块、钢筋等结构原材料，而C++ C# JAVA则进行了一定的继承封装等操作，相当于原材料直接给你，你只需要用它盖楼即可。 现在市场上的语言分三块
C语言概述： 1为什么学习C语言 1). C的起源和发展 2).C的特点 优点 代码量小速度快功能强大 缺点 危险性高 开发周期长 可移植性不强 3.c的应用领域 主要是系统领域 4）.c的重要性 2、怎样学习C语言 3、学习的目标 了解程序语言及发展历史 熟练掌握c语言的语法规则 掌握简单的算法 理解面向过程的思想，这非常有助于将来对面向对象思想的学习能看懂程序 会调试程序 掌握将大问题转化为一系列小问题来求解的思想 为学习c++、数据结构、c#、java打下良好的基础 4、常见的学习问题 1学习java为什么建议先学习C语言 2没学过计算机专业的课程能够学懂C语言 3英语和数学不好能学好C吗 32个关键词：（有系统定义，不能重做其他定义） auto break case char const continue default do double else enum extern float for goto if int long register return short signed sizeof static struct switch typedef unsigned unsigned union void volatile while 5课程规划 c语言简介 第一讲、基本编程知识 第二讲、数据类型 第三讲、运算符和表达式 第四讲、流程控制（所有语言都一样的） 第五讲、函数（体现出面向过程和面向对象的区别） 第六讲、数组 第七讲、指针（c语言的灵魂） 第八讲、变量的作用域和存储方式 第九讲、扩展数据类型 第十讲、专题：
字符串的处理 进制转换 补码 动态内存分配（java、数据结构必学） 综合应用：链表的使用 6、举例子：一元二次方程 # include
第一张概论 1.1 引言 两项基本任务：数据表示，数据处理 软件系统生存期：软件计划，需求分析，软件设计，软件编码，软件测试，软件维护 由一种逻辑结构和一组基本运算构成的整体是实际问题的一种数学模型，这种数学模型的建立，选择和实现是数据结构的核心问题。 机外表示------逻辑结构------存储结构 处理要求-----基本运算和运算-------算法 1.2 数据，逻辑结构和运算 数据：凡是能够被计算机存储，加工的对象通称为数据 数据元素：是数据的基本单位，在程序中作为一个整体加以考虑和处理。又称元素，顶点，结点，记录。 数据项：数据项组成数据元素，但通常不具有完整确定的实际意义，或不被当做一个整体对待。又称字段或域，是数据不可分割的最小标示单位。 1.2.2数据的逻辑结构 逻辑关系：是指数据元素之间的关联方式，又称“邻接关系” 逻辑结构:数据元素之间逻辑关系的整体称为逻辑结构。即数据的组织形式。 四种基本逻辑结构： 1 集合：任何两个结点间没有逻辑关系，组织形式松散 2 线性结构：结点按逻辑关系依次排列成一条“锁链” 3 树形结构：具有分支，层次特性，形态像自然界中的树 4. 图状结构：各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接。 注意点: 1.逻辑结构与数据元素本身的形式，内容无关。 2.逻辑结构与数据元素的相对位置无关 3.逻辑结构与所含结点个数无关。 运算：运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。 加工型运算：改变了原逻辑结构的“值”，如结点个数，结点内容等。 引用型运算:不改变原逻辑结构个数和值，只从中提取某些信息作为运算的结果。 引用：查找，读取 加工：插入，删除，更新 同一逻辑结构S上的两个运算A和B, A的实现需要或可以利用B，而B的实现不需要利用A，则称A可以归约为B。 假如X是S上的一些运算的集合，Y是X的一个子集，使得X中每一运算都可以规约为Y中的一个或多个运算，而Y中任何运算不可规约为别的运算，则称Y中运算（相对于X）为基本运算。 将逻辑结构S和在S上的基本运算集X的整体（S,X）称为一个数据结构。数据结构包括逻辑结构和处理方式。
郝斌数据结构视频学习总结 郝斌数据结构视频学习总结 ......................................................................................................................................... - 1 - 0 教材 ..................................................................................................................................................................... - 2 - 1 数据结构概述 ..................................................................................................................................................... - 2 - 1.1、定义（研究是数据结构的存储和数据的操作的）............................................................................. - 2 - 1.2、算法 ........................................................................................................................................................ - 2 - 1.3、数据结构的地位 .................................................................................................................................... - 2 - 2 预备知识 ............................................................................................................................................................. - 3 - 2.1、指针 ........................................................................................................................................................ - 3 - 2.2、结构体 .................................................................................................................................................... - 3 - 2.3、动态内存的分配和释放 ........................................................................................................................ - 4 - 3 模块一：线性结构[把所有的结点用一条直线穿起来] ................................................................................. - 5 - 3.1、连续存储[数组] ...................................................................................................................................... - 5 - 3.1.1什么叫做数组 ................................................................................................................................ - 5 - 3.1.2.数组的优缺点（相对于链表）..................................................................................................... - 5 - 3.2、离散存储[链表] ...................................................................................................................................... - 5 - 3.2.1.定义及专业术语 ............................................................................................................................ - 5 - 3.2.2.分类 ................................................................................................................................................ - 6 - 3.2.3.算法（typedef/动态分配内存实例） ........................................................................................... - 6 - 3.2. 4.链表的优缺点（相对于数组）..................................................................................................... - 9 - 3.2.5.小结： ............................................................................................................................................ - 9 - 3.3、线性结构的两种常见应用之一栈.................................................................................................... - 11 - 3.3.1.定义：一种可以实现“先进后出”的存储结构 ............................................................................ - 11 - 3.3.2分类 ............................................................................................................................................... - 11 - 3.3.3.算法 ............................................................................................................................................... - 11 - 3.3.4应用 ............................................................................................................................................... - 11 - 3.3.5栈操作代码 ................................................................................................................................... - 11 - 3.4、线性结构的两种常见应用之一队列............................................................................................... - 15 - 3.4.1.定义：一种可以实现“先进先出”的存储结构 ........................................................................... - 15 - 3.4.2.分类 .............................................................................................................................................. - 15 - 3.4.3.算法 .............................................................................................................................................. - 16 - 3.4.4应用及代码 .................................................................................................................................. - 16 - 3.5、专题：递归（使用栈实现的）........................................................................................................... - 19 - 3.5.1.定义:一个函数自己直接或间接调用自己.................................................................................. - 19 - 3.5.2.函数的调用前后的准备工作....................................................................................................... - 19 - 3.5.3递归必须满足的三个条件：....................................................................................................... - 20 - 3.5. 4.循环和递归之间的关系 .............................................................................................................. - 20 - 3.5.5.举例： .......................................................................................................................................... - 21 - 3.5.6.递归的应用 .................................................................................................................................. - 23 - 4 模块二：非线性结构 ....................................................................................................................................... - 23 - 4.1、树 .......................................................................................................................................................... - 23 - 4.1.1.定义及专业术语 .......................................................................................................................... - 23 - 4.1.2.分类 .............................................................................................................................................. - 24 - 4.1.3.存储（解决非线性结构用线性结构表示的问题）................................................................... - 25 -