一、什么是线性表
线性表（Linear List）是由同类型数据元素构成 有序序列 的 线性结构。表中元素个数称为线性表的 长度，线性表没有元素时，称为 空表。表起始位置称为 表头，表结束位置称为 表尾。
线性表的抽象数据类型描述：
- 类型名称：线性表（List）
- 数据对象集：线性表是 n ( ≥ 0 ) 个元素构成有序序列（a1,a2,...,an）
- 操作集：线性表 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
二、线性表的顺序存储实现
我们可以利用数组的连续存储空间顺序存放线性表的各元素。
struct LNode
{
ElementType Data[MAXSIZE];
int Last;
};
typedef struct LNde * List;
struct LNode L;
List PtrL;
- 访问下标为 i 的元素：
L.Data[i]或PtrL->Data[i] - 线性表的长度：
L.Last+1或PtrlL->Last+1
主要操作的实现：
【1】、初始化（建立空的顺序表）
List MakeEmpty()
{
List PtrL;
PtrL = (List)malloc(sizeof(struct LNode));
PtrL->Last = -1;
return PtrL;
}
【2】、查找
int Find(ElementType X,List PtrL)
{
int i = 0;
while(i <= PtrL->Last && PtrL->Data[i] != X)
{
i++;
}
if (i > PtrL->Last){
return -1; // 如果没有找到，返回-1
}
else
{
return i; // 找到后返回的是存储位置
}
}
查找成功的平均比较次数为 (n+1)/2，平均时间性能为 O(n)；
【3】、插入（第 i （1 ≤ i ≤ n+1）个位置插入一个值为X的新元素）
void Insert(ElementType X,int i,List PtrL)
{
int j;
if (PtrL->Last == MAXSIZE-1) // 表已经满了，不能插入
{
printf("表已经满了，无法插入新的元素\n");
return ;
}
if (i < 1 || i > PtrL->Last+2) // 检查插入位置的合法性
{
printf("插入的位置不合法\n");
return;
}
for(j = PtrL->Last; j >= i-1; j--)
{
PtrL->Data[j+1] = PtrL->Data[j]; // 将a[i]~a[n]倒序向后移动
}
PtrL->Data[i-1] = X; // 新元素插入
PtrL->Last++; // Last仍指向最后元素
}
平均移动次数为 n/2，平均时间性能为 O(n)；
【4】、删除（删除表的第 i（1 ≤ i ≤ n）个位置上的元素）
void Delete(int i,List PtrL)
{
int j;
if (i < 1 || i >PtrL->Last+1) // 检查空表及删除位置的合法性
{
printf("不存在第 %d 个元素\n",i);
return;
}
for (j = i; j <= PtrL->Last; j++)
{
PtrL->Data[j-1] = PtrL->Data[j]; // 将a[i+1]~a[n]顺序向前移动
}
PtrL->Last--; // Last仍指向最后元素
}
平均移动次数为 (n-1)/2，平均时间性能为 O(n)；
三、线性表的链式存储实现
线性表的链式存储不要求逻辑上相邻的两个元素物理上也相邻；我们可以通过“链”建立起数据元素之间的逻辑关系。此时，插入、删除元素不需要移动数据元素，只需要修改“链”就可以了。
struct LNode
{
ElementType Data;
List Next;
};
typedef struct LNode *List;
struct LNode L;
List PtrL;
主要操作的实现：
【1】、求表长
int Length(List PtrL)
{
List p = PtrL; // p指向表的第一个结点
int j = 0;
while(p)
{
p = p->Next;
j++; // 当前p指向的第j个结点
}
return j;
}
时间性能为 O(n)
【2】、查找
①、按序号查找：FindKth
List FindKth(int K,List PtrL)
{
List p = PtrL;
int i = 1;
while(p != NULL && i < K)
{
p = p->Next;
i++;
}
if(i == K)
{
return p; // 找到第K个，返回指针
}
else{
return NULL; // 否则返回空
}
}
②、按值查找：Find
List Find(ElementType X,List PtrL)
{
List p = PtrL;
while(p != NULL && p->Data != X)
{
p = p->Next;
}
return p;
}
平均时间性能为 O(n)
【3】、插入（在第 i-1（1 ≤ i ≤ n+1）个结点后插入一个值为 X 的新结点）
- 先构造一个新结点，用 s 指向；
- 再找到链表的第 i-1 个结点，用 p 指向；
- 然后修改指针，插入结点（p 之后插入新节点是 s）
List Insert(ElementType X,int i,List PtrL)
{
List p,s;
if(i == 1) // 新节点插入在表头
{
s = (List)malloc(sizeof(struct LNode)); // 申请、填装结点
s->Data = X;
s->Next = PtrL;
return s; // 返回新表头指针
}
p = FindKth(i-1,PtrL); // 查找第i-1个结点
if(p == NULL) // 第i-1个结点存在，不能插入
{
printf("第 %d-1 个结点存在，不能插入\n",i);
return NULL;
}
else
{
s = (List)malloc(sizeof(struct LNode)); // 申请、填装结点
s->Data = X;
s->Next = p->Next; // 新节点插入在第i-1个结点的后面
p->Next = s;
return PtrL;
}
}
【4】、删除（删除链表的第 i（1 ≤ i ≤ n）个位置上的结点）
- 先找到链表的第 i-1 个结点，用 p 指向；
- 再用指针 s 指向要删除的结点（p 的下一个结点）；
- 然后修改指针，删除 s 所指结点；
- 最后释放 s 所指结点的空间；
List Delete(int i,List PtrL)
{
List s,p;
if(i == 1) // 若要删除的是表的第一个结点
{
s = PtrL; // s指向第1个结点
if(PtrL != NULL) // 从列表中删除
{
PtrL = PtrL->Next;
}
else
{
return NULL;
}
free(s); // 释放被删除结点
return PtrL;
}
p = FindKth(i-1,PtrL); // 查找第i-1个结点
if(p == NULL)
{
printf("第%个结点不存在\n",i-1);
return NULL;
}
else if(p->Next == NULL)
{
printf("第%d个结点不存在\n",i);
return NULL;
}
else
{
s = p->Next; // s指向第i个结点
p->Next = s->Next; // 从链表中删除
free(s); // 释放被删除结点
return PtrL;
}
}