数据结构 第1讲 基础知识

数据结构 第1讲 基础知识

        著名的瑞士科学家N.Wirth教授提出:数据结构+算法=程序。数据结构是程序的骨架,算法则是程序的灵魂。

        学习数据结构首先从几个概念开始:

  • 数据:所有能输入到计算机中去的描述客观事物的符号。 包括文本、声音、图像、各种符号,例如扫一扫的二维码等等。
  • 数据元素:数据的基本单位,也称结点或记录。
  • 数据项:有独立含义的数据最小单位,也称域。

                                                 若干个数据项构成一个数据元素,数据项是不可分割的最小单位。

  • 数据对象:相同特性数据元素的集合,是数据的一个子集。
  • 数据结构:相互之间存在一种或多种特定关系的数据元素的集合。

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

  • 逻辑结构存储结构

数据结构包括逻辑结构和存储结构。逻辑结构是数据元素之间的关系,存储结构是数据元素及其关系在计算机中的存储方式。例如小明同学和小勇同学是表兄弟,这是他们之间的逻辑关系,他们在教室里面的位置是挨着坐,还是分开坐,对角交叉坐,这是他们的存储结构。

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

数据结构的逻辑结构一共有四种:

              1. 集合——数据元素间除"同属于一个集合"外,无其它关系。

         集合中的元素是离散、无序的,就像鸡圈中的小鸡一样,可以随意走动,它们之间没有什么关系,唯一的亲密关系就是在同一个鸡圈里。数据结构重点研究的是数据之间的关系,而集合中元素是离散的,没有什么关系,因此集合虽然是一种数据结构,数据结构书中却不讲,离散数学中有集合论部分。

                        2. 线性结构——一个对一个,如线性表、栈、队列

线性结构就像宝宝穿珠子,是一条线,不会发叉。有一个唯一的开始和结束,除了第一个元素外,每个元素都有唯一的前驱(前面那个),除了最后一个元素外,每个元素都有唯一的后继(后面那个)。

3. 树形结构——一个对多个,如树

树形结构就像一棵倒立的树,树根可以发出多个分支,每个每支也可以继续发出分支。树枝和树枝之间是不相交的。

4. 图形结构——多个对多个,如图

图形结构就像我们经常见到的地图,任何一个结点都可能和其它结点有关系,就像一张错综复杂的网。

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

存储结构可以分为四种:顺序存储,链式存储,散列存储,索引存储。很多数据结构书只说了前两种最基本的存储结构。在这里加上后两种,有必要让大家了解一下。

1. 顺序存储

          顺序存储在计算机内的存储位置是连续的,可以快速定位第几个元素的问题。中间不允许有空,所以插入、删除时需要移动大量元素。

2.链式存储

              链式存储就像一个铁链子,一环扣一环才能连在一起。每个结点除了数据域,还有一个指针域,记录下一个元素的存储地址。

3. 散列存储

           散列存储,又称哈希(hash)存储,由节点的关键码值决定节点的存储地址。用哈希函数确定数据元素的存储位置与关键码之间的对应关系。

例如:设哈希表的地址范围为0~9,哈希函数为:H(key)=key%10。输入关键字序列:(24,10,32,17,41,15,49),构造哈希表。

24%10=4:存储在下标为4的位置

10%10=0:存储在下标为0的位置

32%10=2:存储在下标为2的位置

17%10=7:存储在下标为7的位置

41%10=1:存储在下标为1的位置

15%10=5:存储在下标为5的位置

49%10=9:存储在下标为9的位置

散列存储可以通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。如果有冲突,则有多种处理冲突的方法。

4. 索引存储

         索引存储,除建立存储结点信息外,还建立附加的索引表来标识结点的地址。索引表由若干索引项组成。如果每个节点在索引表中都有一个索引项,则该索引表就被称为稠密索引。若一组节点在索引表中只对应于一个索引项,则该索引表就成为稀疏索引。索引项的一般形式一般是关键字、地址。

在搜索引擎中,需要按某些关键字的值来查找记录,为此可以按关键字建立索引,这种索引就叫做倒排索引,带有倒排索引的文件就叫做倒排索引文件,又称为倒排文件倒排文件可以实现快速检索,这种索引存储方法是目前搜索引擎最常用的存储方法。

  • 抽象数据类型

          抽象数据类型可以用以下的三元组来表示:

ADT抽象数据类型名{

数据对象:<数据对象的定义>

数据关系:<数据关系的定义>

基本操作:<基本操作的定义>

} ADT抽象数据类型名

例如:

线性表的抽象数据类型的定义:     ADT List{         数据对象:D={ai|ai∈Elemset,i=1,2,…,n,n≥0}         数据关系:R1={<ai-1,ai>|ai-1,ai∈D,i=2,…,n}         基本操作:         InitList(&L)          操作结果:构造一个空的线性表L         DestroyList(&L)          初始条件:线性表已存在          操作结果:销毁线性表L         ClearList(&L)          初始条件:线性表已存在          操作结果:置线性表L为空表         ListEmpty(L)          初始条件:线性表已存在          操作结果:若线性表L为空表,则返回TRUE,否则返回FALSE         ListLenght(L)          初始条件:线性表已存在          操作结果:返回线性表L数据元素个数         GetElem(L,i,&e)          初始条件:线性表已存在(1≤i≤ListLenght(L))          操作结果:用e返回线性表L中第i个数据元素的值         locatElem(L,e,comare())          初始条件:线性表已存在,comare()是数据元素判定函数          操作结果:返回线性表L中第1个与e满足关系comare()的数据元素的位序         PriorElem(L,cur_e,&pre_e)          初始条件:线性表已存在          操作结果:若cur_e是线性表L的数据元素,且不是第一个,则用pre_e返回它的前驱,否则操作失败,pre_e无定义         NextElem(L,cur_e,&)          初始条件:线性表已存在          操作结果:若cur_e是线性表L的数据元素,且不是第最后一个,则用next_e返回它的后继,否则操作失败,next_e无定义         ListInsert(&L,i,e)          初始条件:线性表已存在(1≤i≤ListLenght(L)+1)          操作结果:在线性表L中第i个数据元素之前插入新元素e,L长度加1         ListDelete(&L,i,&e)          初始条件:线性表已存在(1≤i≤ListLenght(L))          操作结果:删除线性表L中第i个数据元素,用e返回其值,L长度减1         ListTraverse(L,visit())          初始条件:线性表已存在          操作结果:依次对线性表L的每个数据元素调用visit()函数,一旦visit()失败,则操作失败 }ADT List

对于一种数据结构, 常见的运算:插入,删除,修改,查找,排序。

        为什么要使用抽象数据类型?

信息隐蔽和数据封装,使用与实现相分离。抽象数据类型独立于运算的具体实现,使用户程序只能通过抽象数据类型定义的某些操作来访问其中的数据,实现了信息隐藏。在C++中可以用类的声明表示抽象数据类型,用类的实现来实现抽象数据类型。

        小结:

        本节需要知道数据、数据元素、数据项、数据结构的基本概念,逻辑结构有四种:集合,线性结构,树,图,存储结构有四种:顺序存储,链式存储,散列存储,索引存储。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏灯塔大数据

技术 | Python从零开始系列连载(十)

导读 Python特色数据类型(元组)(下) 元组和列表相互转化 ? ? 没错,只要在原来的列表外套一层tuple()就可以转为元组 在原来的元组外面套一层li...

34850
来自专栏JAVA高级架构

java面试需要掌握知识点

重点知识 由于我面试的JAVA开发工程师,针对于JAVA,需要理解的重点内容有: JVM内存管理机制和垃圾回收机制(基本每次面试都会问,一定要搞得透彻) JVM...

38850
来自专栏互联网杂技

Javascript 中的神器——Promise

Promise in js 回调函数真正的问题在于他剥夺了我们使用 return 和 throw 这些关键字的能力。而 Promise 很好地解决了这一切。 2...

35850
来自专栏Java技术栈

跟我学 Java 8 新特性之 Stream 流(二)关键知识点

我们的第一篇文章,主要是通过一个Demo,让大家体验了一下使用流API的那种酣畅淋漓的感觉。如果你没有实践,我还是再次呼吁你动手敲一敲,自己实实在跑一遍上一篇的...

15040
来自专栏编程之旅

线性表的顺序存储结构

举个简单的例子,蔺老师在给九班学生安排座位之前,会让学生们从矮到高按照身高的高矮升序排列,假如蔺老师的班上只有十个学生,而全班共有50个座位,那蔺老师会把这10...

20420
来自专栏Golang语言社区

用Golang写一个搜索引擎

本篇较长较枯燥,请保持耐心看完。 前面两章介绍了一下倒排索引以及倒排索引字典的两种存储结构,分别是 跳跃表 和 哈希表 ,本篇我们介绍另一种数据结构,他也被大量...

48570
来自专栏架构说

leetcode538. 把二叉搜索树转换为累加树

给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater

19930
来自专栏一枝花算不算浪漫

HashMap中的resize以及死链的情况

451120
来自专栏JavaEdge

设计模式实战-迭代器模式

迭代器是为容器服务的,那什么是容器呢? 能容纳对象的所有类型都可以称之为容器,例如Collection集合类型、Set类型等,迭代器模式就是为解决遍历这些容器中...

34020
来自专栏java一日一条

Java编程常见问题汇总3

这里本意是希望用当前类来加载希望的对象, 但是这里的getClass()可能抛出异常, 特别在一些受管理的环境中, 比如应用服务器, web容器, Java W...

8920

扫码关注云+社区

领取腾讯云代金券