数据结构绪论

《数据结构绪论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构北京邮电大学信息安全中心武斌一个实际问题电话号码查询问题用C语言编写程序，查询某个城市或单位的私人电话号码。要求对任意给出的一个姓名，若该人有电话号码，则迅速找到其电话号码；否则指出该人没有电话号码。2一个实际问题—方法一构造一张电话号码登记表表中每个结点存放两个数据项：姓名和电话号码进行顺序查询查找效率低序号姓名电话号码1张三138123456782李四139876543213王五15900000001„„„200赵六186888888883一个实际问题—方法二高效的查找算

2、法：取决于表的结构及存储方式。表按姓氏排列另外构造一张姓氏索引表查找过程：先在索引表中查对姓氏，然后根据索引表中的地址到电话号码登记表中核查姓名。计算查找概率，将高概率的姓氏排在索引表前面4一个实际问题—方法二姓名电话号码张三1xxx张一元1xxx：：姓氏地址：：张xxx张无忌1xxx李xxx李四1xxx„：：王xxx李寻欢1xxx王五1xxx：：王重阳1xxx5数据结构的主要内容数据的各种逻辑结构和物理结构及之间的相应关系为每种数据结构定义相应的各种操作设计相应的算法分析算法的效率6课程

3、安排课程内容第一章绪论第二章线性表第三章栈和队列第四章串第五章数组和广义表第六章树和二叉树第七章图第九章查找第十章内部排序7课程安排课时安排本课程共48学时。单周每周两次课，双周每周一次课，每次课2学时。授课方式课堂：讲授、演示、讨论、学生参与课下：作业、助教答疑考核方式平时成绩、期中考试成绩、期末考试成绩8本次课程学习目标学习完本次课程，您应该能够：理解数据结构知道数据结构的基本概念和术语了解抽象数据类型的表示与实现理解算法和算法分析掌握计算语句频度和估算算法

4、时间复杂度的方法9本章课程内容（第一章绪论）1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析10第一章绪论计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：信息的表示信息的处理信息的表示和组成，直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门

5、课所要研究的问题。11什么是数据结构1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析12什么是数据结构众所周知，计算机的程序是对信息进行加工处理。在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。那么，什么是数据结构呢？PASCAL之父NiklausWirth在1976年出版了一本书，书名为《算法+数据结构=程序设计》，并于1984年获得了图灵奖。它正说明了数据结构在程序设计中的作用。程序设计的实质即

6、为计算机处理问题编制一组“指令集"，首先需要解决两个问题：即算法和数据结构。算法即处理问题的策略，而数据结构即为问题的数学模型。很多数值计算问题的数学模型通常可用一组线性或非线性的代数方程组或微分方程组来描述，而大量非数值计算问题的数学模型正是本门课程要讨论的数据结构。13什么是数据结构例如求n个整数中的最大值这似乎不成问题，但如果这些整数的值有可能达到1012，那么对32位的计算机来说，就存在一个如何表示的问题。例如图书馆的计算机书目检索系统书目文件+检索表线性数据结构例如人机对弈棋盘状

7、态格局树形数据结构14什么是数据结构例如交叉路口的红绿灯管理如今十字路口横竖两个方向都有三个红绿灯，分别控制左拐、直行和右拐，那么如何控制这些红绿灯既使交通不堵塞，又使流量最大呢？若要编制程序解决问题，首先要解决一个如何表示的问题。例如煤气管道的铺设问题需为城市的各小区之间铺设煤气管道，对n个小区只需铺设n-1条管线，由于地理环境不同等因素使各条管线所需投资不同，如何使投资成本最低？这是一个讨论图的生成树的问题。15什么是数据结构以上所举例子中的数学模型正是数据结构要讨论的问题。因此，简单地

8、说，数据结构是一门讨论“描述现实世界实体的数学模型（非数值计算）及其上的操作在计算机中如何表示和实现”的学科。16学习数据结构的意义意义算法和数据结构是计算机学科的两大支柱早期计算机科学：研究算法的科学近期计算机科学：研究数据的科学数据结构是程序设计的基础程序=算法+数据结构数据结构是计算机专业的综合性专业基础课程17学习数据结构的要求要求掌握各类基本数据结构类型及其相应的存储结构提高阅读和编写算法的能力针对给定问题，能够选择相应的数据结构，设计和分析算法18基本概