第1章 数结构概论.pptVIP

数据结构教学指南 课程性质和任务 　　数据结构是介于数学、计算机硬件和软件之间的一门计算机科学与技术专业的核心课程，是高级程序设计语言、编译原理、操作系统、数据库、软件工程等课程的基础。 　　数据结构课程的内容体系可以从以下三方面认识。 ⑴抽象。从实际问题中抽象出逻辑结构，即分析解决该问题需要用到什么样的数据，数据元素之间的关系，以及基于这种逻辑结构上的基本运算。 ⑵实现。将逻辑结构用适当的物理结构在计算机内表示出来，同时编写算法实现各种基本运算。 ⑶评价。对不同的数据结构进行比较和算法分析。 ● 1.1.2 基本术语 数据结构探讨问题 ⑴如何以最节省存储空间的方式来表示存储在内存中的数据。 ⑵各种不同的数据结构表示法和其相关的算法。 ⑶如何有效地改进算法的效率，使程序的执行速度更快。 ⑷以最优的用户界面呈现数据存取的方法和数据存储的结构。 ⑸数据处理的各种技巧，如排序、有哪些信誉好的足球投注网站等算法的介绍和比较。 ⑹程序模块的单纯化，可以有效提高系统开发的生产力。　　 　　数据结构课程的任务就是将实际问题抽象成数据的逻辑结构，再将逻辑结构用适当的存储结构在计算机中表示出来，并实现基本运算，为编写程序及实现用计算机处理实际问题打下坚实的基础。 ● 1.1.2 基本术语 ● 1.2 数据类型 　　在用高级程序设计语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。例如，C语言中的基本数据类型有：整型、字符型、实型（包括单精度型和双精度型）及枚举型。 　　程序中对变量或常量说明其所属类型的作用是，对它们加上两个约束条件：一是可取值的范围，二是可进行的操作。 　　在高级编程语言中实现的整数都具有下列“数学特性”：　　它是这样一个序列：　　　……,-2,-1,0,1,2,……　　此外，它可以进行“+”、“-”、“*”、“/”及取模等运算。 　　数据类型是一个“值”的集合和定义在此集合上的“一组操作”的总称。 　　 　　所有高级语言中都有“整型”数据类型，它们的实现方法可以各自不同，但对程序员而言，它们是“相同”的。程序员使用它们时仅需了解它们的数学特性，而不需要了解它们在语言中是如何实现的。换句话说，各种语言中实现的是同一个“整数类型”，而这个“整数类”的定义仅对“整数的数学特性”有明确规定。可称这个“整数类型”为“抽象数据类型”。 　　抽象意为提取数学特性。 ● 1.2.1 数据类型 ● 1.2.2 抽象数据类型 抽象数据类型（abstract data type）－简称ADT 　　是指一个数学模型以及定义在该数学模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。 　　Elemtype就是一种抽象数据类型，既可以是整型、实型、字符型或某种结构体类型，具体使用时只需将它重新定义即可。 　　抽象数据类型的实现包括数据结构的实现和操作的实现，因此不仅要借用高级语言中的数据类型来描述它的存储结构，也要利用高级语言中已经实现的固有数据类型的操作来实现抽象数据类型的操作。 　　 ● 1.2.3 参数传递 　　模块化程序设计的思路是将基本操作的每一项功能用函数或子程序实现。在调用函数与被调用函数之间用参数来传递数据。常用的两种参数传递方法： ⑴传值调用： 　　调用函数在引用函数时，只把实参的值传给形参，实参和形参使用不同的内存地址。 ⑵传址调用： 　　调用函数在引用函数时，只把实参的地址传给形参，使调用与被调用函数的参数占用相同的内存地址。 void swap1(int x,int y) {int temp; temp=x;x=y;y=temp; printf(“swaped is:%d,%d\n”,x,y); } void swap2(int *x,int *y) {int temp; temp=*x;*x=*y;*y=temp; } main() {int a,b; a=3;b=50; swap1(a,b); printf(“swaped is:%d,%d\n”,a,b); swap2(a,b); printf(“swaped is:%d,%d\n”,a,b); } 程序执行结果： swaped is 50,3 swaped is 3,50 swaped is 50,3 ● 1.2.3 参数传递 3 y y 3 a 50 b 50 x x 3 a 50 b 传值调用 并互换a,b y y 3 a 50 b x x 3 a 50 b 传址调用 并互换a,b ● 1.2.3 参数传递 ● 1.2.3 参数传递 　　调用函数通过指针传递，不仅可以将数据传递到被