Dotcpp  >  编程教程  >  数据结构  >  什么是数据结构?

什么是数据结构?

点击打开在线编译器,边学边练

一、什么是数据结构?

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。结构包括逻辑结构和物理结构。

数据的逻辑结构包括4种

(1)集合:数据元素之间除了有相同的数据类型再没有其他的关系。

(2)线性结构:数据元素之间是一对一的关系 ——线性表、栈、队列。

(3)树形结构:数据元素之间是一对多的关系。

(4)图状结构:数据元素之间是多对多的关系。

物理结构包括顺序存储结构和链式存储结构。


二、解释一下顺序存储与链式存储

顺序存储结构是用一段连续的存储空间来存储数据元素,可以进行随机访问,访问效率较高。链式存储结构是用任意的存储空间来存储数据元素,不可以进行随机访问,访问效率较低。


三、头指针和头结点的区别?

头指针:是指向第一个节点存储位置的指针,具有标识作用,头指针是链表的必要元素,无论链表是否为空,头指针都存在。

头结点:是放在第一个元素节点之前,便于在第一个元素节点之前进行插入和删除的操作,头结点不是链表的必须元素,可有可无,头结点的数据域也可以不存储任何信息。


四、线性结构的特点

(1)集合中必存在唯一的一个"第一个元素";

(2)集合中必存在唯一的一个"最后的元素";

(3)除最后元素之外,其它数据元素均有唯一的"后继";

(4)除第一元素之外,其它数据元素均有唯一的"前驱"。


五、数组和链表的区别?

从逻辑结构来看:数组的存储长度是固定的,它不能适应数据动态增减的情况。链表能够动态分配存储空间以适应数据动态增减的情况,并且易于进行插入和删除操作。

从访问方式来看:数组在内存中是一片连续的存储空间,可以通过数组下标对数组进行随机访问,访问效率较高。链表是链式存储结构,存储空间不是必须连续的,可以是任意的,访问必须从前往后依次进行,访问效率较数组来说比较低。

如果从第i个位置插入多个元素,对于数组来说每一次插入都需要往后移动元素,每一次的时间复杂度都是O(n),而单链表来说只需要在第一次寻找i的位置时时间复杂度为O(n),其余的插入和删除操作时间复杂度均为O(1),提高了插入和删除的效率。


六、单链表结构和顺序存储结构的区别?

当进行插入和删除操作时,顺序存储结构每次都需要移动元素,总的时间复杂度为O(n^2),而链式存储结构确定i位置的指针后,其时间复杂度仅为O(1)。由于顺序存储结构需要进行预分配存储空间,所以容易造成空间浪费或者溢出。链式存储结构不需要预分配存储空间,元素个数不受限制。


七、栈和队列的区别

队列是允许在一段进行插入另一端进行删除的线性表,对于进入队列的元素按“先进先出”的规则处理,在表头进行删除在表尾进行插入。

栈是只能在表尾进行插入和删除操作的线性表。对于插入到栈的元素按“后进先出”的规则处理,插入和删除操作都在栈顶进行。由于进栈和出栈都是在栈顶进行,所以要有一个size变量来记录当前栈的大小,当进栈时size不能超过数组长度,size+1,出栈时栈不为空,size-1。


知识点标签:数据结构


本文固定URL:https://www.dotcpp.com/course/961

算法竞赛教程
第一章 算法基础
第二章 搜索算法
第三章 排序算法
第四章 字符串相关
第五章 数学相关
第六章 动态规划
第七章 数据结构
第八章 图论
第九章 计算几何
第十章 其他算法
Dotcpp在线编译      (登录可减少运行等待时间)