通信原理大综合课件软件

1数据结构与算法

2

○学习的目的：为了分析待处理的对象的特性以及各处理对象之间的存在关系。

概述2.1学习目的因此，简单说来，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。

3

2．1．1数据结构对数据处理的重要性数据结构可描述为Group=（D，R）学生成绩查询学号姓名成绩9861109张卓1009861107刘忠赏959861103胡孝臣86交通路灯问题4

数据:所有能输入到计算机中并能被计算机程序处理的符号集合.数据元素:

数据的基本单位,也称结点或记录.数据结构:

相互间存在一种或多种特定关系的数据元素的集合.

基本概念5

数据结构：由某一数据对象及该对象中所有数据成员之间的关系组成。记为：

Data_Structure={D,R}

其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。

数据结构数据结构是一门研究数据组织、存储和运算的一般方法的学科。6

1．数据的逻辑结构

2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A.线性结构B.非线性结构A.顺序存储

B.链式存储线性表栈队树形结构图形结构2．1．2数据结构研究的三个主要问题：7

集合:数据元素之间属于一个集合,别无其他关系.

线性结构:结构中的数据元素存在一个对一个的关系.

树结构:结构中的数据元素存在一个对多个的关系.

图结构:结构中的数据元素存在多个对多个的关系.1234数据的逻辑结构8

树形结构例子——结点间具有分层次的连接关系HBCDEFGA9

1423

D={1,2,3,4}R={(1,2),(1,3),(1,4),(2,3)(3,4),(2,4)}213

D={1,2,3}R={<1,2>,<2,3>,<3,2>,<1,3>}

图形结构例子——结点间的连结是任意的10

元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i-1)*m数据的顺序存储11

1536元素21400元素11346元素3∧元素41345存储地址存储内容指针

1345元素1

1400

1346元素4∧

…….

……..

…….

1400元素2

1536

…….

……..

…….

1536元素3

1346h数据的链式存储12

하도급건설기술자배치관리

程序＝算法＋数据结构

程序设计的实质是选择一个好的数据结构，设计一个好的算法。算法取决于描述实际问题的数据结构。13

2.1.3算法的基本概念

1算法：是对特定问题求解步骤的一种描述。算法的四个特性：有穷性确定性可行性有输出14

12Voidexam1(){n=2;while(n%2==0)n=n+2;printf(“%d\n”,n);}Voidexam2(){y=0;x=5/y;printf(“%d%d”,x,y);}15

评价算法：正确性、易读性、健壮性、运行时间及占用空间。

正确性：正确与否可读性：容易阅读健壮性：容错处理效率和低存储量需求：

和算法执行时间相关的因素有：1）算法所用“策略”；2）算法所解问题的“规模”；3）编程所用“语言”；4）“编译”的质量；5）执行算法的计算机的"速度"。16

for(i=1;i<=n;i++)/*n+1*/for(j=1;j<=n;j++)/*n*(n+1)*/{c[i][j]=0;/*n2*/for(k=1;k<=n;k++)/*n2(n+1)*/c[i][j]=c[i][j]+a[i][k]*b[k][j];/*n3*/}T(n)=2n3+3n2+2n+1两个n阶矩阵相乘的算法2算法的复杂度：时间复杂度：评估算法的时间增长趋势。影响运行时间的因素：语句执行的次数(频度)

执行每行语句所需的时间(与算法无关)T(n)=2n3+3n2+2n+1当n趋向充分大时，T(n)/n3的值趋于常数算法时间复杂度表示为T(n)=O(n3)17

当问题的规模n趋于无穷大时，把时间复杂度T(n)的数量级（阶）称为算法的渐进时间复杂度（有时简称为时间复杂度）。

严格的数学定义为：若T(n)和f(n)是定义在正整数集合上的两个函数，当存在两个正的乘数C和n0时，使得对所有的成立，则都有这时称T(n)的时间复杂度为f(n)数量级。18

例：x=0;y=0;for(k=1;k<=n;k++)x++;for(i=1;i<=n;i++)for(j=1;j<=n;j++)//n*ny++;一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，而忽略循环体中步长加1、终值判断、控制转移等成分。时间复杂度是以算法中频度最大的语句来衡量。19

voidselect_sort(inta[],intn)

{

//将a中整数序列重新排列成自小至大有序的整数序列。

for(i=0;i<n-1;++i){

j=i;

for(k=i+1;k<n;++k)

if(a[k]<a[j])j=k;

if(j!=i){w=a[j];a[j]=a[i];a[i]=w;}}

}20

例：x=1;for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x++;21대한주택공사Ⅰ

1

2如果算法的执行时间是一个与问题规模n无关的常数，则算法的时间复杂度为常数阶，记作T(n)=O(1)。空间复杂度：指算法中所需的辅助空间单元。交换i和j的内容。Temp=i;i=j