顺序表的常见算法

初始化线性表

参数用引用

Status InitList_Sq(SqList &L) //传入一个顺序表L
{L.elem = new ElemType[MAXSIZE]; //为该顺序表的基地址分配空间if(!L.elem) exit(OVERFLOW); //分配失败L.length = 0; //由于初始化的是一个空表，所以将其长度设置为0
return OK;
}

参数用的是引用型，对实参进行操作就是对形参进行操作

InitList_Sq是线性表名字，是顺序存储的，所以是Sq（sequence)

返回的状态值是Status

参数用指针

Status InitList_Sq(SqList *L) //传入一个顺序表L
{L->elem = new ElemType[MAXSIZE]; //为该顺序表的基地址分配空间if(!L->elem) exit(OVERFLOW); //分配失败L->length = 0; //由于初始化的是一个空表，所以将其长度设置为0
return OK;
}

 销毁线性表

void DestroyList_Sq(SqList &L) //传入一个顺序表L
{if (L.elem) //若该顺序表的基地址空间不为空delete[] L.elem; //则释放存储空间（因为线性表的顺序存储是用的数组，所以在delete后加上一个中括号）
}

清空线性表

void ClearList_Sq(SqList &L)
{L.length = 0; //将线性表的长度置为0
}

求线性表的长度（只读访问）

因为只读访问，实际上并不需要修改线性表，所以这个线性表SqList L，不需要使用引用型，即不需要＋"&"这个符号

int GetLength_Sq(SqList L)
{return (L.length);
}

判断顺序表是否为空

int IsEmpty_Sq(SqList L)
{if (L.length == 0)return 1;elsereturn 0;
}

 

取值（根据位置i查找）

int GetElem_Sq(SqList L, int i, ElemType &e) //为什么这里要用&
{
//判断i值（不是索引）是否合理，若不合理，返回ERROR
if(i < 1 || i > L.length)
return ERROR;e = L.elem[i-1]; //第i-1的单元存储着第i个数据。例：第1个位置的元素，实际上对应的是索引位置上的第0个元素return OK;
}
//使用：
int value = 0;
if (GetElem_Sq(L, 2, value) == OK) {
// 成功获取到值，可以在下面的代码中编辑 value 的逻辑
}

查找（根据值为e查找）

int LocateELem(SqList L, ElemType e){//在线性表L中查找值为e的数据元素，返回其序号(是第几个元素)for (i=0;i< L.length;i++)if(L.elem[i]==e) return i+1;//查找成功，返回序号return 0; //查找失败，返回0

 

顺序表的插入

Status ListInsert_Sq(SqList &L, int i, ElemType e)
{
//判断插入位置i是否合法if(i < 1 || i > L.length + 1) return ERROR;
//判断顺序表的存储空间是否已满
if(L.length == MAXSIZE) return ERROR;
//将第n至第i位的元素依次向后移动一个位置，空出第i个位置
for(int j = L.length - 1; j >= i - 1; j--)L.elem[j + 1] = L.elem[j];
//将要插入的新元素e放入第i个位置L.elem[i - 1]=e;
//表长加1，插入成功返回OK
++L.length;
return OK;
}

给个例子加强理解

 

顺序表的删除（删除的原理跟插入挺相似的，就是一个向前移动一个向后移动的问题）

Status ListDelete_Sq(SqList &L, int i)
{//判断删除位置i是否合法if(i < 1 || i > L.length) return ERROR;//将第i+1至第n位的元素依次向前移动一个位置for (int j = i; j <= L.length - 1; j++)L.elem[j - 1] = L.elem[j];//表长减1，删除成功返回OK--L.length;return OK;
}