资源描述：
《数据结构讲义》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、讲义邮箱zhydts@sina.com密码：1234567数据结构北京邮电大学计算机学院张海旸zhhy@bupt.edu.cn考核方式平时成绩占最后总成绩的40％期末考试占最后总成绩的60％平时成绩（考勤，作业，期中）期末闭卷考试教材《数据结构与算法》，张晓莉等，机械工业出版社参考书《数据结构》，严蔚敏，清华大学出版社《数据结构习题与解析（A级第3版）》，李春葆，清华大学出版社《算法与数据结构考研试题精析（第二版）》，陈守孔 胡潇琨 李玲，机械工业出版社第一章绪论1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析1.4.1算法1.
2、4.2算法设计的要求1.4.3算法效率的度量1.4.4算法的存储空间的需求第一章绪论计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：信息的表示信息的处理而信息的表示又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。1.1什么是数据结构建立数学模型是分析具体问题的过程，包括：分析具体问题中操作对象找出这些对象间的关系，并用数学语言描述数学模型分两类
3、：1）数值计算类：例：根据三条边，求三角形面积。假定：三条边依次为a,b,c三个实型数，满足：a>0,b>0,c>0,a+b>c,b+c>a,c+a>b,则s=area=2）非数值计算类：例1:5个整数组成的集合：D={20,-5，66,15,44}其中:20,-5,66等称为数据元素(元素)，元素与元素之间关系是它们同属于集合D。D={20,-5,66,15,44}是一个数据对象姓名电话号码陈海13612345588李四锋13056112345。。。。。。例2：电话号码查询系统设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：(a1,b1
4、)，(a2,b2)，…(an,bn)，其中ai,bi(i=1，2…n)分别表示某人的名字和电话号码。本问题是一种典型的表格问题。如表1-1，数据与数据成简单的一对一的线性关系。表1-1线性表结构算法的设计，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电话号码的结构。数据的结构，直接影响算法的选择和效率。上述的问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表结构、向量。假定名字和其电话号码逻辑上已安排成N元向量的形式，它的每个元素是一个数对(ai，bi)，1≤i≤n数据结构还要提供每种结构类型所定义的各种运算的算法。例3：磁盘目录
5、文件系统磁盘根目录下有很多子目录及文件，每个子目录里又可以包含多个子目录及文件，但每个子目录只有一个父目录，依此类推：本问题是一种典型的树型结构问题，如图1-1，数据与数据成一对多的关系，是一种典型的非线性关系结构—树形结构。树形结构例4树状结构其中:A、B、C等是结点(node)；A与B,B与E,A与C之间是层次关系或父子关系。北京邮电大学(A)计算机学院(B)管理学院(C)理学院(D)计算机系(E)信科系(F)信安系(G)例5：交通网络图从一个地方到另外一个地方可以有多条路径。本问题是一种典型的网状结构（图）问题，数据与数据成多对多的关系，是一种非线性关系结构。佛山
6、惠州广州中山东莞深圳珠海网状结构综上几个例子可见，描述这类非数值问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。因此简单说来，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。程序设计的实质是对实际问题选择一个好的数据结构，加之设计一个好的算法。而好的算法在很大程度上取决于描述实际问题的数据结构。算法+数据结构=程序1976年，瑞士N.Wirth教授[例]查找某人的社会关
7、系计算机中如何表示/存储和操作？张三李四王五陈六赵七输入输出CPU控制器运算器寄存器(组)内存储器外存储器控制器：控制系统一步步从存储器中取出指令、译码运算器：根据指令完成算术/逻辑运算寄存器：保持程序运行状态、存储当前指令信息及下一条指令地址等0OxFF…操作系统内存存储方案1：存储方案2：存储方案3：张三…...李四王五陈六李四……王五………...204020802120张三…...234李四……王五…...204020802120(1)(2)(3)40Byte张三…...311830601596王五……李四…...204030603
