#define Maxsize 22
typedef int ElemType;
typedef struct {
ElemType data[Maxsize];
int length;
}Sqlist;
#define InitSize 100
typedef struct {
ElemType *data;
int Max_size, length;
}Seqlist;
//顺序表插入
bool ListInsert(Sqlist &L, int i, ElemType e) {
if (i<1 || i>L.length)
{
return false;
}
if (L.length >= Maxsize)
{
return false;
}
for (int j = L.length; j >= i; j--)
{
L.data[j] = L.data[j - 1];//第i个元素及以后依次后移
}
L.data[i - 1] = e;//在位置i插入元素e;
L.length++;//线性表长度加1
return true;
}
/*算法分析:表尾插入 i=n+1; 时间复杂度:O(1)
表头插入 i=1; 时间复杂度 O(n)
平均时间复杂度: O(n)
*/
bool ListDelete(Sqlist &L, int i, ElemType &e)
{
if (i<1 || i>L.length)
{
return false;
}
e = L.data[i]; //将被删除的元素赋值给e
for (int j = i; j < L.length; j++)
{
L.data[j - 1] = L.data[j]; //将第i个位置后的元素前移
}
L.length--; //线性表长度减1
return true;
}
/*算法分析:表尾删除 i=n; 时间复杂度:O(1)
表头删除 i=1; 时间复杂度 O(n)
平均时间复杂度: O(n)
*/
int LocateElem(Sqlist L, ElemType e) {
int i;
for (int i = 0; i < L.length; i++) {
if (L.data[i] == e) {
return i + 1;
}
}
return 0;
}
/*算法分析:表头查找 : 时间复杂度:O(1)
表尾查找 : 时间复杂度 O(n)
平均时间复杂度: O(n)
*/