数据结构教程第四十课总复习

教学目的:数据结构概述

教学重点:数据结构课程的核心

教学难点:理解概念

教学内容:

一，学习数据结构的意义

想象一下，你决定投资一家公司，你对一家公司的了解仅限于公司的一条生产线每分钟能生产2000件产品。你会做出投资决定吗？如果你是一家公司的管理者，这家公司每天每一笔交易的细节对你来说确实很重要，但是如果你把时间花在这些数据上，你就无法从宏观的角度把握公司的经营方向。

无论是经营公司还是管理国家，描述事物特征的数据都必须进行分析处理。真实的事物是普遍相关的，描述这些事物属性和特征的数据也是普遍相关的。通过总结这些数据之间的关系，可以得到集合、线性、树、图四种基本关系，从而得到四种基本的数据结构。但是，同样的操作(如遍历、搜索等)需要不同的方法(算法)。)的结构类型，不同的结构类型可以执行的操作也是不同的。通过应用这些算法，可以获得事物的一般抽象特征。如:一个公司的年产值、年利润总额、利润率。

另一方面，为了描述一个复杂的事物，需要分析它的组成部分，不仅要描述各部分的特征，还要描述各部分之间的关系。再细分的话，最后就方便计算机处理了。而计算机的基本数据类型不适合描述复杂的结构，只使用基本数据类型不便于人们理解和记忆。因此，在它们之间使用抽象的数据类型成为了计算机语言描述真实事物的纽带。人们可以方便地用抽象数据类型描述事物，也可以方便地用基本数据类型实现抽象数据类型，这为用计算机处理现实问题提供了解决方案。

二，数据结构的学习重点

如何描述一个新的抽象数据类型？

如何分析算法的优劣？

线性表的主要特点。

线性表的存储表示(顺序表示，单向链表，循环链表，双向链表)

特殊线性表:堆栈、队列、字符串

二叉树的定义、性质、存储结构和遍历算法

图的定义、术语和存储结构

静态查找表的构造，二叉排序树，哈希函数和冲突处理方法。

插入排序、快速排序、选择排序