151601学期课程知识点回顾-数据结构与算法-v10

《151601学期课程知识点回顾-数据结构与算法-v10》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、1概述1.1课程介绍为什么要学数据结构与算法怎么学数据结构与算法1.2数据结构什么是数据结构什么是逻辑结构，有哪些逻辑结构（线性.树、网络.集），各逻辑结构分别有什么特点。什么是存储方式（物理结构），有哪些存储方式（顺序存储、链式存储）O有哪些常见数据操作（增删查改、排序等）1・3算法什么是算法。算法与数据结构有什么关系。怎么评价算法的好坏。软件质量评估指标体系算法效率的度量方法：什么是时间复杂度，什么是空间复杂度，如何确定算法的时间复杂度。2线性表2.1线性表概述什么是线性表，线性表的基本操作2

2、.2顺序表2.2.1什么是顺序表什么是顺序表根据下标和顺序表中元素类型，计算顺序表中某元素的地址2.2.2顺序表的数据结构描述顺序表结构描述肘，必须的几点要素。如何用c语言描述顺序表。2.2.3顺序表的算法思路.实现和效率分析顺序表的基本算法（操作）：初始化.求表长.增加元素、删除元素、查找元素（按下标杳.按值杳）。懂得算法思路，和算法实现，懂得分析算法效率（时间复杂度和空间复杂度，重点是时间复杂度）。2.2.4Java中的顺序表Java中顺序表结构有基本数组和ArrayList类，懂得Array

3、List类的基本结构,懂得用ArrayList类自带的方法对其中元素增删查改。懂得用Iterator和Listiterator接□访冋ArrayListo如何根据不同情况，在Java的世界中，选择合适的顺序表，即基本数组或ArrayListo2.3链表2.3.1什么是链表什么是链表，懂得区分顺序表和链表在数据结构上的差异2.3.2链表的数据结构描述链表结构描述时，必须的几点要素。如何用c语言描述链表带头结点和不带头结点的链表2.3.3链表的算法思路、实现和效率分析链表的基本算法（操作）：初始化.求

4、表长.增删杳改（杳包括按下标和按值查）o懂得算法思路、算法实现，并懂得分析算法效率（时间和空间复杂度，重点是时间用头插法和尾插法创建链表（带头结点或者不带头结点）2.3.4循环链表和双向链表单向和双向链表.循环和不循环链表的各自特点双向链表结构描述时，必须的几点要素。如何用c语言描述双向链表双向链表的前插和删除算法的思路和c语言实现Oracle索引B*树结构中的双向链表2.3.5Java中的链表Java中的链表：LinkedList类。懂得LinkedList类的基本结构（带头结点的双向循环链表）

5、。懂得用LinkedList类自带的方法对其中元素增删查改。懂得用Iterator和Listiterator接□访问LinkedList。如何根据不同情况，在J&腹的世界中，选择合适的线性表，即基本数组、ArrayList^或LinkedList。2.3.6顺序表和链表的比较增加结点时，顺序表和链表的时间效率（即时间复杂度）分析顺序表和链表的综合比较（包括存储方法.根据index查找/更新的时间效率.根据值查找/更新的时间效率.定位后增删的时间效率.空间效率）3栈与队列2.1栈2.1.1什么是栈什

6、么是栈（我们身边的栈八什么是顺序栈.什么是链栈3.1.2顺序栈的数据结构描述顺序栈结构描述时，必须的几点要素。如何用c语言描述顺序栈3.1.3顺序栈的算法思路.实现和效率分析顺序栈的基本算法：初始化.判断栈是否空、判断栈是否满.入栈.出栈、取栈顶元素。这些算法的思路、c语言实现和效率分析（时间和空间复杂度，重点是时间复杂度）3.1.4链栈的数据结构描述链栈结构描述时，必须的几点要素。如何用c语言描述链栈3.1.5链栈的算法思路、实现和效率分析链栈的基本算法：初始化.判断栈是否空、判断栈是否满.入栈

7、.出栈.取栈顶元素。这些算法的思路.c语言实现和效率分析（时间和空间复杂度，重点是时间复杂度）2.1.6Java中的栈Stack用ArrayList或LinkedList制作一个栈Collections・asLifoQueue()2.2队列什么是队列（我们身边的队列）.什么是顺序队列.什么是链队列2.2.2顺序队列的数据结构描述顺序队列结构描述时，必须的几点要素。如何用c语言描述顺序队列2.2.3顺序队列的算法思路.实现和效率分析顺序队列的基本算法：初始化、判断队列是否空、判断队列是否满.入队.出

8、队、取队列顶元素。这些算法的思路、c语言实现和效率分析（时间和空间复杂度，重点是时间复杂度）2.2.4循环顺序队列的数据结构描述循环顺序队列结构描述时，必须的几点要素。如何用c语言描述循环顺序队列3.2.5循环顺序队列的算法思路、实现和效率分析循环顺序队列的基本算法：初始化、判断队列是否空.判断队列是否满、入队、出队、取队列顶元素。这些算法的思路.c语言实现和效率分析（时间和空间复杂度,重点是时间复杂度）3.2.6链队列的数据结构描述链队列结构描述时，必须的几点要素。如何用c语言描