数据结构与算法 第一章 绪论 知识点梳理总结.docx
《数据结构与算法 第一章 绪论 知识点梳理总结.docx》由会员分享，可在线阅读，更多相关《数据结构与算法 第一章 绪论 知识点梳理总结.docx（19页珍藏版）》请在冰点文库上搜索。
数据结构与算法第一章绪论知识点梳理总结
第一章绪论
1.1《数据结构》课程的内容
程序设计问题两类：
⏹数值运算——模型：
数学方程
f（x）=1+2+3+……+n
f（x）=a0+a1x+a2x2+....+anxn
⏹非数值运算——模型：
表、树、图等
计算机操作的对象：
字符、表格、图像、视频、格局等。
例如：
图书馆书目检索自动化P1
计算机与人对弈问题。
多叉路口交通灯的管理问题
城市交通导航
数据结构：
研究非数值运算的程序设计问题中，待处理的对象以及各处理对象之间关系和操作的学科。
主要研究：
⏹待处理的对象——数据抽象及其表示
⏹数据的逻辑结构——数据之间的逻辑关系
集合，线性结构，非线性结构
⏹数据的存储结构——数据及其逻辑结构在计算机中的表示
顺序存储，链式存储
⏹操作算法——插入，删除，查找，定位，排序，合并
举例：
一个班学生某门课的成绩
开设数据结构的目的:
提高程序设计的水平，具有复杂编程的能力。
更高的抽象思维和数学建模能力。
1.2基本概念和术语
（1）数据
（2）数据元素，数据项
数据的基本单位。
一个数据元素可由若干个数据项组成。
数据项不可分割
学号
姓名
语文
数学
英语
1001
张三
85
54
90
1002
李四
70
99
80
（3）数据对象
性质相同的数据元素的集合。
例：
整数
字母
一个班级的成绩表
学号
姓名
语文
数学
英语
1001
张三
85
54
90
1002
李四
70
99
80
1003
Q&A：
图书检索自动化中，数据对象是？
多叉路口交通灯的管理问题中，数据对象是？
（4）数据结构（狭义）
相互之间存在特定关系的数据元素的集合。
根据关系的不同特性，有四类基本逻辑结构：
P5
集合（关系松散）
线性（集合+顺序）一对一
树形（集合+层次）一对多
图（网）状（集合+复杂关系）多对多
（5）存储结构
数据结构在计算机中的表示
又称：
数据的物理结构
两种基本存储结构：
P6
顺序存储
链式存储
例1：
随机产生20个数字，对此进行排序。
分析数据对象的逻辑结构和存储结构
例2：
对称矩阵的存储
15137a00
50800a10a11
18926a20a21a22
30251………………..
70613an-10an-11an-12…an-1n-1
对称矩阵下三角矩阵
N*N矩阵的存储结构1：
二维数组Sa[N][N]
N*N矩阵的存储结构2：
一维数组Sa[N（N+1）/2]。
以行主序的方式存储：
Sa[0]123……
a00
a10
A11
a20
……
an-10
……
an-1n-1
aij和Sa[k]的对应关系？
If（i>=j）
k=i*（i+1）/2+j
Else
k=j*（j+1）/2+i
——逻辑结构与存储结构之间存在一定的映射
现实问题：
5个城市之间的公路交通网
注意：
存储结构包括数据元素的表示和关系的表示
Typedefstruct{
intstuno;
charname[20];
floatChinese;
floatMaths;
floatEnglish;
}Stu;//元素的表示
Stuclassone[26];//关系的表示
现实问题是？
（6）操作＝运算
数据结构=逻辑结构+存储结构+运算
数据结构，按某种逻辑关系组织起来的一批数据，按一定的存储方式存储在计算机上，并在这些数据上定义运算（操作）的集合。
（另一种说法）
如何对现实问题进行抽象？
（7）抽象数据类型
AbstractDataType（ADT）
一个数学模型以及定义在该模型上的一组操作。
抽象层次越高，复用性越好。
ADT形式定义：
（D，S，P）
D：
数据元素的集合（数据对象）
S：
D上的关系集
P：
D上的基本操作集
？
关系如何描绘：
口头描述
分解成两个两个的关系，一个个罗列
例：
1、一维数组{a1,a2,a3,a4,a5,a6}
数据对象：
{a1,a2,a3,a4,a5,a6}
数据元素的关系：
存在如下的次序关系:
{|i=1,2,3,4,5}
2、在2行3列的二维数组中六个元素
{a1,a2,a3,a4,a5,a6}之间存在两个关系:
行的次序关系:
row={,,,}
列的次序关系:
col={,,}
3、例1.5学校科学研究课题小组的各项事务管理
P5
4、图
？
操作如何描述、实现
例子：
“复数”
“复数”抽象数据类型定义
ADTComplex
{
数据对象：
D={c1,c2|c1,c2∈R（R为实数集）}
数据关系：
S={（c1为实部,c2为虚部）}
基本操作：
Assign（&A,c1,c2）
初始条件：
复数的实部和虚部c1,c2
操作结果：
构造一个复数，实部和虚部分别被赋以参数c1,c2的值
Add（&A,B）//用A返回加法运算后结果
初始条件：
两个复数已存在
操作结果：
用复数A返回两复数相加的结果
Minus（A,B）
初始条件：
两个复数已存在
操作结果：
用函数返回值，返回两复数相减的结果
Multiply（A,B）
Divide（A,B）
GetReal（A,&e）
初始条件：
复数已存在
操作结果：
用元素e，返回复数的实部
GetVirtual（A,&e）
初始条件：
复数已存在
操作结果：
用元素e，返回复数的虚部
...
}ADTComplex
实验：
复数数据类型的实现
（8）数据类型
数据类型，内在地规定了变量的所有可能取值的范围，以及所允许进行的操作。
例：
int
取值的范围：
某个区间上的整数，-215+1—215-1（16位）
定义在其上的操作：
+-*/mod等
数据类型分为两类：
⏹基本类型（原子类型）
⏹结构类型
引入数据类型的目的：
实现信息的屏蔽，即将一切用户不需要了解的细节封装在类型中，只管用好了。
例：
“复数”——演示complex.c
“复数”抽象数据类型的C语言实现：
typedefdoubleElemType;//定义数据项类型
typedefstruct
{
ElemTyper;
ElemTypev;
}Complex;//复数抽象数据类型
//具体操作的实现：
statusAssign（Complex&A,ElemTypec1,ElemTypec2）{}
//Assign（）生成一个复数
voidAssign（Complex*A,ElemTypereal,ElemTypevirtual）
{
A->r=real;
A->v=virtual;
}
//Add（）两个复数相加，和返回
voidAdd（Complex*A,ComplexB）
{
A->r=A->r+B.r;
A->v=A->v+B.v;
}
ComplexMinus（ComplexA,ComplexB）;
{
ComplexC;
C.r=A.r+B.r
C.v=A.v+B.v
returnC;
}//A-B
ComplexMultiply（CompexA,ComplexB）
{……}//A*B
ComplexDivide（ComplexA,ComplexB）
{……}//A/B
说明：
①类C语言、伪码P10
②算法、程序之区别
③理解操作符&（引用）
例：
yinyong.c
2011-2-21作业：
书面作业：
1、输入10个学生记录，每个记录包括学号、姓名、性别、年龄、成绩，组成记录数组，统计男、女生人数，计算平均年龄，平均成绩，并将低于平均成绩的学生记录输出。
要求：
模块化的编程思想，每个操作用一个函数实现，共有统计人数、平均成绩计算、平均年龄计算、输出低于平均成绩的学生等4项操作。
2、上机调试。
复习：
《C程序设计》第十章结构体与共用体
10.2定义结构体类型变量的方法
10.7用指针处理链表
10.10用typedef定义类型
1.4算法及其分析
一、算法及其特性
算法：
特定问题求解步骤的一种描述。
算法不唯一。
算法的特性：
1）有穷性
2）确定性
3）可行性
4）输入>=0
5）输出>=1
二、算法设计的要求
好算法：
1）正确性
2）可读性
算法主要是为了人的阅读与交流，其次才是机器执行。
3）健壮性
4）高效，低存储
算法与程序的区别？
三、算法效率的度量
“最短的时间以及耗费最小的空间”
（1）时间上分析
两种方法：
事后统计
事前估算
★事前估算：
问题的规模、机器的速度、语言的效率
一般方法：
算法=控制结构+原操作（指固有数据类型的操作）
以执行次数作为程序效率分析的方法
特别是：
基本操作重复执行的次数，作为算法的时间量度
例：
二个n*n矩阵的乘法
for（i=0;ifor（j=0;j{
c[i][j]=0;//an2
for（k=0;kc[i][j]+=a[i][k]*b[k][j]//cn3
}
T（n）=O（n3）
c语句执行了多少次？
b语句执行了多少次？
a语句执行了多少次？
时间复杂度：
n：
问题的规模。
f（n）：
基本操作执行的次数是问题规模的某个函数f（n）。
算法的时间量度计作：
T（n）=O（f（n））算法的渐进时间复杂度
——随问题规模的增大，算法执行时间的增长率和f（n）的增长率相同。
语句的频度与阶：
P15
（a）{++x;s=0;}
（b）for（i=1;i<=n;++i）{++x;s+=x;}
（c）for（j=1;j<=n;++j）
for（k=1;k<=n;++k）{++x;s+=x;}
O
（1）O（n）O（n2）O（logn）O（2n）
——很多时候难以精确计算语句频度，只要求出它关于n的增长率或阶即可。
Try：
时间复杂度
for（i=0;ix=x+1;//
For（i=1;iprintf（“i=%d”,i）;//x
例:
P16
for（i=2;i<=n;i++）2…n
for（j=2;j<=i-1;++j）2…i-1
{++x;a[i][j]=x;}//？
intfac（intn）T（n）
{
if（n<=1）return1;①O
（1）
elsereturn（n*fac（n-1））;②T（n-1）
}
最好时间复杂度、最坏时间复杂度、平均时间复杂度
例子：
顺序查找算法
intdata[20]={1,7,9,…}；
intcounter=1;
intseq_search（intkey）
{
inti;
for（i=0;i{
if（data[i]==key）return1;
counter++;//执行次数
}
return0;
}search.c
冒泡排序:
P16
voidbubble_sort（inta[],intn）
{
for（i=n-1;change=true;i>=1&&change）;--i）
{
change=false;
for（j=0;jif（a[j]>a[j+1]）
{a[j]a[j+1];change=true;}
}
}//bubble_sort
比较——C程序设计中的算法：
for（i=n-1;i>=1;--i）
{
for（j=0;jif（a[j]>a[j+1]）a[j]a[j+1];
}
（2）空间上分析
空间复杂度：
实现算法所需的辅助存储空间的大小。
空间复杂度计作：
S（n）=O（f（n））按最坏情况分析。
五、算法实例
例1：
计算f（x）=a0+a1x+a2x2+....+anxn
用什么数据模型？
floateval（floatcoef[],intn,floatx）;
算法一：
先将x的幂存于数组power[]，再分别乘以相应系数。
floateval（floatcoef[],intn,floatx）
{
floatpower[n],f;
inti;
for（power[0]=1,i=1;i<=n;i++）
power[i]=x*power[i-1];//功能？
for（f=0,i=0;i<=n;i++）
f+=coef[i]*power[i];
return（f）;
}
算法二：
f（x）=a0+（a1+（a2+……（an-2+（an-1+anx）x）x）…x）x
//迭代法
floateval（floatcoef[],intn,floatx）
{
inti;
floatf;
for（f=coef[n],i=n-1;i>=0;i--）
f=coef[i]+f*x;
return（f）;
}
书面作业3.9：
1、分析：
@语句执行的次数
voidmain（）
{
X=91;y=100;
while（y>0）
if（x>100）{x-=10;y--;}//@语句
elsex++;
}
x=0;
for（i=1;i<=n;i++）
for（j=1;j<=i;j++）
for（k=1;k<=j;k++）
x+=6;//@语句
2、分析以下程序的时间复杂度，问题规模皆为n.
voidmain（）
{
inti=1,k=0;
while（i<=n-1）
{
k+=10*i;i++;
}
}
voidgame（intn）
{
inti=1,j=0;
while（i+j<=n）
if（i>j）j++;
elsei++;
}
voidprime（intn）
{
inti=2;
while（n%2&&i<=sqrt（n））
i++;
if（i>sqrt（n））printf（“%d是一个素数！
\n”,n）;
elseprintf（“%d不是素数！
\n”,n）;
}
3、设计求解下列问题的C语言算法，并分析其最坏情况的时间复杂度。
（1）在数组A[1..n]中查找值为K的元素，若找到则输出其位置i;否则输出0作为标志.
（2）找出数组A[1..n]中元素的最大值和次最大值。
实验2.23：
实验预习：
书面作业第3题，算法实现。
升级会员 