数据结构（C语言描述）

数据结构（C语言描述）计算机系刘延芳第章程序第一章

绪论引言数据结构发展简史及学科地位什么是数据结构基本概念和术语算法概念、算法的描述和算法评价 练习第章程序引言本章介绍了数据结构这门学科诞生的背景,发展历史以及在计算机

科学中所处的地位,重点介绍了数据结构有关的概念和术语,读者学习本章后应能掌握数据,数据元素,逻辑结构,存储结构,数据处理,数据结构,算法设计等基本概念,并了解如何评价一个算法的好坏。20世纪40年代(1946),为了解决弹道轨迹计算问题而产生计算机。早期，计算机应用范围局限于科学和工程计算,处理对象是纯数值性信息,人们称这类问题为“数值计算”。如今,计算机应用远远超出数值计算范围,渗透人类生活的一切领域。计算机处理对象也从纯数值发展到非数值性和具有一定结构的信息。现代计算机科学的观点，把计算机程序处理的一切数值的、非数值信息、乃至程序统称数据（Data），而计算机只是处理数据的工具。处理对象的转变导致系统和应用程序的规模越来越大，结构也相当复杂，单凭程序员经验和技巧已难以设计效率高、可靠性强的程序。

数据的表示方法和组织形式成为处理数据效率的关键。即研究数据的特性以及数据间存在的关系——数据结构（Data

Structure）第章程序发展简史及学科地位数据结构随着计算机产生和发展而发展起来的一门较新学科。1968年开始设立这门课，由美国教授开创数据结构的最初体系。观点是：认为程序设计的实质是对确定的问题选择一种好的结构，加上一种好的

算法。研究内容：软件设计中常用的基本技术地位：核心课程之一，也是非计算机专业的主修课程之一数据结构是介于数学、计算机硬件和软件之间的学科。第章程序什么是数据结构用计算机解决一个具体问题的步骤：从具体问题中抽象出一个适当的数学模型设计一个解此数学模型的算法编出程序、进行测试、调整直至得到最终解答例如：在(有规律)学生通讯录中，1.按照索引查找某一学生2.插入和删除一个学生记录？数据结构直接影响算法的选择和效率。数据结构：研究程序设计中计算机操作对象及其关系和运算的一门学科第章程序基本术语(1)数据:一切能够输入到计算机中并被其处理的信息(文字,表格图像等)。数据元素:也称结点,记录,顶点。是组成数据的基本单位。通常作为一个整体考虑和处理。如图：每一行作为基本单位考虑。字段:一个结点中含有若干个字段(也叫数据项).是构成数据的最小单位。逻辑结构：结点与结点间的逻辑关系。如图:逻辑上是种线性关系。存储结构：数据在计算机中的存储表示。如图：表格数据可有多种存储表示(如：数组、文件等)数据结构：组成数据元素之间构造关系。登录号书号书

名作者出版社价格00001TP22高等数学陈灯高等教育56.0000002TP23实用英语丁萍电子工业20.5000003TP24电子商务通江涛中央电大18.80第章程序数据逻辑结构逻辑结构的四种基本结构：集合：结构中的数据元素除了同属于一种类型外，别无其它关系。线性结构：结构中的数据元素间存在一对一的关系。(3)树形结构：结构中的数据元素间存在一对多的关系。(4)图形或网状结构：结构中的数据元素之间存在多对多的关系。数据的逻辑结构分为线性结构和非线性结构两大类。线性结构:包括数组、链表、栈、队列、优先级队列等;

(2)非线性结构:包括树、图等.第章程序存储结构常见存储结构：顺序存储结构：特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结构.即逻辑上相邻,物理上也相邻.链式存储结构：特点是借助于指示数据元素地址的指针表示数据元素之间的逻辑结构。索引存储结构:

(4)散列存储结构:第章程序基本术语(2)一般：把数据的逻辑结构统称为数据结构，把数据的物理结构统称为存储结构。说明：一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的存储结构。我们的重点是算法的设计。数据字段数据结构分解描述数据元素逻辑结构:结点与结点间的逻辑关系。不依赖于具体形式存储结构：数据在计算机中的存储表示。运算：是最终目的第章程序基本术语(3)数据处理：对数据进行查找、插入、删除、合并、排序统计及简单计算等操作过程。数据类型：指程序设计语言中各变量可取的数据种类。 即是一个值的集合和定义在此值集上的一组操作总称例如：C语言中，整型变量其值集：在某个区间上整数操作：加,减,乘,除,求模等运算按“数据类型”性质分类：原子类型：其值是不可分解的.(整,实,字,枚,指,空类型)

(2)结构类型：其值按某种结构组成(由若干成分)，如：数组第章程序算法的概念算法——解决某一类问题的求解方法——执行特定计算的有穷过程（即指令的有限序列）2.算法的特点：动态有穷:即有限性;经过有限步骤后，算法一定要终止。(2)确定性:指令无二义性.在任何条件下,算法只有一条惟一的执行路径。(3)输入：有0~N个

(4)输出：有1~N个(5)可行性:每条指令都充分基本,即每条指令均可用有限次的计算机指令来实现。算法与程序比较程序是算法在计算机程序设计语言中的具体实现。通常定义一个算法必须提供足够细节,才能转化为程序。(多个程序表示同一算法)算法的有穷性意味着不是所有程序都是算法.例如;操作系统是一个程序不是算法,但把操作系统各种任务看成单独问题,每个问题是由特定算法实现,得到输出结果便终止。算法和程序是相互独立的。第章程序算法的描述自然语言伪代码和流程图计算机高级程序语言（例如C语言）C语言语法结构第章程序自然语言3.如果d=0，计算x=(-b)/(2*a)如果d<0，显示没有实根的信息例：设计算法：求一元二次方程ax2+bx+c=0的根。计算d=b*b-4*a*c如果d>0，计算x1=(-b+sqrt(d))/(2*a)自x2=(-b-sqrt(d))/(2*a然)语言第章程序流程图例：设计算法：求一元二次方程ax2+bx+c=0的根。d=b*b-4*a*cd>0计算x1x2并显示d=0计算x并显示显示无根流程图第章程序计算机语言•••••••••void

solution

(float

a,float

b,float

c){

float

d,x,x1,x2;

d=b*b-4*a*c;if

(d>0){

x1=

(-b+sqrt(d))

/(2*a)

;x2=(-b-sqrt(d))/(2*a);printf(“两个实根：x1=%f,x2=%f\n”,x1,x2);}else

if

(d=0){x=

(-b)

/(2*a);printf(“一个实根：x1=%f\n”,x);

}else

printf(“不存在实根\n”);

}main(

){

float

a,

b,

c;printf(“请输入a,b,c：”scanf(“%f,%f,%f”,&a,&b,&c);solution

(

a,

b,

c);}计算机语言第章程序C语言语法结构(1)输入语句scanf(“格式字符串”[，输出项表])；输出语句printf(“格式字符串”[，输出项表])；赋值语句变量名=表达式；条件语句••if<条件><语句>；或者if<条件><语句1>else<语句2>;第章程序C语言语法结构(2)5.循环语句••••while<表达式><循环体语句>；do<循环体语句>；while<表达式>；••for

（<赋初值表达式1>；<条件表达式2>;<步长表达式3>）<循环体语句>;6.

定义函数语句•<函数返回值类型><函数名>（<类型名><形参1><类型名><形参2>，…）••{<说明语句>；<函数语句部分>；}7.调用函数语句<函数名>（<实参1><实参2>，…）8.

返回语句

return(<返回表达式>)第章程序算法的评价算法评价目的:选择合适算法或对已有的算法进行改进。通常设计一个好的算法应考虑：

(1)正确性——首要条件运行时间:算法的时间复杂度(即:执行一个简单操作所需时 间与操作次数的乘积)。占用存储空间:算法的空间复杂度(含存储算法本身,算法输 入输出数据和算法运行过程中临时占用空间)。简单性:算法易于理解,易于编码及调试。算法的时间复杂度和空间复杂度S(n)=O(f(n))一般用数量级来表示。举例第章程序时间复杂度(Time

Complexity)（1）算法在计算机中运行时间受很多因素(与计算机系统的软硬件环境有关)的影响。通常利用语句频度和渐进时间复杂度衡量时间复杂度。语句频度——指该语句被执行的次数。任何算法都可分解为简单操作(如赋值、比较、移位等)来执行.

(2)假设执行每条语句所需时间为单位时间,则算法运行时间转化为所有语句执行次数,即语句频度之和（频度统计法）。一般情况下,语句频度是问题规模n的函数,用T(n)表示,若有某个辅助函数f(n)使：则称f(n)与T(n)同阶,记作:T(n)=O(f(n))O(f(n))表示时间复杂度(或称渐进时间复杂度),f(n)是最大语频例题求n！算法时间复杂度第章程序时间复杂度(Time

Complexity)（2）算法分析的几个方法：执行一些简单的输入,输出或赋值语句时,可近似认为需要O(1)时间.(2)对于顺序结构,需要依次执行一系列语句所需时间可采用累加求和的方式进行估计对于选择结构,如if语句。它的时间主要消耗在执行then子句或else子句时所用的时间，但if语句判断条件本身也消耗O(1)的时间对于循环语句,它的时间主要耗费在执行循环体以及循环条件的检验上,可采用乘法计算出算法的语频,从而得到算法时间复杂度。对于较为复杂算法,采用先分解为几个容易估计的部分,然后利用求和方法计算出整个算法的时间复杂度。求两个n*n矩阵相乘算法时间复杂度综合考虑第章程序时间复杂度综合考虑由于算法时间复杂度考虑的只是问题规模n的增长率,在难以精确计算语句频度的情况下,只需求出关于n的增长率或阶数即可。有时算法时间复杂度与算法处理的输入数据集有关,算法的时间复杂度难以确定。这时一般采用算法在最坏的情况下复杂度作为时间复杂度。例如：在排序算法中,要求从小到大排序.若给定输入集为从大到小最坏情况,时间复杂度为T(n)=O(n2)若不作特别说明,以后各章均为最坏情况时间复杂度。在分析时间复杂度是,随着问题规模n的增大，各种时间复杂度存在下列大小关系：数量级的大小顺序：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)

<

…<O(2n)<(n!)第章程序例题求n！算法时间复杂度例题：求n！算法时间复杂度Void

fact

(

int

n){

int

i,

total

;/*1次*//*n次*//*n次*//*1次*/total

=

1;for

(

i

=

1;

i

<=

n;

i

++)total

=

total

*

i;

printf

(“%d”,

total

)

;}算法语频之和为T(n)=2n+2,取f(n)=n，则因此,其同阶表示形式为T(n)=O(n)，即算法时间复杂度O(n)第章程序求两个n*n矩阵相乘算法例题：求两个n*n矩阵相乘算法/*语频n*//*n*n*/for

(

i

=1

;i

<=

n

;

i

+

+)for

(

j

=1

;j

<=

n

;

j

+

+){c[

i

][

j

]=0;for

(

k

=1

;k

<=

n

;

k

+

+)/**//**/c[i][j]+=a[