线性列表的顺序显示是指在一系列地址连续的存储单元中依次存储线性列表的数据要素。
高级编程语言通常以数组形式描述数据结构中的顺序存储结构。 另一方面,由于线性表的长度可变,所需的最大存储空间因问题而异,因此c语言可以使用动态分配的一维数组,如下所示:
#defineLIST_INIT_SIZE10//线性表中存储空间的初始分配量
#defineLISTINCREMENT2//线性表存储空间的分配增量
类型结构
{
ElemType*elem; //存储空间的基地址
intlength; //当前长度
英特尔尺寸; //当前分配的存储容量
}SqList;
顺序表的基本操作(12个)用c语言如下实现
//SeqList.h
#ifndef SEQLIST_H
#defineSEQLIST_H
#defineLIST_INIT_SIZE10
#defineLISTINCREMENT2
#定义真1
#defineFALSE0
类型结构
{
ElemType*elem;
intlength;
英特尔尺寸;
}SqList;
类型定义布尔;
intinitlist(sqlist*L );
intdestroylist(sqlist*L );
intclearlist(sqlist*L );
intlistempty(sqlistl;
安装长度(sqlistl;
intgetelem(sqlistl、inti、ElemType*e );
intlocateelem(sqlistl,ElemTypee,int ) compare (ElemType,elemtype );
intpriorelem(sqlistl,ElemTypecur_e,ElemType*pre_e );
intnextelem(sqlistl,ElemTypecur_e,ElemType*next_e );
intlistinsert(sqlist*L,inti,ElemTypee );
intlistdelete(SQLIST*L,inti,ElemType*e );
intlisttraverse(sqlistl,void ) VI ) ) ElemType* );
下面是每个函数的实现代码。
#include'SeqList.h '
#包含
#包含
intinitlist(sqlist*L ) ) )。
//操作结果:创建空顺序线性表
{
(l ).elem=) elemtype* ) malloc ) list _ init _ size * sizeof (elemtype ) );
if (! (l ).elem ) )
内存定位故障(n ); //内存分配失败
(l ).length=0;
(l ).listsize=LIST_INIT_SIZE;
返回1;
}
intdestroylist(sqlist*L ) /初始条件:顺序表l已经存在。 操作结果:销毁顺序表l
{
free () l ).elem );
(l ).elem=NULL;
(l ).length=0;
(l ).listsize=0;
返回1;
}
intclearlist(sqlist*L )//初始条件:顺序表l已经存在。 操作结果:将l重置为空表
{
(l ).length=0;
返回1;
}
intlistempty(sqlistl )//初始条件:顺序表l已经存在。 操作结果:如果l是空表,则返回TRUE;否则返回FALSE
{
if(l.length==0) ) ) ) ) ) ) ) )。
返回真;
else
返回假;
}
IntlistLength(SQListL )//初始条件:顺序表l已经存在。 操作结果:返回l中数据元素的数量
{
returnL.length;
}
intgetelem(sqlistl、inti、ElemType*e ) /初始条件:顺序表l已经存在,1=i
=ListLength(L)//操作结果:用e返回L中的第i个数据元素的值
{
if(i<1||i>L.length)
printf("ERRORn");
*e=*(L.elem+i-1);
return1;
}
intLocateElem(SqListL,ElemTypee,int(*compare)(ElemType,ElemType))
{//初始条件:顺序表L已存在,compare()是数据元素判定函数(满足为1,否则为0)
//操作结果:返回L中第1个与e满足关系compare()数据元素的位序。
//若这样的数据元素不存在,则返回值为0
ElemType*p;
inti=1;
p=L.elem;
while(i<=L.length&&!compare(*p++,e))
++i;
if(i<=L.length)
returni;
else
return0;
}
intPriorElem(SqListL,ElemTypecur_e,ElemType*pre_e)
{
//初始条件:顺序表L已存在
//操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,否则操作失败,pre_e无定
//义
inti=2;
ElemType*p=L.elem+1;
while(i<=L.length&&*p!=cur_e)
{
p++;
i++;
}
if(i>L.length)
return-1;
else
{
*pre_e=*--p;
return1;
}
}
intNextElem(SqListL,ElemTypecur_e,ElemType*next_e)
{
//初始条件:顺序表L已存在
//操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继,否则操作失败,next_e无
//定义
inti=1;
ElemType*p=L.elem;
while(i
{
i++;
p++;
}
if(i==L.length)
return-1;
else
{
*next_e=*++p;
return1;
}
}
intListInsert(SqList*L,inti,ElemTypee)
{
//初始条件:顺序表L已存在,1<=i<=ListLength(L)+1
//操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1
ElemType*newbase,*q,*p;
if(i<1||i>(*L).length+1)//i值不合法
printf("ERRORn");
if((*L).length>=(*L).listsize)//当前存储空间已满,增加分配
{
newbase=(ElemType*)realloc((*L).elem,((*L).listsize+LISTINCREMENT)*sizeof(ElemType));
if(!newbase)
printf("MemoryAllocationFailuren");//存储分配失败
(*L).elem=newbase;//新基址
(*L).listsize+=LISTINCREMENT;//增加存储容量
}
q=(*L).elem+i-1;//q为插入位置
for(p=(*L).elem+(*L).length-1;p>=q;--p)//插入位置及之后的元素右移
*(p+1)=*p;
*q=e;//插入e
++(*L).length;//表长加1
return1;
}
intListDelete(SqList*L,inti,ElemType*e)
{
//初始条件:顺序表L已存在,1<=i<=ListLength(L)
//操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1
ElemType*p,*q;
if(i<1||i>(*L).length)
printf("ERRORn");
p=(*L).elem+i-1;
*e=*p;
q=(*L).elem+(*L).length-1;
for(++p;p<=q;++p)
*(p-1)=*p;
(*L).length--;
return1;
}
intListTraverse(SqListL,void(*vi)(ElemType*))
{
//初始条件:顺序表L已存在
//操作结果:依次对L每个数据元素调用函数vi()。一旦vi()失败,则操作失败
// vi()的形参加'*',表明可通过调用vi()改变元素的值
ElemType*p;
inti;
p=L.elem;
for(i=1;i<=L.length;i++)
vi(p++);
printf("n");
return1;
}
以下是测试主函数
int main()
{
SqListL;
ElemTypee,e0;
inti;
intj,k;
i=InitList(&L);
printf("初始化L后:L.elem=%uL.length=%dL.listsize=%dn",L.elem,L.length,L.listsize);
for(j=1;j<=5;j++)
i=ListInsert(&L,1,j);
printf("在L的表头依次插入1~5后:*L.elem=");
for(j=1;j<=5;j++)
printf("%d",*(L.elem+j-1));
printf("n");
printf("L.elem=%uL.length=%dL.listsize=%dn",L.elem,L.length,L.listsize);
i=ListEmpty(L);
printf("L是否空:i=%d(1:是0:否)n",i);
i=ClearList(&L);
printf("清空L后:L.elem=%uL.length=%dL.listsize=%dn",L.elem,L.length,L.listsize);
i=ListEmpty(L);
printf("L是否空:i=%d(1:是0:否)n",i);
for(j=1;j<=10;j++)
ListInsert(&L,j,j);
printf("在L的表尾依次插入1~10后:*L.elem=");
for(j=1;j<=10;j++)
printf("%d",*(L.elem+j-1));
printf("n");
printf("L.elem=%uL.length=%dL.listsize=%dn",L.elem,L.length,L.listsize);
ListInsert(&L,1,0);
printf("在L的表头插入0后:*L.elem=");
for(j=1;j<=ListLength(L);j++)
printf("%d",*(L.elem+j-1));
printf("n");
printf("L.elem=%u(有可能改变)L.length=%d(改变)L.listsize=%d(改变)n",L.elem,L.length,L.listsize);
GetElem(L,5,&e);
printf("第5个元素的值为:%dn",e);
for(j=3;j<=4;j++)
{
k=LocateElem(L,j,comp);
if(k)
printf("第%d个元素的值为%d的平方n",k,j);
else
printf("没有值为%d的平方的元素n",j);
}
for(j=1;j<=2;j++)
{
GetElem(L,j,&e0);
i=PriorElem(L,e0,&e);
if(i==-1)
printf("元素%d无前驱n",e0);
else
printf("元素%d的前驱为:%dn",e0,e);
}
for(j=ListLength(L)-1;j<=ListLength(L);j++)
{
GetElem(L,j,&e0);
i=NextElem(L,e0,&e);
if(i==-1)
printf("元素%d无后继n",e0);
else
printf("元素%d的后继为:%dn",e0,e);
}
k=ListLength(L);
for(j=k+1;j>=k;j--)
{
i=ListDelete(&L,j,&e);
if(i==0)
printf("删除第%d个数据失败n",j);
else
printf("删除的元素值为:%dn",e);
}
printf("依次输出L的元素:");
ListTraverse(L,visit);
printf("L的元素值加倍后:");
ListTraverse(L,dbl);
ListTraverse(L,visit);
DestroyList(&L);
printf("销毁L后:L.elem=%uL.length=%dL.listsize=%dn",L.elem,L.length,L.listsize);
return0;
}