数据结构听课记录.doc

数据结构听课记录1 数据结构讨论的范畴2 基本概念3 算法及其量度 1 数据结构讨论的范畴 1976年美国wirth(C语言的创始人)出版算法+数据结构=程序设计过 程序设计：为计算机处理问题编制一组指令集。（计算机对某类信息进行某种处理例：此时包含两个问题，一个是怎样进行处理（算法）二是被处理的信息怎样表示（数据结构） 算法：处理问题的策略 数据结构：问题的数学模型 例1求一组（n个）整数中的最大值 算法：基本操作是“比较个数的大小“模型是：（数的大小不知）例2计算机对弈 算法：对弈的规则和策略 模型：棋盘、棋子怎样表示例3足协数据库的管理 算法：需要管理的项目？如何管理？用户界面？ 模型：各种各样的表格和数据库（数据结构描述现实世界体的数学模型（非数值计算）及其上的操作在计算机中表示和实现）数据的基本概概念数据与数据结构数据：所有能被输入到计算机中，且被计算机处理符号的集合计算机操作对象的总称。是计算机处理的信息某种特定符号表示形式。 上面提出集合的那么集合的个体？数据元素：数据中的一个“个体”，数据结构中讨论的基本单位数据项：数据结构中讨论的最小单位（数据元素是数据项的集合）例如：运算员（数据元素）数据结构：带结构的数据元素的集合（结构是指数据元素之间存在的一个因素关系） 例如： 一个含12位数的十进制数可以用三个4位十进制数表示 3214，6587，9345a1(3214),a2(6587),a3(9345) 数据类型 ：例以上有用三个带次序关系的整数表示一个长整数时，可利用C语言中提供整数数组类型，定义为长整数为：typedef in long _int3 数据类型的概念 用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。（类型影响取值范围及相关操作） 数据类型是一个值的集合和定义在此集合上的一组操作的总称 （类据类型两种（简单型和结构（数组，值是分割） 抽象数据类型 Abstract Date Type 简称ADT 指一个数学模型以及定义在此数学模型上的一组操作。ADT 有两个重要特征 数据抽象用ADT描述程序处理的实体时，强调的是其本质的特征，其所能完成的功能以及它和外部用户接口（即外界使用它的方法）3.3算法算法：算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特征1. 有穷性（对任意一组合法输入值，在执行有穷步骤之后一定能结束，即算法中的每个步骤都能在有限时间内完成）2. 确定性(对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行，并且在任何条件下，算法都只有一条执行路径)3. 可行性（使用者一看就知道它的含义）4. 有输入性5. 有输出性算法设计的原则1 正确性（首先，算法应当满足以特定的“规格说明”方式给出的需求。其次，对算法是否正确的理解可以有以下四个层次a. 程序中不含语法错误b. 程序对于几组输入数据能够得出满足要求的结果c. 程序对于精心选择的、典型、苛刻切带有刁难性的几组输入数据能够得出满足要求的结果；d. 程序对于一切佥的输入数据都能得出满足要求的结果。2 可读性（算法主要是为了人的阅读与交流，其次才是为计算机执行，因此算法应该易于人理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。3 健壮性，当输入的数据非法时，算法应恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果，并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在列高的抽象层次上进行处理。4 高效率与低存储量需求（通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间。两者都问题的规模有关）算法效率的衡量方法和准则 方法： 事后统计法缺点：1必须执行程序 2其它因素掩盖算法本质事前分析估算法和算法执行时间相关的因素：1 算法选用的策略2 问题的规模3 编写程序的语言4 编译程序产生的机器代码的质量5 计算机执行指令的速度一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示）,或者说，它是问题规模的函数。假如，随着问题规模n的增长，算法执行时间的增长和f(n)的增长率相同，则可记作：T（n）=O(f(n)称T（n）为算法的（渐近）时间复杂度原操作（i）的执行次数*原操作（i）的执行时间算法的执行时间与原操作执行次数之和成正比从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作，在算法中重复执行的次数作为算法运行时间的衡量准则。算法的存储量包括1 输入数据所占空间2 程序本身所占空间；3 辅助变量所占空间若输入数据所占空间只取决与问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量据所占额外空间。 若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。长度为n的数组，以及移位数p算法思路：1）从第n个元素开始移位，将它直接移到第n-p位，然后再对第n-p位操作，依次类推n-2p，n-3p.；2）上述移位操作经过一定次数后，必定又重新对第n位操作，此时完成了一次循环；比如 当n=6，p=2时，先将第6位移到第4位，第4位移到第2位，第2位移到第6位，循环一次，此时一次循环未能将数组移位完毕。 当n=6，p=5时，6-1；1-2；2-3；3-4；4-5；5-6；此时一次循环即将整个数组移位完毕。3）注意到，当一次循环不能将整个数组完全移位时，可从第n-1位，再进行第1）步的操作；如果还没移完，继续从第n-2位开始循环，依次类推。4）现在的关键之处是移动需要多少次循环。 由数论性质可知： a.当n和p的最大公约数【记为gcd(n,p)】为1时，一次循环必定将整个数组移动完毕。 b.当n和p的最大公约数【记为gcd(n,p)】大于1时，则需要的循环次数就是gcd(n,p)！ 比如，上述n=6，p=2，gcd(6,2)=2，第一次循环从第6位开始，第二次循环从第5位开始，两次过后，移动完成！ n=6，p=5，gcd(6,5)=1，一次循环即可。下面是模拟程序，R是输入数组（设第i位元素下标位i-1） 1. #include 2. #include 3. #include 4. using namespace std;5.6. int gcd(int m, int n) /递归求n,p的最大公约数，也可用迭代实现7. if (n = 0) return m;8. else return gcd(n, m % n);9. 10.11. void leftP(int R, int n, int p) 12. int m = gcd(n, p); / m位n,p的最大公约数，即为需要移动的循环数13. int times = n / m; / 即一次循环移动的元素个数14. for (int i = 1; i = m; i+) 15. int t = n - i; / 每次从第n-i位(此处操作的是下标)开始移动16. int tmp = Rt;17. for (int j = 1; j = times; j+) /每次循环一共移动times个元素18. int t_p = (t - p) % n + n) % n;19. swap(tmp, Rt_p);20. t = t_p;21. 22. 23. 24.25. /*移动前R = 0, 1, 2, 3, 4, .26. 移动后R = p, p+1,.,n,0,1,.,p-127. */28. 29. int main() 30. int n, p;31. int *R;32. printf(数据结构第一大题：时间复杂度O(n)，空间复杂度O(1)的算法！n请分别输入n和p（必须大于0）n);33. scanf(%d %d, &n, &p);34. R = (int *)malloc(sizeof(int) * n);35. for (int i = 0; i n; i+)36. Ri = i;37. leftP(R, n, p);38. f