第一章数据结构与算法。
1.1算法。
（1）算法的有穷性是指：指算法必须能在执行有限个步骤之后终止；
（2）算法是解决问题的步骤。而程序是对问题的具体**实现。算法依靠程序来完成功能。
（3）算法的空间复杂度是指：一个算法在运行过程中临时占用存储空间的大小。
（4）算法的时间复杂度是指：算法在执行过程中所需要的基本运算次数。
（5）算法的时间复杂度是指执行算法所需的计算工作量，算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题的规模函数；算法的空间复杂度，一般指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占用的空间、输入的初始数据所占的存储空间以及算法执行过程中所需的额外空间。时间复杂度和空间复杂度并不相关。
数据的逻辑结构是数据元素之间的逻辑关系，是独立于计算机的，与存储结构不是一一对应关系。算法的执行效率不仅与问题的规模有关，还与数据的存储结构有关。
1.2数据结构的基本概念。
（1）数据的存储结构是指：数据的逻辑结构在计算机中的表示。
（2）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率。
（3）一般来说，一种数据结构的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等。
（4）在数据结构中，树这类的数据结构只有一个根节点，但它不是线性的。
1.3线性表及其顺序存储结构。
（1）一般将数据结构分为两大类：线性结构和非线性结构。循环队列、带链队列、带链栈是线性结构，二叉树是非线性结构。
（2）线性链表是线性表的链式存储结构。
（3）线性表是最简单、最常用的一种线性结构。
1.4栈和队列。
（1）栈是限定在一端进行插入和删除的线性表，允许进行插入和删除元素的一端称为栈顶，另一端称为栈底。栈是按照“先进后出”的原则组织数据的。
（2）支持子程序调用的数据结构是栈，这是由栈的特点决定的。
（3）栈跟队列不同，元素只能在栈顶压人或弹出，栈底指针不变，栈中元素随栈顶指针的变化而动态变化，遵循“后进先出的原则”。“栈只能顺序存储” 是错的。
（4）队列是指允许在一端进行插入、而在另一端进行删除的线性表，允许插入的一端称为队尾，允许删除的一端称为对头。是一种先进先出的队列表。
（5）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构。所谓有序表，是指这样的线性表，其中所有的元素以递增或递减的方式排列，并且规定有序表中不存在元素值相同的元素！
（6）循环队列中元素的个数是由队头指针和队尾指针共同决定的，元素的动态变化也是通过队头指针和队尾指针来反映的。循环队列中元素的个数是可以变化的。
（7）队头指针可以大于队尾指针，也可以小于队尾指针。
（8）循环队列是队列的一种也应该是线性结构。队列是一种逻辑结构，循环队列是队列的一种顺序存储结构。
（9）队列头指针为front，队列尾指针为rear，队列容量为m，则元素个数为队列元素=（尾指针-头指针+队列容量）%队列容量，即[rear-front+m]%m,注意，这个%是求余运算。(rear-front+35)%35=0 or 35，rear=front=15时。
1.5线性链表。
（1）线性表的链式存储结构称为线性链表。在链式存储结构中，存储数据结构的存储空间可以不连续，各数据节点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是有指针域来确定的。
（2）线性表的存储分为顺序存储和链式存储。在顺序存储中，所有元素所占的存储空间是连续的。而在链式存储的方式中，将存储空间的每一个存储节点分为两部分，一部分用于存储数据元素的值，称为数据域；另一部分用于存储下一个元素的序号，称为指针域。
所以线性表的链式存储方式比顺序存储方式的存储空间要大一些。
（3）对于线性链表，存储空间不一定连续，且各元素的存储顺序是任意的。
（4）二叉链表作为树的存储结构。链表中节点的两个链域分别指向该节点的第一个孩子节点和下一个兄弟节点。
1.6树和二叉树。
（1）在树结构中，树的最大层次称为树的深度。
（2）二叉树种叶子节点总是比度为二的节点总数多一个。
（3）二叉树结点的度数指该结点所含子树的个数，二叉树结点子树个数最多的那个结点的度为二叉树的度。
二叉树的根结点所在的层数为1，根结点的孩子结点所在的层数为2，以此下去。深度是指所有结点中最深的结点所在的层数。
叶子结点就是没有孩子的结点，其度为0，度为二的结点是指有两个子数的结点。
（4）完全二叉树的定义：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树。
特点：叶子结点只可能在层次最大的两层上出现；对任一结点，若其右分支下子孙的最大层次为l，则其左分支下子孙的最大层次必为l 或l+1 。
满二叉树：一棵深度为k，且有2的(k)次方－1个节点的二叉树 。
特点：每一层上的结点数都是最大结点数。
5) ①具有n个节点的完全二叉树的深度为㏒2n（向上取整）。
完全二叉树中度为1的节点只有两种可能：1或0（n=1时取零）。
（6）序是根据树根的遍历位置来说的，前序就是先遍历根，后遍历左右子节点；
中序遍历按左子树， 根节点， 右子树的顺序遍历。
前序遍历按根节点， 左子树， 右子树的顺序遍历。
后序遍历按左子树， 右子树， 根节点的顺序遍历。比如 6
中序： 1 5 4 6 7
先序： 6 5 1 4 7
1.7查找技术。
（1）顺序查找又称顺序搜索。顺序查找一般是指**性表中查找指定的元素，其基本方法是：从线性表的第一元素开始，依次将线性表中的元素与被查找的元素进行比较，若相等则表示查找到（即查找成功），若线性表中的所有元素都与被查找元素进行了比较但都不相等，则线性表中没有要查找的元素（查找失败）。
最坏情况下，查找次数是线性表的长度。
（2）顺序查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构（使用单链表作存储结构时，扫描必须从第一个结点开始）。二分法查找只适用于顺序存储的有序表，并不适用于线性链表。
（3）对于长度为n的有序线性表，在最坏情况下，二分法查找只需要比较o（㏒2n）。
1.8排序技术。
（1）冒泡法排序比较次数的计算式：n*（n‐1）∕2
比较n个数的大小并排序的话，要比较n-1遍。第一遍比较n-1次，将最大的数放在最后；第二遍比较n-2次，将第二大的数放在了倒数第二的位置；依次类推，最后一遍只比较两个数的大小，即一次。
等差数列求和公式＝(首数+末数)*项数/2
等比数列求和公式＝首项*(1-比值^项数)/(1-比值)
（2）快速排序法也是一种互换类的排序方法，但由于它比冒泡排序法的速度快，因此，称为快速排序法。最大比较次数与冒泡法排序相同。
（3）各种排序方法中最坏情况下需要比较的次数分别为：冒泡排序n*（n‐1）∕2、
快速排序n*（n‐1）∕2、简单插入排序n*（n‐1）∕2、希尔排序o（n1.5）、
简单选择排序n*（n‐1）∕2、堆排序o（n㏒2n）。
数据结构与算法
本章知识要点 算法的基本概念 数据结构的定义 线性表的定义和存储 树 二叉树的定义和存储 查找与排序算法。算法 algorithm 是一组有穷的规则，规定了解决某一特定类型问题的一系列运算，是对解题方 与完整的描述。算法是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中...
算法与数据结构
学院专业姓名学号。实验1 线性表的操作 12学时 问题描述 假设一个班级内有n个学生，定义一个学生类和一个班级类。学生类中包括学号 姓名 性别 年龄 专业等属性 班级类包括一个学生对象链表。定义如下 class student class myclass student stu head 链表表头指...
算法与数据结构
1 简述算法的概念及其五个重要特性。2 下图是用邻接表存储的图，请画出此图，写出其邻接矩阵以及从c点开始分别按广度优先搜索和深度优先搜索遍历该图的结果。给定一棵用二叉链表表示的二叉树，其根指针为root，编写求此二叉树叶结点个数的算法，要求先写出二叉链表的类型定义。2.编写简单选择排序的算法。1 用...