博客

线性表定义

0个或多个数据元素的有限序列

理解：相同类型的元素之间是有顺序的，第一个元素只有一个后继结点，没有前驱结点，最后一个元素只有一个前驱结点，没有后继结点，其他元素各有一个前驱结点和后继结点

抽象数据类型

ADT 线性表（List）
Data
	数据元素之间满足线性表的定义
Operation
	InitList(*L)            // 初始化操作，建立一个空的线性表
	ListEmpty(L)            // 若线性表为空，返回true，否则返回false
  ListLength(L)           // 返回线性表L的元素个数
	ClearList(*L)           // 将线性表清空
	GetElem(L, i, *e)       // 将线性表L中的第i个元素值返回给e
	LocateElem(L, e)        // 在线性表L中查找与给定值e相等的元素，如果成功，返回该元素在表中的序号，否则返回0
	ListInsert(*L, i ,e)    // 在线性表L中第i个位置插入新元素e
	ListDelete(*L, i, e)    // 删除线性表L中第i个位置元素，并用e返回其值
endADT

存储结构

从存储结构上分，线性表的实现可以分成两种：

• 顺序存储结构：数组
• 链式存储结构：单链表、双向链表、循环链表

动态数组(Deque)

C/C++中只提供的静态数组（不考虑STL），静态数组的优点是随机访问