​

一，线性表的定义及其实现

1.线性表及顺序结构 

管理一个有序的线性序列，归结为线性表问题

线性表（Linear List）:由同类型数据元素构成有序序列的线性结构

表中元素个数被称为线性表的长度线性表没有元素时被称为空表表起始位置称为表头，结束位置为表尾

2.线性表的抽象数据类型描述

类型名称：线性表

数据对象集：线性表是n个元素构成的有序序列

操作集：线性表L -> List，整数i表示位置，元素X -> ElementType

List MakeEmpty(): 初始化一个空线性表L;ElementType FindKth( int K, List L): 根据位序K，返回相应元素 ;int Find( ElementType X,List L): 在线性表L中查找X的第一次出现位置;void Insert( ElementType X, int i, List L): 在位序i前插入一个新元素X;void Delete(int i, List L): 删除指定位序i的元素;int Length( List L): 返回线性表L的长度n。

3.线性表的顺序存储实现

​编辑

数组 

 访问下标为i的元素：L.Data[i]  |  pL->Data[i]

线性表的长度：L.Last+1  |  pL->Last+1

链表

4.主要操作的实现

(1)数组

利用数组的连续存储空间顺序存放线性表的各元素

​编辑

1）初始化（建立空的顺序表）

2）查找

3）插入（第i（1<=i<=n+1）个位置上插入一个值为X的新元素）

​编辑

4）删除（删除表的第i（1<=i<=n）个位置上的元素）

​编辑

（2）链表

不要求逻辑上相邻的两个元素物理上也相邻；通过“链”建立起数据元素之间的逻辑关系。

插入，删除不需要移动数据元素，只需要修改“链”。

​编辑

 1） 求表长

2）查找

按序号查找：

按值查找：

3）插入（第i（1<=i<=n+1）个位置上插入一个值为X的新元素）

（1）先构造一个新结点，用s指向；

（2）再找到链表的第i-1个结点，用p指向；

（3）然后修改指针，插入结点（p之后插入新结点是s）

​编辑

                             s->Next=p->Next;  p->Next=s;

4）删除（删除表的第i（1<=i<=n）个位置上的元素）

（1）先找到链表的第i-1个结点，用p指向；

（2）再用s指针指向被删除的结点（p的下一个结点）

（3）然后修改指针，删除s所指结点

（4）最后释放s所指结点的空间

​编辑

​