第1章绪论1.1数据结构的基本概念基本术语数据的逻辑结构线性结构数据的存储结构顺序存储结构数据的操作1.2抽象数据类型和软件构造方法抽象数据类型使软件设计成为工业化流水线生产的一个中间环节。一方面，根据给出的抽象数据类型的功能定义，负责设计这些抽象数据类型的专门公司设计该抽象数据类型的具体存储结构以及在具体存储结构下各操作的具体实现算法；另一方面，利用已设计实现的抽象数据类型模块，负责设计应用软件的专门公司可以安全、快速、方便的完成该应用软件系统的设计。1.3算法及其时间复杂度例1-1:设计一个把存储在数组中的有n个抽象数据元素a0,a1,…,an-1逆置的算法，即要求逆置后的数组中数据元素序列为an-1,…,a1,a0,并要求原数组中的数据元素值不能被改变。例1-2:设计一个把存储在数组中的有n个抽象数据元素a0,a1,…,an-1逆置的算法，即要求逆置后的数组中数据元素序列为an-1,…,a1,a0,并要求原数组中的数据元素值被改变。算法满足以下性质:(1)输入性(2)输出性(3)有限性(4)确定性(5)可执行性程序运行消耗时间的有关因素:例1-3设数组a和b在前边部分已赋值，求如下两个n阶矩阵相乘运算算法的时间复杂度。例1-4设n为如下算法处理的数据个数，求如下算法的时间复杂度。for(i=1;i<=n;i=2*i)cout<<"i="<<i;例1-5:下边的算法是用冒泡排序法对数字a中的n个整数类型的数据元素(a[0]~a[n-1])，从小到大进行排序，求该算法的时间复杂度。解:设基本语句的执行次数为f(n),最坏情况下有f(n)≈n+4*n2/2因T(n)=f(n)≈n+2*n2≤c*n2,其中c为常数，所以该算法的时间复杂度为T(n)=O(n2)。例1-6下面的算法是在一个有n个数据元素的数组a中删除第i个位置的数组元素，要求当删除成功时数组元素个数减1，求该算法的时间复杂度。其中数组下标从0至n-1。解:假设删除任何位置上的数据元素都是等概率的,设Pi为删除第i个位置上数据元素的概率，则有Pi=1/n，设E为删除数组元素的平均次数，则有例1-7对比在数据元素个数为30000时，冒泡排序算法和快速排序算法的实际耗时。根据问题的要求，设计测试程序，并在计算机上实际运行。程序运行结果：冒泡排序:6.00秒；快速排序:0.00秒程序运行结果说明：系统中的difftime(end,start)函数以秒为单位计时，快速排序的实际耗时少于0.5秒，所以输出显示为0.00秒。程序运行结果说明，当数据元素个数足够大时，理论分析的快速排序算法优于冒泡排序算法的结果，和程序的实际测试结果吻合。算法的时间复杂度是衡量一个算法好坏的重要指标。一般来说，具有多项式时间复杂度（如O(n)、O(n2)、O(n6)、O(n8)等）的算法，是可接受、可实际使用的算法；而具有指数时间复杂度（如O(2n)、O(nn)、O(n！)等）的算法，是理论上可以计算，但实际上不可计算的问题，通常称作难解的问题。对于具有多项式时间复杂度的算法，无论数据元素个数多大（只要是有限的数值），算法都可以在有限的时间内运行完成；而对于难解的问题，当n足够小时，算法可以在有限的时间内运行完成，当n比较大时，其运行时间将是一个天文数字！习题1-1，1-2习题1-13，1-14，1-15