REST

绪论（4学时）

1. 数据结构的基本概念
   1. 术语：
      1. 数据：人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的抽象描述。
      2. 数据元素(数据对象)：表示一个事物的一组数据。
      3. 数据项：构成数据元素的数据。
      4. 抽象数据元素：没有实际含义的数据元素。
   2. 数据的逻辑结构(数据元素之间的相互联系方式。 )
      1. 线性结构：除第一个和最后一个数据元素外，每个数据元素只有一个前驱和一个后继数据元素。
      2. 树结构：除根结点外，每个数据元素只有一个前驱数据元素，可有０个或若干个后继数据元素。
      3. 图结构：每个数据元素可有０个或若干个前驱数据元素和０个或若干个后继数据元素。
      4. 集合结构：数据元素之间没有任何次序。
   3. 数据的存储结构(物理结构)(数据元素在计算机中的存储方式。)
      1. 顺序存储结构：
      2. 把数据元素存储在一块连续地址空间的内存中，程序设计方法是使用数组。
      3. 特点:逻辑上相邻的数据元素在物理上也相邻，数据间的逻辑关系表现在数据元素存储位置关系上。
      4. 指针：指向一个内存的单元地址。数据元素和一个指针称为一个结点。
      5. 链式存储结构：
      6. 使用指针把相互直接关联的结点(即直接前驱结点或直接后继结点)链接起来，
      7. 特点:逻辑上相邻的数据元素在物理上不一定相邻，数据间的逻辑关系表现在结点的链接关系上。
   4. 数据的操作
      1. 数据的操作：对一种类型的数据进行的某种方法的处理。
      2. 数据的操作集合：一种类型的数据所有的操作集合。
      3. 数据结构从功能和实现两个方面讨论数据的操作。
      4. 功能方面：主要讨论某种类型数据应包含的操作和每种操作的逻辑功能，一般与数据的逻辑结构一起讨论。
      5. 实现方面：主要讨论操作的具体实现方法，操作的实现必须在数据的存储结构确定后才能进行。
   5. 数据结构课程讨论的内容
      1. 数据结构课程主要讨论线性表、堆栈、队列、串、数组、树、二叉树、图等典型的非数值型问题的常用数据结构。
      2. 在讨论这些典型数据结构时，主要从它们的逻辑结构、存储结构和数据操作三个方面进行分析讨论。
2. 抽象数据类型
   1. 术语
      1. 类型：一组值的集合。
      2. 数据类型：一个类型和定义在这个类型上的操作集合。
      3. 在数据结构课程中，通常把在已有的数据类型基础上设计新的数据类型的过程称作数据结构设计。
      4. 抽象数据类型(Abstract Data Type, ADT)：一个逻辑概念上的类型和这个类型上的操作集合。
      5. 数据类型和抽象数据类型的不同之处
      6. 仅仅在于数据类型指的是高级程序设计语言支持的基本数据类型，
      7. 而抽象数据类型指的是在基本数据类型支持下用户新设计的数据类型。
      8. 数据结构课程主要讨论表、堆栈、队列、串、数组、树、二叉树、图等典型的常用数据结构，
      9. 这些典型的常用数据结构就是一个个不同的抽象数据类型。
      10. 抽象数据类型是软件设计初期使用的概念，也可以把它看做软件模块（教材中讨论的都是可重复使用的通用软件模块）开发时的用户需求。在用Java语言具体进行软件开发时，抽象数据类型通常用接口或抽象类表示。
3. 算法和算法的时间复杂度
   1. 算法的定义和算法的表示方法
      1. 算法：描述求解问题方法的有限操作步骤集合
      2. 文字形式:用中文或英文这样的文字来描述算法。
      3. 伪码形式:用一种仿程序设计语言的语言来描述算法。
      4. 程序设计语言形式:用某种程序设计语言描述算法。其优点是算法不用修改，直接作为程序语句键入计算机，计算机能调用和运行。
   2. 算法的性质：**(1)输入性 (2)输出性 (3)有限性 (4)确定性 (5)可执行性**
      1. 程序和算法的主要区别
      2. 程序允许无限循环，而算法不允许无限循环。
      3. Java是一种纯面向对象程序设计语言，在Java中，一个具体的算法表示为类中的一个成员函数。
      4. 带关键字static的成员函数是可以直接调用的成员函数(类函数)；
      5. 不带关键字static的成员函数要先定义对象，通过向对象发消息来调用成员函数。
   3. 算法设计的目标：**(1)正确性 (2)可读性 (3)健壮性 (4)高时间效率 (5)高空间效率**
   4. 算法的时间复杂度分析（）
      1. (1)事后统计方法 (2)事前分析方法
      2. O()函数
      3. 算法的时间复杂度T(n)随数据元素个数n的增长率和函数f(n)的增长率在数量级上相同。
4. 算法的空间复杂度分析
5. Java语言的工具包

---

3. 堆栈和队列（4学时）
4. 数组、集合和矩阵（4学时）
5. 递归算法（4学时）
6. 树和二叉树（8学时）
7. 图（8学时）
8. 排序（4学时）
9. 查找（4学时）
10. 哈希表（2学时）

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达，可以邮件至 963614756@qq.com。