数据结构第一章(绪论)

《数据结构第一章(绪论)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构北京邮电大学自动化学院北京邮电大学自动化学院1使用教材及参考书使用教材：严蔚敏吴伟民编著，数据结构（C语言版），清华大学出版社参考书：1、曹桂琴编著，数据结构基础，大连理工大学出版社。2、晋良颖编，数据结构，人民邮电出版社3、BrunoR.Preiss，数据结构与算法，电子工业出版社北京邮电大学自动化学院2《数据结构》辅导老师名单辅导老师负责班级电话地点06501～024－311或4－32706503和054－311或4－32706506～074－311或4－32706508～094－311或4－327北京邮电大学自动化学院3课程教学目的

2、在计算机及其应用的各个领域中，都会用到各种各样的数据结构，通过本课程使学生学会分析和研究计算机加工对象的特性，选择合适的数据结构和存储表示，以及编制相应的实现算法。北京邮电大学自动化学院4课程教学基本要求本课程介绍各种最常用的数据结构，阐述各种数据结构内涵的逻辑关系，讨论它们在计算机中的存储表示，以及在这些数据结构上的运算和实际的执行算法，并对算法的效率进行简要的分析和讨论。北京邮电大学自动化学院5课程介绍数据结构的研究不仅涉及到计算机硬件（特别是编码理论、存储装置和存取方法）的研究范围，而且和计算机软件的研究有着密切的关系，无论是编译程

3、序还是操作系统，都涉及到数据元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据，以便查找和存取数据元素更为方便。北京邮电大学自动化学院6课程介绍因此，可以认为数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。程序＝算法＋数据结构目前在我国，《数据结构》已经不仅仅是计算机专业的教学计划中的核心课程之一，而且是其它非计算机专业的主要选修课程之一。通过对这门课程的学习可增强选择合适的数据结构与编写高效的程序的能力。北京邮电大学自动化学院7教学安排及考试讲课学时：32学时上机时间：4次（每次2学时）考试成绩计算：平时成绩

4、（考勤、作业及上机）30分考试（70分）北京邮电大学自动化学院8目录第1章绪论第2章线性表第3章栈和队列第4章串第5章数组和广义表第6章树和二叉树第7章图第8章查找第9章内部排序北京邮电大学自动化学院9第一章绪论计算机的应用已不再局限于科学计算，而更多地用于控制、管理及数据处理等非数值计算的处理工作。第一章绪论与此对应，计算机加工处理的对象由纯粹的数值发展到字符、表格和图像等各种具有一定结构的数据。为了编写出一个“好”的程序，必须分析待处理的对象的特征以及各对象之间存在的关系，这就是“数据结构”这门学科形成和发展的背景。北京邮电大学自

5、动化学院101.1什么是数据结构一般来说，用计算机解决一个具体问题时，大致需要经多下列几个步骤：首先要从具体问题抽象出一个适当的数学模型然后设计一个解此数学模型的算法，最后编出程序、进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。然而，更多的非数值问题无法用数学方程描述。什么是数据结构呢？先看以下几个例子。北京邮电大学自动化学院11例1书目自动检索系统书目文件001高等数学樊映川S01002理论力学罗远祥L01003高等数学华罗庚S01004书目卡片线性代

6、数栾汝书S02登录号：线性表……………………书名：作者名：分类号：出版单位：索引表出版时间：价格：按书名按作者名按分类号高等数学001，003……樊映川001,…L002,…理论力学002，……..华罗庚002,….S001,003,线性代数004，……栾汝书004,….……………………..…….…….北京邮电大学自动化学院12例2人机对奕问题树……..……..…...…...…...…...北京邮电大学自动化学院13例3多叉路口交通灯管理问题对于一个多叉路口，设计一个交通信号灯的管理系统。CD首先需要分析一下所有车辆的行B驶路线的冲突问题。这个问题可以

7、归结为对车辆的可E能行驶方向作某种分组，对分组A的要求是使任一个组中各个方向行驶的车辆可以同时安全行驶而不发生碰撞。北京邮电大学自动化学院14例3多叉路口交通灯管理问题C可通行方向DBA→BA→CA→DB→AB→CB→DED→AD→BD→CAE→AE→BE→CE→D北京邮电大学自动化学院15有些通行方向显然不能同时进行，相应的结点间画一条连线。图ABACADCDBABCBDBEDADBDCAEAEBECED图1.2交叉路口的图示模型北京邮电大学自动化学院16例3多叉路口交通灯管理问题把图1.2中的结点进行分组，使得有线相连的结点不在同一个组里。地图

8、着色问题如果把上图中的一个结点理解为