#include
#include
# define MaxSize 50
typedef struct{
ElemType data[MaxSize];//存放顺序表元素
int length;//存放顺序表长度
}SqList;//顺序表类型定义
//建立顺序表
void CreateList(SqList *&L,ElemType a[],int n){
int i;
for(i=0;i
}
L->length =n;
}
//顺序表基本运算算法
//初始化线性表InitList(L)
void InitList(SqList *&L){
L=(SqList *)malloc(sizeof(SqList));//分配存放线性表的空间
L->length =0;
}//本算法的时间复杂度为O(1)
//销毁线性表
void DestroyList(SqList *&L){
free(L);
}//本算法的时间复杂度为O(1)
//判断线性表是否为空
int ListEmpty(SqList *L){
return (L->length ==0);
}//本算法的时间复杂度为O(1)
//求线性表的长度
int ListLength(SqList *L){
return (L->length);
}//本算法的时间复杂度为O(1)
//输出线性表
void DispList(SqList *L)
{
int i;
if(ListEmpty(L)) return;
for(i=0;i
printf(nn,L->data[i]);
}
printf("\n");
}//本算法的时间复杂度为O(L->length)
//求线性表中某个数据的元素值
int GetElem(SqList *L,int i,ElemType &e)
{
if(i<1||i>L->length)
return 0;
e=L->data[i-1];//这儿体现了数组的优点,可以直接通过下标访问
return 1;
}//本算法的时间复杂度为O(1)
//按元素的值查找
int LocateElem(SqList *L,ElemType e){
int i=0;
while(i
if(i>=L->length)
return 0;
else
return i+1;
}//本算法中基本运算为while循环中的i++语句,故时间复杂度为O(L->length)
//插入数据元素
int ListInsert(SqList *&L,int i,ElemType e){
int j;
if(i<1 || i>L->length+1)
return 0;//参数错误,返回0
i--;//将顺序逻辑位序变为物理位序
for(j=L->length;j>i;j--){
L->data[j]=L->data[j-1];//将data[i]及后面的元素后移一个位置
}
L->data[i]=e;//插入元素e
L->length++;//增加长度
return 1;
}//本算法的平均时间复杂度为O(n)
//删除数据元素
int ListDelete(SqList *&L,int i,ElemType &e){
int j;
if(i<1 || i>L->length)
return 0;
i--;//将顺序逻辑位序变为物理位序
e=L->data[i];
for(j=i;j
L->data[j]=L->data[j+1];//将data[i]之后的元素前移一个位置,这就是数组中的删除思想
}
L->length--;
return 1;
}//本算法的平均时间复杂度为O(n)