数据结构（C语言版）市公开课一等奖省赛课获奖课件

数据结构（C语言版）数据结构（C语言版）第1页简介《数据结构》是计算机专业一门专业基础课，在计算机学科中起着承上启下作用，在计算机技术各个领域也有着广泛应用。学习这门课需要程序设计语言作为其基础，学习前要有比较扎实程序设计基本功（这部分内容本课程中将不予包括），同时又为后续数据库等一系列课程提供知识基础。《数据结构》这门课程包括数据组织、存放以及运算普通方法。希望经过这门课学习，掌握数据结构基本概念，掌握求解问题思绪与方法，具备数据抽象能力。数据结构（C语言版）第2页数值问题和非数值问题比较

数值问题

对象：len，wide，area——用数值表示

对象之间关系：

area=lenwide，可用方程或函数表示。数据存放：可用程序设计语言中实型变量存放数据。

非数值问题

对象：课程——用课程名表示

对象之间关系：课程间有“次序”关系（不能用方程或函数表示，可用图来表示）

数据存放：数据及数据之间关系存放。数据结构（C语言版）第3页第一章绪论学习关键点熟悉数据、数据对象、数据元素、数据类型、数据结构等基本概念，尤其是数据逻辑结构与物理结构概念及其关系。了解算法定义、算法特征、算法时间代价、算法空间代价。掌握计算语句频度和估算算法时间复杂度方法。数据结构（C语言版）第4页1.1概述1.2数据结构基本概念1.3数据类型和抽象数据类型1.4算法第一章绪论数据结构（C语言版）第5页1.1概述计算机解题步骤详细问题数学模型算法编程、调试数据处理种类和能力数(整数,实数)字符、字符串、文字、图形、图象、声音数值数据

非数值数据

数据结构（C语言版）第6页1.2数据结构基本概念数据：是对客观事物符号表示。学号姓名语文数学C语言601张三855492602李四928464603王五877473604...例：张三C语言考试成绩为92分，92就是该同学成绩数据。数据结构（C语言版）第7页数据元素是数据基本单位。在计算机程序中通常作为一个整体考虑和处理。数据项是数据不可分割最小单位。数据对象是性质相同数据元素集合。一个数据项一个数据元素学号姓名语文数学C语言601张三855492602李四928464603王五877473604...整个表统计是学生成绩数据数据结构（C语言版）第8页数据结构是相互之间存在一个或各种特定关系数据元素之间集合。数据结构分类线性结构:元素间为严格一对一关系。 如上面成绩表中各元素集合:元素间为涣散关系。数据结构（C语言版）第9页树形结构：元素间为严格一对多关系图状结构(网状结构):元素间为多对多关系数据结构（C语言版）第10页数据结构形式定义为：数据结构是一个二元组：Data-Structure=（D，R）有限个数据元素集合有限个节点间关系集合例4为毕业设计小组设计一个数据结构。假设每个小组关系由一名教师指导一到十名学生。则数据结构二元组表示以下：

Group=(P,R)

其中：P＝｛T,G1,…,Gn｝1≤n≤10

R＝｛<T,Gi>|1≤i≤n,1≤n≤10｝数据结构（C语言版）第11页逻辑结构：“数据结构”定义中“关系”指数据间逻辑关系，故也称数据结构为逻辑结构。物理结构：数据结构在计算机中表示称为物理结构。又称存放结构。计算机中存放信息最小单位：位，8位为一字节，两个字节为一字，字节、字或更多二进制位可称为位串。次序结构（元素在存放器中相对位置）链式结构（元素地址指针）数据结构（C语言版）第12页元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存放地址存放内容Loc(a)=Lo+（i-1)*m次序存放每个元素所占用存放单元个数全部元素存放在一片连续存贮单元中，逻辑上相邻元素存放到计算机内存依然相邻。数据结构（C语言版）第13页1536元素21400元素11346元素3∧元素41345h链式存放

每个节点都由两部分组成：数据域和指针域。数据域存放元素本身数据，指针域存放指针。数据元素之间逻辑上联络由指针来表达。全部元素存放在能够不连续存贮单元中，但元素之间关系能够经过地址确定，逻辑上相邻元素存放到计算机内存后不一定是相邻。数据结构（C语言版）第14页数据类型：是一个值集合和定义在这个值集上一组操作总称。比如，C语言中整形变量: 其值为某个区间上整数，定义在其上操作为：加、减、乘、除和取模等算术运算。分类：(按值不一样特征)原子类型：每一个对象仅由单值组成类型；结构类型：每一个对象可由若干成份按某种 结构组成类型。1.3数据类型和抽象数据类型数据结构（C语言版）第15页抽象数据类型（ADT）作用：抽象数据类型能够使我们更轻易描述实际问题。 例：用线性表描述学生成绩表，用树或图描述遗传关系。定义：一个数学模型以及定义在该模型上一组操作。好处：可提升软件复用程度。

使用它人能够只关心它逻辑特征，不需要了解它存放方式。定义它人一样无须要关心它怎样存放。数据结构（C语言版）第16页例：线性表这么抽象数据类型，其数学模型是：数据元素集合，该集合内元素有这么关系：除第一个和最终一个外，每个元素有唯一前趋和唯一后继。能够有这么一些操作：插入一个元素、删除一个元素等。原子类型值不可分解，如int固定聚合类型值由确定数目成分按某种结构组成，如复数可变聚合类型值成份数目不确定，如学生基本情况抽象数据类型分类数据结构（C语言版）第17页抽象数据类型表示法：一、三元组表示：（D，S，P） 其中D是数据对象，S是D上关系集，P是对D基本操作集。二、抽象数据类型定义格式： ADT抽象数据类型名{ 数据对象：<数据对象定义> 数据关系：<数据关系定义> 基本操作：<基本操作定义> }ADT抽象数据类型名数据结构（C语言版）第18页抽象数据类型表示与实现抽象数据类型能够经过固有数据类型（如整型、实型、字符型等）来表示和实现。注1：它有些类似C语言中结构（struct）类型，但增加了相关服务。注2：教材中用是类C语言（介于伪码和C语言之间）作为描述工具。其描述语法见P10-11。数据结构（C语言版）第19页算法定义ispass(intnum[4][4]){inti,j;

for(i=0;i<4;i++) for(j=0;j<4;j++)

if(num[i][j]!=i*4+j+1) return0;return1;

}/*类似华容道游戏中判断游戏是否结束算法*/

定义：算法是对特定问题求解步骤一个描述，是指令有限序列，其中每条指令表示一个或多个操作。

1.4算法数据结构（C语言版）第20页算法特征有穷性：算法必须在有限步内结束；确定性：组成算法操作必须清楚无二义性。可行性：组成算法操作必须能够在计算机上实现。输入：0个或多个输入；输出：1个或多个输出；有穷性haha()

{/*onlyajoke,donothing.*/

}

main()

{printf("请稍等...您将知道世界未日...");

while(1)

haha();

}确定性floataverage(int*a,intnum)

{inti;longsum=0;

for(i=0;i<num;i++)

sum+=*(a++);

returnsum/num;

}

main()

{intscore[10]={1,2,3,4,5,6,7,8,9,0};

printf("%f",average(score,10);

}输出getsum(intnum)

{

inti,sum=0;

for(i=1;i<=num;i++)

sum+=i;

}/*无输出算法没有任何意义，数据结构（C语言版）第21页正确性可读性健壮性效率与低存放量需求程序不含语法错误。max(inta,intb,intc)

{

if(a>b)

{if(a>c)returnc;

elsereturna;

}

}程序对于几组输入数据能够得出满足规格说明要求结果。max(inta,intb,intc)

{

if(a>b)

{if(a>c)returna;

elsereturnc;

}

}/*8,6,7*//*9,3,2*/程序对于精心选择经典、苛刻输入数据能够得出满足规格说明要求结果。max(inta,intb,intc)

{

if(a>b){

if(a>c)returna;elsereturnc;}

else{

if(b>c)returnb;elsereturnc;}

}程序对于一切正当输入数据都能产生满足规格说明要求结果。算法设计要求数据结构（C语言版）第22页算法效率度量算法效率——用依据该算法编制程序在计算机上执行所消耗时间来度量。通惯用事后统计和事前分析预计这种方法。但同一个算法用不一样语言、不一样编译程序、在不一样计算机上运行，效率均不一样，所以使用绝对时间单位衡量算法效率不适当。数据结构（C语言版）第23页在三个整数中求最大者max(inta,intb,intc)

{if(a>b)

{if(a>c)returna;

elsereturnc;

}

else

{if(b>c)returnb;

elsereturnc;

}/*无需额外存放空间，只需两次比较*/max(inta[3])

{intc,inti;

c=a[0];

for(i=1;i<3;i++)

if(a[i]>c)c=a[i];

returnc;

}

/*需要两个额外存放空间，两次比较，最少一次赋值*/

/*共需5个整型数空间*/100个整数同上算法难写难读/*共需102个整型数空间*/

数据结构（C语言版）第24页算法效率度量事后统计方法；事前分析估算方法；事前估算法要考虑以下原因：问题规模；编写程序时所用程序设计语言；机器速度；算法所用策略。 撇开这些与机器软硬件相关原因，能够认为一个特定算法“运行工作量”大小只依赖与问题规模，或者说只是问题规模函数。 数据结构（C语言版）第25页例两个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[i][k]*b[k][j]； ⑤} 语句①到语句⑤执行次数依次是（n+1），n（n+1），n2，（n+1）n2，n3。它们之和就是该算法时间开销 T（n）=2n3+3n2+2n+1 当n充分大时候，T（n）与f（n）=n3数量级相同。于是，该算法时间复杂度为：T（n）=O（n3），其原语句是语句⑤。 频度：是指该语句重复执行次数数据结构（C语言版）第26页算法时间复杂度(TimeComplexity) 普通来说，设算法中全部语句频度之和记作T(n)，它是问题规模n某个函数f(n)，记作：

T(n)=O(f(n)) 它表示随问题规模n增大，算法执行时间增加率与f(n)增加率相同，称做算法渐近时间复杂度，简称时间复杂度。语句在算法中被重复执行次数(FrequencyCount)数据结构（C语言版）第27页{++x;s=0;}for(j=1;j<=n;++j) for(k=1;k<=n;++k){ ++x;s+=x; }for(i=1;i<=n;++i){ ++x;s+=x; }T(n)=O(1)T(n)=O(n2)T(n)=O(n)例求下面程序段时间复杂度数据结构（C语言版）第28页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)数据结构（C语言版）第29页例冒泡排序算法。voidbubble_sort(inta[],intn){ for(i=n-1,change=TRUE;i>=1&&change;--i){ cha