线性表是一种线性结构,它是由n(n≥0)个数据元素a1,a2,…,an组成的有限序列。
void insert(Array arr, DataType x, int i) {
//将元素 x 插入到顺序表arr 的第 i 个数据元素之前
if (arr.length == Maxsize)
exit("表已满");
if (i < 1 || i > arr.length + 1)
exit("插入位置错误");//检查插入位置是否合法
for (j = arr.length; j >= i; j--) { //初始 i=arr.length
arr.data[j] = L.data[j - 1]; //依次后移
}
arr.data[i - 1] = x; //元素 x 调整到下标为 i-1 的位置
arr.length++; //表长度加 1
}
void delete(Array A, int i) {
//删除线性表L中的第i个数据结点
if (i < 1 || i > A.length) //检查位置是否合法
exit("非法位置");
for (j = j; j < A.length; j++) { //第i个元素的下标为i-1
A.data[j - 1] = A.data[j]; //依次左移
}
A.length--;//表长度减1
}
定位算法:平均时间复杂度为 O(n)
int Locate(Array arr, DataType x) {
int i = 0;
while ((i < arr.length) && (arr.data != x)) { //在顺序表中查找值为 x 的结点
i++;
}
if (i < arr.length) return i + 1;//若找到值为x的元素,返回元素的序号
else return 0;//未查找到值为x的元素,返回0
}