当前位置：文档之家 › 数据结构北航软件技术基础课程ppt

数据结构北航软件技术基础课程ppt

  • 格式：ppt
  • 大小：494.00 KB
  • 文档页数：50

下载文档原格式

  / 50

合集下载

软件技术数据结构PPT课件

软件技术数据结构PPT课件

for (i = 0; i < num; i++) scanf("%d",
&array[i]);
printf("All of %d elements are: \n", num); // 输出提示
for (i = 0; i < num; i++) printf("%d,", array[i]); // 输出刚输入的num个数据
第6页/共16页
软件技术
1）一维数组
▲ 使用前必须定维 ▲ 作为函数的参数时，可以不定维 ▲ 作为函数的参数时，可以从函数中带出值来 ▲ 使用当中不要超界（C语言不检查） ▲ 下标从0开始，到n-1为止（与VB不同） ▲ 可用于保存向量
第7页/共16页
软件技术
2）二维数组
▲ 存储方式：按行存放 ▲ 作为函数的参数时，列必须定维 ▲ 可用于保存矩阵，用于解线性方程组
第15页/共16页
感谢您的观看！
第16页/共16页
开发平台 标识符 匈牙利命名法 集成环境 如何保持运算精度 软件调试
第2页/共16页
软件技术
1 什么是数据
客观事物属性的符号表达，能输入到计算机中 并被其处理 1）并非只是数字，还包括字符等 2）并非只是常量，主要是指变量 3）广义的数据 ▲ 数字、字符等常量 ▲ 简单变量、数组、结构体、链表、树、图等 ▲ 图形、影像、声音等——信息
软件技术
可调数组
if (array == 0) // 内存申请失败,提示退出 {
printf(“Error, press any key to quit\n");
exit(0); // 终止程序运行,返回操作系统 }

北航数据结构课件 (10)

北航数据结构课件 (10)

（ 1，4，6 ， 12 8，8 12 ， 6，11，… ）
例
49
temp
temp＞K[j] j=0 38 97 76 65 13 27 50
… (若干趟后)
K[j+1]=K[ j ]； j=j−1；
65
38
49
76 65
76 97
65 97
13
27
50
K[j+1]=temp;
38
49
65
76
97
核心思想
首先确定一个元素的间隔数gap。 将参加排序的元素按照gap分隔成若干个子序列 ( 即分别把那些位置相隔为gap的元素看作一个子序 列),然后对各个子序列采用 某一种排序方法 进行排 序；此后减小gap值，重复上述过程，直到gap<1。
一种减小gap的方法：
gap1 = n/2 gapi = gapi-1/2
1.时间性能 —— 排序过程中元素之间的比较次数与元素的
移动次数。 本章讨论各种排序方法的时间复杂度 时主要按照最差情况下所需要的比较次数 来进行。
2.空间性能 —— 除了存放参加排序的元素之外，排序过程
中所需要的其他辅助空间。
3.排序稳定性 —— 对于值相同的两个元素，排序前后的先后
次序不变，则称该方法为稳定性排序方法， 否则，称为非稳定性排序方法。
算 法
泡排序法的排序趟数与原始序列中数 据元素的排列有关，因此，排序的趟数为 一个范围，即[1..n-1]。
什么情况下至少排序一趟 什么情况下要排序n-1趟
O(n
2)
结论
泡排序方法比较适合于 参加排序的序列的原始状态 基本有序的情况
泡排序法是 稳定性排序方法。

北航数据结构课件第一章

北航数据结构课件第一章

祝同学们新学期愉快学习进步！课程名称：数据结构教材名称：《数据结构教程》唐发根刘又诚编著北京航空航天大学出版社1996《数据结构》唐发根编著科学出版社1998开设本课程的必要性以及课程的特点：1. 计算机专业重要的专业基础课之一.2. 需要有关“程序设计语言”和“离散数学”的知识作为课程的基础.3. 实践性较强.第一章绪论1.1 什么是数据结构描述客观事物的数字、字符以及一切能够输入到计算机中，并且能够被计算机程序处理的符号的集合。

数据这个集合中的一个一个元素。

具有相同特性的数据元素的集合。

数据元素之间具有的关系(联系)。

数据数据元素数据对象结构一. 名词术语二. 数据结构的定义1.数据元素之间的联系称之为结构，数据结构就是具有结构的数据元素的集合。

2. 数据结构是一个二元组Data-Structure=(D，R)其中，D是数据元素的有限集合，R是D上的关系的集合。

数据元素之间具有的逻辑关系(结构)。

线性关系(线性结构)如线性表、数组、堆栈、队列、串、文件等具有某种逻辑结构的数据在计算机存储器中的存储方式(存储映象)。

物理结构也被称为存储结构。

顺序存储结构链式存储结构用一组地址连续的存储单元依次存放数据元素，数据元素之间的逻辑关系通过元素的地址直接反映。

用一组地址任意的存储单元依次存放数据元素，数据元素之间的逻辑关系通过指针间接地反映。

非线性关系(非线性结构)如树、二叉树、图等物理结构逻辑结构例刘晓光马广生王民…张玉华男男…女男汉回壮…汉161721…25……………姓名性别民族年龄其他逻辑结构：线性结构(线性表)a 1a 2a 3 a 30…d 1d 2 d 3d 4…d 30a 2a 1a 3a 4a 30存储结构:1. 顺序存储结构:2. 链式存储结构:…d 1d 2 d 3d 4a 1a 2a 3a 30∧list…a 2a 1a 4a 3d 4d 1d 5d31.研究数据元素之间的客观联系。

软件技术基础-ppt可编辑全文

软件技术基础-ppt可编辑全文
*
《数据结构课程》所处的地位：
*
什么是数据结构？ 几个概念： 数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入（识别）到计算机中（存储）并被计算机程序处理（加工）的符号的总称。 数据元素(Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。 数据对象(Data Object)：是性质相同的数据元素的集合。是数据的一个子集。
*
数据的逻辑结构分类 根据数据元素间关系的基本特性，有四种基本数据结构 （集合）——数据元素间除“同属于一个集合”外，无其 它关系 线性结构——一个对一个，如线性表、栈、队列 树形结构——一个对多个，如树 图状结构——多个对多个，如图
*
数据的逻辑结构
从逻辑关系上描述数据，与数据的存储无关； 从具体问题抽象出来的数据模型； 与数据元素本身的形式、内容无关； 与数据元素的相对位置无关。
*
例1 书目自动检索系统
登录号：
书名：
作者名：
分类号：
出版单位：
出版时间：
价格：
书目卡片
书目文件
按书名
按作者名
按分类号
索引表
线性表
*
树
……..
……..
…...
…...
…...
…...
例2 计算机和人对弈问题
*
例3 多叉路口交通灯管理问题
C
E
D
A
B
AB
AC
AD
BA
BC
BD
DA
DB
DC
EA
EB
*
数据的逻辑结构

最新版《软件技术基础》精品课件第二 章基本数据结构及其运算

最新版《软件技术基础》精品课件第二 章基本数据结构及其运算

以行为主压缩存储
B[i(i 1) / 2 j ] ( j i) aij ( j i) 0
以列为主压缩存储
B[(2n j 2)( j 1) / 2 i j 1] ( j i) aij ( j i) 0
三、对称矩阵的压缩存储
对称矩阵的元素满足：aij = aji 1 ≤ i ，j ≤ n 因此将n*n 个元素压缩存放到 n（n+1）/2 个单元的
ci 是第i维的下界 dj 是第j维的上界
两维数组的元素个数为: (d1-c1+1)*(d2-c2+1)
二、数组元素之间的关系
二维数组m行n列可以看作是m个或n个一维数组:
Am×n = ((a11a12…a1n),(a21a22…a2n),.. (am1am11 a12 a1n a a a 21 22 2n am1 am 2 amn
2.按列优先顺序存储结构
按列优先顺序存放是将数组看作若干个列向量。 例如，二维数组Amxn，可以看作n个列向量，每个 列向量m个元素。数组中的每个元素由元素的两个下 标表达式唯一确定。 地址计算公式： LOC（aij）=LOC（a11）+（（j-1）*m+（i-1））*L
其中，L 是每个元素所占的存储单元。
2.3.2 数组的压缩存储
实际工程问题中推导出的数组常常是 高阶、含大量零元素的矩阵，或者是一些 有规律排列的元素。为了节省存储空间， 通常是对这类矩阵进行压缩存储。 压缩的含义是： –相同值的多个元素占用一个存储单元； –零元素不分配存储单元。
一、能够采用压缩存储的矩阵
• 对称矩阵:存储主对角线以上（下）的元素；

软件技术基础第3章 算法与数据结构(一)精品PPT课件

软件技术基础第3章 算法与数据结构(一)精品PPT课件

13
3.1.2 基本概念和术语
• 数据
➢ 是对客观事物的符号表示。在计算机科学中其含义是指所 有能够输入到计算机中并被计算机程序处理的符号集合
• 数据元素
➢ 是数据集合中的一个实体，是计算机程序中加工处理的基 本单位（记录、结构体）
• 数据项
➢ 组成数据元素的有特定意义的最小的不可分割的单位。
《软件技术基础》电子教案
• 数据结构的形式定
义
数据结构是一个二元组:Data_Structures = (D, R)
其中:D是数据元素的有限集，R是D上关系的有限集。
• 数据结构分为四大类:
➢ 表:元素是线性关系(连接)
➢ 图:元素间是非线性关系(连接)
➢ 树:元素间是非线性关系，连接不得有回路
➢ 文件:记录的序列
《软件技术基础》电子教案
（字符、表格、图像） • 对非数值数据的处理：分析数据的逻辑特征
→抽象出合适的数学模型→合理地存储到计 算机→设计出算法→编写出程序
《软件技术基础》电子教案
5
例1 学生信息查询系统
首先要构造学生信息表，表3-1表达出学生数据的逻辑关系，
它就是一个数学模型，这张表如何构造、在计算机内如何 存储将直接影响查找算法的设计以及算法的效率
......
表3-1
《软件技术基础》电子教案
6
学生信息表的特点
• 每个学生的信息占据一行，所有学生的信息 按学号顺序依次排列构成一张表格
• 表中每个学生的信息依据学号的大小存在着 一种前后关系，这就是我们所说的线性结构， 现实中这类关系的数据有很多。
• 通常的操作
➢ 插入某个学生的信息 ➢ 删除某个学生的信息 ➢ 更新某个学生的信息 ➢ 按条件查找某个学生的信息

计算机软件技术基础课件(共19张PPT)

计算机软件技术基础课件(共19张PPT)
1）软件规模越来越大，结构越来越复杂 2）软件开发过程缺乏管理
3）软件开发技术落后
4）软件开发工具和生产方式落后
3、解决软件危机的途径
要充分吸取和借鉴人类长期以来从事各种工程项目 所积累的行之有效的原理、概念、技术和方法，并应用 于软件开发的实践中，将软件开发变成一种组织良好、 管理严密、各类人员协同完成的工程项目
3、软件的特征与类型 特征 a 智能性 b 抽象性 d 依附性 e 非损性 类型
按功能分
类型
按规模分
c系统性
系统软件 支撑软件 应用软件
微型 小型 中型 大型 超大型
从开发人数， 开发周期，源 程序行数几方 面考虑，有软件的产生：伴随计算机产生而产生，伴 2）对程序进行修改，排除错误
定义 阶段
问题定义
（目标与范围说明）
可行性研究
（可行性论证报告）
需求分析
（需求说明书）
设计
（设计文档）
开发 阶段
编程 测试
（程序）
维护 阶段
运行与维护 （维护报告）
传统软件生命周期模型―瀑布模型
3、软件测试
软件测试是为了发现错误而执行程序的过程。
软件测试分为：单元测试和综合测试。
中所遇到的困难问题，从此进入软件工程时代。 软件测试分为：单元测试和综合测试。 传统软件周期模型――瀑布模型 ●程序调试的基本步骤：
三、软件危机 指令是指示计算机进行某一工作的命令。
2）对程序进行修改，排除错误 程序不再是硬件的附属，有软件的概念。 1）软件的产生：伴随计算机产生而产生，伴随计算机发展而发展
四、软件工程
软件工程是开发、运行、维护和修复软件的系统方 法
1、软件工程学的多个分支
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

eMail:gaoliansheng@
2020/9/23
liansheng_gao@
软件技术基础
• 第零章 编程的一些问题 • 第五章 二叉树和树
• 第一章 绪 论
• 第六章 图和广义表
• 第二章 线 性 表
• 第七章 排 序
• 第三章 栈和队列
• 第八章 查 找
试，通过测试用例保证每条源代码至少执行一次
2020/9/23
第零章 程序设计的一些问题
• 需求分析-Requ综 结i述 果re： ：m由 测e专 试n门 报t的 告A测n试a人ly员s对is软件进行测试
• 概要设计-Prim12ary测 测试 试D计e划sign
• 详细设计-Detaile条 wda件lDkt：her编osu译gihg、n链接成功，完成单元测试，
2020/9/23
第零章 程序设计的一些问题
• 软件和属性
– 计算机运行中不可缺少的 – 预先编好，能为他人使用 – 商品
• 盘和软件
– 盘是软件的载体
• 软件的分类
– 应用软件 – 系统软件
2020/9/23
第零章 程序设计的一些问题
• 程序设计的几个阶段(软件工程简介)
– 六、七十年代出现了软件危机
2020/9/23
数据元素
• 数据元素是数据的基本单位。 • 它也可以再由不可分割的数据项组成
2020/9/23
数据对象 性质相同的数据元素的集合 。
例：一个班级的成绩表可以看作一个数据对象。 一个图片、声音…..
数据对象是性质相同的数据元素集合。
2020/9/23
数据结构
• 数据元素集合（也可称数据对象） • 各元素之间的关系，即结构。
2020/9/23
第零章 程序设计的一些问题
• 需求分析-Requ综 调i述 试re：m根e据n详t细A设n计a说ly明s书is，编程实现，并进行 • 概要设计-Prim编 语a程 言ry标 －D准 结e： 构s化i，gn编程格式－缩进等，控制结构－ • 详细设计-Deta三 口ile种 入d控 ，制 出D口结e出构s，，ig出插n/入入或口复结制构程－序唯时一要，完禁整止－自从修入改， • 编码调试-Codi程 的n序g长单&≤元6D的0行规eb，模u≤注g2意00转行移，，程重序定中位平能均力单，元命 • 测试-Testing 名统一，数值约定一致，有效数字，注释 • 运行与维护-Ma行调i试n≥t后2e0要n%进a行nc单e元测试，先逐步审查代码，后测
构
2020/9/23
存储结构 具有某种逻辑结构的数据在计算机存 储器中的存储方式。
存储结构是数据结构在计算机中的表示，也称之为物理结构。
软件技术基础
• 教材：
– 数据结构教程，迟乐军等编著，北京航空航天大学出版社， 2003.4
– 软件技术基础 王人骅 唐梓荣 北京航空航天大学出版社
• 参考资料：
– 数据结构与算法分析，[美]Clifford A. Shaffer著，电 子工业出版社，2001.2
权威著作：
– The Art of Computer Programming(计算机程序设计技巧),其中 的第一卷、第三卷
2020/9/23
第零章 程序设计的思维方法
• 程序设计的本质是实现算法，而算法是计算机解决问题精 确描述，有如下特征：
– 入口
– 出口
– 有穷次结束
– 序列化
– 后继唯一
• 抽象法：变量的应用，树的处理
反对教条化
• 枚举法：
• 归纳法：例如求自然数的和公式
• 回朔法：走迷宫
• 子问题法：Hanio塔问题，二叉树的遍历
• 第四章 串和数组
• 第九章 文 件
(1) 适 合 于 软 件 的 开 发 与 设 计 程 序 包括：程序，软件开发的步骤-软件工程，程
序设计的思维方法，结构化程序设计， O-O程序设计 (2) 数据结构 包括：线性表，链表，栈，队列，树，图等
2020/9/23
软件技术基础
• 学习方法
– 讲练结合
• 测试-Testing
决方案，数据的处理方式，存贮 方式，模块的划分、调用关系
• 运行与维护-Mainte参na考n：c与e 系统相关的资料，需求
规格说明书，程序设计手册，设备技术手册，支持软件文档
2020/9/23
第零章 程序设计的一些问题
• 需求分析-Requirement Analysis • 概要设计-Primary Design • 详细设计-Detailed Design
综述：设计程序的基本流程，组织结构，输入输出，接口设计及数据
• 编结码构设调计试-Coding & Debug 任务：
• 测试1概-T要e结s构tin设g计－程序结构，给出程序的分层结构 • 运行23功 程与能序维划的分控护－制-分流M程 程a序 和i与 数nt模 据e块 流n的a功nc能e
4系统间接口，与其他系统的接口 5内部接口 6算法上列举可能的求解算法 产生：概要设计说明，用户手册
接口：与外设，与软件，与人的界面
产生：需求规格说明书，数据流程图，数据字典
202（0/9/2标3 准：国标，军标，DOD标准）
第零章 程序设计的一些问题
• 需求分析-Requirement Analysis
• 概要设计-Primary Design
• 详细设计-Detailed Design
• 编码调试-Coding &设D计e：b如ug何解决问题，可能的解
• 程序与软件？
程序是最终达到一定目的指令序列。 例如课程表，会议程序，开学注册程序
计算机程序：计算机指令的序列，实现预期的目的。
软件 狭义：软件=程序，除了硬件都是软件 广义：软件≠程序 软件是一种抽象的、逻辑性的产品，它不仅是在 计算机上运行的程序,还包括开发、使用和维护程 序所需要的文档。 软件可以减轻劳动，提高工作效率，是计算机工 作的延伸。
学号 6201001 6201002 6201003 6201004 ...
姓名 语文 数学 C语言 张三 85 54 92 李四 92 84 64 王五 87 74 73
2020/9/23
例2：声音、图象
数据是信息的载体，是对客观事物的符号表示，它被计算机 所识别、存储和加工，构成计算机程序的加工原料。
• 概要设计-Primary Design
评 审
• 详细设计-Detailed Design
• 编码调试-Coding & Debug
• 测试-Testing
• 运行与维护-Maintenance
（标准：国标，军标，DOD标准）
2020/9/23
第零章 程序设计的一些问题
• 需求分析-Requirement Analysis • 概要设计-Primary Design • 详综细述：设说计明-问D题et，ai明le确d软D件e的si功gn能，明确做什么，建立数 • 编据任码流务图：调，确试数定-据软C字件od典开in发g的&主要De任b务ug • 测功试能：-T确es定ti主ng要功能－输入/处理/输出(IPO) • 运性间行能，：数与确据维定刷护主新要时-M性间a能in，te速n度an，c响e应时间，数据转换/传输时
2020/9/23
第零章 程序设计的一些问题
• 需求分析-Requ综 任i述 务re： ：m对e模n块t进A行n过a程ly描s述is，设计模块内部细节。 • 概要设计-Primary12结 资D构 源e设 分s计 析ig： 及n模 余块 量细 －化 大， 于形20成%的程余序量单元 • 详细设计-Detaile34d参 算D数 法化 的es： 具i设 体gn计 化参数，增加软件的柔性 • 编码调试-Codi产n生g：&详D细设eb计u说g明书 • 测试-Testing • 运行与维护-Maintenance
数据结构 = 数据 + 结构
从三个方面研究数据结构：
逻辑结构 存储结构
算法
2020/9/23
逻辑结构 • 数据元素之间具有的逻辑关系(结构)。
线性关系(线性结构)： 数据元素间为严格的一对一关系。
非 树形结构 ： 线 数据元素间为严格的一对多关系。
性
图状结构（或网状结构）：
结
数据元素间为多对多关系
• 通用性好
– 可靠性，可移植性-传统的程序 – 方法上：抽象思维，模块化
2020/9/23
第零章 程序设计方法
• 结构化程序设计方法 1968年Dijkstra提出结构化程序设计，主要思想：
– 自上而下，逐步求精-功能结构 – 分层结构与模块结构的程序设计-系统结构，先全局后局部，保证
块间不构成圈，块独立，块的层次分明 – 避免GOTO-控制结构采用三种结构 – 主程序员-组织结构
– 错误：60%发生在设计阶段，36%发生在编码阶段 – 纠正错误的费用：编制程序的费用为1，则说明阶段的费用为0.5
，测试阶段的费用为2－5，运行阶段的费用为10
• 组织结构：七人小组 • 软件生命周期的概念
2020/9/23
第零章 程序设计的一些问题
• 讨论 – 软件工程强调开始定型，以后不变，这在实际 工作中会有问题吗？ – 快速原型法Prototyping – 软件工程还是快速原型？
– 作业：至少完成6次作业(每次 布置作业后一周后上交，两周 截止日期，过期减少分数-最 后一次除外)
• 结业方法
1. 作业：30%, 考试70%
2. 考试占100%
数据结构在程序设计中是非常实用的一门技术， 是前人程序设计的结晶，希望大家能掌握这门技术， 为研究工作奠定基础。
2020/9/23
第零章 程序设计的一些问题