【什么是算法？】
空间复杂度S(n)：根据算法写成的程序在执行时占用存储单元的长度。
时间复杂度T(n)：根据算法写成的程序在执行时消耗的时间长度。
分析算法复杂度
Tworst(n)：最坏情况复杂度
Tav(n)：平均复杂度
【什么是线性表？】
“线性表（Linear List）”：由同类数据元素构成有序序列的线性结构
表中的元素个数称为线性表的长度，没有元素时称为空表，表的起始位置称为表头，结束位置称为表尾。
【线性表的顺序存储实现】
typedef struct Lnode *List;
struct Lnode {
ElementType Data[MAXSIZE];
int Last; //线性表最后一个元素
};
struct LNode L;
List PtrL; //PtrL为指向结构体的指针 || struct Lnode * PtrL
访问下标为i的元素：L.Data[i]或者PtrL->Data[i]
线性表长度：L.Last+1或者PtrL->Last+1
【线性表的主要操作】
1、初始化（建立空的顺序表）
List MakeEmpty()
{
List PtrL;
PtrL=(List )malloc(sizeof(struct LNode));
PtrL->Last=-1;
return PtrL;
}
2、查找
/* 查找成功的平均比较次数是（n+1）/2
平均时间性能是O（n） */
int Find()(ElementType X,List PtrL)
{
int i=0;
while(i<=PtrL->Last && PtrL->Data[i]!=X)
i++;
if(i>PtrL->Last) return -1;
else return i;
}
3、插入
/* 第i个位置上插入一个值为x的新元素 */
void Insert(ElementType X, int i, List PtrL)
{
/*MAXSIZE 数组大小*/
if (PtrL->Last == MAXSIZE - 1) {
printf("表满");
return;
}
if (i<1 || i>PtrL->Last + 2) {
printf("位置不合法");
return;
}
for (j = PtrL->Last; j >= i - 1; j--)
PtrL->Data[j + 1] = PtrL->Data[j];
PtrL->Data[i - 1] = X;
PtrL->Last++;
return;
}
4、删除
/* 删除表的第i个位置上的元素 */
void Delete(int i, List PtrL)
{
int j;
if (i<1 || i>PtrL->Last + 1) {
printf("不存在第%d个元素", i);
return;
}
for (j = i; j <= PtrL->Last; j++)
PtrL->Data[j - 1] = PtrL->Data[j];
PtrL->Last--;
return;
}
