数据结构---C++版_海狸_hlz的博客-程序员宝宝_数据结构c++版

技术标签: 数据结构  

第 1 章 数据结构的基本概念
1.1 数据结构在程序设计中的作用
1)程序设计的实质是什么?
数据表示:将数据存储在计算机(内存)中
数据处理:处理数据,设计方案(算法)
1.2 计算机求解问题:
1)问题→抽象出问题的模型→求模型的解
问题——数值问题、非数值问题
2)数 值 问 题→数学方程
非数值问题→数据结构
3)本书讨论非数值问题的数据组织和处理,主要内容如下:
(1)数据的逻辑结构:线性表、树、图等数据结构,其核心
是如何组织待处理的数据以及数据之间的关系;
(2)数据的存储结构:如何将线性表、树、图等数据结构存
储到计算机的存储器中,其核心是如何有效地存储数据以及
数据之间的逻辑关系;
(3)算法:如何基于数据的某种存储结构实现插入、删除、
查找等基本操作,其核心是如何有效地处理数据;
(4)常用数据处理技术:查找技术、排序技术、索引技术等。
1.3 数据结构的基本概念
1)数据结构的基本概念
(1)数据:所有能输入到计算机中并能被计算机程序识别和处理的符号集合。
数值数据:整数、实数等
非数值数据:图形、图象、声音、文字等
(2)数据元素:数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。
(3)数据项:构成数据元素的不可分割的最小单位。
2)数据、数据元素、数据项之间的关系
(1)包含关系:数据由数据元素组成,数据元素由数据项组成。
(2)数据元素是讨论数据结构时涉及的最小数据单位,其中的数据项一般不予考虑。
3)数据结构的基本概念
(1)数据结构:相互之间存在一定关系的数据元素的集合。
按照视点的不同,数据结构分为逻辑结构和存储结构。
逻辑结构:指数据元素之间逻辑关系的整体。
(2)数据的逻辑结构是从具体问题抽象出来的数据模型
数据的逻辑结构在形式上可定义为一个二元组:
Data_Structure = (D, R)
其中D是数据元素的有限集合,R是D上关系的集合。
(3)存储结构:又称为物理结构,是数据及其逻辑结构在计算机中的表示。
(4)存储结构实质上是内存分配,在具体实现时依赖于计算机语言。
5)数据结构从逻辑上分为四类:
(1)集合:数据元素之间就是“属于同一个集合” ;
(2)线性结构:数据元素之间存在着一对一的线性关系;
(3)树结构:数据元素之间存在着一对多的层次关系;
(4)图结构:数据元素之间存在着多对多的任意关系。
6)通常有两种存储结构:
(1)顺序存储结构:用一组连续的存储单元依次存储数据元素,数据元素之间的逻辑关系由元素的存储位置来表示。
(2)链接存储结构:用一组任意的存储单元存储数据元素,数据元素之间的逻辑关系用指针来表示 。
7)逻辑结构和存储结构之间的关系
(1)数据的逻辑结构属于用户视图,是面向问题的,反映了数据内部的构成方式;数据的存储结构属于具体实现的视图,是面向计算机的。
(2)一种数据的逻辑结构可以用多种存储结构来存储,而采用不同的存储结构,其数据处理的效率往往是不同的。
8)抽象数据类型
(1) 数据类型(Data Type):一组值的集合以及定义于这个值集上的一组操作的总称。
例如:C++中的整型变量
(2)抽象(Abstract):抽出问题本质的特征而忽略非本质的细节。
例如: 地图、驾驶汽车
(3)抽象数据类型(Abstract Data Type,ADT):一个数据结构以及定义在该结构上的一组操作的总称。
注意:在设计ADT时,把ADT的定义、设计和实现分开来。定义部分只包含数据的逻辑结构和所允许的操作集合,一方面,ADT的使用者依据这些定义来使用ADT,即通过操作集合对该ADT进行操作;另一方面,ADT的实现者依据这些定义来完成该ADT各种操作的具体实现。
9)抽象数据类型
ADT 抽象数据类型名
Data
数据元素之间逻辑关系的定义
Operation
操作1
前置条件:执行此操作前数据所必须的状态
输 入:执行此操作所需要的输入
功 能:该操作将完成的功能
输 出:执行该操作后产生的输出
后置条件:执行该操作后数据的状态
操作2
……
……
操作n
……
endADT
10)数据结构的基本概念(小结)
在这里插入图片描述
1.4 算法及算法分析
1)算法的相关概念
(1)算法(Algorithm):是对特定问题求解步骤的一种描述,是指令的有限序列
(2)算法的五大特性:
【1】输入:一个算法有零个或多个输入。
【2】输出:一个算法有一个或多个输出。
【3】有穷性:一个算法必须总是在执行有穷步之后结束,且每一步都在有穷时间内完成。
【4】确定性:算法中的每一条指令必须有确切的含义,对于相同的输入只能得到相同的输出。
【5】可行性:算法描述的操作可以通过已经实现的基本操作执行有限次来实现。
(3)算法的描述方法
【1】自然语言
【2】流程图
【3】程序设计语言
【4】伪代码
【5】介于自然语言和程序设计语言之间的方法,它采用某一程序设计语言的基本语法,操作指令可以结合自然语言来设计。
优点:表达能力强,抽象性强,容易理解
使用方法:7 ± 2
(4)算法分析
【1】度量算法效率的方法:
 事后统计:将算法实现,测算其时间和空间开销。
缺点:⑴ 编写程序实现算法将花费较多的时间和精力;
⑵ 所得实验结果依赖于计算机的软硬件等环境因素。
 事前分析:对算法所消耗资源的一种估算方法。
【2】算法分析(Algorithm Analysis):对算法所需要的计算机资源——时间和空间进行估算。
时间复杂性(Time Complexity)
空间复杂性(Space Complexity)
【3】算法的时间复杂度分析
定理:若A(n)=amnm+am-1nm-1+…+a1n+a0是一个m次多项式,则A(n)=O(nm)。
说明:在计算算法时间复杂度时,可以忽略所有低次幂和最高次幂的系数。
第 2 章 线性表
2.1 线性表的逻辑结构
1)线性表的定义
线性表:简称表,是n(n≥0)个具有相同类型的数据元素的有限序列。
 线性表的长度:线性表中数据元素的个数。
 空表:长度等于零的线性表,记为:L=( )。
 非空表记为:L=(a1, a2 , …, ai-1, ai , …, an)。其中,ai(1≤i≤n)称为数据元素;下角标 i 表示该元素在线性表中的位置或序号 。
2)线性表的特性

  1. 有限性:线性表中数据元素的个数是有穷的。
  2. 相同性:线性表中数据元素的类型是同一的。
  3. 顺序性:线性表中相邻的数据元素ai-1和ai之间存在序偶关系(ai-1, ai),即ai-1是ai的前驱, ai是ai-1的后继;a1无前驱,an无后继,其它每个元素有且仅有一个前驱和一个后继
    3)线性表的抽象数据类型定义
    (1)初始描述
    ADT List
    Data
    线性表中的数据元素具有相同类型,
    相邻元素具有前驱和后继关系
    Operation
    ADT
    (2)增
    Insert
    前置条件:表已存在
    输入:插入i;待插x
    功能:在表的第i个位置处插入一个新元素x
    输出:若插入不成功,抛出异常
    后置条件:若插入成功,表中增加一个新元素
    (3)删
    Delete
    前置条件:表已存在
    输入:删除位置i
    功能:删除表中的第i个元素
    输出:若删除成功,返回被删元素,否则抛出异常
    后置条件:若删除成功,表中减少一个元素
    (4)改
    (5)查
    【1】根据序号查找元素
    Get
    前置条件:表已存在
    输入:元素的序号i
    功能:在表中取序号为i的数据元素
    输出:若i合法,返回序号为i的元素值,否则抛出异常
    后置条件:表不变
    【2】根据元素值查找序号
    Locate
    前置条件:表已存在
    输入:数据元素x
    功能:在线性表中查找值等于x的元素
    输出:若查找成功,返回x在表中的序号,否则返回0
    后置条件:表不变
    (6)排序
    (7)其他
    【1】初始化表
    InitList
    前置条件:表不存在
    输入:无
    功能:表的初始化
    输出: 无
    后置条件:建一个空表
    【2】销毁表
    DestroyList
    前置条件:表已存在
    输入:无
    功能:销毁表
    输出:无
    后置条件:释放表所占用的存储空间
    【3】求表长度
    Length
    前置条件:表已存在
    输入:无
    功能:求表的长度
    输出:表中数据元素的个数
    后置条件:表不变
    【4】判断表是否为空
    Empty
    前置条件:表已存在
    输入:无
    功能:判断表是否为空
    输出:若是空表,返回1,否则返回0
    后置条件:表不变
    2.2 线性表的顺序存储结构及实现
    1)顺序表——线性表的顺序存储结构
    (1)存储要点 用一段地址连续的存储单元
    依次存储线性表中的数据元素
    (2)用什么属性来描述顺序表?
    存储空间的起始位置
    顺序表的容量(最大长度)
    顺序表的当前长度
    (3)如何实现顺序表的内存分配?
    顺序表 对应 一维数组
    在这里插入图片描述
    在这里插入图片描述
    【1】如何求得任意元素的存储地址呢?
    在这里插入图片描述
    2)存储结构和存取结构
    存储结构是数据及其逻辑结构在计算机中的表示;
    存取结构是在一个数据结构上对查找操作的时间性能的一种描述。
    “顺序表是一种随机存取的存储结构”的含义为:在顺序表这种存储结构上进行的查找操作,其时间性能为O(1)。
    3)顺序存储要求存储位置反映逻辑关系
    4)顺序表的优缺点
     顺序表的优点:
    ⑴ 无需为表示表中元素之间的逻辑关系而增加额外的存储空间;
    ⑵ 随机存取:可以快速地存取表中任一位置的元素。
     顺序表的缺点:
    ⑴ 插入和删除操作需要移动大量元素;
    ⑵ 表的容量难以确定,表的容量难以扩充;
    ⑶ 造成存储空间的碎片。
    2.3 线性表的链接存储结构及实现
    1)单链表
    在这里插入图片描述
    2)存储特点:
  4. 逻辑次序和物理次序不一定相同。
    2.元素之间的逻辑关系用指针表示。
    在这里插入图片描述
    3)什么是存储结构?
    重点在数据元素之间的逻辑关系的表示,所以,将实际存储地址抽象。
    头指针:指向第一个结点的地址。
    尾标志:终端结点的指针域为空。
    头结点:在单链表的第一个元素结点之前附设一个类型相同的结点,以便空表和非空表处理统一。
    在这里插入图片描述
    4)算法设计的一般步骤
    第一步:确定入口(已知条件)、出口(结果);
    第二步:根据一个小实例画出示意图;
    第三步:① 正向思维:选定一个思考问题的起点,逐
    步提出问题、解决问题;② 逆向思维:从结论出发分
    析为达到这个结论应该先有什么;③ 正逆结合;
    第四步:写出顶层较抽象算法,分析边界情况;
    第五步:验证第四步的算法;
    第六步:写出具体算法;
    第七步:进一步验证,手工运行。
    5)循环链表
    (1)从单链表中某结点p出发如何找到其前驱
    将单链表的首尾相接,将终端结点的指针域由空指针改为指向头结点,构成单循环链表,简称循环链表。
    在这里插入图片描述
    6)双链表
    在这里插入图片描述
    (1)基本概念
    在这里插入图片描述
    2.4 顺序表和链表的比较
    1)存储分配方式比较
    顺序表采用顺序存储结构,即用一段地址连续的存储单元依次存储线性表的数据元素,数据元素之间的逻辑关系通过存储位置来实现。
    链表采用链接存储结构,即用一组任意的存储单元存放线性表的元素,用指针来反映数据元素之间的逻辑关系。
    2)时间性能比较
    时间性能是指实现基于某种存储结构的基本操作(即算法)的时间复杂度。
    按位查找:
    顺序表的时间为O(1),是随机存取;
    链表的时间为O(n),是顺序存取。
    插入和删除:
    顺序表需移动表长一半的元素,时间为O(n);
    链表不需要移动元素,在给出某个合适位置的指针后,插入和删除操作所需的时间仅为O(1)。
    3)空间性能比较
    (1)空间性能是指某种存储结构所占用的存储空间的大小。
    在这里插入图片描述
    (2)结点的存储密度:
     顺序表:结点的存储密度为1(只存储数据元素),没有浪费空间;
     链表:结点的存储密度<1(包括数据域和指针域),有指针的结构性开销。
    (3)结构的存储密度
     顺序表:结点的存储密度为1(只存储数据元素),没有浪费空间;
     链表:结点的存储密度<1(包括数据域和指针域),有指针的结构性开销。
    (4)结论
    ⑴若线性表需频繁查找却很少进行插入和删除操作,或其操作和元素在表中的位置密切相关时,宜采用顺序表作为存储结构;若线性表需频繁插入和删除时,则宜采用链表做存储结构。
    ⑵当线性表中元素个数变化较大或者未知时,最好使用链表实现;而如果用户事先知道线性表的大致长度,使用顺序表的空间效率会更高。
    2.4 顺序表和链表的比较
    总之,线性表的顺序实现和链表实现各有其优缺点,不能笼统地说哪种实现更好,只能根据实际问题的具体需要,并对各方面的优缺点加以综合平衡,才能最终选定比较适宜的实现方法。
    2.5 线性表的其它存储方法
    1)静态链表
    在这里插入图片描述
    (1)相对于顺序表而言,静态链表有什么优点?
     优点:在执行插入和删除操作时,只需修改游标,不需要移动表中的元素,从而改进了在顺序表中插入和删除操作需要移动大量元素的缺点。
     缺点:没有解决连续存储分配带来的表长难以确定的问题;静态链表还需要维护一个空闲链;静态链表不能随机存取。
    2)间接寻址
    在这里插入图片描述
    本章总结
    在这里插入图片描述
    第 3 章 栈和队列
    本章的基本内容是:
    两种特殊的线性表——栈和队列
    从数据结构角度看,栈和队列是操作受限的线性表,他们的逻辑结构相同。
    从抽象数据类型角度看,栈和队列是两种重要的抽象数据类型。
    3.1 栈
    1)栈的逻辑结构
    在这里插入图片描述
    在这里插入图片描述
    (2)栈的操作特性:后进先出
    2)栈的顺序存储结构及实现
    (1)顺序栈——栈的顺序存储结构
    【1】如何改造数组实现栈的顺序存储?
    在这里插入图片描述
    在这里插入图片描述
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_33410995/article/details/104257973

智能推荐

alter session set ddl_lock_timeout=10_数据库人生的博客-程序员宝宝

SQL&gt; set lines 200;SQL&gt; set pages 200;SQL&gt; show parameter ddl_lock_timeout;NAME TYPE VALUE------------------------------------ -------------------------------- ---------...

电机的恒压频比控制原理_捡蘑菇的小竹篓的博客-程序员宝宝_恒压频比控制

    变频调速系统的控制方式有变压变频(U/f)控制、矢量控制、直接转矩控制等。根据异步电动机的转速公式,异步电动机的转速有下列三种调节方式。    ①调频调速。改变三相交流电的频率厂,可调节异步电动机的同步转速,从而调节异步电动机的转子转速。平滑改变三相交流电的频率,可实现异步电动机的无级调速。    ②改变磁极对数p。增加磁极对数,使同步转速降低。与调频调速不同,这种调速方式会成倍改...

聊聊如何学好 Python_GitHubDaily的博客-程序员宝宝

程序员在普通人眼里就像魔法师,一个插件就能解决春运抢票难的问题,一个脚本就可以自动用微信和妹纸聊天,几十行代码就能采集微信文章。一周搭建一个网站等等。可这些东西在程序员眼里都是稀松平常的...

[论文解读]UNet++解读 + 它是如何对UNet改进 + 作者的研究态度和方式_Cierlly的博客-程序员宝宝_unet的改进

UNet++论文: 地址UNet++论文翻译:地址UNet++ 源代码:地址UNet++作者在知乎 上进行了解读,里面还有视频的详解,深入人心。里面的每一句话都令我印象深刻,我总结如下:很多论文给出了他们建议的网络结构,其中包括非常多的细节,比如用什么卷积,用几层,怎么降采样,学习率多少,优化器用什么,这些都是比较直观的参数,其实这些在论文中给出参数并不见得是最好的,所以关注这些的意义不大,...

Javascript模块化编程(二):AMD规范_原野-的博客-程序员宝宝

这个系列的第一部分介绍了Javascript模块的基本写法,今天介绍如何规范地使用模块。(接上文)七、模块的规范先想一想,为什么模块很重要?因为有了模块,我们就可以更方便地使用别人的代码,想要什么功能,就加载什么模块。但是,这样做有一个前提,那就是大家必须以同样的方式编写模块,否则你有你的写法,我有我的写法,岂不是乱了套!考虑到Javascript模块现在还没有官方规范,这...

台式计算机如何设置屏幕亮度,怎么调整台式电脑屏幕亮度的方法,如何调整显示器..._龙心有你的博客-程序员宝宝

使用计算机时,会遇到屏幕亮度过高或过低,看起来不太舒服的情况,因此我们需要调整计算机的亮度,但是有些用户仍然没有知道如何调整。台式计算机的屏幕亮度,因此如何调整显示器的亮度,下面的编辑器将与您分享调整台式计算机的屏幕亮度的步骤。解决方案:1、显示器的右下角通常有一行按钮。我们可以在这里调整亮度。您可以按此处的MENU按钮打开菜单,然后通过显示器下方的向上和向下箭头调整亮度。当然,此处的按钮与显示器...

随便推点

阿里8年SQL技术专家耗时6个月总结出SQL优化核心思想笔记_码农成神之路的博客-程序员宝宝

随着数据量逐年增加,并发量也成倍增长,SQL性能逐渐成为IT系统设计和开发时重点考虑的问题之一。SQL优化就像做数学题一样,如果没有思路,那你将无从下手。本书旨在帮助读者建立SQL优化理念,并在其指导下快速掌握SQL优化的方法和技巧。本书基于Oracle进行讲解,适合数据库开发人员、数据库运维及管理人员、数据仓库ETL、BI报表开发人员以及数据库相关的各类技术人员阅读。鉴于SQL优化思想在任何数据库中都殊途同归,因此无论是基于MySQL.sQL Server,还是基于DB2的技术人员,都能从本书中有所受

Linux 流量监控_运维生涯记录的博客-程序员宝宝_linux流量监控

在类Linux系统中可以使用top查看系统资源、进程、内存占用等信息。查看网络状态可以使用netstat、nmap等工具。若要查看实时的网络流量,监控TCP/IP连接等,则可以使用iftop。iftop类似于top的实时流量监控工具,可以用来监控网卡的实时流量(可以指定网段)、反向解析IP、显示端口信息等。安装iftop命令[[email protected] ~]# yum install epel-release -y[[email protected] ~]# yum install -y i

mysql语句count(1)_mysqlÖÐcount(1)Óëcount(*)±È½Ï_DeepWeaver的博客-程序员宝宝

mysqlÖÐcount(1)Óëcount(*)±È½Ï2019/10/10/17:36:22ÔĶÁ£º1157À´Ô´£º¹È¸èSEOËã·¨±êÇ£º·òΨSEOÊÓƵ½Ì³Ìsqlµ÷ÓÅ,Ö÷ÒªÊÇ¿¼ÂǽµµÍ:consistent getsºÍphysical readsµÄÊýÁ¿.count(1)Óëcount(*)±È½Ï:Èç¹ûÄãµÄÊý¾Ý±í...

Oracle用户的变量LANG,Oracle 设置环境变量NLS_LANG(客户端的环境变量)_黄抒扬的博客-程序员宝宝

NLS_LANG格式:NLS_LANG=LANGUAGE_TERRITORY.Client CHARACTERSET1、NLS_LANG 参数组成NLS_LANG参数由以下部分组成:NLS_LANG=_.NLS_LANG各部分含义如下:LANGUAGE指定:Oracle消息使用的语言日期中月份和日显示TERRITORY指定货币和数字格式地区和计算星期及日期的习惯CHARACTERSET:控制客户端...

八款优秀的Linux天文学软件_benwdm的博客-程序员宝宝

八款优秀的Linux天文学软件 天文学是一门研究恒星、小行星、彗星、卫星、流星雨等天体的科学。它十分适合业余爱好者,没有年龄限制,没有贫贱之分。在这门学科中,业余爱好者常常能发现专业人士未注意到的奇妙现象,他们能帮助观测恒星和跟踪小行星。只凭借肉眼我们也能去观测夜空中的无数星星。Linux平台上有大量天文学软件,能为天文学业余爱好者提供有用的工具,帮助绘制夜空地图,制定详细观测计划...

推荐文章

热门文章

相关标签