安徽理工大学 数据结构 (C语言版) 孙克雷 —1— 课程介绍 课程类型：必修，学科基础课 课时：48+16 教材 严蔚敏.数据结构(C语言版).清华大学出版社 考核方式： 考试60% 平时40%(考勤20%，作业40%，实验40%) 课程设计 —2— —2— 课程关系 前期课程 计算机基础C语言离散数学 承上启下数据结构 —4— 后期课程 操作系统编译原理数据库原理软件工程 —4— 课程关系 掌握基本编程方法 C语言 学习识字 掌握数据组织和数据处理的方法 数据结构 学习写作文 —5— 基本要求 课程关系 与语文学习过程类比 —5— 研究内容数据结构研究什么？ 数据结构是一门研究用计算机进行信息表示和处理的科学。
随着应用问题的不断复杂，导致许多程序的规模很大，结构又相当复杂。
因此，必须分析待处理问题中的对象的特征及各对象之间存在的关系。
—6— —6— 课程内容 介绍一些最常用的数据结构，阐明数据结构内在的逻辑关系，讨论它们在计算机中的存储表示，并结合各种数据结构，讨论其各种操作的实现算法。
—7— —7— 教学内容 文件 外部排序 内部排序 课程内容 查找 动态存储管理 图 —8— 绪论 线性表 栈和队列 串 树和二叉树 数组和广义表 —8— 学习要求 第1章绪论 了解数据结构的目的和意义掌握数据结构基本概念和相关术语了解算法的基本概念和算法评价依据掌握算法的时间复杂度 —9— —9— 目录页 ContentsPage 什么是数据结构基本概念和术语抽象数据类型的表示与实现算法和算法分析 —10— —10— 1.1什么是数据结构 NiklausWirth：Algorithm+DataStructures=Programs 程序设计: 算法:数据结构: 为计算机处理问题编制一组指令集 处理问题的策略问题的数学模型 —11— 1.1什么是数据结构 计算机求解问题的一般步骤： 从具体问题抽象出一个适当的数学模型设计或选择一个解此数学模型的算法编出程序进行调试、测试得到最终的解答。
具体 数学 算 编程、 问题 模型 法 调试 —12— 1.1什么是数据结构 数值问题: 例1求解梁架结构中的应力。
数学模型:KU=Ma这11些是典型数值x1数据b1问题，当涉及×到非数值＝数据时a，nn又如何解xn决？bn …… 例2预报人口增长情况。
数学模型: N(t)＝N0ert—13— 1.1什么是数据结构 例1-1书目自动检索系统 线性表 001高等数学书目樊卡映片川 S01 002理论力学罗远祥 L01 书目文件 003高登等录数号学：华罗庚 S01 004 线性代数栾汝书 书名： S02 … … … … 索引表 作者名： 按书名每本书的信分息类占号据：一行，按所作有者名信息按登录按号分类号 高等数顺学序依001次,00排3出列版构单成位樊：一映张川
表0格01 L002 理论力表学中书002目信出息版依时据间华：登罗录庚号0的02大小存在着S一0种01,003 线性代数004 前后关系 价格： 栾汝书 004 … … —…14—… …… 1.1什么是数据结构 树 例1-2人机对奕问题 —15— 1.1什么是数据结构 图 例1-3多叉路口交通灯管理问题 CD
B ABACADBABCBD EA DADBDC EAEBECED —16— 1.1什么是数据结构 解决数值计算问题的核心:建立适当的数学模型 解决非数值计算问题的核心:寻找适当的数据结构！ 数据结构是一门研究非数值计算的程序设计问题时处理的操作对象以及它们之间的关系和操作等等的学科。
—17— 1.1什么是数据结构 数据结构的研究对象：非数值数据之间的结构关系，如何表示，如何 存储，如何处理的问题。
本课程讨论的问题： 应用中常用的几种数据间的结构关系，以及如何存储，如何处理它们。
—18— 目录页 ContentsPage 什么是数据结构基本概念和术语抽象数据类型的表示与实现算法和算法分析 —19— —19— 1.2基本概念和术语 数据：是对客观事物的符号表示。
学号6201001620100262010036201004... 姓名张三李四王
五 语文859287 数学548474 C语言926473 定例义：二张：三能的输C入语到言计考算试机成中绩并为被92计分算，机92程就序是处该理同的学符的号成的绩总数称据。
。
例：图像、声音等。
—20— 1.2基本概念和术语 数据元素是数据的基本单位。
在计算机程序中通常作为一个整体考虑和处理 数据项是数据不可分割的最小单位。
学号6201001620100262010036201004... 姓名张三李四王
五 语文859287 数学548474 C语言926473 一个数据元素一个数据项 整—2个1—表的记录是学生成绩数据 1.2基本概念和术语 数据结构：带结构的数据元素的集合 假设用三个4位的十进制数表示一个含12位数的十进制数。
例如: 3214,6587,9345─a1(3214),a2(6587),a3(9345) 则在数据元素a1、a2和a3之间存在着“次序”关系a1,a2、a2,a3 3214，6587，9345a1a2a3 ≠ —22— 6587，3214，9345a2a1a3 1.2基本概念和术语 数据结构：带结构的数据元素的集合 又例，在2行3列的二维数组{a1,a2,a3,a4,a5,a6} 中六个元素之间存在两种关系: a1a2a3a4a5a6 行的次序关系:row={,,,} 列的次序关系:col={,,} a1a3a5a2a4a6 a1a2a3—23—a4a5a6 1.2基本概念和术语 数据结构：带结构的数据元素的集合 再例，在一维数组{a1,a2,a3,a4,a5,a6}的数据元素之间存在如下的次序关系: {|i=1,2,3,4,5}可见，不同的“关系”构成不同的“结构” —24— 1.2基本概念和术语 逻辑结构：“数据结构”定义中的“关系”指数据间的逻辑关系。
集合结构线性结构 树形结构 图状结构—25— 1.2基本概念和术语 数据的逻辑结构 集合：元素间为松散的关系。
线性结构：元素间为严格的一对一关系。
如上面的成绩表中各元素 —26— 1.2基本概念和术语 数据的逻辑结构 树形结构：元素间为严格的一对多关系 图状结构：元素间为多对多关系 —27— 1.2基本概念和术语 数据的逻辑结构 数据结构的形式定义为:数据结构是一个二元组Data_Structures=(
D,S) 其中：D是数据元素的有限集，S是D上关系的有限集。
—28— 1.2基本概念和术语 数据的逻辑结构 数据结构是一个二元组 Data_Structures=(
D,S) D={ki|1≤i≤n,n≥0}ki表示集合D中的第i个数据元素n为D中结点的个数若n=
0,则D是一个空集,表示D无结构可言,有时也可以认为它具有任意的结构 —29— 1.2基本概念和术语 数据的逻辑结构 数据结构是一个二元组 Data_Structures=(
D,S) S={rj|1≤j≤m,m≥0}rj表示集合S中的第j个二元关系(简称关系)m为S中关系的个数若m=
0,则S是一个空集,表明集合D中的元结点间不存在任何关系,彼此是独立的 —30— 1.2基本概念和术语 数据的逻辑结构 例1-4用二元组表示学生表，学生表中共有7个结点,依次用k1～k7表示,则对应的二元组表示为： Student=(
D,S)其中：D={k1,k2,k3,k4,k5,k6,k7} S={,,,,,} 逻辑结构图如下： k1 k2 k3 k4 k5 k6 k7 —31— 1.2基本概念和术语 数据的逻辑结构 例1-5设数据的结构描述如下：Tree=(
D,R)D={1,2,3,4,5,6}R={<1,2>,<1,3>,<3,4>,<3,5>,<4,6>}画出其逻辑结构图？ —32— 1.2基本概念和术语 数据的存储结构 ——逻辑结构在存储器中的映象“数据元素”的映象？“关系”的映象？ —33— 1.2基本概念和术语 数据的存储结构 数据元素的映象方法：用二进制位(bit)的位串表示数据元素 (321)10=(501)8=(101000001)2A=(101)8=(001000001)
2 —34— 1.2基本概念和术语 数据的存储结构 关系的映象方法：（表示x,y的方法） 顺序结构以数据元素在存储器中的相对位置 表示后继关系… 03003.0 复数z1=3.0-2.3iz2=-0.7+4.8i 0302-2.3… 0632-0.706344.8 —35— … 1.2基本概念和术语 数据的存储结构 关系的映象方法：（表示x,y的方法） 链式结构以附加信息(指针)表示后继关系 复数z1=3.0-2.3i —36— …0415-2.3 …06113.006130415 … 1.2基本概念和术语 数据结构：数据的逻辑结构数据的存储结构 线性结构树形结构图形结构 顺序存储链式存储 —37— 1.2基本概念和术语 数据类型 不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。
数据类型是一个值的集合和定义在此集合上的一组操作的总称。
—38— 1.2基本概念和术语 数据类型 分类：(按值是否可分)原子类型：每一个对象仅由单值构成的类型结构类型：每一个对象可由若干成分按某种结构构成的类型。
—39— 1.2基本概念和术语 抽象数据类型 定义：一个数学模型以及定义在此数学模型上的一组操作。
抽象数据类型可以用三元组来表示：ADT=（
D，S，P） 数据对象D上的关系集D上的操作集 —40— 1.2基本概念和术语 抽象数据类型 ADT抽象数据类型名{数据对象：〈数据对象的定义〉数据关系：〈数据关系的定义〉基本操作：〈基本操作的定义〉 }ADT抽象数据类型名 基本操作名（参数表）初始条件：〈初始条件描述〉操作结果：〈操作结果描述〉 —41— 1.2基本概念和术语 抽象数据类型 Put(&T,i,e)初始条件：三元组T已存在。
操作结果：改变T的第i个元素的值为e。
初始条件描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。
若初始条件为空，则省略之。
操作结果说明了操作正常完成之后，数据结构的变化状况和应返回的结果。
—42— 1.2基本概念和术语 例1-6抽象数据类型复数的定义： ADTComplex{数据对象： D＝{e1,e2｜e1,e2∈RealSet}数据关系： R＝{|e1是复数的实数部分，e2是复数的虚数部分} 基本操作：… } —43— 1.2基本概念和术语 例1-6抽象数据类型复数的定义： 基本操作：AssignComplex(&Z,v1,v2)操作结果：构造复数
Z,其实部和虚部分别被赋以参数v1和v2的值。
DestroyComplex(&Z)操作结果：复数Z被销毁。
GetReal(
Z,&realPart)初始条件：复数已存在。
操作结果：用realPart返回复数Z的实部值。
—44— 1.2基本概念和术语 例1-6抽象数据类型复数的定义： 基本操作：GetImag(
Z,&ImagPart)初始条件：复数已存在。
操作结果：用ImagPart返回复数Z的虚部值。
Add(z1,z2,&sum)初始条件：z1,z2是复数。
操作结果：用sum返回两个复数z1,z2的和。
—45— 目录页 ContentsPage 什么是数据结构基本概念和术语抽象数据类型的表示与实现算法和算法分析 —46— —46— 1.3抽象数据类型的表示与实现 本书采用伪码和C语言之间的类C语言作为描述的工具，有时也采用伪码描述一些只含抽象操作的抽象算法。
这使得数据结构和算法的描述和讨论简明清晰，不拘泥于C语言的细节，又能容易转换成C或C++程序。
—47— 1.3抽象数据类型的表示与实现
(1)预定义常量和类型 //函数结果状态代码 #defineTRUE
1 #defineFALSE
0 #defineOK
1 #defineERROR
0 #defineINFEASIBLE -
1 #defineOVERFLOW -
2 //Status是函数的类型，其值是函数结果状态代码 typedefintStatus; —48— 1.3抽象数据类型的表示与实现
(2)结构类型定义 数据结构的表示(存储结构)用类型定义(typedef)描述。
数据元素类型约定为ElemType，由用户在使用该数据类型时自行定义。
typedefintElemType; —49— 1.3抽象数据类型的表示与实现
(3)基本操作 基本操作的算法都用以下形式的函数描述： 函数类型函数名（函数参数表）{ //算法说明 语句序列 }//函数名 除了函数的参数需要说明类型外，算法中使 用的辅助变量可以不作变量说明，必要时对其 作用给予注释。
—50— 目录页 ContentsPage 什么是数据结构基本概念和术语抽象数据类型的表示与实现算法和算法分析 —51— —51— 1.4算法和算法分析
一、算法
二、算法的设计要求
三、算法效率的度量
四、算法的存储空间需求 —52— 1.4算法和算法分析 引例写程序计算给定多项式在给定点x处的值 doublef1(intn,doublea[],doublex){inti; doublesum=a[0];for(i=1;i<=n;i++) sum+=(a[i]*pow(x,i));returnsum;} —53— 1.4算法和算法分析 引例写程序计算给定多项式在给定点x处的值 doublef2(intn,doublea[],doublex){inti; doublesum=a[n];for(i=n;i>0;i--) sum=a[i-1]+x*sum;returnsum;} —54— 1.4算法和算法分析 clock()：捕捉从程序开始运行到clock()调用时所用时间。
其时间单位是clocktick，即时钟打点。
常数CLK_TCK为机器时钟每秒所走的时钟打点数。
—55— 1.4算法和算法分析 #include#include clock_tstart,; 在给定点x=1.1处的值 doubleduration; intmain(){ start=clock(); 解决问题的效率和算法的巧妙程度有关 MyFunction(); =clock(); duration=((double)(-start))/CLK_TCK; return0;} —56— 1.4算法和算法分析 1.4.1算法 算法(Algorithm)：是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。
一个算法必须满足以下五个重要特性：
1．有穷性
2．确定性
3．可行性
4．有输入
5．有输出 —57— 1.4算法和算法分析 1.4.1算法 有穷性：算法必须在有限步内结束； haha(){/*onlyajoke,donothing.*/ }main(){ printf("请稍等...您将知道世界的未日...");while
(1) haha();}—58— 1.4算法和算法分析 1.4.1算法 有穷性：算法必须在有限步内结束；确定性：组成算法的操作必须清晰无二义性。
可行性：组成算法的操作必须能够在计算机上 实现。
输入：0个或多个输入；输出：1个或多个输出； —59— 1.4算法和算法分析 1.4.2算法的设计要求正确性 程序不含语法错误 max(inta,intb,intc){if(a>b){ if(a>c)returnc;elsereturna;}} —60— 1.4算法和算法分析 1.4.2算法的设计要求正确性 程序对于几组输入数据能够得出满足规格说明要求的结果 max(inta,intb,intc){if(a>b){ if(a>c)returna;elsereturnc;}}/*8,6,7*//*9,3,2*/ —61— 1.4算法和算法分析 1.4.2算法的设计要求 正确性 程序对于精心选择的典型、苛刻的输入数据能够得出满足规格说明要求的结果 max(inta,intb,intc){if(a>b){ if(a>c)returna;elsereturnc;}else{ if(b>c)returnb;elsereturnc;}} —62— 1.4算法和算法分析 1.4.2算法的设计要求正确性 程序对于一切合法的输入数据都能产生满足规格说明要求的结果。
—63— 1.4算法和算法分析 1.4.2算法的设计要求正确性可读性健壮性效率与低存储量需求 —64— 1.4算法和算法分析 空间复杂度S(n)—根据算法写成的程序在执行时占用存储单元的长度。
这个长度往往与输入数据的规模有关。
空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常中断。
时间复杂度T(n)—根据算法写成的程序在执行时耗费时间的长度。
这个长度往往也与输入数据的规模有关。
时间复杂度过高的低效算法可能导致我们在有生之年都等不到运行结果。
—65— 1.4算法和算法分析 1.4.3算法效率的度量 算法效率依据该算法编制的程序在计算机上执行所消耗的时间来度量 衡量算法效率的方法事后统计法事前分析估算法 —66— 1.4算法和算法分析 1.4.3算法效率的度量和算法执行时间相关的因素：
1．算法选用的策略
2．问题的规模
3．编写程序的语言
4．编译程序产生的机器代码的质量
5．计算机执行指令的速度 —67— 1.4算法和算法分析 1.4.3算法效率的度量 算法执行时间 =∑原操作(i)的执行次数×原操作(i)的执行时间 算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，则可记作：T(n)=O(f(n))，称T(n)为算法的(渐近)时间复杂度。
如何估算算法的时间复杂度？ —68— 1.4算法和算法分析 doublef1(intn,doublea[],doublex) {inti; doublep=a[0];for(i=1;i<=n;i++) p+=(a[i]*pow(x,i)); (1+2+…+n)=(n2+n)/2次乘法 returnp;} T(n)=C1n2+C2n doublef2(intn,double{inti; doublep=a[n];for(i=n;i>0;i--) p=a[i-1]+x*p;returnp;} —69— a[],doublex) n次乘法T(n)=C*n 1.4算法和算法分析 1.4.3算法效率的度量在分析一般算法的效率时，我们经常关注下面 两种复杂度最坏情况复杂度Tworst(n)平均复杂度Tavg(n) Tavg(n)<=Tworst(n) —70— 1.4算法和算法分析 1.4.3算法效率的度量输入规模n与时间复杂度 —71— 1.4算法和算法分析 —72— 1.4算法和算法分析 1.4.3算法效率的度量 若两段算法分别有复杂度T1(n)=O(f1(n))和T2(n)=O(f2(n))，则T1(n)+T2(n)=max(O(f1(n)),O(f2(n)))T1(n)*T2(n)=O(f1(n))*O(f2(n)) 若T(n)是关于n的k阶多项式，那么T(n)=O(nk)一个for循环的时间复杂度等于循环次数乘以循 环体代码的复杂度 —73— 1.4算法和算法分析 1.4.3算法效率的度量 例求下面程序段的时间复杂度
1.{++x;s=0;} 2.for(j=0;j(1)T(n)=O(n2)T(n)=O(n) 1.4算法和算法分析 1.4.3算法效率的度量例求下面程序段的时间复杂度 4.for(i=2;i<=n;++i)for(j=2;k<=i-1;++j){++x;a[i][j]=x;} 语句的频度表达式为(n-1)(n-2)/2T(n)=O(n2) —75— 1.4算法和算法分析 1.4.4算法的存储空间需求 算法的空间复杂度定义为:S(n)=O(g(n)) 表示随着问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率相同。
输入数据所占空间程序本身所占空间辅助变量所占空间 —76—