数据结构 第一章概论

数据结构

---------------------------------------------数据结构第一章概论第一章绪论1.1数据结构研究什么？

将现实世界中的数据描述及关系表示出来，并存储到计算机内，供用户程序操作。现实世界中的数据描述及关系：

4种：离散型，线性结构，层次结构，网状结构。离散数学：研究离散型。数据结构：研究线性结构，层次结构和网状结构。线性结构：线性表表示。层次结构：树形结构表示。网状结构：图结构表示。数据结构研究：数据逻辑结构，存储结构及施加其上的运算。

数据结构第一章概论例1L=(20,-5,66,15,44)是一个线性表例2一张登记表DL

序号姓名性别年龄

1李刚男25记录12王霞女29记录23刘大海男40记录34李爱林男44记录4其中：姓名、性别、年龄是数据项(item)、数据域(field)；

(姓名，性别，年龄)是记录(record),C语言将"记录"(record)定义为”结构”(struct)；登记表也是一个线性表。

数据结构第一章概论例3家族中父子关系是一种层次结构--树

T

张一张三张二一张三一张三小张三大

张二张四

层次结构：部门之间的隶属关系：学校->系->科->班领导和被领导之间领导关系：主席->部长->司长->处长->科长数据结构第一章概论例4无向图G

ABDCEFG其中：A、B、C等是顶点(vertex),

图中任意两个顶点之间都可能有关系。网络结构：电网，电信网，计算机通信网等。数据结构第一章概论

1.基本数据结构的定义、特性、运算与算法

1.1线性结构：线性表；栈,队列,双队列；数组,串。

1.2非线性结构：树,二叉树；图,网络。

2.数据结构的存储结构与实现选择存储结构,设计算法

3.查找算法：顺序,折半,分块,哈希,二叉排序树等

4.排序算法：内部排序,外部排序

5.文件

6.基本应用与综合应用

要求具备的知识：

c语言及程序设计，具有一定的程序设计能力。

本课程的内容和任务数据结构第一章概论1.2基本概念和术语1.数据（data)----

所有能输入到计算机中并被计算机程序加工、处理的符号的总称。如：整数、实数、字符、声音、图象、图形等。2.数据元素(dataelement)---

数据的基本单位。（元素、记录、结点、顶点）在计算机程序中通常作为一个整体进行考虑和处理。3.数据项(dataitem)----

是数据的不可分割的最小单位。如：姓名、年龄等一个数据元素可由一个或多个数据项组成。如:(姓名、年龄)数据结构第一章概论4.数据对象(dataobject)——

由性质相同(类型相同)的数据元素组成的集合。

数据对象是数据的一个子集。例1由4个整数组成的数据对象

D1={20,-30,88,45}

例2由正整数组成的数据对象

D2={1,2,3,...}

例3由26个字母组成的数据对象

D3={A,B,C,...,Z}

其中：D1，D3是有穷集，D2是无穷集。5.抽象数据对象

ElemSet={某种同类型的数据元素}数据结构第一章概论6.数据结构(datastructure)----

数据之间的相互关系，即数据的组织形式。内容包括：数据逻辑结构、数据存储结构和数据运算。

数据逻辑结构：数据元素之间的逻辑关系。数据存储结构：数据元素及其关系在存储器中的存储表示。数据运算：定义在数据逻辑结构上的操作。如：查询，插入，删除和修改，排序等。数据逻辑结构有两大类：

线性结构：特征：若结构是非空集，则仅有一个开始结点和一个终止结点；其他结点都只有一个前趋结点和一个后继结点。

非线性结构：特征：一个结点有多个前趋结点和后继结点。

数据存储结构有4种：顺序存储结构，链接存储结构，索引存储结构和散列存储结构。

数据结构第一章概论数据逻辑结构和存储结构与运算三者之间有紧密的关系：如：给定一种数据的逻辑结构，可采取顺序存储结构或链接存储结构进行存储；按定义的运算和运算性质的不同，施加于同一数据结构上，则会导致有不同的种类的数据结构产生。如：限制在线性表的一端做插入和删除操作，称该线性表为栈；若限制在线性表的一端插入，另一端删除操作，称该线性表为队。其栈和队都有顺序存储结构或链接存储结构，则它们存储结构称为：顺序栈，链式栈，顺序队，链式队。数据结构第一章概论1.线性表

2.栈线性结构3.队列,双队列

4.数组数据结构5.字符串

非线性1.树,二叉树结构2.图

数据逻辑结构分类数据结构第一章概论数据顺序存储结构和链式存储结构（物理结构，存储表示,物理表示）

数据结构在计算机存储器中的映象(mapping)。(1)顺序存储结构(向量,一维数组)

例.chara[5]={'A','B','C','D'}；

ABCDE01234a是一维数组(2)非顺序存储结构(链接表：指针类型和结构类型定义）例.单链表

datanext┌─┬┐┌─┬┐┌─┬┐┌─┬─┐Head─→│A│┼→│B│┼→│C│┼→│D│^│└─┴┘└─┴┘└─┴┘└─┴─┘4个结点的单链表数据结构第一章概论7.数据类型（datatype)---

是一个值的集合和定义在这个值上的一组操作的总称。用数据类型定义数据结构。

(1)原子类型(如：int,char,float等)(2)结构类型(如：数组,结构,联合体等）8.抽象数据类型(AbstractDataType)----

与计算机的实现无关的数据类型。形式定义：

ADT抽象数据类型名

{1.数据对象；

2.数据关系:一个或多个关系；

3.一组基本操作/运算

}ADT抽象数据类型名注意：常用DataType表示抽象元素类型。数据结构第一章概论1.3算法和算法分析

数据的运算是通过算法描述的。1.算法----求解一个特定任务的指令的有限序列。例.求a[0..n-1]中n个数的平均值(假定n>0)。

floataverage(floata[],intn){inti；floats=0.0；//累加器赋初值

for(i=0；i<n；i++)s=s+a[i]；//a[i]累加到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++；

}(2)确定性：无二义性。例.{x=5；y=10；

z=x+++y；

printf(“%d,%d,%d”,x,y,z)；

}x+++y解释为：x+(++y)？

(x++)+y？数据结构第一章概论

(3)可行性：可以在计算机上实现。

for(i=1,s=0；i<10；++i)s++；？？？

(4)输入：有0或多个输入量。

(5)输出：至少有一个输出量。3.算法设计要求

(1)正确性

a.无语法错误；

b.对n组输入产生正确结果；

c.对特殊输入产生正确结果；

d.对所有输入产生正确结果。

(2)可读性：“算法主要是为了人的阅读与交流”。

(3)健壮性：有出错处理的提示。

(4)高效与低存储量数据结构第一章概论下列描述不符合算法的什么特征和要求？

例1voidsuanfa1(){inti,s=0；

for(i=0；i>=0；i++)//死循环

s++；//不能终止

}

例2floatsuanfa2(){intx,y；

scanf(“%d”,&x)；

y=sqrt(x)；//当x<0时,出错

return(y)；

}数据结构第一章概论4.算法的时间复杂度衡量算法性能：

a.算法正确性；

b.执行算法所消耗的时间；

c.执行算法所消耗的空间（主要考虑辅存空间）；

d.算法易读易理解，易于编码，易于调试等。

主要讨论算法执行时间。算法所消耗的时间：算法中每条语句执行时间之和。每条语句执行时间=语句的执行次数×一次执行该语句的时间。语句的频度：设n为求解的问题的规模,基本操作(或语句)执行次数总和称为语句频度,记作f(n)。问题的规模n：指线性表的长度，多项式的项数，矩阵的阶数，树的结点数，图中的顶点或边数等。

注：一次执行语句的时间是很难精确算出的：它与机器的执行速度，编译程序编译质量及运行环境等因素有关。算法所消耗的时间粗略地用算法中语句执行的最大次数来度量。数据结构第一章概论

//求两个n阶方阵的乘积：C=A*B#definen100intMultiply(inta[n][n],intb[n][n],intc[n][n]){intj,i,k；语句的频度f(n)(1)for(i=0；i<n；i++)n+1(2)for(j=0；j<n；j++){n(n+1)(3)c[i][j]=0；n2(4)for(k=0；k<n；k++)n2(n+1)(5)c[i][j]=c[i][j]+a[i][k]*b[k][j]；n3}}算法所消耗的时间就是所有语句频度之和T(n):T(n)=2n3+3n2+2n+1T(n)是矩阵的阶数n的函数。当n→∞，2n3+3n2+2n+1与n3

同阶，即同一数量级。记为：

T(n)=O(f(n))=O(n3)即与f(n)中最高的阶相同。数据结构第一章概论

例1{ints；语句的频度f(n)scanf(“%d”,&s)；1s++；1printf(“%d”,s)；1}

其中：语句频度为：f(n)=f(1)=3与问题规模n无关的常数。时间复杂度为：T(n)=O(f(n))=O(3)=O(1）

O(1)称成为常量阶/常量数量级只要算法的执行时间不随问题规模n增大而增长，即使算法中有上千条语句，其执行的时间只不过是一个较大的常数，算法的时间复杂度仍然是常数阶O(1)。数据结构第一章概论例2分析下面的算法voidsum(inta[],intn)f(n）

{ints=0,i；//1次

for(i=0；i<n；i++)//n次

s=s+a[i]；//n次

printf(“%d”,s)；//1次

}其中：语句频度为：f(n)=1+n+n+1

时间复杂度为：T(n)=O(f(n))=O(2n+2)=O(n）

O(n)称成为线性阶/线性数量级一般情况下，对步进循环，只考虑循环体中的语句执行的次数，可忽略步长加1，终值判断，控制转移等成分。数据结构第一章概论例3分析下面的算法1.voidsum(intm,intn)2.{inti,j,s=0；//1次

3.for(i=1；i<=m；i++)//m次

4.{for(j=1；j<=n；j++)//m*n次

5.s++；//m*n次

6.printf(“%d”,s)；//m次

7.}8.}

其中:f(m,n)=1+m+2*m*n+m=2mn+2m+1

当m=n时,f(n)=2n2+2n+1T(n)=O(f(n))=O(2n2+2n+1)=O(n2)平方阶。

对嵌套层次的循环结构，时间的复杂度T(n)由最内层循环体语句的频度f(n)决定。数据结构第一章概论例4分析下面的算法1.voidsum(intn)2.{inti,j,s=0；//1次

3.for(i=1；i<=n；i++)//n次

4.{for(j=1；j<=i；j++)//?次

5.s++；//?次

6.printf(“%d”,s)；//n次

7.}8.}数据结构第一章概论

其中：第4行的次数为1+2+...+n=n(1+n)/2

第5行的次数为1+2+...+n=n(1+n)/2f(n)=1+n+n(n+1)+n=n2+3n+1T(n)=O(f(n))=O(n2）平方阶例5有算法：在数组a[0..n-1]中查找k值：

(1)i=n-1;(2)while(i>=0&&(a[i]!=k))(3)i--;(4)returni;(3)语句的频度不仅问题规模n有关，而且与a数组各元素和k的取值有关。若a中没有要找的k值，(3)语句的频度为f(n)=n;若a中最前一个元素是要找的k，则(3)语句的频度为常数0。在这种情况下，采用最坏的时间复杂度作为算法的时间复杂度：T(n)=0(n)

数据结构第一章概论常用时间复杂度递增依次为：常数阶O(1),

对数阶O(log2n),

线性阶O(n),

线性对数阶O(nlog2n),

平方阶O(n2),

立方阶O(n3)…K方阶O(nk)，指数阶O(2n)。

O(1)算法效率最高，O(2n)算法效率最低。5.算法的空间复杂度执行算法所需存储空间的大小。也是问题规模n的函数。

6.算法的复杂度包括：算法时间复杂度和算法空间复杂度。低高数据结构第一章概论例6冒泡排序的C语言算法

//对数组a中n个数按递增次序作冒泡排序

1.Voidbubble1(inta[],intn)2.{inti,j,temp；

3.for(i=0；i<=n-2；i++)//？次

4.for(j=0；j<=n-2-i；j++)