数据结构与—chapter 1- 绪论 .pptVIP

一维数组 函数 函数的调用 数组作为函数参数 局部、全局变量 预处理命令 指针 结构体（11.7 用指针处理链表） 3. 用C语言描述算法的有关说明 ● 算法以函数形式描述 函数类型 函数名(函数参数表) /* 算法说明 */ { 局部变量的类型说明；  语句序列；?????? } ● 抽象数据元素类型约定为DataType，由用户利用typedef自行定义。 例. 图书自动检索系统中数据元素的类型定义 struct Date { int year; int month; int day; } //时间 typedef struct Book { long loginnumber; char booktitle[20]; char authorname[20]; long classnumber; char publisher[20]; struct Date publishdate; } BookType // 数据元素类型 typedef BookType DataType // DataType：抽象数据元素类型 作业1 p26，1-11，1-13 ● 数据结构的产生与发展 1）60’s 初，散见于“操作系统”、“编译原理”等专业课 2）1968年作为一门独立的课程，但内容没做明确的规定。几乎和图论，特别和表、树的理论是同义语。后来逐步扩充网络、集合代数论、格、关系等内容，变成了现在称为“离散结构”的内容。 3）1968， 唐?欧?克努特（美）：数据结构=数据的逻辑结构+数据的存储结构+对数据的操作 4）70年代，出现大型程序，结构化程序设计成为主流。程序设计的实质：对所研究的问题选择一种好的结构以及设计一种好的算法。“数据结构”越来越受到重视。 70年代后期，我国高校陆续开设该课程。 目前：数据结构在计算机领域占有重要地位。 发展：空间数据结构、多维图形数据结构 例? for (i=1；i=22*n-37；i++)?????? ?? x++; Part 1): f(n)= ? Part 2): 已知T(n)=22n-37，使用大O表示法，证明T(n) =O(n2). 证明：我们需要找到c和n0 以使22n – 37 = c n2. (1) 假设c = 1. （2） 由（1）和（2）得到: 22n – n2 = 37 n(22 – n) = 37. （3） ?当 n 22, （3）式成立. 因此当c = 1 ，n0 = 23时对所有的n(n≥ n0)满足T(n)≤ c n2 ，即T(n)= O(n2). * 《C语言程序设计（第二版）》，谭浩强，清华大学出版社 Knuth D E.The Art of Computer programming.Addison?Wesley,1973 Wirth N.Algorithms+Data Structures=Programs.Prentice Hall,1978 Gotlieb C C,Gotlieb L R.Data Types and Structures.Prentice Hall,1978 Kochan S G.Programming in C.Hayden Book Company,1983 Williaw Ford et al.Data Structures with C++.Prentice Hall Inc.,1996 Robert Kruse et al.Data Structures Program Design in C.2nd Ed.Prentice Hall,1997 严蔚敏，吴伟民：《数据结构》，第二版，清华大学出版社，1992年。 严蔚敏的书特点是更突出抽象数据类型的特点，采用类C语言（c语言的核心子集+ c++语言的引用调用参数传递方式，因为面向对象程序设计不是数据结构的先修课程） * 随着个人计算机和Internet的飞速发展，形形色色的信息处理系统已渗入到社会和生活的各个领域。但是，信息处理系统的软件和硬件这两大组成部分发展极不平衡，与飞速发展的硬件相比，软件的发展速度相对迟缓，这就需要越来越多的人掌握设计高性能软件的技术，以推动社会信息化的进程。无论是计算机系统软件还是应用软件，其核心是数据结构及其算法，所以作为软件设