东南大学数据结构课件第01讲绪论研讨.ppt

设定3个参数，分别是存放元素的数组、参与排列的第一个元素的位置以及数组中元素的个数： perm(a,k,n)，调用参数：a，0，n。 void perm (char *a, const int k，const int n) { // n 是数组a的元素个数，生成a[k],…,a[n-1]的全排列 int i; if (k = = n-1) { // 终止条件，输出排列 for ( i=0; in; i++) cout a[i] “ ”; // 输出包括前 // 缀，以构成整个问题的解 cout endl; } else { // a[k],…,a[n-1] 的排列大于1，递归生成 for ( i = k; i n; i++) { char temp = a[k]; a[k] = a[i]; a[i] = temp; // 交换a[k] // 和 a[i] perm(a,k+1,n); // 生成 a[k+1],…,a[n-1]的全排列 temp = a[k]; a[k] = a[i]; a[i] = temp; // 再次交换 a[k] 和a[i] , 恢复原顺序 } } // else结束 } // perm结束 当n=4，a[4]={a,b,c,d}时，perm(char *a,0,4)调用的循环部分为： for i = 0 to 3 { 交换位置为0和i的元素; k=k+1，递归调用perm函数; 交换位置为i和0的元素;} 循环 交换 数组a的内容 递归调用 i=0 0-0 (a, b, c, d) Perm(a,1,3) i=1 0-1 (b, a, c, d) Perm(a,1,3) i=2 0-2 (c, b, a, d) Perm(a,1,3) i=3 0-3 (d, b, c, a ) Perm(a,1,3) 用n=3 和 a[3]=(a,b,c)调用perm的示意如下： 基本概念 数据：数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中、被计算机程序识别和处理的符号集合。例如：数字、字母、汉字、图形、图像、声音都称为数据。 数值性数据 非数值性数据 数据元素：数据元素是组成数据的基本单位，在计算机中作为一个整体进行考虑和处理。数据元素是一个数据整体中相对独立的单位，但它还可以分割成若干个具有不同属性的项（数据项或字段），故不是组成数据的最小单位。 数据项：具有独立含义的最小标识单位，用于组成数据元素。 姓名 学号 性别 班号 出生日期 入学成绩 年 月 日 关键字：指的是能识别一个或多个数据元素的数据项。若能起唯一识别作用，则称之为 主 关键字，否则称之为 次 关键字。 数据对象：具有相同性质的数据成员（数据元素）的集合，是数据的子集。如：整数、实数等。整数数据对象 N = { 0, ?1, ?2, … } 学生数据对象:初等项（不可分割）、组合项（可再划分） 数据类型：具有相同性质的计算机数据集合（值的集合）及在这个集合上的一组操作。例如，高级语言中用到的整数数据类型，是指由－32768到32767中值构成的集合及一组操作（加、减、乘、除、乘方等）的总称。 结构：数据元素之间的关系。 什么是数据结构 定义: 由某一数据元素的集合以及该集合中所有数据元素之间的关系组成。记为： Data_Structure = {D, R} 其中，D 是某一数据元素的集合，R 是该集合中所有数据元素之间的关系的有限集合。 例：N 个网点之间的不同关系 1 5 6 1 5 2 4 3 6 2 4 3 树形关系（代价最小） 网状关系（连通） 数据结构的内容 数据元素间的逻辑关系，即数据的逻辑结构； 从解决问题的需要出发，为实现必要的功能所建立的数据结构，它属于用户的视图，是面向问题的。数据的逻辑结构独立于计算机，是数据本身所固有的。 数据元素及其关系在计算机存储内的表示，即数据的存储表示（逻辑结构的实现） 存贮结构是逻辑结构在计算机存贮器中的映像，指数据该如何在计算机中存放，是数据逻辑结构的物理存储方式，是属于具体实现的视图，是面向计算机的。必须依赖于计算机。 数据的运算，即对数据元素施加的操作。 运算是指所施加的一