开发者社区> 流楚丶格念> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

数据结构与算法设计基础

简介: 数据结构与算法设计基础
+关注继续查看

1 数据结构的研究内容


数据结构的研究内容为:


研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作。


数据结构课程的形成和发展:


  • 形成阶段:


60年代初期,“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年,“数据结构”被列入美国一些大学计算机科学系的教学计划。


  • 发展阶段:


数据结构的概念不断扩充,包括了网络、集合代数论、关系等“离散数学结构”的内容。


70年代后期,我国高校陆续开设该课程。


数据结构地位


介于数学、计算机硬件和计算机软件三者之间的一门核心课程


image


数据结构在计算机学科中的地位


image


2 基本概念和术语


基本概念


1、数据(data):所有能输入到计算机中去的描述客观事物的符号:


  • 数值性数据


  • 非数值性数据(多媒体信息处理)


2、数据元素(data element):数据的基本单位,也称结点(node)或记录(record)


3、数据项(data item):有独立含义的数据最小单位,也称域(field)


三者之间的关系:数据 > 数据元素 > 数据项


4、数据对象(Data Object):相同特性数据元素的集合,是数据的一个子集


  • 整数数据对象


N = { 0, 1, 2, … }


  • 学生数据对象


学生记录的集合


5、数据结构(Data Structure):是相互之间存在一种或多种特定关系的数据元素的集合。


数据结构是带“结构”的数据元素的集合,“结构”就是指数据元素之间存在的关系。


数据结构的两个层次:


逻辑结构


数据元素间抽象化的相互关系,与数据的存储无关,独立于计算机,它是从具体问题抽象出来的数学模型。


划分方法一:


(1)线性结构


有且仅有一个开始和一个终端结点,并且所有结点都最多只有一个直接前趋和一个后继。


例如:线性表、栈、队列、串


(2)非线性结构


一个结点可能有多个直接前趋和直接后继。


例如:树、图


划分方法二:


image


存储结构(物理结构)


数据元素及其关系在计算机存储器中的存储方式。


存储结构分为:


  • 顺序存储结构——借助元素在存储器中的相对位置来表示


    • 数据元素间的逻辑关系


image


  • 链式存储结构——借助指示元素存储地址的指针表示数据


    • 元素间的逻辑关系 可以连续 可以不连续


image


3 抽象数据类型的表示与实现


数据类型


定义:在一种程序设计语言中,变量所具有的数据种类


FORTRAN语言:整型、实型、和复数型


C语言:


 基本数据类型: char int float double void


 构造数据类型:数组、结构体、共用体、文件


数据类型是一组性质相同的值的集合, 以及定义于这个集合上的一组运算的总称


抽象数据类型(ADT: Abstract Data Types)


  • 更高层次的数据抽象


  • 由用户定义,用以表示应用问题的数据模型


  • 由基本的数据类型组成, 并包括一组相关的操作


image


4 算法与算法分析


  • 算法定义:一个有穷的指令集,这些指令为解决某一特定任务规定了一个运算序列


  • 算法的描述:


自然语言


流程图


程序设计语言


伪代码


  • 算法的特性:


输入 有0个或多个输入


输出 有一个或多个输出(处理结果)


确定性 每步定义都是确切、无歧义的


有穷性 算法应在执行有穷步后结束


有效性 每一条运算应足够基本


  • 算法的评价


正确性


可读性


健壮性


高效性(时间代价和空间代价)


  • 算法的效率的度量


1.事后统计:利用计算机内的计时功能,不同算法的程序可以用一组或多组相同的统计数据区分


缺点:


必须先运行依据算法编制的程序


所得时间统计量依赖于硬件、软件等环境因素,掩盖算法本身的优劣


2.事前分析估计:


一个高级语言程序在计算机上运行所消耗的时间取决于:


  • 依据的算法选用何种策略


  • 问题的规模


  • 程序语言


  • 编译程序产生机器代码质量


  • 机器执行指令速度


同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行,效率均不同,———使用绝对时间单位衡量算法效率不合适


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
数据结构与算法(一)
近日受北京疫情影响居家办公,给自己充充电,刷一遍 邓俊辉老先生的算法与数据结构教程,纯属学习笔记,有总结不当的地方欢迎指正~
20 0
数据结构与算法之并查集
数据结构与算法之并查集
32 0
数据结构与算法——堆
堆(Heap),其实是一种特殊的二叉树,主要满足了二叉树的两个条件: 1. 堆是一种完全二叉树,还记得完全二叉树的定义吗?叶节点都在最底下两层,最后一层的节点都靠左排列,并且除了最后一层,其他层的节点个数都要达到最大,这种树叫做完全二叉树。 2. 堆中的每个节点的值都必须大于等于(或者小于等于)其左右子节点的值。 对于堆中的每个节点都大于等于其左右子节点的值,叫做大顶堆,反之,则叫做小顶堆。看看下面的图就能懂了。
17 0
数据结构与算法(中)
树的深度优先搜索
43 0
数据结构与算法(上)
数据结构和算法有什么关系?
29 0
🔴数据结构与算法零基础入门1️⃣🔴
数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。
33 0
数据结构与算法(二)算法
算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。
24 0
数据结构和算法
顺序表常用的一种,学习并了解显得十分重要,顺序表为以后的学习打下了基石。通过学习可以对顺序表有一定的掌握。
48 0
数据结构与算法之基础概述
以下博客根据B站罗召勇老师视频:数据结构与算法基础-Java版(罗召勇)写的详细笔记
48 0
+关注
流楚丶格念
csdn平台优质创作者,51cto TOP博主,360图书馆科技博主,燕山大学目前大三在读,日拱一卒,功不唐捐,加油!!!
1010
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载