一、数据结构的基本概念
1、数据。信息载体，能够被计算机识别、存储和加工处理。可以是数值数据（整数、实数），也可以是非数值数据（声音、图像等）。
2、数据项。
是数据的具有独立含义的不可分割的最小标识单位，如成绩表中学号、姓名。
3、数据元素（ 又称结点、记录）
一个数据元素由若干数据项组成，是数据的基本单位，通常作为一个整体进行考虑和处理。
4、数据对象。
具有相同性质的数据元素的集合。是数据的一个子集。
5、数据结构。
相互之间存在着一种或多种关系的数据元素的集合。
1）研究内容。
数据的逻辑结构：各数据元素之间的逻辑关系。
数据的存储结构：各数据元素在计算机中的存储关系。
对各种数据结构进行的运算：添加、删除、排序等。
2）研究目的。
一是提高数据处理的速度；二是尽量节省在数据处理过程中所占用的计算机存储空间。
3）常见的数据结构类型。
集合：元素间为松散的关系（属于关系）。
线性结构：元素间为一对一关系。
树形结构：元素间为一对多关系。特点：结点间具有分层次的连接关系。
图状结构：元素间为多对多关系。特点：结点间的连结是任意的，数据元素之间存在多个对多个关系。
4）包含信息。
表示数据元素的信息。
表示各数据元素之间的前后件关系。
5）有关概念。
结点：组成数据结构的数据元素称为一个结点。
前后件关系：数据元素之间的固有关系可以用前后件关系（前驱与后继关系）描述。
根节点：在数据结构中，没有前件的节点称为根结点。
叶子节点：没有后件的结点称为终端结点或叶子结点。
6、数据结构的逻辑结构。
1）数据的逻辑结构。
数据之间的相互关系，被称为数据的逻辑结构。
2）逻辑结构分类。
根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据逻辑结构分为：线性结构与非线性结构。
3）线性结构。
数据元素之间存在一个对一个的前后次序关系。
特点：有且只有一个根结点每个结点最多有一个前件，也最多有一个后件。
4）非线性结构。
一个数据结构如果不是线性结构，则称之为非线性结构。
特点：数据元素的前后关系复杂，一个结点既可以有多个前件，也可以有多个后件，如集合、树型、图形结构属于非线性结构。
集合结构：数据元素间的关系是属于同一个集合 。
树型结构：数据元素之间存在一个对多个的关系。
图形结构：数据元素之间存在多个对多个的关系 。
7、数据结构的存储结构。
数据的逻辑结构在计算机存储空间中的存放形式。数据存储结构中不仅存放各数据元素信息，还存放前后件关系的信息。
1）特点 存储结构研究的是逻辑结构用计算机语言实现，依赖于计算机语言。
一种数据结构可以根据需要采用多种不同的存储结构，常用的存储结构有顺序、链接与索引等存储方式。
数据的存储结构不同，解决问题的方法就有所不同，数据处理的效率也是不同的。
2）实现方式。
顺序存储方式。
逻辑上相邻的元素存储在物理位置相邻的存储单元中；主要用于线性结构；通常借助于数组来实现。
链式存储方式。
对逻辑上相邻的元素不要求其物理地址相邻，元素间逻辑关系通过附加的指针字段来表示；通常借助于指针类型实现。
链式存储方式特点：每个结点由两部分组成，一部分存放数据，另一部分存储指向前件或后件结点的指针域；逻辑上相邻的结点物理上不必相连；数据运算（插入和删除等）灵活。
索引存储方法和散列存储方法。
8、数据的运算。
在数据的逻辑结构上定义的操作算法。
常见运算：插入、删除、查找、排序和更新等。
分类：加工型运算，运算改变了数据结构的值；引用型运算，不改变值，只查询或求得结构值。
注意：数据的运算定义在逻辑结构上，而具体的实现都要在数据的存储结构上即计算机内进行。
9、数据类型及其分类。
数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
分类：1）非结构的原子类型。
原子类型的值是不可分解的。如：程序设计语言中的基本类型（整型，实型，字符型，指针类型和空类型）。
2）结构类型。
结构类型的值是由若干成分按某种结构组成的，因此是可分解的，并且它的成分可以是非结构的，也可以是结构的。
二、算法及算法分析
1、 算法的基本概念。
1）定义。为解决某个特定问题而采取的确定且有限的步骤。
用计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题抽象出一个适当的数学模型；然后设计一个解此数学模型的算法；最后采用一种计算机语言编出程序，调试、修改直至得到最终答案。
2）算法特性。
有穷性： 一个算法应包含有限个操作步骤，而且每一步都应在有限时间内完成。
确定性：算法中每一条指令必须有确切的含义，确保不会产生二义性。
可行性：算法中指定的操作都是可以通过基本运算执行有限次后实现。
输入：一个算法有零个或多个的输入，这些输入取自于某个特定的对象集合。
输出：一个算法有一个或多个的输出，这些输出是同输入有着某些特定关系的量。
2、算法的基本要素及描述。
1）算法基本要素构成。
对数据对象的运算和操作：算术运算，加、减、乘、除；逻辑运算，与、或、非等运算；关系运算，大于、小于、等于等；数据传输，赋值、输入、输出。
算法的控制结构：顺序、选择、循环（重复）。
2） 算法的描述。
自然语言、伪**、流程图、 n-s图、类c。
3、算法设计要求（评价算法标准）
1）正确性：执行结果应满足预先的功能和性能要求。
2）可读性：思路清晰、层次分明、简单明了、易读易懂。
3）健壮性：输入数据非法时，算法能作适当处理，不致于引起严重后果。
4）效率：有效使用存储空间和较高的时间效率。
4、算法设计的基本方法。
1）列举法：列举出所有可能情况，用给定条件检验哪些是需要的，哪些是不需要的（如用循环解决百元买百鸡问题）。
2）归纳法：列举少量简单而又特殊的情况，分析归纳出一般结论。
3）递推法：从已知初始条件出发，逐步推出各种中间结果和最后结果（如猴子吃桃）。
4）递归法：解决复杂问题时，将问题逐层分解，归纳为一些简单问题，解决了最后简单问题后，再沿原来的逆过程逐步综合（如求某数的阶乘）。
5、算法的分析。
1）评价算法标准。
算法所占用计算机资源，即时间代价（算法所需要的时间）和空间代价（算法所需要的存储空间）。
算法所需要的时间包括：源程序进行编译所需要的时间；计算机执行每条指令所需要的时间；程序中指令重复执行的次数，而本条正是讨论算法中的重点内容。
2）相关名词。
问题规模：不同种类问题，问题规模含义不同。如矩阵运算取决于矩阵阶数，多项式运算取决于项数。
算法运行时间：大致等于其所有语句执行时间的总和。
语句频度：该语句在算法中重复执行的次数。
3）算法的时间复杂度。
即算法运行从开始到结束所需要的计算工作量。同一个算法使用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行，效率均不同，这表明使用绝对的时间单位衡量算法的效率是不合适的，撇开这些与计算机硬件、软件有关的因素，可以认为一个特定算法“运行工作量”的大小，只依赖于问题的规模（通常用整数n表示），它是问题的规模函数，即：算法的工作量=f(n)。
一个算法是由控制结构和原操作构成的，则算法时间取决于两者的的综合效果。为了便于比较同一个问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题（或算法类型）来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间度量。（t (n)=o( f (n) )
最优算法：随n的增大，t (n)增长较慢的算法。
平均时间复杂度：所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。
最坏时间复杂度：最坏情况下算法的时间复杂度。
4）算法的空间复杂度。
算法运行从开始到结束所需的存储空间量，包括固定部分和可变部分。
固定部分：此部分空间与所处理数据的大小和规模无关。通常用来保存本身所用的程序**、常量、变量等。
可变部分：此部分空间与处理的数据的大小和规模有关，即执行算法时所需额外空间。
数据结构与算法
本章知识要点 算法的基本概念 数据结构的定义 线性表的定义和存储 树 二叉树的定义和存储 查找与排序算法。算法 algorithm 是一组有穷的规则，规定了解决某一特定类型问题的一系列运算，是对解题方 与完整的描述。算法是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中...
算法与数据结构
学院专业姓名学号。实验1 线性表的操作 12学时 问题描述 假设一个班级内有n个学生，定义一个学生类和一个班级类。学生类中包括学号 姓名 性别 年龄 专业等属性 班级类包括一个学生对象链表。定义如下 class student class myclass student stu head 链表表头指...
算法与数据结构
1 简述算法的概念及其五个重要特性。2 下图是用邻接表存储的图，请画出此图，写出其邻接矩阵以及从c点开始分别按广度优先搜索和深度优先搜索遍历该图的结果。给定一棵用二叉链表表示的二叉树，其根指针为root，编写求此二叉树叶结点个数的算法，要求先写出二叉链表的类型定义。2.编写简单选择排序的算法。1 用...