网站建设 事业单位 安全网站开发语言
该系列属于计算机基础系列中的《数据结构基础》子系列，参考书《数据结构考研复习指导》(王道论坛 组编)，完整内容请阅读原书。
1.线性表的定义和基本操作
1.1 线性表的定义
- 线性表是具有相同数据类型的n(n≥0)n(n≥0)n(n≥0)个数据元素的有限序列，其中nnn为表长，当n=0n=0n=0时，线性表为一个空表；
- 若用LLL命名线性表，则一般表示为：L(a1,a2,⋯,ai,ai+1,⋯,an)L(a_1,a_2,\cdots,a_i,a_{i+1},\cdots,a_n)L(a1,a2,⋯,ai,ai+1,⋯,an)；其中：a1a_1a1是唯一的"第一个"数据元素，称为表头元素，ana_nan是唯一的"最后一个"数据元素，称为表尾元素；
- 除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继；
- 线性表的特点：
- 表中元素的个数有限；
- 表中元素具有逻辑上的顺序性，表中元素有其先后次序；
- 表中元素都是数据元素，每个元素都是单个元素；
- 表中元素的数据类型都相同，即每个元素占有相同大小的存储空间；
- 表中元素具有抽象性，即仅讨论元素间的逻辑关系，不考虑元素究竟表示什么内容；
- 注：线性表是一种逻辑结构，表示元素间一对一的相邻关系；顺序表和链表是指存储结构；
1.2 线性表基本操作
线性表的主要操作：
- InitList(&L){\rm InitList(\&L)}InitList(&L)：初始化表，构造一个空的线性表；
- Length(L){\rm Length(L)}Length(L)：求表长，返回线性表LLL的长度，即LLL中数据元素的个数；
- LocateElem(L,e){\rm LocateElem(L,e)}LocateElem(L,e)：按值查找操作，在表LLL中查找具有给定关键字值的元素；
- GetElem(L,i){\rm GetElem(L,i)}GetElem(L,i)：按位查找操作，获取表LLL中第iii个位置的元素的值；
- ListInsert(&L,i,e){\rm ListInsert(\&L,i,e)}ListInsert(&L,i,e)：插入操作，在表LLL中的第iii个位置上插入指定元素eee；
- ListDelete(&L,i,&e){\rm ListDelete(\&L,i,\&e)}ListDelete(&L,i,&e)：删除操作，删除表LLL中第iii个位置的元素，并用eee返回删除元素的值；
- PrintList(L){\rm PrintList(L)}PrintList(L)：输出操作，按前后顺序输出线性表LLL的所有元素值；
- Empty(L){\rm Empty(L)}Empty(L)：判空操作，若LLL为空表，则返回true{\rm true}true，否则返回false{\rm false}false；
- DestroyList(&L){\rm DestroyList(\&L)}DestroyList(&L)：销毁操作，销毁线性表，并释放线性表LLL所占用的内存空间；
1.3 线性表定义习题
- 线性表是具有nnn个( )的有限序列；
- 数据表；
- 字符；
- 数据元素；
- 数据项；
- 以下( )是一个线性表；
- 由nnn个实数组合的集合；
- 由100100100个字符组成的序列；
- 所有整数组成的序列；
- 邻接表；
- 在线性表中，除开始元素外，每个元素( )。
- 只有唯一的前驱元素；
- 只有唯一的后继元素；
- 有多个前驱元素；
- 有多个后继元素；