文章目录

• ​​数据结构三要素/逻辑结构和物理存储结构/线性表与顺序表链表/队列与循环队列​​

• ​​数据结构的内容(三要素)（outline)​​

• ​​关联​​

• ​​逻辑结构​​

• ​​逻辑结构小结​​

• ​​物理结构(存储结构)​​
• ​​线性表​​
• ​​循环队列的长度​​

• ​​循环队列满判断​​

数据结构三要素/逻辑结构和物理存储结构/线性表与顺序表链表/队列与循环队列

数据结构的内容(三要素)（outline)

• 逻辑结构
• 存储结构
• 数据运算

关联

• 数据的逻辑结构和存储结构密不可分

• 另外,逻辑结构独立于存储结构;而存储结构建立在逻辑结构上思考
• 对于一种数据存储结构而言，必定有包括它的逻辑结构，
• 某一种逻辑结构在计算机语言中映射其存储结构
• 相比于某一种逻辑结构和某一种数据结构,存储结构关乎代码结构,是更具体的

• 在计算机语言编写代码上就可以看出
• 给定一种数据结构

• 算法的设计取决于逻辑结构的选定
• 算法的实现取决于物理结构的采用

逻辑结构

• 指数据元素之间的逻辑关系,从逻辑关系上描述数据
• 它于数据的存储结构无关,是独立于计算机的
• 逻辑结构分为

• 线性结构(三大类)

• 一般线性表

• 它的实现方式(存储方式)可以是

• 顺序存储,此时称为​

  ​顺序表​

  ​(存储结构上顺序表的方式是基于一片连续的物理地址)
• 链式存储,此时称为​

  ​链表​

  ​(存储结构上链表并不连续)

• 但是,实现​

  ​链表​

  ​的存储结构可以是顺序存储结构
• 不仅仅是链式存储才能实现链表(只是说,线性表的链式存储实现的一定是链表)
• (比如静态链表,基于数据组实现链表)

• (操作)受限线性表

• stack
• queue
• string

• 线性表的推广

• array

• 线性结构经常可以由顺序存储结构实现，也可以由链式存储实现

• 非线性结构

• 集合
• 树形结构

• 一般树
• 二叉树

• 图状结构

• 有向图
• 无向图

逻辑结构小结

• 通过上面的分析可以知道,下面这些都还是属于逻辑结构的范畴:

• 线性结构

• 线性表

• 栈
• 队列

• ⛔注意,如果一个"名字"可以体现出存储结构,那么一般就认为他是具体的数据结构(默认包含了数据运算)

• 顺序表:线性表的顺序存储
• 单链表:线性表的链式存储
• 哈希表:非线性结构的散列存储
• 循环队列:线性结构逻辑结构(队列)的顺序存储

• 非线性结构

• 集合
• 树

• 二叉树
• 一般树

• 图

• 有向图
• 无线图

物理结构(存储结构)

• 数据结构在计算机中的表示
• 包括一下方面:

• 数据元素的表示
• 关系表示（存储数据是，通常不仅仅存储各数据元素的值，还要存储数据元素之间的关系）

• 比如前驱、后继

• 用计算机语言实现的逻辑结构(依赖于计算机语言)

• 具体的存储结构主要有:

• 顺序存储

• 顺序存储也可以用来实现线性结构和非线性结构(比如:树/图)

• 链式存储

• 注意，链式存储设计的时候，各个不同结点的存储空间可以不连续
• 但是结点内的存储单元地址必须连续

• 索引
• 散列

线性表

• 栈,队列,循环队列这几种数据结构都属于线性表(逻辑结构)的范畴

• 它们既可以通过顺序存储来实现也可以通过链式存储来实现

• 以队列为例

• 队列的顺序存储实现的可以称为顺序队列

#define MaxSize 50
typedef struct{
    ElemType data[MaxSize];
    int front,rear;
}SequentialQueue      

• 顺序存储的队列基本缺点在于空间分配上不容易把握,(比如容易发生溢出或者空间利用率低下)
• 因此,基于顺序存储结构的这一缺点,改进出来​

  ​循环队列​

  ​(任然基于顺序存储结构)实现的

• 循环队列可以一定程度提高空间利用率以及降低溢出的发生
• 但是在链式存储中,​

  ​循环队列​

  ​就显得多余,应为链式存储的灵活性,基本不用考虑溢出问题
• 而且对于操作受限的线性表而言,基本操作只允许在端(队列是两端,栈只有一端)操作,没有随机访问栈内或者队列内的某个元素的需求,链式存储往往更加合适用来实现这类逻辑结构

• 队列的链式存储实现可以称为链队列

typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;
typedef struct{
    LinkNode *front,*rear;
}LinkQueue;      

循环队列的长度

• 我们设循环队列的长度(队列中存在的元素数量(实际有效长度))
• 为了方便计算,我们为循环队列打了两重下标,第二重开始的下标是虚拟的

• 第二重下标是第一重下标加上MaxSize后得到的(本例中MaxSize=8)

• 并且,队列头指针F总是沿着顺时针的方向追赶队尾指针R
• 我们允许R取得第二重下标,而F只允许取第一重下标中的值

• 这样,队列的元素数量(实际长度)就可以表示为:

• 而实际上,我们知道队列的元素长度是不会超过;
• 恰好地,我们有一种运算(取模运算),

• 为了同一表达式,我们限制R的值只可以在第二重下标中取得,并把此时的值记为()

循环队列满判断

• 判断队列满的方案有多种

• 牺牲掉一个位置来判断​

  ​队满​

  ​

• 具体的判空条件为​

  ​(Q.rear+1)%MaxSize==Q.front​

  ​

• 之所以这里要用,
• 这种情况下,这超过了数组下标的范围
• 不可能超过数组的下标范围,这样及时满足队满条件,也无法做出正确判断!

• 在队列的数据类型中设置​

  ​size​

  ​成员来表示队列元素个数
• 或者设置​

  ​tag​

  ​​成员来区分​

  ​Q.front==Q.rear​

  ​是队满还是队空