线性表的相关概念数据结构与算法

线性表

一、线性表的定义和基本操作
- 1.线性表的定义
- 注意：
- 2.线性表的基本操作：
二、线性表的顺序表示
- 1.顺序表的定义：
- 注意：
- 2.顺序表上基本操作的实现
- - ①插入操作
  - ②删除操作
  - ③按值查找
三、线性表的链式表示
- 1.单链表
- 2.双链表的定义
- 3.循环链表
- 4.静态链表

一、线性表的定义和基本操作 1.线性表的定义线性表是具有相同数据类型的n(n≥0)个数据元素的有限序列，其中n为表长，当n=0时，该线性表是一个空表。若用L命名线性表，则其一般表示为
L=(a1，a2，a3，.……，an)
式中，a1是唯一的“第一个”数据元素，又称表头元素；an是唯一的“最后一个”数据元素，又称表尾元素。得出线性表的特点如下：
表中元素的个数有限。
表中元素具有逻辑上的顺序性，在序列中各元素排序有其先后顺序。
表中元素都是数据元素，每个元素都是单个元素。
表中元素数据类型都相同，这意味着每个元素占有相同大小的存储空间。
表中元素具有抽象性，即只讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。
注意：线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构，两者属于不同层次的概念，因此不要将其混淆。
2.线性表的基本操作：

InitList(&L):初始化表。构造一个空的线性表Length(L):求表长。返回线性表L 的长度，即L中数据元素的个数LocateElem(L.e):按值查找操作。在表L中查找具有给定关键字值的元素GetElem(L,i):按位查找操作。获取表L中第i个位置上的元素的值ListInsert(&L,i,e):插入操作。在表L中第i个位置上插入指定元素eListDelete(&L,i,&e):删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值PrintList(L):输出操作。按前后顺序输出线性表的所有元素值Empty(L):判空操作。若L为空表，则返回true，否则返回falseDestroyList(&L):销毁操作。销毁线性表一并释放线性表L所占用的内存空间

二、线性表的顺序表示 1.顺序表的定义：线性表的顺序表示又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。第1个元素存储在线性表的起始位置，第i个元素的存储位置后面紧接着第i+1个元素。因此线性表最大的特点是表中元素的逻辑顺序与其物理顺序相同。
假定线性表的元素类型为ElemType，则线性表的顺序存储结构类型描述为

#define MaxSize 50 typedef struct{ ElemType data[MaxSize]; int length; }SqList

顺序表最主要的特点是随机访问，即通过首地址和元素序号可在时间O(1)内找到指定的元素。
顺序表的存储密度告，每个结点只存储数据元素。
顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。
注意：线性表中元素的位序是从1开始的，而数组中元素的下标是从0开始的。
2.顺序表上基本操作的实现 ①插入操作
在顺序表的第p个位置插入新元素e。若i的输入不合法，则返回false，表示插入失败；否则将顺序表的第p个元素以及其后的所有元素右移一个位置，腾出一个空位置插入新元素e，顺序表长度增加1，插入成功，返回true。

bool insertElem(Sqlist &L, int p, int e) { if (p < 0 || p > L.length || L.length == maxSize) { return false; } for (int i = L.length-1; i >= p; i--) { L.data[i+1] = L.data[i]; } L.data[p] = e; ++(L.length); return true; }

最好情况：在表尾插入，元素后移语句将不执行，时间复杂度为O(1)；
最坏情况：在表头插入，元素后移语句执行n次，时间复杂度为O(n)；
平均情况：在第i个结点插入的概率p为1/(n+1)，从1到n+1元素后移语句的执行次数为(n-i+1)，等差数列求和得n(n+1)/2，乘以概率p得n/2，因此线性表插入算法的平均时间复杂度为O(n)。
②删除操作
【线性表的相关概念】删除顺序表中第p个位置的元素，若成功返回true，并将被删除的元素用引用变量e返回，否则返回false。

bool deleteElem(Sqlist &L, int p, int &e) { if (p < 0 || p >= L.length) { return false; } e = L.data[p]; for (int i = p; i < L.length-1; i++) { L.data[i] = L.data[i+1]; } --(L.length); return true; }

最好情况：删除表尾元素，无需移动元素，时间复杂度为O(1)；
最坏情况：删除表头元素，需移动除第一个元素外的所有元素，时间复杂度为O(n)；
平均情况：删除第i个结点的概率p为1/n，从1到n元素删除后的移动语句的执行次数为(n-i)，等差数列求和得n(n-1)/2，乘以概率p得(n-1)/2，因此线性表删除算法的平均时间复杂度为O(n)。
③按值查找
在顺序表中查找第一个元素值等于e的元素，并返回其位序。

int findElem(Sqlist L, int e) { for (int i = 0; i < L.length; i++) { if (L.data[i] == e) { return i+1; } } return -1; }

最好情况：查找的元素在表头，仅需比较一次，时间复杂度为O(1)；
最坏情况：查找的元素在表尾或不存在时，需比较n次，时间复杂度为O(n)；
平均情况：查找的元素在第i个结点的概率p为1/n，从1到n元素比较次数为i，等差数列求和得n(n+1)/2，乘以概率p得(n+1)/2，因此线性表按值查找算法的平均时间复杂度为O(n)。
三、线性表的链式表示 1.单链表线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的链式存储。链式存储线性表时，不需要使用地址连续的存储单元，即它不要求逻辑上相邻的两个元素在物理位置上也相邻，它通过“链”建立起数据元素之间的逻辑关系，因此对线性表的插入，删除不需要移动元素，只需要修改指针。
2.双链表的定义双链表结点中有两个指针prior和next，分别指向其前驱结点和后继结点。
3.循环链表循环单链表表中的最后一个结点的next指针不是null，而是指向头结点，从而形成一个闭环。
循环双链表表中的头结点的prior指针指向尾结点，尾结点的next指针指向头结点，
4.静态链表