线性表思维导图
线性表
树图思维导图提供 线性表 在线思维导图免费制作，点击“编辑”按钮，可对 线性表 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：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.
基于时间的比较
存取方式：顺序表可以随机存取，也可以顺序存取；链表只能顺序存储
插入／删除时移动元素的个数 ：顺序表平均需要移动近一半元素；链表不需要移动元素，只需要修改指针
沪公网安备 31011502019485号
上海工商