数据结构课件第01章.ppt

数据结构(C语言版) Data Structure 参考书目 计算机及软件技术丛书—— 现代计算机常用数据结构和算法? 潘金贵 编著 南京大学出版社 数据结构习题与解析（C语言篇）修订版 李春葆 主编 计算机专业教学辅导丛书 清华大学出版社 《程序设计》课程与《数据结构》课程的关系 《程序设计》强调程序设计的基本概念和做法，如： 数据类型与表达式 程序流程控制 子程序 递归 数据抽象，等 《数据结构》强调程序设计思想和技术的典型应用，如： 线性表、栈、队列 检索、排序 图、树，等 两者的内容又有交叉 本课程的体系结构 第一章 绪论 介绍数据、数据结构和抽象数据类型的概念。 第二章 —— 第七章 基本数据结构 从抽象数据类型的角度， 分别讨论线性表、栈和队列、 串、数组和广义表、 树、图等基本数据结构及其应用。 1.1 数据结构学科的研究对象 什么是程序、软件？ N.沃思（Niklaus Wirth)教授提出： 程序=算法+数据结构 以上公式说明了如下两个问题： （1）数据上的算法决定如何构造和组织数据 （算法→数据结构） （2）算法的选择依赖于作为基础的数据结构 （数据结构→算法） 软件=程序+文档（软件工程的观点） 2. 电子计算机的主要用途 ?早期： 主要用于数值计算。 ?后来： 应用逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。 数据复杂→数据结构 3. 计算机解决问题的一般步骤 数学模型→算法→程序 (1)数值计算 数学模型→选择计算机语言→编出程序→测试→最终解答。 数值计算的关键是：如何得出数学模型（方程）？ 程序设计人员比较关注程序设计的技巧。 (2)非数值计算问题 数据元素之间的相互关系一般无法用数学方程加以描述。 例1、电话号码查询问题 查找 ：给出一个姓名，如果存在，打印此人的电话号码； 如果不存在，报告没有这个人的标志。 （1）按顺序存储方式：须遍历表 （2）按姓氏索引方式：索引 要写出好的查找算法，取决于这张表的结构及存储方式。 电话号码表的结构和存储方式决定了查找（算法）的效率。 例3 人机对奕问题 例4 多叉路口交通灯管理问题 求解非数值计算的问题 主要考虑的是设计出合适的数据结构及相应的算法。 即：首先要考虑对相关的各种信息如何表示、组织和存储？ 数据结构的研究对象是：非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作。 5. 数据结构课程的形成和发展 形成阶段： 60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。 发展阶段： 数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。 70年代后期，我国高校陆续开设该课程。 6.《数据结构》课程所处的地位 1.2 基本概念和术语 1. 数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 2. 数据元素(Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 一个数据元素可由若干个数据项组成。 数据项是数据的不可分割的最小单位。 3. 数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。 C++的引用类型 引用类型用于给一个变量取一个别名。例如： int x=0; int y=x; //y为引用类型的变量 cout x , y endl; //结果为：0,0 y = 1; cout x , y endl; //结果为：1,1 在语法上，对引用类型变量的访问与非引用类型相同；但在语义上，对引用类型变量的访问实际访问的是另一个变量（被引用的变量）。 引用类型作为函数的参数类型 #include iostream using namespace std; void swap(int x, int y) { int t; t = x; x = y; y = t; } int main() { int a=0,b=1; cout a ‘,’ b endl; //结果为：0,1 swap(a,b); cout a ‘,’ b endl; /