搜索
房产
装修
汽车
婚嫁
健康
理财
旅游
美食
跳蚤
二手房
租房
招聘
二手车
教育
茶座
我要买房
买东西
装修家居
交友
职场
生活
网购
亲子
情感
龙城车友
找美食
谈婚论嫁
美女
兴趣
八卦
宠物
手机

数据结构导论之第一章(概论)

[复制链接]
查看: 71|回复: 0

1万

主题

1万

帖子

3万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
32649
发表于 2020-1-15 03:39 | 显示全部楼层 |阅读模式
数据结构导论之第一章(概论)  热点新闻 1911569-20200113140713663-628156008

一、引言

数据结构(Data structure):是盘算机机关数据和存储数据的方式,是指一组相互之间存在一种或多种特定关系的数据的机关方式和它们在盘算机内的存储方式,以及界说在该组数据上的一组操纵。
数据结构:数据的逻辑结构+数据的存储结构+数据的底子运算
盘算机治理题目标步伐:

  • 1、建立数学模子
  • 2、筹划求解算法
  • 3、编程实现算法(应用各类盘算机说话实现算法)
1976年瑞士盘算机科学家尼克劳斯·维尔特[Niklaus Wirth]提出:算法+数据结构=步伐
二、底子概念和术语

数据(Data):全数能被盘算机处置赏罚的标记的聚集。现实题目中的数据称为原始数据
数据元素(Data Element):是数据这个集会合的一个个体即数据的底子单元。
数据项(Data Item):数据元素经常还可分为几多个数据项,数据项是数据具故意义的最小单元;数据库中,数据项又称为字段/域,它是数据的不成份割的最小标识单元。
1、数据的逻辑结构:数据的逻辑结构是指数据及数据的机关方式,是一种数学模子;指数据元素之间的结构关系
数据的逻辑结构(D, {R}) 可分为以下几种: D = {d1,d2, …, dn}

  • ◆ 聚集: 数据元素同“属于一个聚集”。R = { }。尽情两个结点之间都没有毗连关系,机关形式疏松
  • ◆ 线性结构: R= {(d1, d2), (d2, d3), …, (dn-1, dn)},即除肇端节点和终端结点d1、dn外,每个节点有一个先驱和一个后继;结点按逻辑关系依次排列构成一条“链”,结点之间一个一个依次相毗连。
  • ◆ 树形结构: (D, {R}) 组成树,即每个元素最多有一个先驱,可以有多个后继;具有分支、条理特征,上层的结点可以和下层多个结点相毗连,但下层结点只能和上层的一个结点相毗连
  • ◆ 图结构: (D, {R})组成一个图;最复杂,任何两个结点都可以相毗连。
2、数据的存储结构(物理结构):数据的存储结构是指数据的逻辑结构在盘算机中的表示,数据的存储结构分为顺序存储结构和链接存储结构两种。
存储结构的重要部分:

  • 存储结点:每个存储结点寄存一个数据元素
  • 元素逻辑关系:数据元素之间关联方式的表示
数据结构的存储=数据元素的存储+元素逻辑关系的存储
元素关联关系的存储方式重要有:

  • 顺序存储方式:指全数存储节点寄存在一个连续的存储区里,操纵节点在存储器中的相对位置来表示元素之间的逻辑关系
  • 链式存储方式:指每个存储点除了包含一个数据元素外,还包含指针,每个指针指向一个与本节点有逻辑关系的节点,用指针表示数据元素之间的逻辑关系
  • 索引存储方式
  • 散列存储方式
=============顺序存储方式=================
顺序存储方式:借助数据元素的相对存储位置来表示数据的逻辑结构;
线性表的顺序存储方式:将表中的结点一次寄存在盘算机内存中一组连续的存储单元中。
顺序的方式: 将元素存储到一片连续的存储区
特点:

  • 1、 预先分派好长度,必要预估存储数据必要的存储量;
  • 2、插入和删除必要移动其他元素;
  • 3、存取快速,是随机存取结构。
=============链式存储方式=================
链式存储方式:借助数据元素地点的指针表示数据的逻辑结构;这类结构是给结点附加一个指针字段,指出后来继节点的位置,即寄存结点的存储单元分为两部分:数据项和指针项
特点:

  • 静态分派,不必要预先肯定内存分派;
  • 插入和删除不必要移动其他元素;
  • 非随机存取结构
===========索引存储方式===============
索引存储方式:借助索引表中的索引指示各存储节点的存储位置。
===========散列存储方式===============
散列存储方式:用散列函数指示各节点的存储位置。
3、运算
运算:指在某种逻辑结构上施加的操纵,即对逻辑结构的加工。
加工型运算:其操纵改变原逻辑结构的值;如:结点个数,结点内容等。
援用型运算:其操纵不改变原逻辑结构的值。
底子运算:建立(建立)、查找 、读取 、插入 、删除
三、算法及描摹

算法:算律例定了求解给定典范题目所需的全数“处置赏罚步伐”及实行顺序,使给定典范题目能在有限时候内被机械的求解。
算法必须操纵某种说话描摹:

  • 步伐
  • 介于自然说话和步伐筹划说话的伪代码
  • 非形式算法(自然说话)
  • 框图(N-S图)
一个算法是对特定题目求解步伐的一种描摹,它是指令的有穷序列。
算法具有以下特征:

  • ① 有穷性: 一个算法总是在实行有穷步后竣事。
  • ② 肯定性: 算法的每一步都必须是明白地界说的。
  • ③ 可行性: 算法中的每一步都是可以经过已经实现的操纵来完成的。
  • ④ 输入: 一个算法有零个大要多个输入,这些输入取自于特定的工具聚集。
  • ⑤ 输出:一个算法有一个大要多个输出,它们是与输入有特定关系的量。
四、算法分析

算法的筹划应满足:

  • ① 正确性:对于正当的输入发生合适要求的输出。
  • ② 易读性:算法应当易读、便于交换, 这也是保证算法正确性的条件;增加诠释也是一种增加可读性的法子。
  • ③ 结实性:当输入不法数据时, 算法还能做出适当的反应而不会崩溃,如输出错误信息;算法中应当考虑适当的毛病处置赏罚。
  • ④ 时空性:指算法的时候复杂度和空间复杂度,算法分析重要分析算法的时候复杂度和空间复杂度,目标是进步算法的服从。
最优算法的2个怀抱:

  • 时候复杂度:算法运转时必要的总步数,凡是是题目范围的函数。
  • 空间复杂度:算法实行时所占用的存储空间,凡是是题目范围的函数
肯定算法的盘算量:

  • 公道地挑选一种或几种操纵作为“标准操纵”,无特别分析,默许以赋值语句作为标准操纵;肯定每个算法共实行几多次标准操纵,并将此次数规定为该算法的盘算量。
  • 算法的最坏情况时候复杂度:以算法在全数输入下的盘算量的最大值作为算法的盘算量。
  • 算法的均匀情况时候复杂度:以算法在全数输入下的盘算量的加权均匀值作为算法的盘算量。
  • 最坏情况时候复杂度平静均情况时候复杂度统称为时候复杂度
================时候复杂度================
数据结构导论之第一章(概论)  热点新闻 1911569-20200114194145377-548853169

运转该代码必要1秒 ,时候复杂度记作O(1)
数据结构导论之第一章(概论)  热点新闻 1911569-20200114195002719-1640687153

运转该代码必要n*1秒 时候复杂度记作O(n)
数据结构导论之第一章(概论)  热点新闻 1911569-20200114200130356-1322002582

运转该代码必要n*n*1秒 时候复杂度记作O(n*n);
数据结构导论之第一章(概论)  热点新闻 1911569-20200114200355751-2132629985

================空间复杂度===============
空间复杂度:是对一个算法在运转进程中姑且占用存储空间巨细的量度;预算算法空间复杂度时,一样平常只分析帮助变量所占用的空间。
一个算法在实行时代所必要的存储空间量包含以下部分:

  • 步伐代码所占用的空间;
  • 输入数据所占用的空间;
  • 帮助变量所占用的空间;

免责声明:假如加害了您的权益,请联系站长,我们会实时删除侵权内容,感谢合作!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Copyright © 2006-2014 全椒百姓网-全椒知名**,发布及时新鲜的全椒新闻资讯 生活信息 版权所有 法律顾问:高律师 客服电话:0791-88289918
技术支持:迪恩网络科技公司  Powered by Discuz! X3.2
快速回复 返回顶部 返回列表