🙊🙊作者主页：🔗求不脱发的博客
📔📔 精选专栏：🔗数据结构与算法
📋📋 精彩摘要：线性表、栈、队列、串和数组都属于线性结构。线性结构的基本特点是除第一个元素无直接前驱，最后一个元素无直接后继之外，每个元素都有一个前驱和后继。线性表示最基本切最常用的一种线性结构，同时也是其他数据结构的基础，尤其单链表，是贯穿整个数据结构的基本技术。
💞💞觉得文章还不错的话欢迎大家点赞👍➕收藏⭐️➕评论💬支持博主🤞
📚目录
📖【数据结构与算法】第二章：线性表
📝1️⃣初始线性表
✨线性结构
定义：若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前驱和一个直接后继。
可表示为：(a1 , a2, a3, ...,an)。
特点：
- 只有一个首结点和尾结点
- 除首尾结点外，其他结点只有一个直接前驱和一个直接后继。
简言之，线性结构反映结点间的逻辑关系是一对一的，线性结构包括线性表、堆栈、队列、字符串、数组等等。其中，最典型、最常用的是线性表。
✨线性表
在日常生活中，线性表的例子比比皆是。例如26个英文字母的字母表，(A, B, C, ..., Z) 就是一个线性表，表中的数据元素是单个字母。在稍微复杂的线性表中，一个数据元素可以包含若干个数据项。
形如字母表，他们的数据元素虽然不同，但同一线性表中的元素，必定具有相同的特性，即属于同一数据对象，相邻数据元素之间存在着序偶关系。
定义：由n(n>=0)个数据特性相同的元素构成的优先序列。
编辑
特点：
- 存在唯一的一个被称作“第一个”的数据元素
- 存在唯一的一个被称作“最后一个”的数据元素
- 除第一个之外，结构中的每个数据元素均只有一个前驱
- 除最后一个之外，结构中的每个数据元素均只有一个后继
重要基本操作：
编辑
📝2️⃣线性表的顺序表示和实现
线性表的顺序表示又称为顺序存储结构或顺序映像。
✨顺序存储
编辑
定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。简言之，逻辑上相邻，物理上也相邻。
存储方法：用一组地址连续的存储单元一次存储线性表的元素，可通过数组V [n] 来实现。
特点：
- 利用数据元素的存储位置标示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构一致。
- 在访问线性表时，可以快速的计算出任何一个数据元素的存储地址，因此可以粗略地认为，访问每个元素所花时间相等。‘
- 存储密度大（结点本身所占存储量 / 结点结构所占存储量）
- 可以随机存取表中任一元素
这种存取元素的方法被称为随机存取法。
缺点：
- 在插入、删除某一元素时，需要移动大量元素。
- 浪费存储空间
- 属于静态存储形式，数据元素的个数不能自由扩充。
类型定义：
#define MAXSIZE 100 //最大长度 typedef struct { ELemType *elem; //指向数据元素的基本地址 int length; //线性表的当前长度 }SqList;
例如：图书表的顺序存储结构类型定义：
#define MAXSIZE 10000 //图书表可能达到的最大长度 typedef struct //图书信息定义 { char no[20]; //图书ISBN char name[50]; //图书名字 float price; //图书价格 }Book; typedef struct //图书信息定义 { Book *elem; //存储空间的基地址 int length //图书表中当前图书个数 }SqList; //图书表的顺序存储结构类型为 SqList
✨初始化线性表（引用参数类型）
Status InitList_Sq(SqList &L) //构造一个空的顺序表L { L.elem = new ElemType[MAXSIZE]; //为顺序表分配空间 if(!L.elem) exit(OVERFLOW); //存储分配失败 L.length = 0; //空表长度为 0 return OK; }
✨初始化线性表（参数用指针）
Status InitList_Sq(SqList *L) //构造一个空的顺序表L { L-> elem = new ElemType[MAXSIZE]; //为顺序表分配空间 if(!L->elem) exit(OVERFLOW); //存储分配失败 L->length = 0; //空表长度为 0 return OK; }
✨几个简单基本操作的算法实现
销毁线性表
void DestroyList(SqList &L) { if(L.elem) delete[]L.elem; //释放存储空间 }
清空线性表
void ClearList(SqList &L) { L.length=0; //将线性表的长度置为0 }
求线性表的长度
int GetLength(SqlList L) { return (L.length); }
判断线性表是否为空
int IsEmpty(SqList L) { if(L.length == 0) return 1; else return 0; }
获取线性表中某个元素的内容
int GetElem(SqList L,int i,ELemType &e) { if(i < 1 || i > L.length) return ERROR; //判断i是否合理，如果不合理，则返回ERROR e=L.elem[i - 1]; //第i - 1 的单元存储这第 i 个数据 return OK; }
顺序查找（根据指定数据获取数据所在的位置）
int LocateElem(SqList, ElemType e) { for(int i = 0; i < L.length; i++) if(L.elem[i] == e) return i+1; return 0; }
📝3️⃣顺序线性表的插入（插在第i个结点之前）
✨算法步骤
- 判断插入位置i是否合法
- 判断顺序表的存储空间是否已满
- 将第n到第i位的元素依次向后移动一个位置，空出第i个位置。
- 将要插入的新元素e放入第i个位置
- 表长+1，插入成功返回OK
✨算法描述
在线性表中第i个数据元素之前插入数据元素e
Status ListInsert_Sq(SqList &L, int i,ElemType e) { if(i < 1 || i> L.length+1) return ERROR; //i值不合法 if(L.length == MAXSIZE) return ERROR; //存储空间已满 for(j =L.length -1 ; j >=i-1;j--) L.elem[j+1] = L.elem[j]; //插入位置之后的元素后移 L.elem[i] = e; //将新元素e放入第i个位置 ++L.length; //表长+1 return OK; }
✨算法分析
算法时间只要耗费在移动元素的操作上。
如果插入在尾结点之后，则无需移动（速度较快）
如果元素全部后移（速度较慢）
如果考虑在各种位置插入（n + 1种可能）的平均移动次数则
编辑
最终可得AMN = n/2
📝4️⃣顺序线性表的删除（删除第i个结点）
✨算法步骤
- 判断删除位置i是否合法（合法值为 1 <= i <= n）
- 将于删除的元素保留在e中
- 将第 i+1 至 第 n 位的元素依次向前移动有一个位置
- 表长-1，删除成功返回OK
✨算法描述
将线性表中第i个数据元素删除
Status ListDelete_Sq(SqList & L,int i) { if(i < 1 || i > L.length) return ERROR; //i值不合法 for( j = i; j < L.length ; j ++) L.elem[j - 1] = L.elem[j]; //将被删除元素之后的元素前移一位 --L.length; //表长-1 return OK; }
✨算法分析
算法时间主要耗费在移动元素的操作上
若删除尾结点，则无需移动（速度较快）
若删除首结点，则表中n-1个元素全部前移（速度较慢）
若考虑在各种位置（n中可能）删除的平均移动次数
编辑
最终计算得 AMN = （n-1）/ 2。
查找、插入。删除算法的平均时间复杂度为：T(n) = O(n)，空间复杂度 S(n) = O(1)。并没有占用辅助空间。
