151601学期课程知识点回顾-数据结构与算法-v1.0摘要.docx

COPYRIGHT (C) 2015 BY MULDINI. ALL RIGHTS RESERVED. 1 概述 课程介绍 为什么要学数据结构与算法 怎么学数据结构与算法 1.2 数据结构 什么是数据结构 什么是逻辑结构，有哪些逻辑结构（线性、树、网络、集），各逻辑结构分别有什么特点。 什么是存储方式（物理结构），有哪些存储方式（顺序存储、链式存储）。 有哪些常见数据操作（增删查改、排序等） 1.3 算法 什么是算法。算法与数据结构有什么关系。 怎么评价算法的好坏。软件质量评估指标体系 算法效率的度量方法：什么是时间复杂度，什么是空间复杂度，如何确定算法的时间复杂度。 2 线性表 2.1 线性表概述 什么是线性表，线性表的基本操作 2.2 顺序表 2.2.1 什么是顺序表 什么是顺序表 根据下标和顺序表中元素类型，计算顺序表中某元素的地址 2.2.2 顺序表的数据结构描述 顺序表结构描述时，必须的几点要素。如何用c语言描述顺序表。 2.2.3 顺序表的算法思路、实现和效率分析 顺序表的基本算法（操作）：初始化、求表长、增加元素、删除元素、查找元素（按下标查、按值查）。懂得算法思路，和算法实现，懂得分析算法效率（时间复杂度和空间复杂度，重点是时间复杂度）。 2.2.4 Java中的顺序表 Java中顺序表结构有基本数组和ArrayList类，懂得ArrayList类的基本结构，懂得用ArrayList类自带的方法对其中元素增删查改。懂得用Iterator和ListIterator接口访问ArrayList。 如何根据不同情况，在Java的世界中，选择合适的顺序表，即基本数组或ArrayList。 2.3 链表 2.3.1 什么是链表 什么是链表，懂得区分顺序表和链表在数据结构上的差异 2.3.2 链表的数据结构描述 链表结构描述时，必须的几点要素。如何用c语言描述链表 带头结点和不带头结点的链表 2.3.3 链表的算法思路、实现和效率分析 链表的基本算法（操作）：初始化、求表长、增删查改（查包括按下标和按值查）。懂得算法思路、算法实现，并懂得分析算法效率（时间和空间复杂度，重点是时间复杂度）。 用头插法和尾插法创建链表（带头结点或者不带头结点） 2.3.4 循环链表和双向链表 单向和双向链表、循环和不循环链表的各自特点 双向链表结构描述时，必须的几点要素。如何用c语言描述双向链表 双向链表的前插和删除算法的思路和c语言实现 Oracle索引B*树结构中的双向链表 2.3.5 Java中的链表 Java中的链表：LinkedList类。懂得LinkedList类的基本结构（带头结点的双向循环链表）。懂得用LinkedList类自带的方法对其中元素增删查改。懂得用Iterator和ListIterator接口访问LinkedList。 如何根据不同情况，在Java的世界中，选择合适的线性表，即基本数组、ArrayList、或LinkedList。 2.3.6 顺序表和链表的比较 增加结点时，顺序表和链表的时间效率（即时间复杂度）分析 顺序表和链表的综合比较（包括存储方法、根据index查找/更新的时间效率、根据值查找/更新的时间效率、定位后增删的时间效率、空间效率） 3 栈与队列 3.1 栈 3.1.1 什么是栈 什么是栈（我们身边的栈）、什么是顺序栈、什么是链栈 3.1.2 顺序栈的数据结构描述 顺序栈结构描述时，必须的几点要素。如何用c语言描述顺序栈 3.1.3 顺序栈的算法思路、实现和效率分析 顺序栈的基本算法：初始化、判断栈是否空、判断栈是否满、入栈、出栈、取栈顶元素。这些算法的思路、c语言实现和效率分析（时间和空间复杂度，重点是时间复杂度） 3.1.4 链栈的数据结构描述 链栈结构描述时，必须的几点要素。如何用c语言描述链栈 3.1.5 链栈的算法思路、实现和效率分析 链栈的基本算法：初始化、判断栈是否空、判断栈是否满、入栈、出栈、取栈顶元素。这些算法的思路、c语言实现和效率分析（时间和空间复杂度，重点是时间复杂度） 3.1.6 Java中的栈 Stack 用ArrayList或LinkedList制作一个栈 Collections.asLifoQueue() 3.2 队列 3.2.1 什么是队列 什么是队列（我们身边的队列）、什么是顺序队列、什么是链队列 3.2.2 顺序队列的数据结构描述 顺序队列结构描述时，必须的几点要素。如何用c语言描述顺序队列 3.2.3 顺序队列的算法思路、实现和效率分析 顺序队列的基本算法：初始化、判断队列是否空、判断队列是否满、入队、出队、取队列顶元素。这些算法的思路、c语言实现和效率分析（时间和空间复杂度，重点是时间复杂度） 3.2.4 循环顺序队列的数据结构描述 循环顺序队列结构描述时，