零个或者多个（相同类型）数据元素的有限序列
Data
线性表的数据对象集合为{a1,a2,a3,a4,,,an}每个元素的类型均为DataType.其中，出第一个元素a1，每个元素有且只有一个直接前驱元素，除了最后一个元素an 外，每个元素都有且只有一个直接后继元素，数据元素之间的关系是一对一的关系
operation
InitList(*L)；初始化操作，简历一个空的线性表
ListEmpty(L);若线性表为空，返回true,否则false
ClearList(*L) 将线性表清空
GetElem(L,i,*e);将线性表L中第i的元素的值返回给e。
LocateElem(L,e) ; 在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中的序号表示成功，否则返回0失败。
ListInsert(*L,i.e);在线性表L 中的第I个位置插入元素e.
ListDelete(*L,i,*e)删除线性表L中第i 个位置元素，并用e 返回其值
ListLength(L);返回线性表L 的元素个数
线性表的顺序存储结构
指的是用一段地址连续的存储单元依次存储线性表的数据元素。
顺序存储的结构属性
#define MAXSIZE 20 //分配的最大内存
typedef int ElemType; 类型根据需求而定
typedef struct
{
ElemType data[MAXSIZE];
int length;
}SqList;
地址的计算方法
LOC(ai) = LOC(a1) + (i-1) *c ; //c为每个元素占用存储空间
获取元素操作
只需要i i 的数值在数组下标范围内，就是把数组第i-1 的下标的值返回即可
Status GetElem(SqlList L,int i,ElemType *e)
{
if(L.length==0 || i<i||i>L.length) return ERROR;
*e =L.data[i-1];
return ok;
}
插入：
思想：
1、插入位置不合适，抛出异常
2、如果线性表长度大于等于数组长度，则抛出异常或动态增加容量。
3、从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置；
4、将要插入元素填入位置i处。表的长度加一
初始条件： 顺序表L 已存在，1《=i《ListLength(L);
ElemType ListInsert(Sqlist *L, int i, ElemType e)
{
int k;
if (L->length == MAXSIZE)
{
return ERROR;
}
if (i<1 || i>L->length + 1) return ERROR;
if (i <= L->length)//插入数据不在表尾
{
for (k = L->length - 1; k >= i - 1; k--)//将要插入位置后数据元素向后移动一位
L->value[k + 1] = L->value[k];
}
L->value[i - 1] = e;//将新元素插入
L->length++;
return OK;
}
删除
ElemType ListDel(Sqlist *L, int i, ElemType* e)
{
int k;
if (L->length == 0) return ERROR; //线性表空
if (i<1 || i>L->length) return ERROR; //删除的位置不正确
*e = L->value[i - 1];
if (i < L->length)
{
for (k = i; i < L->length; k++)
L->value[k - 1] = L->value[k];
}
L->length--;
return OK;
}
线性表顺序存储结构的特点：
优缺点：
无须为表示表中元素之间的逻辑关系而增加额外的存储空间；可以快速的存取表中任意位置的元素
插入和删除操作需要移动大量的元素； 当线性表长度变化较大，难以确定存储空间的容量；造成存储空间的碎片
网友评论