数据结构-使用C语言朱战立

教材：

朱战立编著，数据结构——使用C语言（第3版)，西安交通大学出版社，2003年数据结构

学时数：70（50学时授课＋20学时上机)教材：朱战立编著，数据结构（使用C语言)第3版，西

安交通大学出版社

，2003年参考书:严蔚敏等，数据结构（C语言版)，清华大学出版社数据结构学习指导与典型题解,朱战立等编著,西安交通大学出版社,2002年内容安排3章内容学时章内容学时1绪论47树和二叉树102线性表48图103栈和队列89排序44串210查找45数组411上机（共10次）20合计70对学生的几点要求4上课认真听讲,适当做好笔记。

01考试成绩分两部分：平时成绩（包括出勤和上机实验)占20%，期末成绩占80%。

02课后需要多读课文和参考书,上网查看相关内容,在理解基本内容的基础上,多看、多做习题。

03上机实验十分重要,一定要在上机前做好充分准备,多采用不同的数据存储结构和不同的实现算法解决一个问题。

04讨论5个问题:第1章绪论52019数据结构的基本概念012020抽象数据类型和软件构造方法022021算法和算法的时间复杂度032022算法书写规范041.1数据结构的基本概念6如何记录所有学生记录（及选择何种逻辑数据结构)？选择何种存储结构？若把所有记录依次存储在一个数组中——采用顺序存储结构若采用指针链表——采用链式存储结构解决的方法步骤:举例建立一个学生档案系统。学生表包括学号、姓名、性别、籍贯。要求：查找"王红”是否存在。

7为什么要学习数据结构？什么是程序、软件？N.沃思（NiklausWirth)教授提出：

程序=算法+数据结构以上公式说明了如下两个问题：（1)数据上的算法决定如何构造和组织数据（算法→数据结构)。（2)算法的选择依赖于作为基础的数据结构（数据结构→算法)。

软件=程序+文档（软件工程的观点)电子计算机的主要用途:早期：主要用于数值计算。后来：处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据)。

数值计算解决问题的一般步骤:数学模型→选择计算机语言→编出程序→测试→最终解答。数值计算的关键是：如何得出数学模型（方程)？程序设计人员比较关注程序设计的技巧。

非数值计算问题:数据元素之间的相互关系一般无法用数学方程加以描述非数值计算问题:例1.1电话号码查询问题：按顺序存储方式：须遍历表按姓氏索引方式：索引要写出好的查找算法，取决于这张表的结构及存储方式。电话号码表的结构和存储方式决定了查找（算法)的效率。

例1.2田径赛的时间安排问题（无向图的着色问题)：设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示)设计比赛日程表，使得在尽可能短的时间内完成比赛。

非数值计算问题:010212（1)设用如下六个不同的代号代表不同的项目：跳高

跳远

标枪

铅球100米200米A B CDE F（2)用顶点代表比赛项目不能同时进行比赛的项目之间连上一条边。（3)某选手比赛的项目必定有边相连（不能同时比赛)。

非数值计算问题

----田径赛的时间安排问题解法13姓名项目1项目2项目3丁一ABE马二CD张三CEF李四DFA王五BF比赛时间比赛项目1A，C2B，D3E4F只需安排四个单位时间进行比赛非数值计算问题:主要考虑的是设计出合适的数据结构及相应的算法。即：首先要考虑对相关的各种信息如何表示、组织和存储?因此，可以认为：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。

数据结构课程的形成和发展:15形成阶段:60年代初期，"数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，"数据结构”被列入美国一些大学计算机科学系的教学计划。

发展阶段:数据结构的概念不断扩充，包括了网络、集合代数论、关系等"离散数学结构”的内容。

70年代后期,我国高校陆续开设该课程。

16数据结构课程的地位17它是计算机专业及相关专业的核心课程之一,是计算机及相关专业的重要骨干基础课程。

它针对非数值计算的程序设计问题,研究计算机的操作对象以及它们之间的关系和操作。即其研究目的是研究有效地组织和处理非数值类型数据的理论、技术和方法。

《数据结构课程》所处的地位:18数据结构的核心研究内容19数据的逻辑结构、存储结构及它们之间的关系和相应的基本操作运算的定义和实现。本书围绕数据结构的三种基本结构：线性结构（第2-5章)、树形结构（第7章)和图形结构（第8章)展开讨论，研究解决如下问题：一个具体问题的逻辑数据结构是什么？适宜选用什么样的存储结构？采用什么样的操作实现算法效率更高？2.基本术语201数据：所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息)。

2数据元素:是数据的基本单位,具有完整确定的实际意义。在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。

3数据项:构成数据元素的项目。它是数据不可分割的最小单位。4数据类型：指一个类型和定义在这个类型上的操作集合。例：C语言（基本类型：整型、浮点型、字符型等构造类型：数组、结构、联合、指针、枚举等)抽象数据类型（AbstructDataType，简称ADT)：是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。

1抽象数据元素:抽象定义的、没有实际含义的数据元素。

22.基本术语(续）22数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。或按照一定逻辑关系组织，并按一定存储方法存储的数据的集合，且需要定义一系列运算。逻辑结构、存储结构和运算合称为三要素。表示为:01Data_Structure=（D,R)02其中,D—元素有限集,R—关系有限集03数据结构涵盖的内容23集合结构：

仅同属一个集合线性结构:一对一(1:1)树

结

构:一对多(1:n)图

结

构:多对多(m:n)线性答:指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

非线性逻辑结构可细分为4类:解释1：

什么叫数据的逻辑结构?此结构为线性的。D={a,b,c,d,e,f}R={(a,e),(b,c),(c,a),(e,f),(f,d)}例:用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。S=(D,R)01bcaefd解:上述表达式可用图形表示为:02该结构是非线性的。D={di|1≤i≤5}

R={(di,dj),i<j}（2)S=(D,R)d1d5d2d4d3解:上述表达式可用图形表示为:答：物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像)。它依赖于计算机。

存储结构可分为4大类:例:复数3.0－2.3i的两种存储方式:顺序、链式、索引、散列－2.303023.00300041503023.003000415－2.3法1:地址

内容法2:地址

内容2字节解释2：什么叫数据的物理结构?答:在数据的逻辑结构上定义的操作算法。它在数据的存储结构上实现。

最常用的数据运算有5种:插入、删除、修改、查找、排序解释3：什么是数据的运算?练习29设有数据逻辑结构为：line=(D,R);其中D={01，02，03，04，05，06};01R={r};02r={<01,02>,<02,05>,<05,04>,<04,06>,<06,03>}.03试分析该数据结构属于哪种逻辑结构。0401->02->05->04->06->0305线性结构06设有数据逻辑结构为tree={D,R},其中D={01,02,03,04,05,06,07,08};R={r};r={<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<03,07>,<07,08>}.试分析该数据结构属于哪种逻辑结构.树型作业31什么是逻辑结构与存储结构，他们之间的关系如何?设有数据逻辑结构为：line=(D,R);其中D={a，b，c，d，e，f,g};R={r};r={<a，b>，<b，c>,<c,d>,<d,e>,<e,f>,<f,g>}.试画出对应的图形并说明属于哪种逻辑结构.将上述关系改为r={<a,b>,<a,c>,<b,d>,<b,e>,<c,f>,<c,g>}.试画出对应的图形并说明属于哪种逻辑结构.1.4什么是抽象数据类型34数据类型与抽象数据类型的区别?抽象数据类型如何定义?抽象数据类型如何表示和实现?讨论:1数据类型与抽象数据类型的区别35231数据类型:是一个值的集合和定义在该值上的一组操作的总称。

抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作)它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机)2抽象数据类型如何定义36抽象数据类型可以用以下的三元组来表示：ADT=（D，R，P)ADT抽象数据类型名{

数据对象:<数据对象的定义>

数据关系:<数据关系的定义>

基本操作:<基本操作的定义>}ADT抽象数据类型名ADT常用定义格式数据对象D上的关系集D上的操作集抽象数据类型如何表示和实现01抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等)来表示和实现。（参看课本P28，线性表的抽象数据类型，思考用具体C语言如何实现)02注意:上机时要必须用具体语言实现，如C或C++等03队列的抽象数据类型定义ADTQueue{

数据对象:D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}

数据关系:R1={<ai-1,ai>|ai-1,ai∈D,i=1,2,…,n}

约定a1为队列头，an为队列尾。

基本操作:

InitQueue(&Q)

操作结果:构造一个空队列Q。

DestroyQueue(&Q)

初始条件:队列Q已存在。

操作结果:销毁队列Q。QueueLength(Q)

初始条件:队列Q已存在。

操作结果:返回Q的数据元素个数，即队列的长度。

算法效率的度量什么是算法?如何评判算法的好坏?时间复杂度和空间复杂度如何表示?计算举例讨论:什么是算法?如何评判一个算法的好坏?常用时间复杂度来衡量算法评价指标：常用空间复杂度来衡量01正确性、可读性、健壮性、高效率与低存储量需求(见课本P20)算法:是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。

算法的基本特性:02有穷性、确定性、可行性、必有输出好的程序设计:好算法＋好结构1有穷性:一个算法必须总是(对任何合法的输入值)在执行有穷步之后结束，且每一步都可在有穷时间内完成。

2确定性:每条指令必须有确切的含义3可行性:算法是能行得通的4必有输出正确性:算法应当满足具体问题的需求可读性:算法的可读性有利于人们对算法的理解健壮性:当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的结果。

效率与低存储需求：时间短，存储空间少（两者不能兼得)1.3.3算法效率的度量43求解同一个问题,可以有许多不同的算法,究竟如何评价这些算法的好坏呢?显然,选用的算法首先应该是"正确的”.此外,主要考虑如下三点:执行算法所消耗的时间;执行算法所消耗的存储空间,其中主要考虑辅助存储空间.算法应该易于理解,易于编码,易于调试等.时间复杂度(timecomplexity)01040203语句频度(FrequencyCount)语句重复执行的次数语句的执行时间语句频度×执行一次所需时间算法的执行时间所有语句执行时间的总和算法的渐近时间复杂度(asymptotictimecomplexity),简称时间复杂度

因为语句的执行时间取决于机器的硬件速度、指令类型、以及编译所产生的代码质量,所以将算法中基本操作的最大语句频度作为算法执行时间的量度,它是问题规模n的某个函数f(n)时间复杂度表示法

记作T(n)=O(f(n))(称为大O表示法)，表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。时间复杂度往往不是精确的执行次数，而是估算的数量级，它着重体现的是随着问题规模n的增大，算法执行时间的变化趋势

时间复杂度的数量级O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(3n)<O(n!)时间复杂度的求解例如在下列三个程序段中：(a)x=x+1;(b)for(i=1;i<=n;i++)x=x+1;(c)for(j=1;j<=n;j++)for(k=1;k<=n;k++)x=x+1;基本语句均为x=x+1;程序段(a)中频度为1，则T(n)=O(1);程序段(b)中频度为n，则T(n)=O(n);程序段(c)中频度为n2，则T(n)=O(n2)。

算法1.1的时间复杂度voidsort(ElemTypeS[MAXSIZE]，intn)

／*对数组S中的n个数据按由大到小的顺序排序并输出,n<MAXSIZE*/{for(i=1;i<n;i++)for(j=i；j<=n；j++)if(S[i]．score＜S[j]．score){t=S[i]；S[i]=S[j]；S[j]=t；}for(i=1；i<=n；i++)printf(“%8d%8d%8d\n”,i,S[i].no,S[i].score);}/*sort*/∵算法中if语句的执行频度为：n+(n-1)+(n-2)+…+3+2+1=n*(n+1)/2∴T(n)=O(n2)加法规则(针对并列程序段)T(n,m)=T1(n)+T2(m) =O(max(f(n),g(m)))乘法规则(针对嵌套程序段)

T(n,m)=T1(n)*T2(m)

=O(f(n)*g(m))算法1.1中既有并列程序段又有嵌套程序段

并列程序段:T(n)=O(max(n2,n))=O(n2)

嵌套程序段:T(n)=O(f(n)*g(n))=O(n2)有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。例如:Voidbubble-sort(inta[]，intn)fo