第一章概论。
1．数据元素是数据的基本单位，可有若干数据项组成，数据项是具有独立含义的最小标识单位，数据对象是具有相同性质的数据元素的集合，是数据的子集。
2. 数据结构是带有结构的数据元素的集合，一般包括以下三方面内容：数据的逻辑结构、数据的存储结构、数据的运算。
数据元素之间的逻辑关系，也称数据的逻辑结构，数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。
数据元素及其关系在计算机存储器内的表示，称为数据的存储结构。
数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。
数据的运算，即对数据施加的操作。最常用的检索、插入、删除、更新、排序等。
3. 数据的逻辑结构分类： 线性结构和非线性结构。
线性结构：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。
线性表是一个典型的线性结构。栈、队列、串等都是线性结构。
非线性结构：一个结点可能有多个直接前趋和直接后继。
数组、广义表、树和图等数据结构都是非线性结构。
4. 数据的四种基本存储方法： 顺序存储方法、链接存储方法、索引存储方法、散列存储方法。
1）顺序存储方法：
该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。通常借助程序语言的数组描述。
2）链接存储方法：
该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。通常借助于程序语言的指针类型描述。
3）索引存储方法：
该方法通常在储存结点信息的同时，还建立附加的索引表。
索引表由若干索引项组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引，稠密索引中索引项的地址指示结点所在的存储位置。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引稀疏索引中索引项的地址指示一组结点的起始存储位置。
索引项的一般形式是：(关键字、地址)
关键字是能唯一标识一个结点的那些数据项。
4）散列存储方法：
该方法的基本思想是：根据结点的关键字直接计算出该结点的存储地址。
5. 数据类型是一个值的集合和定义在这个值上的一组操作的总称。可分为：
原子类型和结构类型。抽象数据类型(adt):是指抽象数据的组织和与之相关的操作。
可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。
6. 算法+数据结构=程序。
数据结构：是指数据的逻辑结构和存储结构。
算法：是对数据运算的描述。
算法的5个准则：输入（0或多个输入）、输出（至少有1个或多个输出）、有穷性（每一条指令执行次数是有限的）、确定性（每一条指令的含义必须明确，无二义性）、可行性（算法描述的操作可以通过有限次的基本运算来实现）。
7. 常见的时间复杂度按数量级递增排列依次为：常数0(1)、对数阶0(log2n)、线形阶0(n)、线形对数阶0(nlog2n)、平方阶0(n2)立方阶0(n3)、…k次方阶0(nk)、指数阶0(2n)。
第二章线性表。
4. 顺序存储方法：把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法。
顺序表（sequential list）：用顺序存储方法存储的线性表简称为顺序表。顺序表是一种随机存取结构，顺序表的的特点是逻辑上相邻的结点其物理位置亦相邻。
5. 顺序表中结点ai 的存储地址： loc（ai）= loc（a1）+（i-1）*c 1≤i≤n，
算法的时间主要花费在for循环中的结点后移语句上。该语句的执行次数是n-i+1，在表中第i个位置插入一个结点的移动次数为n-i+1，当i=n+1：移动结点次数为0，即算法在最好时间复杂度是o(1)，当i=1：
移动结点次数为n，即算法在最坏情况下时间复杂度是o(n)
即在顺序表上进行插入运算，平均要移动一半结点（n/2）。
结点的移动次数由表长n和位置i决定：i=n时，结点的移动次数为0，即为0(1)，i=1时，结点的移动次数为n-1，算法时间复杂度分别是o(n)
顺序表上做删除运算，平均要移动表中约一半的结点（n-1）/2，平均时间复杂度也是o(n)。
10. 建立单链表：
1） 头插法建表：从一个空表开始，重复读入数据，生成新结点，将读入数据存放在新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。
2） 尾插法建表：从一个空表开始，重复读入数据，生成新结点，将读入数据存放在新结点的数据域中，然后将新结点插入到当前链表的表尾上，直到读入结束标志为止。
3） 尾插法建带头结点的单链表：
头结点及作用：头结点是在链表的开始结点之前附加一个结点。它具有两个优点：
⒈由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其它位置上操作一致，无须进行特殊处理；
⒉无论链表是否为空，其头指针都是指向头结点的非空指针（空表中头结点的指针域空），因此空表和非空表的处理也就统一了。
头结点数据域的阴影表示该部分不存储信息。在有的应用中可用于存放表长等附加信息。
以上三个算法的时间复杂度均为o(n)。
11.单链表上的查找：
1）链表不是随机存取结构。
在链表中，即使知道被访问结点的序号i，也不能像顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直至搜索到第i个结点为止。因此，链表不是随机存取结构。
2）查找的思想方法。
计数器j置为0后，扫描指针p指针从链表的头结点开始顺着链扫描。当p扫描下一个结点时，计数器j相应地加1。当j=i时，指针p所指的结点就是要找的第i个结点。
而当p指针指为null且j≠i时，则表示找不到第i个结点。头结点可看做是第0个结点。
时间复杂度：在等概率假设下，平均时间复杂度为：为n/2=o(n)
2） 按值查找：
时间复杂度为：o(n)
12.插入运算：插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。
算法的时间主要耗费在查找操作getnode上，故时间复杂度亦为o(n)。
13. 删除运算。
删除运算是将表的第i个结点删去。
具体步骤：
算法的时间复杂度也是o（n）。
链表上实现的插入和删除运算，无须移动结点，仅需修改指针。
14.单循环链表——在单链表中，将终端结点的指针域null改为指向表头结点或开始结点即可。判断空链表的条件是head==head->next;
15. 仅设尾指针的单循环链表： 用尾指针rear表示的单循环链表对开始结点a1和终端结点an查找时间都是o(1)。
而表的操作常常是在表的首尾位置上进行，因此，实用中多采用尾指针表示单循环链表。判断空链表的条件为rear==rear->next;
16.循环链表：循环链表的特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。
若在尾指针表示的单循环链表上实现，则只需修改指针，无须遍历，其执行时间是o(1)。
循环链表中没有null指针。涉及遍历操作时，其终止条件就不再是像非循环链表那样判别p或p-＞next是否为空，而是判别它们是否等于某一指定指针，如头指针或尾指针等。
在单链表中，从一已知结点出发，只能访问到该结点及其后续结点，无法找到该结点之前的其它结点。而在单循环链表中，从任一结点出发都可访问到表中所有结点，这一优点使某些运算在单循环链表上易于实现。
17. 双向链表： 双（向）链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还增加一个指向其直接前趋的指针域prior。
双链表由头指针head惟一确定的。
带头结点的双链表的某些运算变得方便。
将头结点和尾结点链接起来，为双（向）循环链表。
18.双向链表的前插和删除本结点操作。
双链表的前插操作。
双链表上删除结点*p自身的操作。
与单链表上的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算法的时间复杂度均为o(1)。
第三章栈和队列。
3. 进栈操作：进栈时，需要将s-＞top加1，s-＞top==stacksize-1表示栈满。
"上溢"现象--当栈满时，再做进栈运算产生空间溢出的现象。
退栈操作：退栈时，需将s-＞top减1
s-＞top<0表示空栈。
"下溢"现象--当栈空时，做退栈运算产生的溢出现象。
下溢是正常现象，常用作程序控制转移的条件。
4. 两个栈共享同一存储空间：
当程序中同时使用两个栈时，可以将两个栈的栈底设在向量空间的两端，让两个栈各自向中间延伸。当一个栈里的元素较多，超过向量空间的一半时，只要另一个栈的元素不多，那么前者就可以占用后者的部分存储空间。
当top1=top2-1时，栈满。
5. 链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。
链栈中的结点是动态分配的，所以可以不考虑上溢，无须定义stackfull运算。
6. 队列（queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。
允许删除的一端称为队头（front），允许插入的一端称为队尾（rear），当队列中没有元素时称为空队列，队列亦称作先进先出（first in first out）的线性表，简称为fifo表。
7. 队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。
顺序队列的基本操作。
1 入队时：将新元素插入rear所指的位置，然后将rear加1。
②出队时：删去front所指的元素，然后将front加1并返回被删元素。
当头尾指针相等时，队列为空。
在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。
8. 顺序队列中的溢出现象：
当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。
当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。
"假上溢"现象：由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。
该现象称为"假上溢"现象。
数据结构复习提纲
软件学院数据结构与算法复习提纲。data structures and algorithms 概念 type,类型 一组值的集合。type,简单类型例如整数，因为它的值不含有子结构。aggregate type,复杂类型，一个记录含有多项信息。银行账户含有多项信息如姓名 地址 composite t...
数据结构复习提纲
第一章概论 1 数据结构的基本概念和术语。数据 数据元素 数据项 数据对象 数据结构等基本概念。数据结构的逻辑结构，存储结构及数据运算的含义及其相互关系。数据结构的四种逻辑结构及四种常用的存储表示方法。第二章算法分析技术。1 算法的描述和分析。无穷大阶的几种描述方法的区别。算法 算法的时间复杂度和空...
数据结构复习提纲
第一部分试题说明。1 试卷考试时间为90分钟。2 试题类型 选择题 20个，每题2分，共40分 简答题 6个，每题5分，共30分 和算法设计题 2个，每题15分，共30分 第二部分各章知识点。第1章绪论。1 数据结构的概念。2 数据结构的形式化表示方法 ds d，r 要求给定一个形式化表示，能够画出...