线性表思维导图

🐰

2023-05-13

浏览量: 55

线性表

计算机

专业知识

线性表

树图思维导图提供《线性表》在线思维导图免费制作，点击“编辑”按钮，可对《线性表》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：c835f27f198cc45d96c624380797139f

思维导图大纲

线性表的定义

线性表是具有相同数据类型的n个数据元素的有限虚列，其中n为表长，当n=0时称为空表

线性表的特点

有且仅有一个开始节点，它没有直接前驱

有且仅有一个终端节点，它没有直接后继

除了开始节点和终端节点外，其余节点都有且仅有一个直接前驱和一个直接后继

注意

线性表是一种逻辑结构，表示元素之间一对一的相邻关系

顺序表和链表是指存储结构

线性表的基本操作

InitList(L）：初始化表，构造一个空的线性表

GetLength（L）：求表长，返回线性表L的长度，即L中数据元素的个数

GetElem（L,i,x）：按位查找操作，在线性表L查找第i位上的数据元素，x是找到该元素返回的值

Locate（L，x）：按值查找操作，在线性表L中查找一个与给定x相等的数据元素，存在则返回元素所在位置的最小值或地址值；否则返回0或NULL值

InsElem（L,i,x）：插入操作，在线性表的第i个位置上插入一个值为x的新元素,其中1<=i<=GetLength（L）+1

DelElem（L,i,x）：删除操作，删除表L中第i个位置的元素并用x将其存储，其中1<=i<=GetLength（L）

线性表的顺序储存

顺序表

定义：用一组地址连续存储单位依次存储数据表的数据元素

特点

顺序表的逻辑顺序和物理顺序是一致的

顺序表中任意一个数据元素都可以随机存取

顺序表的类型定义

顺序表的基本运算的实现（p19）

顺序表的初始化：建立一个空表L，将L设为指针参数，将L的实际长度设为0

顺序表的建立：void CreateList（SeqList*L,int n）建立顺序表并输入多个元素函数

查找操作

按位置查找

int GetElem(SeqList*L,int i) 查找第i个位置的元素值

按值查找

int Locate(SeqList*L,DataType x)在顺序表L中定位元素x函数

插入操作

定义：在线性表的第i个位置上插入一个值为x的新元素，插入后表长增1

步骤

1.将ai~an之间的所有节点依次后移动，为新元素让出第i个位置

2.将新节点x插入到第i个位置

3,。修改表长

时间复杂度为O（n）

注意：检查顺序表是否已满；插入的有效范围是1<=i<=n+1,n是原来的表长

删除操作

定义：是指将第i个元素从顺序表中去掉，删除后顺序表表长减1

步骤

1.将要删除的元素值赋给指针x所指的变量

2.将ai+1~an之间的节点依次顺序向前移动

3.顺序表表长减1，删除成功，并返回

时间复杂度为O（n）

线性表的链式存储结构

单链表

定义：单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素

构成

数据域：data

指针域：next

单链表的基本操作实现（P27）

单链表的初始化：即构造一个包含头节点的空单链表，其过程是首先申请一个节点并让指针head指向该节点，然后将它的指针域赋为空（NULL），最后返回头指针head

单链表的建立

头插法

尾插法

求表长

查找

按值查找

按序号查找

插入

删除

循环链表

循环单链表

循环双链表

双向链表

定义：是链表的一种，双向链它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点

双链表的构成

前驱指针域：prior

数据域：data

后继指针域：next

栈

基本概念

先进后出，只能在一端插入和删除（线性表）

存储结构

顺序存储

top指针（int型）

栈空：S.top=-1

栈长：S.top+1

栈满：S.top==MaxSize-1

共享栈：两个top指针

当两个栈顶指针都栈顶元素时

栈空

top0=1

top1=Maxsize

栈满：top1-top0=1

入栈

top0++；赋值 0号栈入栈

top1--；赋值 1号栈入栈

特点

更有效地利用存储空间

获取数据的时间复杂度为O（1），不影响存储效率

链式存储

栈顶节点，栈低节点，next指针

特性分析

顺序栈

优点：简单，存储密度高

缺点：采用数组存储，不能动态地分配大小，可能发生上溢

链栈

优点：可以动态分配存储空间

缺点：存储密度较低

顺序表与链表的比较

基于空间的比较

顺序表的存储空间是一次性分配的，链表的存储空间是多次分配的。

存储密度的比较（存储密度=结点值域所占的存储量／结点结构所占的存储总量）顺序表的存储密度=1，链表的存储密度<1.

基于时间的比较

存取方式：顺序表可以随机存取，也可以顺序存取；链表只能顺序存储

插入／删除时移动元素的个数：顺序表平均需要移动近一半元素；链表不需要移动元素，只需要修改指针

线性表思维脑图思维导图

U560769240

3.01

树图思维导图提供《线性表思维脑图》在线思维导图免费制作，点击“编辑”按钮，可对《线性表思维脑图》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：f461a41c5b3eb00f8a549187674e8366

第二章线性表思维导图

U347986064

0.08

树图思维导图提供《第二章线性表》在线思维导图免费制作，点击“编辑”按钮，可对《第二章线性表》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：ea99a0a6a48dffc0ba5bfda78aa940cd

思维导图模板

资格考试

计算机

正文

相似思维导图模版

计算机等级考试知识点：密码学基本概念思维导图

计算机四级网络工程师知识点TCP/IP的分层思维导图

2022-11-13 13:43:20

思维导图模版推荐

首页

我的文件

我的团队

个人中心