1、1第一章 绪论 2 学学 号号 姓姓 名名 性性别别 籍籍 贯贯 出出生生年年月月 1 98131 刘刘激激扬扬 男男 北北 京京 1979.12 2 98164 衣衣春春生生 男男 青青 岛岛 1979.07 3 98165 卢卢声声凯凯 男男 天天 津津 1981.02 4 98182 袁袁秋秋慧慧 女女 广广 州州 1980.10 5 98203 林林德德康康 男男 上上 海海 1980.05 6 98224 洪洪 伟伟 男男 太太 原原 1981.01 7 98236 熊熊南南燕燕 女女 苏苏 州州 1980.03 8 98297 宫宫 力力 男男 北北 京京 1981.01 9 98
2、310 蔡蔡晓晓莉莉 女女 昆昆 明明 1981.02 10 98318 陈陈 健健 男男 杭杭 州州 1979.12例1：“学生”表格3四皇后问题的状态树四皇后问题的状态树4课程编号课程编号课程名称课程名称 先修课程先修课程C C1 1计算机导论计算机导论无无C C2 2数据结构数据结构C C1 1，C C4 4C C3 3汇编语言汇编语言C C1 1C C4 4C C程序设计语言程序设计语言C C1 1C C5 5计算机图形学计算机图形学C C2 2，C C3 3，C C4 4C C6 6接口技术接口技术C C3 3C C7 7数据库原理数据库原理C C2 2，C C9 9C C8 8编译
3、原理编译原理C C4 4C C9 9操作系统操作系统C C2 2（a）计算机专业的课程设置计算机专业的课程设置5C1C2C3C6C4C5C9C7C8（b）表示课程之间优先关系的有向图表示课程之间优先关系的有向图6（a）结点间管道的代价结点间管道的代价 （b）最经济的管道铺设最经济的管道铺设789 101112 数据结构涉及三个方面：数据结构涉及三个方面：1.数据的逻辑结构数据的逻辑结构-从用户视图看，是面向问题的。从用户视图看，是面向问题的。2.数据的物理结构（存储结构）数据的物理结构（存储结构）-从具体实现视图看，从具体实现视图看，是面向计算机的。是面向计算机的。3.相关的操作及其实现。相关
4、的操作及其实现。Example:学生表：逻辑结构学生表：逻辑结构-线性表线性表 物理结构物理结构-数组数组,链表链表 操作操作-插入插入,删除删除,查找查找13数据结构数据结构包括包括“逻辑结构逻辑结构”和和“物理物理结构结构”两个方面两个方面(层次层次):):逻辑结构逻辑结构 是对数据成员之间的逻辑关是对数据成员之间的逻辑关系的描述，它可以用一个数据成员的集合和系的描述，它可以用一个数据成员的集合和定义在此集合上的若干关系来表示定义在此集合上的若干关系来表示;物理结构物理结构 是逻辑结构在计算机中的表是逻辑结构在计算机中的表示和实现，故又称示和实现，故又称“存储结构存储结构”。14l数据的数
5、据的逻辑结构逻辑结构是从逻辑关系（某种顺序）上观是从逻辑关系（某种顺序）上观察数据，它是独立于计算机的；可以在理论上、察数据，它是独立于计算机的；可以在理论上、形式上进行研究、推理、运算等各种操作。形式上进行研究、推理、运算等各种操作。l数据的数据的存储结构存储结构是逻辑结构在计算机中的实现，是逻辑结构在计算机中的实现，是依赖于计算机的；是数据的最终组织形式。是依赖于计算机的；是数据的最终组织形式。l任何一个任何一个算法的设计算法的设计取决于选定的逻辑结构；而取决于选定的逻辑结构；而算法的最终实现算法的最终实现依赖于采用的存储结构。依赖于采用的存储结构。15例如：Class=(D,S)数据数据
6、集合：D=a,b1,bn,c1,cn,d1,dn关系关系集合：S=R1,R2 R1=,/班长-组长 R2=,|j=2,3,n /组长-组员16ab1c1b2b3bnc2c3cnd2d3dnd1班级Class的逻辑结构的图示17存储结构存储结构是逻辑结构在存储器中的映象。是逻辑结构在存储器中的映象。数据元素的映象：数据元素的映象：任何数据元素在计任何数据元素在计算机中最终都是转化成一个二进制的算机中最终都是转化成一个二进制的位串。位串。关系的映象：关系的映象：18关系的映象方法：关系的映象方法：（关系对x,y）1.1.顺序映象（顺序存储方法）：顺序映象（顺序存储方法）：以相对的存储位置表示后继关
7、系以相对的存储位置表示后继关系例如例如:令 y 的存储位置和 x 的存储位置之间差一个常量 C，而 C 是一个隐含值，整整个存储结构中只含数据元素本身的信息个存储结构中只含数据元素本身的信息 x y192.2.链式映象（链接存储方法）链式映象（链接存储方法）:以附加信息以附加信息(指针指针)表示后继关系表示后继关系需要用一个和 x 在一起的附加信息附加信息（指针（指针)指示 y 的存储位置y x203.3.索引存储方法索引存储方法4.4.散列存储方法散列存储方法2122bindevetclibuser前驱后继2314131211123456789109874562312412354871110
8、291641012115123698725125643125436113318146651619212627不同类型的变量，其所能取的不同类型的变量，其所能取的值的值的范围范围不同，所能不同，所能进行的操作进行的操作不同不同。例如：整型例如：整型(int)值的范围是：值的范围是：-32768 32767（16位）位）操作是：操作是：+，-，*，/，%2829303132 面向对象方法中类的定义充分体现了抽象面向对象方法中类的定义充分体现了抽象数据类型的思想数据类型的思想3334NicklausWirth（1984年TuringAward）为计算机处理为计算机处理问题编制的一问题编制的一组指令集
9、组指令集 处理问题处理问题的策略的策略问题的数问题的数学模型学模型常用的算法的描述方式：常用的算法的描述方式：自然语言自然语言 流程图流程图 特定的表示算法的图形特定的表示算法的图形 符号符号算法描述算法描述 伪语言伪语言 包括程序设计语言的三包括程序设计语言的三 大基本结构及自然语大基本结构及自然语 言的一种语言言的一种语言 类语言类语言 类似高级语言的语言，类似高级语言的语言，例如，类例如，类PASCAL 类类C语言语言3637 void selectSort(inta,constintn)for(int i=n-1;i 0;i-)int j=MaxKey(a,0,i);if(j!=i)s
10、wap(j,i);38int MaxKey(inta,const int low,const int high)int max=low;for(int k=low+1,k=high,k+)if(amax ak)max=k;return max;3940 算法的效率算法的效率包括包括时间代价时间代价和和空间代价空间代价，前者指的是前者指的是算法执行时间算法执行时间；后者指的是算；后者指的是算法执行过程中法执行过程中所需的最大存储空间所需的最大存储空间。两者。两者都与问题的规模有关。都与问题的规模有关。41算法效率的衡量方法：算法效率的衡量方法：q 后期测试后期测试q 事前估计事前估计42 tim
11、e()434445floatsum(floata,const intn)12float s=0.0;3for(int i=0;i n;i+)4s+=ai;5return s;646floatsum(floata,constintn)float s=0.0;count+;/count统计执行语句条数统计执行语句条数for(int i=0;i n;i+)count+=2;/针对针对for语句语句 s+=ai;count+;count+=2;/针对针对for的最后一次的最后一次count+;/针对针对return语句语句return s;执行结束得执行结束得 程序步数程序步数 count=3*n+4
12、47注意：注意：484950例例1：s=0;例例2：s=0;/a 中各行中各行进行累加进行累加for(int i=0;i n;i+)s+=ai;例例3：for(int i=0;i n;i+)/x 中各行数据累加中各行数据累加 sumi=0.0;for(int j=0;jn;j+)sumi+=xij;各个程序段中的关键操作重复执行的次数？各个程序段中的关键操作重复执行的次数？5152O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(2n)O(3n)O(n!)53 T(n,m)=T1(n)+T2(m)=O(max(f(n),g(m)T(n,m)=T1(n)*T2(m)=O(
13、f(n)*g(m)T(n)=O(c*f(n)=O(f(n)54 voidexample(float x,int m,intn,int k)floatsum;for(int i=0;i m;i+)/x 中各行中各行 sumi=0.0;/数据累加数据累加 for(int j=0;jn;j+)sumi+=xij;for(i=0;i m;i+)/打印各行数据和打印各行数据和cout “Line”i “:”sumiendl;O(max(m*n,m)55 template voiddataList:bubbleSort()/对表对表Element0到到 ElementArraySize-1/逐趟进行比较逐
14、趟进行比较,ArraySize 是表当前长度是表当前长度inti=1;intexchange=1;/当当exchange为为0则停止排序则停止排序while(i ArraySize&exchange)BubbleExchange(i,exchange);i+;/一趟比较一趟比较 56template voiddataList:BubbleExchange(const inti,int&exchange)exchange=0;/假定元素未交换假定元素未交换 for(int j=ArraySize-1;j=i;j-)if(Elementj-1Elementj)Swap(j-1,j);/发生逆序发生逆序/交换交换Elementj-1与与Elementjexchange=1;/做做“发生了交换发生了交换”标志标志 571 1n n1 1i i2 21 1)n n(n ni i)(n nT(n)渐近时间复杂度渐近时间复杂度 O(n2)58 S(n)=O(f(n)n S(n)
