当前位置:首页 >> 高中教育 >>

一:序言


? 1.1 什么是数据结构

第一章 绪言
线性表
S01 L01 S01 S02 ……
书目信息

程序=数据结构+算法 ? 例1 书目自动检索系统

书目卡片 001 高等数学 樊映川 002 理论力学 罗远祥 登录号: 003 高等数学 华罗庚 004 书名: 线性代数 栾汝书 ……

作者名: …… ……
按书名
高等数学 理论力学 线性代数 ……

索引表

分类号: 001,003…… 樊映川 出版单位: 002,…….. 华罗庚 出版时间: 004,…… 栾汝书 价格: ……..
…….

按作者名
001,… 002,…. 004,…. …….

按分类号
L S …… 002,… 001,003, ……

? 例2 人机对奕问题



……..

……..

…...

…...

…...

…...

? 多叉路口交通灯管理问题



C AB

AC

AD
B

D

BA

BC

BD

E
DA EA EB DB EC DC ED

A

? 数据结构定义: 是一门研究非数值计算的程序设计问题中 计算机的操作对象以及它们之间的关系和操作等等的学科

? 1.2 基本概念和术语
? 数据(data)—所有能输入到计算机中去的描述客观事 物的符号 ? 数据元素(data element)—数据的基本单位,也称 节点(node)或记录(record) ? 数据项(data item)—有独立含义的数据最小单位, 也称域(field) ? 数据结构(data structure)—数据元素和数据元素关 系的集合
根据数据元素间关系的基本特性,有四种基本数据结构 (集合)——数据元素间除“同属于一个集合”外,无其它关系 线性结构——一个对一个,如线性表、栈、队列 树形结构——一个对多个,如树 图状结构——多个对多个,如图

? 数据的逻辑结构—只抽象反映数据元素的逻辑关系 ? 数据的存储(物理)结构—数据的逻辑结构在计算机存 储器中的实现
存储结构分为: 顺序存储结构——借助元素在存储器中的相对位置来表示 数据元素间的逻辑关系 链式存储结构——借助指示元素存储地址的指针表示数据 元素间的逻辑关系 数据的逻辑结构与存储结构密切相关

算法设计
算法实现

逻辑结构
存储结构

存储地址 存储内容
Lo 元素1 元素2 ……..

Lo+m

顺序存储
Lo+(i-1)*m

元素i

…….. Lo+(n-1)*m
元素n

Loc(元素i)=Lo+(i-1)*m

h
1345

链式存储
元素2 1536 元素3 1346 元素4

h
元素1 1400



存储地址 1345 1346 ……. 1400 …….

存储内容 元素1 元素4 …….. 元素2 ……..

指针 1400 ∧ ……. 1536 …….

1536

元素3

1346

数据结构的三个方面:

线性结构
数据的逻辑结构 非线性结构 数据的存储结构

线性表 栈 队 树形结构

图形结构

顺序存储
链式存储

数据的运算:检索、排序、插入、删除、修改等

? 数据类型—高级语言中指数据的取值范围及其上可进 行的操作的总称
例 C语言中,提供int, char, float, double等基本 数据类型,数组、结构体、共用体、枚举 等构造数据类型,还有指针、空(void)类 型等。用户也可用typedef 自己定义数据类型 typedef struct { int num; char name[20]; float score; }STUDENT; STUDENT stu1,stu2, *p;

? 1.3 算法的描述和算法分析简介
? 算法(algorithm)—解决某一特定问题的具体步骤 的描述,是指令的有限序列 ? 算法特性—
?有穷性 —一个算法必须在执行有限步骤之后结束 ? ?确定性 —算法的每一步必须是确切定义的,不能产生二义性 ? ?可行性—算法是能行的 ?输入—一个算法有零个或多个输入 ? ?输出—一个算法有一个或多个输出 ?

?算法的描述—采用C语言 ?算法的评价—衡量算法优劣的标准
?正确性(correctness) ?可读性(readability) ?健壮性(robustness) ?效率与低存储量

算法效率——用依据该算法编制的程序在计算机上执行所消耗 的时间来度量
1.事后统计——利用计算机内记时功能,不同算法的程序可以用一组或 多组相同的统计数据区分 缺点:?必须先运行依据算法编制的程序 ?所得时间统计量依赖于硬件、软件等环境因素,掩盖算法本 身的优劣 2.事前分析估计——一个高级语言程序在计算机上运行所消耗的时间取 决于: ?依据的算法选用何种策略 ?问题的规模 ?程序语言 ?编译程序产生机器代码质量 ?机器执行指令速度 同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行, 效率均不同,———所以使用绝对时间单位衡量算法效率不合适

? 时间复杂度:基本操作重复执行的次数的阶数 T(n)=o(f(n)) ? 空间复杂度:s(n)=o(f(n))
例1:NXN矩阵相乘

for(i=1;i<=n;i++)
for(j=1;j<=n;j++) {c[i][j]=0;

T ?n ? ? O ?n 3 ?

f ( n) ? n 3

for(k=1;k<=n;k++)
c[i][j]=c[i][j]+a[i][k]*b[k][j]; }

练习题
? 1.一个数组元素a[i]与________的表示等价。 A、 *(a+i) B、 a+i C、 *a+i D、 &a+i ? 2.下面程序段的时间复杂度为____________。 for(int i=0; i<m; i++) for(int j=0; j<n; j++) a[i][j]=i*j; A、 O(m2) B、 O(n2) C、 O(m*n) D、 O(m+n)

练习题
? 1.数据的逻辑结构被分为__________、 _________、__________和__________ 四种。 ? 2.数据的存储结构被分为__________、和 __________两种。 ? 3.在线性结构、树形结构和图形结构中,前驱和 后继结点之间分别存在着________、 ________和________的联系。 ? 4.一种抽象数据类型包括__________和 __________两个部分。


相关文章:
中国第一 序言
中国第一 序言_日语学习_外语学习_教育专区。序 言 我从香港作为留学生来到日本,开始在东京大学研究生院学习 经济学时,哈佛大学 Ezra F. Vogel 教授 1979 年撰...
一个序言和想说的话
一个序言和想说的话_院校资料_高等教育_教育专区。一个序言和想说的话 现时代的阅读, 我们面对多种语言, 譬如古典汉语、 白话文、 说话或者叫口语、 现代汉语...
一篇序言成就一个作家
一篇序言成就一个作家_韩语学习_外语学习_教育专区。一篇序言成就一个作家 近现代著名作家、翻译家盛成早年曾在法国留学深造,1928 年他以自己的母亲为原型,用法 文...
一篇好序言
一篇好序言 ● 姜明安今年元月,我们中心(北京大学宪法与行政法研究中心)与美国耶鲁大学中国法研究中心共同举办 了一个法治反腐国际研讨会,与会者大多是中美学界[1...
第一章 序言
第一章 序言一、测量 1、目的:进行可靠的定量比较 2、基本要素:单位、测量工具 3、长度符号:l 国际单位:米 m 4、时间符号:t 国际单位:秒 s 5、质量符号:...
开篇 序言1
我知一本书有序、有正文、有后记,这是常理,但书的主体仍然是正文部分,而绝不可能是 序。 读者总不至于为了一篇名人写的序言而去买一本不喜爱的书吧?况且, ...
1第一章 序言
第一章(共 28 题) 第一章((下列选项中只有一个是正确答案 一、单项选择题(8 个)(下列选项中只有一个是正确答案) 单项选择题( 。 下列选项中只有一个是...
第一章序言
第一章 引论 10页 1财富值 序言及第一章(1) 14页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
序言1——OK
序言1——OK 入菩萨行入菩萨行隐藏>> 序言 序 言 《入菩萨行》是修学大乘佛法者不可缺少的论典。 在藏传佛教各派中,每一个正规寺院里的修行人,都会 传讲...
每日一语前言
一套画册【绝对经典】 26页 免费 过往乃今日之序言 5页 2财富值 地产集团企业画册 43页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议...
更多相关标签: