数据结构华中科技大学计算机学院 -,华中科技大学计算机学院,Email Office 87543104 (N1-413) Name 袁 凌,本课程的任务,1.基本数据结构的定义、特性、运算与算法 1.1 线性结构：线性表；栈，队列，串，数组，广义表。 1.2 非线性结构：树,二叉树；图。 2.数据结构的存储结构与实现 选择存储结构,设计算法 3.查找算法：顺序,折半,分块,二叉排序树,哈希等 4.排序算法：插入排序,快速排序，选择排序，归并排序等 5.文件 6.基本应用与综合应用 注：第8章和带*号的内容不作要求。,数据结构教材与参考书,1.数据结构 严蔚敏等 清华大学出版社 2002.7 2.数据结构题集 严蔚敏等 清华大学出版社 1999.2 3.数据结构与算法分析 张 铭等译 电子工业出版社 1998.8 4.数据结构实用教程（C/C+描述） 徐孝凯 清华大学出版社 1999.12,基本要求,1.阅读教材与参考书； 2.完成一定数量的书面作业； 3.使用C或C+完成相应的上机作业 。 成绩 考试（80）+作业和实验（20 ）,第一章 绪 论,1.1什么是数据、结构(关系)、数据结构？ 建立数学模型是分析具体问题的过程，包括： 分析具体问题中操作对象 找出这些对象间的关系，并用数学语言描述 数学模型分两类： 1）数值计算类： 例：根据三条边，求三角形面积。 假定：三条边依次为a,b,c三个实型数， 满足：a0 , b 0 ,c0 ,a+bc ,b+ca, c+ab,则 s= area=,2）非数值计算类： 例1: 5个整数组成的集合： D=20,-5，66, 15,44 其中:20,-5,66等称为数据元素(元素)， 元素与元素之间关系是它们同属于集合D。 元素与元素间无直接关系。 例2: 一列整数：(线性结构) L=(20,-5，66, 15,44） 其中:元素与元素之间在L中是前后关系或线性关系。 L=(20,-5,66,15,44)是一个线性表。,例3 一张登记表DL 序号 姓 名 性 别 年 龄 1 李 刚 男 25 记录1 2 王 霞 女 29 记录2 3 刘大海 男 40 记录3 4 李爱林 男 44 记录4 其中：姓名、性别、年龄是数据项(item)、数据域(field)； (姓名，性别，年龄)是记录(record), C语言将记录(record)定义为”结构”(struct)； 登记表也是一个线性表。,例4 树状结构,其中:A、B、C等是结点(node)； A与B, B与E, A与C之间是层次 关系或父子关系。,华中科技大学(A),计算机学院(B),管理学院(C),成教学院(D),科学系(E),应用系(F),工程系(G),例5 图状结构,A,B,D,C,E,F,G,其中：A、B、C 等是顶点(vertex), 图中任意两个顶点之间都可能有关系。,1.2 基本概念和术语,1.数据（data): 所有能输入到计算机中并被计算机程序加工、处理 的符号的总称。 如：整数、实数、字符、声音、图象、图形等。 2.数据元素(data element): 数据的基本单位。（元素、记录、结点、顶点） 在计算机程序中通常作为一个整体进行考虑和处理。 3.数据项(data item): 是数据的不可分割的最小单位。如：姓名、年龄等 一个数据元素可由一个或多个数据项组成。 如: (姓名、年龄),4.数据对象(data object),由性质相同(类型相同)的数据元素组成的集合。 数据对象是数据的一个子集。 例1 由4个整数组成的数据对象 D1=20,-30,88,45 例2 由正整数组成的数据对象 D2=1,2,3,. 例3 由26个字母组成的数据对象 D3=A,B,C,.,Z 其中：D1，D3是有穷集，D2是无穷集。,6.数据结构(data structure) 相互之间存在一种或多种特定关系的数据元素的集合。 数据元素之间的关系称为结构。 四类基本结构：,集合 线性结构 树形结构 图状结构,1.线性表 2.栈 线性结构 3.队列,双队列 4.数组 数据结构 5.字符串 非 线 性 1.树,二叉树 结 构 2.图,7.数据的逻辑结构 各数据元素之间的逻辑关系。 数据结构(逻辑结构)分类,8.数据的存储结构,数据结构在计算机存储器中的映象(mapping)。 存储结构也称为：存储表示,物理结构,物理表示。,C语言实现方法：char a4=A,B,C,D；,(1)顺序存储结构(向量,一维数组) 例. 线性表L（A,B,C,D）；,(2)非顺序存储结构(链接表） 例. 单链表：分配不一定连续的空间,建立数据 间的联系,(2)非顺序存储结构(链接表） 例. 单链表: 存放数据的空间顺序可任意 一般表达形式： data next Head A B C D 4个结点的单链表,9.数据类型（data type) 是一个值的集合和定义在这个值上的一组操作的总称。 (1)原子类型(如：int,char,float等) (2)结构类型(如：数组,结构,联合体等） 10.抽象数据类型(Abstract Data Type) 与计算机的实现无关的数据类型。 形式定义： ADT 抽象数据类型名 1.数据对象； 2.数据关系:一个或多个关系； 3.一组基本操作/运算 ADT 抽象数据类型名 注意：ElemType是抽象元素类型。,1.3 算法和算法分析,1.算法定义： 求解一个特定任务的指令的有限序列。 例.求a0.an-1中n个数的平均值(假定n0)。 float average(float a ,int n) int i；float s=0.0； /累加器赋初值 for (i=0；in；i+) s=s+ai； /ai累加到s中 s=s/n； /计算平均值 printf(“ave=%f”,s)； /输出 return(s)； /返回 其中：a,n为输入量；s为输出量。,2.算法的5个特征：,(1)有穷性：在有限步(或有限时间)之后算法终止。 例. i=0；s=0； while (i=10) s+=i； i+； (2)确定性：无二义性。,(3)可行性：算法中的操作都是已经实现的基本运算执行有限次来实现的。 (4)输入：有0或多个输入量。 (5)输出：至少有一个输出量。 3.算法设计要求： (1)正确性 a.无语法错误； b.对n组输入产生正确结果； c.对特殊输入产生正确结果； d.对所有输入产生正确结果。 (2)可读性：“算法主要是为了人的阅读与交流”。 (3)健壮性 scanf(“%d”, /一般用于算法函数的返回类型 typedef char ElemType; / 此时char等价于Elemtype; typedef struct node ElemType elem; struct node *next; NODE, *LINK; struct node m,*pm; NODE n,*pn; LINK p; / 等价于 struct node *p;, 函数： 用以表示算法 函数类型 函数名（函数参数表） /算法说明 语句序列 /函数名 注： 算法说明应包括功能说明，输入，输出； 为提高算法可读性，关键位置加以说明； 明确函数实参和形参的匹配规则，以便能正确使用算法函数。 其他,算法描述举例:,问题：设一维数组a0.n-1中已有n个整数, 其中n为个常数,试设计算法:求a中的最大值。 算法基本思想: 1.maxai=a0； 2.i=1； 3.若imaxai,则 maxai=ai； 3.2 i+； 3.3 转3 4.maxai为最大值。,函数(算法),/求数组a中n个元素的最大值 int a_maxint(int a,int n) int j,maxai=a0； /最大值的初值 for (j=1；jmaxai) /比较元素大小 maxaiaj； /新的最大值 printf(maxai%dn,maxai)； /输出 return maxai； ,5.算法的时间复杂度:,算法(或程序)中基本操作(或语句)重复执行的次数的总和 设n为求解的问题的规模,基本操作(或语句)执行次数总和称为语句频度,记作f(n) 时间复杂度记作T(n), T(n)=O(f(n),例1 int s； scanf(“%d”, / 1 do 3. change=FALSE； / 1 或n-1 4. for(j=0；jaj+1) /n-1或n*(n-1)/2 6. aj aj+1； / 0 或n*(n-1)/2 7. change=TRUE； / 0 或n*(n-1)/2 8. 9. while(change for(i=1;i=n;i+) /n次 t=1; /n次 for(j=1;j=i;j+) /n*(n+1)/2次 t*=j; /n*(n+1)/2次 s+=t; /n次 return (s); /1次 f(n)=n+n+n*(n+1)/2+ n*(n+1)/2+n+1=n2+4n+1 T(n)=O(f(n)=O(n2),求i!,例7(续）： 求解：S=1!+2!+.+n! 算法2： long sum_of_fac(int n) long s=0,t,i; t=1; /1次 for(i=1;i=n;i+) /n次 t*=i; /n次 s+=t; /n次 return (s); /1次 f(n)=1+n+n+n+n+1=3n+2 T(n)=O(f(n)=O(n),求i!,6.算法的空间复杂度: 执行算法所需存储空间的大小 记作， S(n)=O(f(n),n为问题的规模 存储空间：寄存指令、常数、变量和输入数据 对数据进行操作的工作单元 实现计算所需用的空间,课后作业,数据结构题集 1.1，1.8,