//2018/5/23
数据结构概述：
预备知识
模块一：线性结构
连续存储[数组]
离散结构[链表]
线性结构的两种常见应用之一栈（堆栈）
线性结构的两种常见应用之二队列
专题：递归
1.1+
2......+100的和
2.求阶乘
3.汉诺塔
4.走迷宫
模块二：非线性结构
树
图
模块三：查找和排序
折半查找
排序：冒泡插入选择快速排序归并排序补录：Java中容器和数据结构相关知识
Iterator接口
Map 哈希表
严蔚敏---高一凡---黄国瑜
//2018/5/24
数据结构概述
定义
我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器（内存）中，以及在此基础上为实现某个功能（比如查找或删除某个元素，对所有元素进行排序）而执行的相应操作，这个相应操作叫做算法。
特定的数据类型:个体如何保存
特定的存储结构:个体与个体的关系如何保存
数据结构 = 个体的存储 + 个体关系的存储
算法（狭义） = 对存储数据的操作
算法：即解题的方法和步骤
衡量算法的标准
1.时间复杂度[重要]
大概程序要执行的次数，而非执行的时间
2.空间复杂度[重要]
算法执行过程中大概所占用的最大内存
3.难易程度
4.健壮性
数据结构的地位
数据结构是软件中最核心的课程。
程序 = 数据的存储 + 数据的操作 + 可以被计算机执行的语言
预备知识：
指针
结构体
动态内存的分配和释放
指针：
指针的重要性:
表示一些复杂的数据结构
快速的传送数据
使函数返回一个以上的值
能否直接访问硬件
能够方便的使用数组和字符串
是理解面向对象语言中引用的基础
指针是C语言的灵魂
定义
地址
内存单元的编号
从0开始的非负整数
范围0-FFFFFFFF 【0 到 4G-1】
注：无论一个变量有多大，其地址只用第一个字节的地址表示，
均只占四个字节。
指针
指针就是地址地址就是指针
指针变量就是存放内存单元地址的变量
指针本质上就是一个操作受限的非负整数
分类
1、基本类型指针【略】
基本概念
int i=10;
int *p = &i; //等价于 int *p; p = &i;
详解这两部操作：
1）p存放了i的地址，所以我们说p指向了i
2）p和i是完全不同的两个变量，修改其中的任意一个变量的值，不会影响另一变量的值
3）p指向i，*p就是i变量本身。更形象的说所有出现 *p的地方都可以换成i，所有出现i的地方都可以换成*p
4）int * p，不是定义了*p的参数，而是定义了一个变量p，为int *类型。
总结：
1、如何一个指针变量(假定为p)存放了某个普通变量(假定为i)的地址，那我们就可以说：“p指向了i”，但p与i是两个不同的变量，修改p的值不影响i的值，修改i的值不影响p的值.
2、*p等价于i 或者说*p可以与i在任何地方互换
3、如果一个指针变量指向了某个普通变量，则*指针变量就完全等价于该普通变量
注意：
指针变量也是变量，只不过它存放的不能是内存单元的内容，只能存放内存单元的地址
普通变量前不能加*
常量和表达式前不能加&
如何通过被调函数修改主调函数中普通变量的值
Ⅰ实参为相关变量的地址
Ⅱ形参为以该变量的类型为类型的指针变量
Ⅲ在被调函数中通过 *形参变量名的方式就可以修改主函数相关变量的值Eg:void f(int * p) //II
{
*p = 100; //III
}
int main(void)
{
int i = 9;
f(&i); //I
printf(“i = %d\n”, i);
}
指针和数组的关系
指针和一维数组
数组名
一维数组名是个指针常量，
它存放的是一维数组第一个元素的地址，
它的值不能被改变
一维数组名指向的是数组的第一个元素
下标和指针的关系
a[i] <<==>> *(a+i)
*a+3 = a[0]+3
假设指针变量的名字为p
则p+i的值是p+i*(p所指向的变量所占的字节数)
指针变量的运算
指针变量不能相加，不能相乘，不能相除
如果两指针变量属于同一数组，则可以相减
指针变量可以加减一整数，前提是最终结果不能超过指针允许指向的范围
p+i的值是p + i*(p所指向的变量所占的字节数)
p-i的值是p - i*(p所指向的变量所占的字节数)
p++ <==> p+1
p-- <==> p-1
举例
如何通过被调函数修改主调函数中一维数组的内容【如何界定一维数组】两个参数
存放数组首元素的指针变量
存放数组元素长度的整型变量
所有的指针变量只占4个子节用第一个字节的地址表示整个变量的地址
动态内存分配和释放：
[程序在运行过程中可以动态的增加或减少内存分配]
动态构造一维数组
假设动态构造一个int型数组
int *p = (int *)malloc(int len);
1、malloc只有一个int型的形参，表示要求系统分配的字节数
2、malloc函数的功能是请求系统len个字节的内存空间，如果请求分配成功，则返回第一个字节的地址，如果分配不成功，则返回NULL
3、malloc函数能且只能返回第一个字节的地址，所以我们需要把[类型不一样。即所占的字节数也不确定]这个无任何实际意义的第一个字节的地址（俗称干地址）转化为一个有实际意义的地址，因此malloc前面必须加（数据类型 *）,
表示把这个无实际意义的第一个字节的地址转化为相应类型的地址。
如：int *p = (int *)malloc(50);
表示将系统分配好的50个字节的第一个字节的地址转化为int *型的地址，更准确的说是把第一个字节的地址转化为四个字节的地址，这样p就指向了第
一个的四个字节，p+1就指向了第2个的四个字节，p+i就指向了第i+1个的4
个字节。p[0]就是第一个元素， p[i]就是第 i+1个元素
double *p = (double *)malloc(80);
表示将系统分配好的80个字节的第一个字节的地址转化为double *型的地址，更准确的说是把第一个字节的地址转化为8个字节的地址，这样p就指向了第一个的8个字节，p+1就指向了第2个的8个字节，p+i就指向了第i+1个的8个字节。p[0]就是第一个元素， p[i]就是第i+1个元素
free（p）：动态分配的内存，必须free()释放，系统不会自动释放。
释放p所指向的内存，而不是释放p本身所占用的内存
【重点：动态分配数组内存】
int * pArr = (int *) malloc (sizeof(int) * len);
(最后一个*代表了乘分配了4 * len个字节)
模块一：线性结构【把所有的结点用一根直线穿起来】连续存储[数组]
1.什么叫数组
元素类型
离散结构[链表]
线性结构中两种常用应用之一栈定义
一种可以实现“先进后出”的存储结构
只能从栈尾（栈顶）进和出。
栈类似于箱子，局部变量都是在栈中存储的。
分类
静态栈【以数组为内核】
动态栈【以链表为内核】
算法
出栈 pTop向下移一个，pBottom不变
压栈（入栈） pTop向上移一个，pBottom不变
应用
函数调用
中断
表达式求值（例如计算器的编写）
内存分配
缓冲处理
//2018/5/20
线性结构中两种常用应用之二队列
定义：一种可以实现“先进先出”的存储结构
分类：变量名：front（头部）和 rear（尾部）
链式队列---用链表实现
静态队列---用数组实现
注：在队首的位置删除元素，然后队首指针指向下一个元素
在队尾的位置添加元素，然后队尾指针指向下一个元素
【重点】Rear指向的是队列最后一个元素的下一个元素
【重点】Front指向的是队列的第一个元素
队列算法：
入队
出队
队列的具体应用：
所有和时间及有关的操作都有队列的影子。
静态队列：
注：将数组的部分功能给去掉，然后再加入一些功能。
静态队列通常都必须是循环队列。
问题：如果按照普通的数组来存储队列的话。每次删掉一个元素，头部指针都会指向下一个元素，会造成原来元素的位置空间浪费，只能被使用一次而不能重复被使用。只能增不能减。
循环队列的讲解：
1.静态队列为什么必须是循环队列
问题：如果按照普通的数组来存储队列的话。每次删掉一个元素，头部指针都会指向下一个元素，会造成原来元素的位置空间浪费，只能被使用一次而不能重复被使用。只能增不能减。
解决方法：当front和rear移动到顶部（队尾）时，下一次移动时可以让它再移动到底部（队首），首尾相连，这实际就是循环队列。
2.循环队列需要几个参数来确定
需要两个参数来确定
front
rear
3.循环队列各个参数的含义
这两个参数在不同场合有不同的含义
建议初学者先记住，然后慢慢体会
1）队列初始化
front和rear的值都是0
2）队列非空
Front代表的是队列的第一个元素
Rear代表的是队列的最后一个有效元素的下一个元素
3）队列空
front和rear的值相等，但不一定为0
4.循环队列入队伪算法讲解
两步完成，详解见图
5.循环队列出队伪算法讲解
6.如何判断循环队列是否为空
如果front和rear的值相等，则该队列就一定为空。
7.如何判断循环队列是否为满
预备知识：
front的值可能比rear大，
也完全有可能比rear小，
当然也可能相等。
两种方式：
1.多增加一个标志位参数
2.少用一个元素【通常使用第二种元素】
队列中有n个元素，只要放到n-1个元素，即认为队列已满。
//2018/5/21
专题：递归
定义：一个函数自己直接或间接调用自己
递归满足的三个条件：
1.递归必须得有一个明确的终止条件
2.递归的值可以是递增的，但所处理的数据规模必须在递减
（n->n-1->n-2……）
3.这个转化必须是可解的
循环和递归
所有的循环都可以用递归实现，
但所有的递归不一定都可以用循环实现。
递归：循环：
易于理解不易理解速度慢速度快
存储空间大（步骤麻烦）存储空间小
n -> n-1 -> n-2 -> ……-> 1
举例：
1.求阶乘
2.1+2……+100的和
3.汉诺塔
4.走迷宫
递归的应用：
树和森林就是以递归的方式定义的
树和图的很多算法就是以递归来实现的
很多数学公式就是以递归的方式定义的(例如：斐波拉切数列)
线性结构总复习：
逻辑结构
线性 {数组链表}
栈和队列是一种特殊的线性结构，算线性结构的应用非线性 { 树图}
物理结构
//2018/5/22
模块二：非线性结构
树
定义：
专业定义：
1.有且只有一个称为根的节点
2.有若干个互补相交的子树，这些子树本身也是一棵树
通俗定义：
1.树是由节点和边组成
2.每个节点只有一个父节点但可以有多个子节点
3.但有一个节点例外，该节点没有父节点，此节点成为根节点。专业术语
节点父节点子节点子孙堂兄弟
深度：从根节点到最底层节点的层数称之为深度（根节点是第一层）
叶子节点：没有子节点的节点。
非终端节点：实际就是非叶子节点。
度：子节点的个数成为度。
分类：
一般树：任意一个节点的子节点的个数都不受限制
二叉树：任意一个节点的子节点的个数最多两个，且子节点的位置不可更改。
分类：
一般二叉树
满二叉树（完全二叉树的特例）
在不增加树的层数的前提下，无法再多添加
一个节点的二叉树就是满二叉树
完全二叉树（用数组存储树时，必须是完全二叉树）
如果只是删除了满二叉树最底层最后边的连续
若干个节点，这样形成的二叉树就是完全二叉
树。
优点：1.根据节点编号可以知道在第几层
2.可以知道父节点和子节点
森林：n个互不相交的树的集合
树的存储：
二叉树的存储
连续存储[将二叉树补充为完全二叉树]
以数组的形式存储时，如果根据只保存有效节点的形式，无
法推出全树的样子。
优点：查找某个节点的父节点和子节点（也包括判断有没有父节点和子
节点）速度很快。
缺点：耗用空间内存过大
链式存储
一般树的存储
双亲表示法（求父节点方便）
把每一个节点编号，然后在每一个节点后标记出其父节点的编号孩子表示法（求子节点方便）
把每一个子节点都写在每一个节点之后。
双亲孩子表示法（求父节点和子节点都方便）
把每一个节点编号，然后在每一个节点后标记出其父节点的编号，
再把每一个子节点写在之后。
二叉树表示法
把一个普通树转化为二叉树来存储。
具体转换方法：
设法保证任意一个节点的
左指针域指向它的第一个孩子
右指针域指向它下一个兄弟
只要满足此条件，就可以把一个普通树转化为二叉树
一个普通树转化成的二叉树一定没有右子树
森林的存储
先把森林转化为二叉树，再将二叉树存储
具体转换方法：
1.设法保证其他树的根节点当成第一颗树根节点的兄弟
2.设法保证其他任意一个节点的
左指针域指向它的第一个孩子
右指针域指向它下一个兄弟
只要满足此条件，就可以把一片森林转化为二叉树
操作：
遍历
先序遍历[先访问根节点][中左右] 先访问根节点
再先序访问左子树
再先序访问右子树
判断： 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）个节点
我本科在燕山大学，作为河北省的一个旅游城市，旅游季节超级多以外，真的没有开拓我太多眼界，但是鉴于老师负责而且很专业，教会了我很多知识。但是我们专业，在一二线城市，机会多，企业多，就业及科研合作机会也多，所以，选择学校，一定要先看城市，再选学校。对我而言，研究生考进北科大，也是一项很大的挑战和提升。下面是我整理的一些考研经验与心得，希望能助你一臂之力，早日考进自己理想的学校。 数学： 对于计算机科技而言，数学很重要。我们专业是以数学逻辑为基础的，数据结构是建立在数学基础之上的一门学科。可以说，数学是我们的工具书。数学真的很重要。要从3月份就开始复习，这样后面会比较轻松。建议先从基础教材着手，看完教材，要做课后练习题，测试自己是否掌握了本章节的知识。这样，高数和线性代数的课本过一遍，需要2-3个月的时间。第二阶段就要做大量的练习了，研数盒子，这个公众号的特点是习题为主，数学一定要多加练习，这个公众号就是以练习各种习题为主，每周都会发各种作业和讲解，研数盒子有一套教材叫做研数800题非常好。做的过程中，对错题要着重注意并记录一下，建立一个错题本，然后针对没做对的题，分析归纳，然后回归到课本上，查到对应章节，重新温习。这套练习要刷个3遍左右，每一遍你都会有新的认识和体会，个人觉得效果会比做3套不同的题更有效。3遍下来，精读的效果就很明显了，这就是“温故知新”的道理。10月开始，真题要开始做起来了，向上面一样，建立错题本，这个本会是你考研备考后期独一无二的宝典。总之，数学真的很重要，要自始至终坚持到底，除了反复多加练习，还要多思考。 英语： 阅读理解很重要，备考需要坚持每天2篇阅读，开始的时候要精度，好好分析一下句式，掌握好主谓宾从，整段意思也就很容易理解了。学会分析句式以后，后续就会容易很多。再就是单词部分，买一本基础的单词书<<一本单词>>，早晨背完，晚上回忆，过电影一样的，重要的单词，要熟悉到知道在哪个位置，上面的解释是什么。没事看看，不想看书的时候看看，随手看看，遍数多了，自然会记住了，或者每个考生都有自己独特的单词记忆方法，请大家用尽十八般武艺，只有一个目的——背好单词，大家也可以关注蛋核英语公众号。再说说作文，作文呢，一定要积累名言警句，有华丽的辞藻才能表达出自己的观点对不对？作文
郝斌数据结构自学笔记 --知识点+程序源代码 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)。 时间复杂度的分析计算请看书本上的例子，然后我们通过做练习加以领会和巩固。 数据结构习题一 --------------------------------------------------------------------------------
※特别章外部排序（2012版《数据结构高分笔记》更新补丁） ·外部排序简介 所谓外部排序，即对外存中的数据进行排序（相对于内部排序而言），也可以说是对文件中的数据进行排序。有了内部排序算法，为什么还要外部排序？因为文件太大，内存放不下。外排做法可以概括为一句话：将内存作为工作空间来调整外存中数据的位置。 具体可以分成以下三个要点： ①文件在外存中的组织； ②文件在内存中的排序； ③文件在内外存之间的交换。 说明：本补丁是2012年数据结构考研大纲新增内容，虽然知识点不多，但由于第一年被列入考试范围，所以大家要重视。 ·归并排序法 归并排序法是外排序中最常用的方法，分为两个执行阶段。第一阶段：将文件中的数据分段输入到内存中，在内存中用内排序方法对其分类，这样排序完的文件段称作归并段，然后将其写回外存中而在外存中形成了许多初始归并段。第二阶段：对这些初始归并段采用某种归并方法，进行多遍归并，最后在外存上形成整个文件的单一归并段，也就完成了这个文件的外排序。 说明：外排序中的归并排序法和内排序中的归并法是类似的，都是由小单元逐渐归并成单元的过程，注意对比，加深理解。 归并排序算法分两个阶段： 1.初始归并段的形成 其过程是根据缓冲区大小，由文件输入（由外存读入内存）记录，当记录充满缓冲区后，选择最小的（以递增排序为例）记录输出（由内存写出到外存），其空缺位置由下一个输入记录来取代，输出的记录成为当前初始归并段的一部分。如果新输入的记录不能成为当前生成的归并段的一部分，即它比生成的当前部分归并段最大的记录要小（如例1中的关键字11，比15要小，不可能出现在当前归并段中），它将等待生成下一个归并段时提供选择。反复进行上述操作，直到所有新输入的记录关键字都小于最后输出记录的关键字时（如步骤9中的所有关键字都比83小，则以83为结尾的归并段生成完毕），就生成了一个初始归并段。接着继续生成下一个归并段，直到全部记录都处理完毕为止。 下面通过例题来具体说明一下。 例1.设输入文件的各个记录的关键字为： 15,19,04,83,12,27,11,25,16,34,26,07,10,90,06, ... ... 假设内存缓冲区可容纳4个记录，成初始归并段。如下表所示，给出了生成初始归并段过程中各步的缓冲区内容和输出结果。
数据结构学习总结 经过一学期的学习，我对数据结构有了我自己的认识。一开始，我以为它和C语言和C++一样，都是讲一门语言。但学习之后，发现事实并不是这样，在数据结构的学习中，有线性表，有队，有栈，有树，有图等等。这些看起来没有关系，其实之间有着千丝万缕的联系。线性表是其中最简单的，所以在前几章学习，后面依次逐章变难，学起来也很吃力。 《数据结构与算法》以基本数据结构和算法设计策略为知识单元，系统地介绍了数据结构的知识与应用、计算机算法的设计与分析方法，主要内容包括线性表、树、图和广义表、算法设计策略以及查找与排序算法等。 线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。线性表具有如下的结构特点：均匀性：虽然不同数据表的数据元素可以是各种各样的，但对于同一线性表的各数据元素必定具有相同的数据类型和长度。有序性：各数据元素在线性表中的位置只取决于它们的序号，数据元素之前的相对位置是线性的，即存在唯一的“第一个“和“最后一个”的数据元素，除了第一个和最后一个外，其它元素前面均只有一个数据元素直接前驱和后面均只有一个数据元素（直接后继）。在实现线性表数据元素的存储方面，一般可用顺序存储结构和链式存储结构两种方法。链式存储结构将在本网站线性链表中介绍，本章主要介绍用数组实现线性表数据元素的顺序存储及其应用。另外栈、队列和串也是线性表的特殊情况，又称为受限的线性结构。 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生
第一章概论 1.数据：信息的载体,能被计算机识别、存储和加工处理。 2.数据元素：数据的基本单位，可由若干个数据项组成，数据项是具有独立含义的最小标识单位。 3.数据结构：数据之间的相互关系，即数据的组织形式。 它包括：1）数据的逻辑结构，从逻辑关系上描述数据，与数据存储无关，独立于计算机； 2）数据的存储结构，是逻辑结构用计算机语言的实现，依赖于计算机语言。 3）数据的运算，定义在逻辑结构上，每种逻辑结构都有一个运算集合。常用的运算：检索/插入/删除/更新/排序。 4.数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的存储结构是逻辑结构用计算机语言的实现。 5.数据类型：一个值的集合及在值上定义的一组操作的总称。分为：原子类型和结构类型。 6.抽象数据类型：抽象数据的组织和与之相关的操作。优点：将数据和操作封装在一起实现了信息隐藏。 7. 抽象数据类型ADT：是在概念层上描述问题；类：是在实现层上描述问题；在应用层上操作对象（类的实例）解决问题。 8.数据的逻辑结构，简称为数据结构，有： （1）线性结构，若结构是非空集则仅有一个开始和终端结点，并且所有结点最多只有一个直接前趋和后继。 （2）非线性结构，一个结点可能有多个直接前趋和后继。 9.数据的存储结构有： 1）顺序存储，把逻辑相邻的结点存储在物理上相邻的存储单元内。 2）链接存储，结点间的逻辑关系由附加指针字段表示。 3）索引存储，存储结点信息的同时，建立附加索引表，有稠密索引和稀疏索引。 4）散列存储，按结点的关键字直接计算出存储地址。 10.评价算法的好坏是：算法是正确的；执行算法所耗的时间；执行算法的存储空间（辅助存储空间）；易于理解、编码、调试。
第八章死锁习题及答案 一、填空题 1．进程的“同步”和“互斥”反映了进程间① 和② 的关系。 【答案】①直接制约、②间接制约 【解析】进程的同步是指在异步环境下的并发进程因直接制约而互相发送消息，进行相互合作、相互等待，使得各进程按一定的速度执行的过程；而进程的互斥是由并发进程同时共享公有资源而造成的对并发进程执行速度的间接制约。 2．死锁产生的原因是① 和② 。 【答案】①系统资源不足、②进程推进路径非法 【解析】死锁产生的根本原因是系统的资源不足而引发了并发进程之间的资源竞争。由于资源总是有限的，我们不可能为所有要求资源的进程无限地提供资源。而另一个原因是操作系统应用的动态分配系统各种资源的策略不当，造成并发进程联合推进的路径进入进程相互封锁的危险区。所以，采用适当的资源分配算法，来达到消除死锁的目的是操作系统主要研究的课题之一。 3．产生死锁的四个必要条件是① 、② 、③ 、 ④ 。 【答案】①互斥条件、②非抢占条件、③占有且等待资源条件、④循环等待条件 【解析】 互斥条件：进程对它所需的资源进行排它性控制，即在一段时间内，某资源为一进程所独占。 非抢占条件：进程所获得的资源在未使用完毕之前，不能被其它进程强行夺走，即只能由获得资源的进程自己释放。 占有且等待资源条件：进程每次申请它所需的一部分资源，在等待新资源的同时，继续占有已分配到的资源， 循环等待条件：存在一进程循环链，链中每一个进程已获得的资源同时被下一个进程所请求。 4．在操作系统中，信号量是表示① 的物理实体，它是一个与② 有关的整型变量，其值仅能由③ 原语来改变。 【答案】①资源，②队列，③P-V 【解析】信号量的概念和 P-V原语是荷兰科学家 E．W．Dijkstra提出来的。信号量是一个特殊的整型量，它与一个初始状态为空的队列相联系。信号量代表了资源的实体，操作系统利用它的状态对并发进程共享资源进行管理。信号量的值只能由P-V原语来改变。 5．每执行一次P原语，信号量的数值S减1。如果S>=0，该进程① ；若S<0，则② 该进程，并把它插入该③ 对应的④ 队列中。 【答案】①继续执行，②阻塞（等待），③信号量，④阻塞（等待） 【解析】从物理概念上讲，S＞0时的数值表示某类资源可用的数量。执行 一次P原语，意味着请求分配一个单位的资源，因此描述为S=S－1。当S<0时，表示已无资源，这时请求资源的进程将被阻塞，把它排在信号量S的等待队列中。此时，S的绝对值等于信号量队列上的阻塞的进程数目。
数据结构及算法知识 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）。
2018北大计算机考研经验分享 我本科毕业于北京科技大学计算机科学与技术专业，研究生将就读于北京大学计算机技术专业。初试考研总分接近370+分，计算机基础综合135分，在专业课上算是有些心得吧。 写这篇经验贴的初衷一是看过很多经验贴，都是比较散乱的回顾+感受，没有系统的复习方法；二是我在新祥旭考研一对一做专业课辅导老师，算是给自己打个广告吧，多说一句，我主要是针对考北大计算机专业的学生。当然，虽然打了一下广告，但是这篇帖子的经验还是希望大家认真看，我觉得还是能够对学弟学妹们有所裨益的。 ，下面主要和大家聊一聊北大计算机考研的情况，政治、英语、数学这些课我就不多说了，这几门课程的资料、老师都是比较成熟且成功的，大家在网上多看看就知道怎么回事了。今天，主要是说专业课以及北大计算机的招录情况。 【北大招录情况】 2018年北大软微计算机技术复试线：复试线为300分，单科线也是50+80。具体的招录比现在基本是没有相关数据的，但是招生人数还是可查的，根据软微学院官网数据：整个软件与微电子学院招收全日制654人，非全日制156人。其中计算机技术专业全日制招生310人，
包含推免生接近70人，留给其他考生的名额为240左右。 总之，现在是大数据时代，北大计算机技术的关注度也越来越高，所以以后考研竞争难度也会越来越大。 【参考书目】 822计算机基础综合 专业课教材 《数据结构》（C语言版）严蔚敏清华大学出版社 《计算机操作系统》汤子瀛西安电子科技大学出版社 《计算机网络》谢希仁电子工业出版社 《计算机组成原理》唐朔飞高等教育出版社 专业辅导书： 王道系列 《数据结构考研复习指导》 《计算机组成原理考研复习指导》 《操作系统考研复习指导》 《计算机网络考研复习指导》 《计算机专业基础综合考试指导全书》 《计算机专业基础综合考试名校真题精析》 《计算机专业基础综合考试最后8套模拟题》
第一章操作系统引论 1、Android DOS LINUX WINDOWS Symbian iOS UNIX CentOS是操作系统 2、计算机系统的组成 计算机系统：计算机硬件：运算器、控制器、存储器、输入设备、输出设备 计算机软件：包括操作系统 3、相关概念 裸机：没有配置任何软件的计算机。 软件:是在硬件基础之上对硬件的性能加以扩充和完善。 虚拟机：一个裸机在每加上一层软件后，就变成了一个功能更强的机器，我们把这种“功能更强的机器”称之为“虚拟机”或“扩展机”。 4、操作系统的定义 操作系统（operating system，简称OS）操作系统是一组控制和管理计算机硬件和软件资源，合理地对各类作业进行调度，以及方便用户使用的程序的集合。操作系统是系统软件的核心。 5、操作系统的目标 （1）.方便性：用户通过命令使用计算机 （2）.有效性：保持忙碌且内外存数据有序,节省空间 （3）.可扩充性：采用层次化结构便于增加和修改 （4）.开放性：遵循OSI国际标准彼此兼容实现互连 6、操作系统的作用 （1）OS作为用户与计算机硬件系统的接口 （2）OS作为计算机系统资源的管理者 （3）OS用作扩充机器 7、推动操作系统发展的主要动力 ?不断提高计算机资源利用率 ?方便用户 ?器件的不断更新换代 ?计算机体系结构的不断发展 ?不断的提出新的要求 8、计算机的发展过程 计算机发展分为四个阶段： ?1946～50年代末：第一代，电子管时代，无操作系统。 ?50年代末～60年代中：第二代，晶体管时代，批处理系统。 ?60年代中～70年代中：第三代：集成电路时代，多道程序设计。 ?70年代中期～至今：第四代：大规模、超大规模集成电路时代，分时系统。 9、操作系统的发展过程 （1）. 人工操作方式 电子管计算机，无操作系统，由手工控制作业的输入输出,通过控制台开关启动 程序运行。 人工操作方式的缺点： 用户独占全机。计算机及其全部资源只能由上机用户独占。
第一张概论 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.3 存储实现和运算实现 由于逻辑结构是设计人员根据解题需要选定的数据组织形式，因此存储实现建立的机内表示应遵循选定的
操作系统考研考试范围和重点 基本要求： 1、考研题目大致分为两种类型，一类是基本概念、技术和方法（即问答题），一类是基本原理的综合应用（即应用题）。P、V操作题肯定考。 2、一般说来，具体操作系统如Windows、Linux/Unix不考，但讲解原理时引用的UNIX实现方法还要考（主要集中在4-6章）。 3、内容：1-9章，重点4-6章。 4、考试的思路两方面兼顾：灵活运用与知识点的全面掌握 说明：蓝色表示重要概念、技术和方法，绿色表示应用。 第1章操作系统概述 ●资源、资源管理的观点 ●操作系统、操作系统的地位和作用、操作系统的特征、操作系统的设计目标 ●历史上著名的操作系统 ●研究操作系统的观点 ●操作系统分类（工作方式，特点，追求目标，与其它类型的区别，吞吐量，时间片） 第2章操作系统的硬件环境 ●CPU状态，管态和目态，程序状态字 ●存储体系 ●缓冲技术 ●中断系统 ●中断、中断源、中断类型（强迫性中断[硬件故障中断、程序性中断、时钟中断、控制 台中断、输入输出中断]，自愿性中断） ●中断响应（中断寄存器，程序状态字，中断响应过程） ●中断处理、各类中断事件的处理 中断优先级、中断屏蔽、中断嵌套处理 ●时钟 第3章作业管理 ●用户与操作系统的接口（操作员级接口，程序员级接口） ●批处理系统作业管理（作业组成，作业控制语言，作业说明书，作业输入[预输入程序， 数入井，作业表，预输入表，收容状态]，作业调度，作业调度的必要条件，设计作业调度算法的准则，作业调度算法[先来先服务，短作业优先，最高响应比优先，优先数，均衡调度]，作业调度与进程调度的关系，作业的控制执行过程，作业的完成[缓输出程序，输出井]）
全国2010年1月高等教育自学考试 数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未 选均无分。 1.下述文件中适合于磁带存储的是（ A ） A.顺序文件 B.索引文件 C.散列文件 D.多关键字文件 2.某二叉树的后根遍历序列为dabec，中根遍历序列为debac，则先根遍历序列为（ D ） A.acbed B.becab C.deabc D.cedba 3.含有n个结点的二叉树用二叉链表表示时，空指针域个数为( C ) A.n-1 B.n C.n+1 D.n+2 注：子域为2n个，有n-1个孩子。 4.在一个图中，所有顶点的度数之和与图的边数的比是( C) A.1∶2 B.1∶1 C.2∶1 D.4∶1 5.长度为n的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为( A) A.O(1) B.O(1og2n) 二分法注：若只有尾指针，那么入和出都为O(1) C.O(n) （入队） D.O(n2) -冒泡 6.下述几种排序方法中，要求内存量最大的是( C ) A.插入排序 B.快速排序 C.归并排序 D.选择排序 7.对n个不同值进行冒泡排序，在元素无序的情况下比较的次数为( D) A.n-1 B.n C.n+1 D.n(n-1)／2 8.对线性表进行二分查找时，要求线性表必须( C) A.以顺序方式存储 B.以链式方式存储 C.以顺序方式存储，且结点按关键字有序排列 D.以链接方式存储，且结点按关键字有序排列 9.在表长为n的顺序表上做删除运算，其平均时间复杂度为( B ) A.O(1) B.O(n) 注：在双向循环链表中，删除最后一个结点 C.O(nlog2n) D.O(n2) 的时间复杂度为O(1)
： 第一张概论 引言 两项基本任务：数据表示，数据处理 软件系统生存期：软件计划，需求分析，软件设计，软件编码，软件测试，软件维护 由一种逻辑结构和一组基本运算构成的整体是实际问题的一种数学模型，这种数学模型的建立，选择和实现是数据结构的核心问题。 机外表示------逻辑结构------存储结构 ~ 处理要求-----基本运算和运算-------算法 数据，逻辑结构和运算 数据：凡是能够被计算机存储，加工的对象通称为数据 数据元素：是数据的基本单位，在程序中作为一个整体加以考虑和处理。又称元素，顶点，结点，记录。 数据项：数据项组成数据元素，但通常不具有完整确定的实际意义，或不被当做一个整体对待。又称字段或域，是数据不可分割的最小标示单位。 — 1.2.2 数据的逻辑结构 逻辑关系：是指数据元素之间的关联方式，又称“邻接关系” 逻辑结构:数据元素之间逻辑关系的整体称为逻辑结构。即数据的组织形式。 四种基本逻辑结构： 1 集合：任何两个结点间没有逻辑关系，组织形式松散 2 线性结构：结点按逻辑关系依次排列成一条“锁链” 3 树形结构：具有分支，层次特性，形态像自然界中的树 { 4. 图状结构：各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接。 注意点: 1.逻辑结构与数据元素本身的形式，内容无关。 2.逻辑结构与数据元素的相对位置无关 3.逻辑结构与所含结点个数无关。 运算：运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。 。 加工型运算：改变了原逻辑结构的“值”，如结点个数，结点内容等。 引用型运算:不改变原逻辑结构个数和值，只从中提取某些信息作为运算的结果。 引用：查找，读取 加工：插入，删除，更新 同一逻辑结构S上的两个运算A和B, A的实现需要或可以利用B，而B的实现不需要利用A，则称A可以归约为B。
//2018/5/23 数据结构概述： 预备知识 模块一：线性结构 连续存储[数组] 离散结构[链表] 线性结构的两种常见应用之一栈（堆栈） 线性结构的两种常见应用之二队列 专题：递归 1.1+ 2......+100的和 2.求阶乘 3.汉诺塔 4.走迷宫 模块二：非线性结构 树 图 模块三：查找和排序 折半查找 排序：冒泡插入选择快速排序归并排序补录：Java中容器和数据结构相关知识 Iterator接口 Map 哈希表 严蔚敏---高一凡---黄国瑜
//2018/5/24 数据结构概述 定义 我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器（内存）中，以及在此基础上为实现某个功能（比如查找或删除某个元素，对所有元素进行排序）而执行的相应操作，这个相应操作叫做算法。 特定的数据类型:个体如何保存 特定的存储结构:个体与个体的关系如何保存 数据结构 = 个体的存储 + 个体关系的存储 算法（狭义） = 对存储数据的操作 算法：即解题的方法和步骤 衡量算法的标准 1.时间复杂度[重要] 大概程序要执行的次数，而非执行的时间 2.空间复杂度[重要] 算法执行过程中大概所占用的最大内存 3.难易程度 4.健壮性 数据结构的地位 数据结构是软件中最核心的课程。 程序 = 数据的存储 + 数据的操作 + 可以被计算机执行的语言
预备知识： 指针 结构体 动态内存的分配和释放 指针： 指针的重要性: 表示一些复杂的数据结构 快速的传送数据 使函数返回一个以上的值 能否直接访问硬件 能够方便的使用数组和字符串 是理解面向对象语言中引用的基础 指针是C语言的灵魂 定义 地址 内存单元的编号 从0开始的非负整数 范围0-FFFFFFFF 【0 到 4G-1】 注：无论一个变量有多大，其地址只用第一个字节的地址表示， 均只占四个字节。 指针 指针就是地址地址就是指针 指针变量就是存放内存单元地址的变量 指针本质上就是一个操作受限的非负整数 分类
“数据结构”读书笔记示例：第2章线性表 学习线索：逻辑结构→基本运算定义→存储结构→基本运算实现（复杂度分析→应用实例） 1. 逻辑结构：是由n(n≥0)个数据元素组成的有限序列。 2. 基本运算定义：（P.16） （1）Init_List(L)，线性表初始化； （2）Length _ List (L)，求线性表的长度； （3）Get_ List (L，i)，取表元； （4）Locate_ List (L，x)，按值查找； （5）Insert_ List (L，x，i)；插入操作； （6）Delete_ List (L，i)，删除操作。 3. 存储结构： （1）顺序表：把线性表的结点按逻辑次序存放在一组地址连续的存储单元里。 顺序存储的结构体定义： typedef struct { datatype data[MAXSIZE]; /* 一维数组子域*/ int last; /* 表长度子域*/ } SeqList; /* 顺序存储的结构体类型*/ 4-1. 顺序表的基本运算的实现（算法及其复杂度分析、应用实例：顺序表的划分、合并、比较大小） （2）单链表：只有一个链域的链表称单链表。 结点结构： Data（节点值）Next（后继结点地址） 其中data是数据域，next是指针域 链式存储的结构体定义： typedef struct lnode { datatype data; /* 数据子域*/ struct lnode *next; /* 指针子域*/ } LNode，*LinkList; /* 链式存储的结点结构类型*/ 4-2. 单链表的基本运算的实现（算法及其复杂度分析、应用实例：链表逆置、归并） 单链表的发展：循环链表、双向链表 顺序表和链表的比较 1）基于空间： 2）基于时间：“数据结构”读书笔记（线性结构部分）
[整理][郝斌老师]自学数据结构大纲笔记 [郝斌老师]自学数据结构大纲笔记 数据结构概述(教材选用严蔚敏、吴伟民，该书程序是伪算法 具体的程序是高一凡，西电的，大牛，只有 程序。还有一本书，台湾的黄国瑜自己写的 只有思路，程序是另外一个合作的清华的写 的，可惜很多错的。) 学完数据结构之后会对面向过程的函数有一个更深的了解 定义 我们如何把现实中大量而复杂的问题以特定的数据类型(单 个数据怎样存储,)和特定的存储结构(个体的关系) 保存到主存储器(内存)中，以及在此基础上为实现某个功能 (比如查找某个元素，删除某个元素，对所有元素进行排序) 而执行的相应操作，这个相应的操作也叫算法。(比如班里有 15个人，其信息量也许一个数组就搞定了，但是假如10000个， 怎么办,内存也许没有这么多连续的空间，所以我们改用链表， you see这就是与存储有关系。又比如，人事管理系统的信息存储， 因为存在着上下级的关系，所以数组和链表就无能为力了， 这时候我们用树，再比如我们做的是交通图，站和站之间肯定要连通，这时候以上的存储方式又无能为力了，所以我们又有了图。图 就是每个结点都可以和其他结点产生联系。所以当我们要解决 问题时，首先要解决的是如何把这些问题转换成数据，先保存 到我们的主存中，)
数据结构 = 个体 + 个体的关系 算法 = 对存储数据的操作 算法 解题的方法和步骤 衡量算法的标准 1、时间复杂度 大概程序要执行的次数，而非执行的时间。 2、空间复杂度 算法执行过程中大概所占用的最大内存 3、难易程度(主要是应用方面看重) 4、健壮性(不能别人给一个非法的输入就挂掉) 数据结构的地位 数据结构是软件中最核心的课程 程序 = 数据的存储，数据的操作，可以被计算机执行的语言(已经提供) (学完数据结构，想用一种语言去实现它，必须有指针，数据结构java 版，就胡扯，变味，因为我们要讲链表，就是通过指针链在一起的。比如在java中A aa = new A();本质上，aa是个地址) 预备知识 指针 指针的重要性:(内存是可以被CPU直接访问的，硬盘不行 主要靠地址总线，数据总线，控制总线。) 指针是C语言的灵魂 定义 地址
数据结构复习笔记 一、绪论 1.数据：能被计算机表示、存储和加工处理的一切信息（数值型和非数值型） 2.数据的基本单位：数据元素 3.组成数据元素的不可分割的最小单位：数据项 4.数据对象：性质相同的数据元素的集合 5.数据类型：指定一种数据对象的类型 6.数据的逻辑结构：指数据之间的逻辑关系, 即指数据元素之间的关联方式或邻接关系 7.数据的存储结构：指数据在计算机中存储的位置 8.运算的集合：定义在逻辑结构上的一组操作 9.数据结构: 按照某种逻辑关系组织起来的一批数据, 按一定的存储方法把它存储在计算机中, 并在这些数据上定义了一个运算的集合 10.逻辑结构分类：线性结构、集合、树形结构、图型或网状结构 11.线性结构：仅一个开始结点、仅一个终端结点；其它都是内部结点，且都有且仅有一个前驱和一个后驱（一对一） 12.集合：结构中数据元素只具有“同属于一个集合”的关系 13.树型结构的特点：有且仅有一个根结点，其它结点有且仅有一个前驱结点，对于非根结点都存在从根到该结点的一条路径（一对多） 14.图型结构的特点：结构中的数据元素存在多对多的关系 15.存储结构：顺序存储结构、链式存储结构 16.顺序存储结构特点：逻辑结构上相邻的两个元素在物理结构上也相邻. 即前驱的结束是后继的开始 17.链式存储结构：存储空间不连续，但保持了逻辑关系 18.算法的五个特征：有穷性、确定性、可行性、输入、输出 19.算法与程序的区别：程序不一定满足有穷性；程序是机器可执行的语言编写的 20.算法评价：正确、简单、可读、健壮、高效 21.算法分析方法：事后统计和事前分析、时间复杂度和空间复杂度 22.影响算法时间代价的因素：输入规模、算法效率、输入顺序、机器、设计者 23.Ο(1)＜O(log2n)＜O (n)＜O (nlog2n)＜O (n2)＜O (n3)＜…＜O (2n)＜O (n!) 二、线性表 1.线性结构特点：唯一第一数据元素、唯一最后数据元素、其他数据元素仅有一个前趋和仅有一个后驱 2.顺序表的优点：无需为表示数据元素之间的逻辑关系而增加额外存储空间；可方便地随机存取表中任一元素 3.顺序表的缺点：预先为数据元素分配空间；插入和删除时必须移动大量元素 4.单链表的插入：newnode→next = p→next；p→next = newnode 5.单链表的删除：p→next = q→next；delete q 6.双向链表的删除：current ->prior->next= current ->next；current ->next->prior= current ->prior；delete current 7.双向链表的插入：p->prior=current；p->next= current ->next；current->next->prior=p；current->next=p 8.顺序表与链表：顺序表结点总数大概确定，表中结点数目稳定（插删操作少）；链表结点数目不预知且动态变化 三、栈和队列 1.栈的逻辑结构：允许插入和删除的一端称为栈顶，另一端称为栈底，特点是后进先出或先进后出 2.先进后出题：若abc顺序入栈，a入栈后可以直接出栈 3.队列的逻辑结构：在一端进行插入操作（队尾），而另一端进行删除操作的线性表（队头），特点是先进先出 4.队满判定条件：(rear+1) % QueueSize==front