1、线性表的基本操作
A.线性表思维导图
B.线性表相关定义
线性表：线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列。一种典型的线性结构。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继。
一维数组可以静态分配，也可以是动态分配。
线性结构特点：在数据元素的非空有限集中
1）存在唯一的一个被称作“第一个”的数据元素
2）存在唯一的一个被称作“最后一个”的数据元素
3）除第一个外，集合中的每个数据元素均只有一个前驱
4）除最后一个外，集合中的每个数据元素均只有一个后继
静态分配：数组的大小和空间事先已固定，一旦空间占满，再加入新的数据将产生溢出，会导致程序崩溃。
动态分配：存储数据的空间是在程序执行过程中通过动态存储分配语句分配，一旦空间占满，可以另外开辟一块更大的存储空间，用来替换原来的存储空间。
线性表的特点：
- 表中元素的个数有限
- 表中元素具有相同逻辑上的顺序性，在序列中各元素有先后次序
- 表中元素都是数据元素，每一个元素都是单个元素
- 表中元素的数据类型相同。这意味着每一个元素占有相同大小的存储空间
- 表中元素具有抽象性。即仅讨论元素间的逻辑关系，不考虑元素究竟表示什么内容。
线性表：线性表是一种典型的线性结构。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继。
线性表（Linear List）：是由n(n>=0)个数据元素（结点）a1，a2…an组成的有限序列。该序列中的所有结点具有相同的数据类型。其中数据元素的个数n称为线性表的长度。
当n=0时，称为空表。
当n>0时，将非空的线性表记作：（a1,a2,…an）
a1称为线性表的第一个（首）结点，an称为线性表的最后一个（尾）结点。
C.线性表的抽象数据类型的定义
1、基本操作
ADT List{
数据对象：D={ai|ai∈Elemset,i=1,2,…,n,n≥0}
数据关系：R1={
基本操作：
InitList(&l)
操作结果：构造一个空的线性表L
DestroyList(&l)
初始条件：线性表已存在
操作结果：销毁线性表L
ClearList(&l)
初始条件：线性表已存在
操作结果：置线性表L为空表
ListEmpty(L)
初始条件：线性表已存在
操作结果：若线性表L为空表，则返回TRUE，否则返回FALSE
ListLenght(L)
初始条件：线性表已存在
操作结果：返回线性表L数据元素个数
GetElem(L,i,&e)
初始条件：线性表已存在（1≤i≤ListLenght(L)）
操作结果：用e返回线性表L中第i个数据元素的值
locatElem(L,e,comare())
初始条件：线性表已存在,comare()是数据元素判定函数
操作结果：返回线性表L中第1个与e满足关系comare()的数据元素的位序
PriorElem(L,cur_e,&pre_e)
初始条件：线性表已存在
操作结果：若cur_e是线性表L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义
NextElem(L,cur_e,&)
初始条件：线性表已存在
操作结果：若cur_e是线性表L的数据元素，且不是第最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义
ListInsert(&L,i,e)
初始条件：线性表已存在（1≤i≤ListLenght(L)+1）
操作结果：在线性表L中第i个数据元素之前插入新元素e，L长度加1
ListDelete(&L,i,&e)
初始条件：线性表已存在（1≤i≤ListLenght(L)）
操作结果：删除线性表L中第i个数据元素，用e返回其值，L长度减1
ListTraverse(L,visit())
初始条件：线性表已存在
操作结果：依次对线性表L的每个数据元素调用visit()函数，一旦visit()失败，则操作失败
}ADT List
2、更复杂的操作
两个或两个以上线性表合并成一个线性表
一个线性表拆分成两个或两个以上的线性表
重新复制一个线性表
对线性表中的元素按某种顺序重新排序
2、线性表的顺序表示
线性表的顺序存储又称为顺序表，它是用一组地址连续的存储单元，依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。
特点：表中元素的逻辑顺序与其物理顺序相同。
顺序表最主要的特点是随机访问，即通过首地址和元素序号可以在O(1)的时间内找到指定的元素。顺序表的存储密度高，每个结点只存储数据元素。
3、线性表的链式表示
链表是动态分配存储空间的链式存储结构。
线性表的链式存储又称为单链表。它是指通过一组任意的存储单元来存储线性表中的数据元素。通过指针来建立各数据元素之间的线性关系。
特点：表中元素散列的分布在存储空间中。
若有收获，就点个赞吧
0 人点赞
