数据结构-线性结构_思维导图模板_知犀官网

数据结构-线性结构

作者：热爱生活的咸鱼宋

0浏览2022-09-29 15:37:56

下载

使用模板已被用16次

线性结构

一、线性表：具有相同数据类型的有限序列

顺序存储（顺序表）：逻辑上相邻的两个元素在物理位置上也相邻

链式存储（链表）：不要求逻辑上相邻的两个元素在物理位置上也相邻

单链表

双链表

循环链表

循环单链表

循环双链表

静态链表：借助数组描述线性表的存储结构，节点有数据域data和指针域next（游标，指节点的相对地址），静态链表也要预先分配一块连续的内存空间

二、操作受限的线性表：只允许在一端进行插入或删除操作的线性表

栈：后进先出（LIFO）

顺序栈：设一个指针（top）指向当前栈顶元素位置

操作实现

栈顶指针：栈顶指针初始时设置S.top=-1；栈顶元素：S.data[S.top]

进栈操作：栈不满时，栈顶指针先加1，再送值到栈顶元素（ S.data[++S.top] = x ）

出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针减1（ x = S.data[S.top--] ）

栈空条件：S.top== -1；栈满：S.top==MaxSize-1；栈长：S.top+1

共享栈：为了更有效地利用存储空间，让两个顺序栈共享一个一维数组

链栈：通常采用单链表，并规定所有操作都在表头进行，一般规定链栈没有头结点，Lhead指向栈顶元素

队列：先进先出（FIFO）

队列的顺序存储

顺序队列：附设头指针front指向队头元素，rear指向队尾元素的下一个元素

初始化：Q.front=Q.rear=0

入队：队不满时，先送值到队尾元素，再将队尾指针加1

出队：队不满时，先取队头元素值，再将队头指针加1

缺点：会出现“假溢出”

循环队列：

初始化：Q.front=Q.rear=0

入队：队不满时，让队尾指针加1取模 Q.rear=(Q.rear+1)%MaxSize

出队：队不满时，再让队头指针加1取模 Q.front=(Q.front+1)%MaxSize

队空：Q.front=Q.rear

队满

①牺牲一个单元区分对空和队满，队满条件：（Q.rear+1）%MaxSize==Q.front

②类型中增设表示元素个数的数据成员size。队空：Q.size==0;队满：Q.size==MaxSize

③类型中增设tag数据成员。对空：tag=0；队满：tag=1

队列的链式存储

链队：同时带有队头指针和队尾指针的单链表

队空：Q.front==NULL且Q.rear==NULL

入队出队同单链表

适用场合：数据元素变动比较大，且不存在队列满且产生溢出的问题。如要适用多个队列，多个栈的情形

双端队列：两端都可以进行入队和出队操作的队列

输出受限：允许再一端进行插入和删除，在另一端只允许插入

输入受限：允许再一端进行插入和删除，在另一端只允许删除

查看详情

模板简介

数据结构线性结构的简单整理

数据结构考研

猜你喜欢

相关文章

八下历史思维导图-第五单元内容整理2022-07-20 七下历史思维导图-唐朝的兴盛思维导图2022-07-19 小数的初步认识思维导图-三年级下册数学脑图整理2022-07-18 八年级生物上册第一章思维导图：动物的主要类群2021-08-29 八年级生物上册第六单元思维导图：生物的多样性及其保护2021-08-28 八年级生物上册第五单元思维导图：生物圈中的其他生物2021-08-28 小学六年级上册数学思维导图：百分数2021-08-26 小学六年级上册数学思维导图：圆2021-08-25 小学六年级上册数学思维导图：比2021-08-24 小学六年级上册数学思维导图：分数乘法2021-08-23 小学六年级上册数学思维导图-全书2021-08-22 九年级上册政治思维导图：中国梦-初三知识点脑图整理2021-08-21 七年级上册地理思维导图：地球和地球仪2021-08-20 高中历史必修一思维导图：现代中国的政治建设与祖国统一2021-08-19 高中历史必修三思维导图：中国近代前期思想变化2021-08-18 高中历史必修二思维导图：中国近代前期政治2021-08-17

您的想法与建议，对知犀思维导图的优化改进非常有用！欢迎反馈！