顺序表以数据元素在计算机内的物理位置相邻来表示数据元素在线性表中的逻辑相邻关系。
特征:
1. 有且仅有一个第一个结点,它没有前趋而只有一个后继;
2. 有且仅有一个最后一个结点,它没有后继而只有一个前趋;
3. 其余结点只有一个前趋和一个后继。
优点:
1. 无须为表示数据元素之间的关系而额外增加存储空间
2. 可以随机存取表中任一数据元素,元素存储位置可以用一个简单,直观的公式表达
缺点:
1. 插入和删除运算必须移动大量(几乎一半)数据元素,效率最低。
2. 必须预先分配存储空间,造成空间利用率低,且表的容量难以扩充。
线性表运算:
建立顺序表,将给定的含有n个元素的数组的每个元素依次放入到顺序表中,并将n赋给顺序表的长度域。
typedef struct
{
ElemType data[MaxSize];
int length;
}SqList;
初始化线性表。该运算是构造一个空的线性表L。只需分配线性表的存储空间并将length域设置为0。
void InitList(SqList *&L)
{
L=(SqList *)malloc(sizeof(SqList));
L->length=0;
}
释放线性表L占用的内存空间
void DestroyList(SqList *&L)
{
free(L);
}
判断线性表是否为空表。判断成员length是否为0,就可以判断线性表是否为空。
int ListEmpty(SqList *&L)
{
return (L->length==0);
}
求线性表的长度
int ListLength(SqList *L)
{
return (L->length);
}
输出线性表。当线性表L不为空的时候,顺序输出每个元素的值
void DispList(SqList *L)
{
int i;
for(i=0;i<L->length;i++)
printf("%c",L->data[i]);
}
求线性表中某个数据元素值。返回L中第i个位置的元素值。
int GetElem(SqList *L,int i,ElemType &e)
{
if(i<1 || i>L->length)
return 0;
e=L->data[i-1];
return 1;
}
int LocateElem(SqList *L,ElemType e)
{
int i=0;
while(i<L->length && L->data[i]!=e)
i++;
if(i>=L->length)
return 0;
else
return i+1;
}
int InsertList(SqList *L,int i,ElemType e)
{
int j;
if(i<1 || i>L->length+1)
return 0;
i--;
for(j=L->length;j>i;j--)
}
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->length-1;j++)
L->data[j]=L->data[j+1];
L->length--;
return 1;
}