数据结构基本概念和基本理论串讲+习题答案+复习要点(1)

需要达到 <识记> 层次的基本概念和术语有：数据、数据元素、数据项、数据结构。特别是数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系。数据结构的两大类逻辑结构和四种常用的存储表示方法。
需要达到 <领会> 层次的内容有算法、算法的时间复杂度和空间复杂度、最坏的和平均时间复杂度等概念，算法描述和算法分析的方法、对一般的算法要能分析出时间复杂度。
对于基本概念，仔细看书就能够理解，这里简单提一下：
数据就是指能够被计算机识别、存储和加工处理的信息的载体。
数据元素是数据的基本单位，有时一个数据元素可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。如整数这个集合中，10这个数就可称是一个数据元素.又比如在一个数据库(关系式数据库)中，一个记录可称为一个数据元素，而这个元素中的某一字段就是一个数据项。
数据结构的定义虽然没有标准，但是它包括以下三方面内容： 逻辑结构、存储结构、和对数据的操作 。这一段比较重要，我用自己的语言来说明一下，大家看看是不是这样。
比如一个 表 ( 数据库 )，我们就称它为一个数据结构，它由很多 记录 ( 数据元素 )组成，每个元素又包括很多 字段 ( 数据项 )组成。那么这张表的逻辑结构是怎么样的呢? 我们分析数据结构都是从 结点 (其实也就是元素、记录、顶点，虽然在各种情况下所用名字不同，但说的是同一个东东)之间的关系来分析的，对于这个表中的任一个记录(结点)，它只有一个 直接前趋 ，只有一个 直接后继 (前趋后继就是前相邻后相邻的意思)，整个表只有一个 开始结点 和一个 终端结点 ，那我们知道了这些关系就能明白这个表的逻辑结构了。
而 存储结构 则是指用 计算机语言 如何表示结点之间的这种关系。如上面的表，在计算机语言中描述为连续存放在一片内存单元中，还是随机的存放在内存中再用指针把它们链接在一起，这两种表示法就成为两种不同的存储结构。( 注意，在本课程里，我们只在高级语言的层次上讨论存储结构。 )
第三个概念就是对 数据的运算 ，比如一张表格，我们需要进行查找，增加，修改，删除记录等工作，而怎么样才能进行这样的操作呢? 这也就是数据的运算，它不仅仅是加减乘除这些算术运算了，在数据结构中，这些运算常常涉及算法问题。
弄清了以上三个问题，就可以弄清数据结构这个概念。
通常我们就将数据的 逻辑结构 简称为 数据结构 ，数据的逻辑结构分两大类： 线性结构 和 非线性结构 (这两个很容易理解)
数据的存储方法有四种： 顺序存储方法 、 链接存储方法 、 索引存储方法和散列存储方法 。
下一个是 难点 问题，就是算法的描述和分析，主要是 算法复杂度 的分析方法及其运用。
首先了解一下几个概念。一个是 时间复杂度 ，一个是 渐近时间复杂度 。前者是某个算法的时间耗费，它是该算法所求解问题 规模 n的函数，而后者是指当问题规模趋向无穷大时，该算法 时间复杂度的数量级。
当我们评价一个算法的时间性能时，主要标准就是 算法的渐近时间复杂度 ，因此， 在算法分析时，往往对两者不予区分，经常是将渐近时间复杂度t(n)=o(f(n)简称为时间复杂度，其中的f(n)一般是算法中频度的语句频度 。
此外，算法中语句的频度 不仅与问题规模有关，还与输入实例中各元素的取值相关 。但是我们总是考虑在最坏的情况下的时间复杂度。以保证算法的运行时间不会比它更长。
常见的时间复杂度，按数量级递增排列依次为： 常数阶o(1) 、 对数阶o(log2n) 、 线性阶o(n) 、 线性对数阶o(nlog2n) 、 平方阶o(n^2)、立方阶o(n^3) 、 k次方阶o(n^k) 、 指数阶o(2^n) 。
时间复杂度的分析计算请看书本上的例子，然后我们通过做练习加以领会和巩固。