




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
ContactMe:jia:(
)为什么学习数据结构?计算机科学是一门研究数据表示和数据处理的科学用计算机来解决实际问题,仅掌握几种计算机程序设计语言是难以应付众多复杂的课题的设计出一个结构好效率高的程序,必须研究数据的特性及数据间的相互关系及其对应的表示象方法与课堂学习:等《数据结构(用面C++描述)》
()课后实习每周实验课程大作业成绩期末考试上机+课程大作业平时作业第一章 绪论§1.1
数据结构早期:数值计算——运算对象是简单的整型、实型或类型数据中后期:非数值计算——处理对象是类型复杂的数据,数据元 间的相互关系一般无法用数学方程式加以描述学号姓名籍贯出生年月98131刘激扬男北京1979.1298164衣男青岛1979.0798165男天津1981.0298182女广州1980.1098203海1980.0598224洪伟男太原1981.0198236熊南燕女苏州1980.0398297宫力男北京1981.0198310女昆明1981.0298318陈健男杭州1979.1212345678910例1:“学生”表格例2:八皇后问题(用四皇后描述)............四皇后问题的状态树先修课程无C1,C4课程名称计算机导论数据结构汇编语言课程C1C2C3C4C5C4C6C7接 术数据库原理C1C程序设计语言
C1计算机图形学
C2,C3,C3C2,C9C8C9例3:教学计划编排问题编译原理
C4(a)计操算作机系专统业的课程设C置2C1C2C3C6C4C5C9C7C8(b)表示课程之间优先关系的有向图例4:城市的煤气管道问题(a)结点间管道的代价(b)最经济的管道铺设描述这类非数值计算问题的数学模型不再是数学方程,而是诸如表、树、图之类的数据结构。数据结构是一门研究(非数值计算的)程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。一些基本概念:数据数据元素(数据成员)数据对象数据:数据是信息的载体,是描述客观事物的数、字符、以及所有能输入到计算机中,被计算机程序识别和处理的符号(数值、字符等)的集合。数据元素(数据成员):是数据的基本单位。在不同的条件下,数据元素又可称为元素、结点、顶点、记录等。数据对象:具有相同性质的数据元素(数据成员)的集合。-
整数数据对象N
={0,
1,
2,
…}-
学生数据对象数据结构由某一数据对象及该对象中所有数据成员之间的关系组成。记为:Data_Structure
=
{D,
R}其中,D是某一数据对象,R是该对象中所有数据成员之间的关系的有限集合。数据结构的形式定义数据结构包括“逻辑结构”和“物理结构”两个方面(层次):逻辑结构是对数据成员之间的逻辑关系的描述,它可以用一个数据成员的集合和定义在此集合上的若干关系来表示;物理结构是逻辑结构在计算机中的表示
,故又称“结构”。根据问题来建立逻辑结构例如:Class=(D,S)数据集合:D={a,b1,…,bn,c1,…cn,d1,…dn}关系集合:S
=
{
R1,
R2
}R1
=
{
<a,
b1>,<a,
c1>,<a,
d1>}//班长-组长R2={<b1,bj>,<c1,cj>,<d1,dj>|
j =
2,
3,
…,
n
}//组长-组员ab1c1…
cnb2
b3
…
bn
c2
c3
d2
d3
…
dnd1班级Class的逻辑结构的图示结构是逻辑结构在 器中的映象。数据元素的映象:任何的数据元素在计算机中最终都是转化成一个二进制的位串。关系的映象:…关系的映象方法:(关系对x,
y)1.顺序映象:以相对的 位置表示后继关系例如:令
y
的 位置和
x
的 位置之间差一个常量
C,而
C
是一个隐含值,整个结构中只含数据元素本身的信息xy2.链式映象:以附加信息(指针)表示后继关系需要用一个和
x 在一起的附加信息(指针)指示y
的 位置yx§1.2
抽象数据类型及面象概念C语言中的数据类型char
int
float
double
void字符型整型浮点型双精度型无值数据类型定义:一组性质相同的值的集合,以及定义于这个值集合上的一组操作的总称.不同类型的变量,其所能取的值的范围不同,所能进行的操作不同。例如:整型(int)值的范围是:-32768~32767(16位)操作是:+,-,*,/,%抽象数据类型
(ADTs: Data
Types)由用户定义,用以表示应用问题的数据模型由基本的数据类型组成,并包括一组相关的服务(或称操作)支持了逻辑设计和物理实现的分离,支持封装和信息隐蔽抽象:抽取反映问题本质的东西,忽略非本质的细节抽象数据类型的两种视图:设计者的角度:根据问题来定义抽象数据类型所包含的信息,给出其相关功能的实现,并提供公共界面的接口。用户的角度:使用公共界面的接口对抽象数据类型进行操作,不需要考虑其物理实现。对于外部用户来说,抽象数据类型应该是一个黑盒子。自然数的抽象数据类型定义ADT
NaturalNumber
isobjects:一个整数的有序子集合,它开始于0,结束于机器能表示的最大整数(MaxInt)。Function:
对于所有的
x,y
NaturalNumber;False,True
Boolean,+、-、<、==、=等都是可用的服务。Zero():
返回自然数0NaturalNumberif(x==0)
返回Trueelse
返回Falseif(x+y<=MaxInt)返回x+yelse
返回MaxIntif(x<y)返回0else
返回x-yif(x==y)返回Trueelse
返回Falseif(x==MaxInt)返回xelse
返回x+1IsZero(x)
:BooleanAdd
(x,
y):NaturalNumberSubtract
(x,
y):NaturalNumberEqual
(x,
y):BooleanSuccessor
(x):NaturalNumberendNaturalNumber面 象的概念面 象
=
对象+类+继承+通信面
象方法中类的定义充分体现了抽象数据类型的思想§1.3
数据结构的抽象层次数据结构的抽象层次线性结构:表、栈、队列非线性结构层次结构:树,二叉树,堆网状结构:图其它:集合线性结构bindevetclibuser层次结构树二叉树11
128
910987456231堆(特殊的树结构)12711103
5
4
8
2“最大”堆96368
9“最小”堆7网状结构图结构12564312311216335
4网络结构C++的函数特征C++的数据C++的作用域C++的类C++的对象C++的输入/输出C++的函数C++的参数传递C++的函数名重载和操作符重载C++的动态
分配(friend)函数内联(inline)函数结构(struct)与类联合(Union)与类§1.4
用C++描述面
象程序Niklaus
Wirth
(1976)数据结构+算法=程序设计为计算机处理问题编制一组指令集处理问题的策略问题的数学模型§1.5
算法定义算法:一个有穷的指令集,这些指令为解决某一特定任务规定了一个运算序列。(算法是对特定问题求解步骤的一种描述)输入
有0个或多个输入输出
有一个或多个输出(处理结果)确定性
每步定义都是确切、无歧义的有穷性
算法应在执行有穷步后结束有效性
每一条运算应足够基本一个算法必须满足以下五个重要特性:§1.6
模板模板:适合多种数据类型的类定义或算法,在特定环境下通过简单地代换,可以变成针对具体某种数据类型的类定义或算法。用模板定义用于排序的数据表(dataList)类#ifndef
DATALIST_H#define
DATALIST_H#include
<iostream.h>//模板标识//类标识template
<class
Type>class
dataList
{private:Type
*Element;int
ArraySize;void
Swap
(const
int
m1,
const
int
m2);
int
MaxKey
(constint
low,constint
high);public:dataList
(int
size
=
10)
:
ArraySize
(size),Element
(new
Type
[Size])
{
}~dataList
(
)
{delete
[
]
Element;}void
Sort
(
);friend
ostream&
operator
<<(ostream&outStream,
const
datalist<Type>&outList);friend
istream&
operator
>>
(istream&inStream,
const
datalist<Type>&inList);};#endifdataList类中所有操作作为模板函数的实现#ifndef
SELECTTM_H#define
SELECTTM_H#include
“datalist.h”template
<class
Type>void
dataList
<Type>::Swap
(const
int
m1, const
int
m2)
{//交换由m1,
m2为下标的两个数组元素的值Type
temp
=
Element
[m1];Element
[m1]
=
Element
[m2];Element
[m2]
=
temp;}template
<class
Type>int
dataList<Type>::MaxKey
(const
int
low,
const
int
high)
{//查找数组Element[low]~Element[high]中//的最大值,函数返回其位置int
max=low;for
(int
k
=
low+1,
k
<=
high,
k++)if
(
Element[max]
<
Element[k]
)max
=
k;return
max;}template
<class
Type>
ostream&operator<<
(ostream&
OutStream,const
dataList<Type>
OutList){//输出对象为OutList,输出流对象为OutStreamOutStream
<<
“Array
Contents
:
\n”;for
(int
i
=
0;
i
<
OutList.ArraySize;
i++)OutStream
<<
OutLis ement[i]
<<
‘
’;OutStream
<<
endl;OuStream
<<
“Array
Current
Size
:
”
<<OutList.ArraySize
<<
endl;return
OutStream;}template
<class
Type>istream&
operator
>>
(istream&
InStream,dataList<Type>
InList)
{//输入对象为InList,输入流对象为InStreamcout
<<
“Enter
array
Current
Size
:
”;Instream
>>
InList.ArraySize;cout
<<
“Enter
array
elements
:
\n”;for
(int
i
=
0;
i
<
InList.ArraySize;
i++)
{cout
<<
“Elememt”
<<
i
<<
“:”
;InStream
>>
InLis
ement[i];}return
InStream;}template
<class
Type>void
dataList<Type>::Sort
(
)
{//按非递减顺序对ArraySize个关键码//Element[0]~Element[ArraySize-1]排序for(int
i=ArraySize
-1;i>0;i--){int
j
=
MaxKey
(0,
i);if
(
j
!=
i
)
swap
(j,
i);}}#endif使用模板的选择排序算法的主函数#include
“selecttm.h”const
int
SIZE
=
10;int
main
(
)
{dataList
<int>
TestList
(SIZE);cin>>
TestList;cout
<<
“Testing
Selection
Sort
:
\n”
<<TestList
<<
endl;TestList.Sort
(
);cout
<<
“After
sorting
:
\n”
<<TestList
<<
endl;return
0;}§1.7
性能分析与度量算法的性能标准:正确性可使用性可读性效率健壮性算法的效率包括时间代价和空间代价,前者指的是算法执行时间;后者指的是算法执行过程中所需的最大空间。两者都与问题的规模有关。算法效率的衡量方法:事后估计事前估计算法的事后估计在算法中的某些部位插装时间函数time
()测定算法完成某
能所花费的时间算法的事前估计空间复杂度时间复杂度时间复杂度编译时间运行时间–程序步:语法(义)上有意义的一段指令例如:注释:程序步数为0语句:程序步数为0表达式、赋值语句:程序步数为1循环语句:循环控制语句每次执行的程序步数为1程序步确定方法计数全局变量count例以迭代方式求累加和的函数行float
sum
(floata[],const
int
n
)1
{floats
=
0.0;for(int
i
=0;
i
<n;i++
)4
s
+=a[i];5
return
s;6
}在求累加和程序中加入count语句float
sum
(
float
a[
],
const
int
n
)
{float
s
=
0.0;count++;
//count统计执行语句条数
for
(int
i=0;i<n;i++){count++;
//针对for语句s
+=
a[i];count++;//针对赋值语句}count++;count++;//针对for的最后一次//针对return语句return
s;}
执行结束得程序步数
count=2
*
n
+3注意:一个语句本身的程序步数可能不等于该语句一次执行所具有的程序步数。例如:赋值语句x
=
sum
(R,
n);本身的程序步数为1;一次执行对函数sum
(R,n)的调用需要的程序步数为2*n+3;一次执行的程序步数为1+2*n+3
=
2*n+4
确定程序的准确程序步数十分
。程序步数本身也不是一个精确的概念,不能确切反映运行时间。一个算法的“运行时间"通常是随问题规模的增长而增长,它是问题规模(用正整数n表示)的函数。统计算法中作为基本运算的原操作,以原操作重复执行的次数作为算法的时间度量。算法中原操作重复执行的次数是规模n的某个函数T(n)。时间复杂度的渐进表示法要精确地计算T(n)通常较引入渐进时间复杂度——在数量上估计一个算法的执行时间,也能够达到分析算法的目的。(观察算法随n增长的趋势)(大Ο记号):T(n)=O(f(n))(称T(n)为算法的(渐近)时间复杂度。表明,随着问题规模n的增长,算法执行时间的增长率和f(n)的增长率相同)例:一个程序的实际执行时间为T(n)=2.7n3+3.8n2+5.3
则T(n)=Ο(n3)大O表示法:T(n)=O(f(n))的几条规则加
则
针对并列程序段T(n,
m) =
T1
(n)
+
T2
(m)=
O(max
(f
(n),
g
(m)))乘
则
针对嵌套程序段T
(n,
m)
=
T1
(n)
*
T2
(m)=
O(f
(n)*g
(m))乘 则中的常数无关项
O(C)
→
O(1)T
(n)
=
O(
c
*
f(n))
=O(f(n))Ο(1)表示常数计算时间例1:两个并列循环void
example
(float
x[
][
],
int
m,
int
n,
int
k)
{float
sum
[
];for
(int
i=0;i<m;i++){ //x[][]中各行sum[i]=0.0;
//数据累加for
(
int
j=0;
j<n;
j++
)
sum[i]
+=
x[i][j];}for
(i=0;i<m;i++)
//打印各行数据和
cout
<<“Line
”<<
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 消防设施操作和维护保养规程
- 47岁高情商生日文案
- mysql 构造死锁场景的代码
- matlab三维成像函数
- 2025年血液透析器合作协议书
- 电流互感器二次侧接地原因
- 电缆导管验收要求
- 制定销售目标提升业绩计划
- 建筑材料行业保安工作计划
- 企业文化对会计工作的影响与作用计划
- 玻璃雨棚维修施工方案
- 安全生产费用提取及使用计划
- WPSOffice办公软件实例教程PPT完整全套教学课件
- 四年级数学下册-小数加减法的简便运算课件
- igcse英语第一语言15年前真题0500 wqp
- 2023年河北省邯郸市统招专升本生理学病理解剖学历年真题汇总及答案
- keba教程科控编程手册
- 高强螺栓检测报告3
- 广东英语中考必背1600词
- 海南码头防波堤工程施工组织设计图文并茂
- 小学“新时代好少年”推荐表
评论
0/150
提交评论