一、顺序表的初始化
顺序表的初始化,就是构造一个数据元素为0的空表,算法如下:
void SequenList::Initiate()
{
len = 0;
}
设调用函数为主函数,主函数对初始化函数的调用如下:
void main()
{
SequenList L;
L.Initiate();
......
}
二、插入运算
顺序表的插入运算是指在顺序表中的第i个位置插入一个值为x的新元素,插入后,使原表为n的顺序表:
(a1, a2,···,ai-1,ai,ai+1,···,an)
变为表长为n+1的顺序表:
(a1, a2,···,ai-1,x,ai,ai+1,···,an)
其中,i的合理取值范围为1≤i≤n+1
顺序表插入运算的图形表示
在顺序表上完成插入运算,主要步骤如下:
- 将数据元素ai ~ an依次向后移动一个位置,为新元素让出位置;
- 将x置入空出的新位置;
- 增加len的值
(一)代码实现
int SequenList::Insert(DataType x, int i) {
//在线性表的第 i 个数据元素之前插入一个新的数据元素 x
int j;
if (len >= MAXSIZE) {
cout << "overflow!" << endl; //数据溢出
return 0;
} else if ((i<1) || (i>len+1)) { //如果插入位置不合法
cout << "position is not correct!" << endl;
return 0;
} else {
for(j=len; j>=i; j--)
data[j]=data[j-1]; //元素后移
data[i-1]=x; //插入元素
len++; //表长度增加 1
return 1;
}
}
要注意的问题:
-
顺序表中数据区域有 MAXSIZE 个存储单元,所以在向顺序表中做插入操作时,首先检查表空间是否满了,在表满的情况下不能再做插入,否则产生溢出错误。
-
要检验插入位置的有效性,这里 i 的有效范围是 1≤i≤n+1,其中 n 为原表长。
-
注意数据的移动方向。
顺序表插入运算的时间复杂度为 O(n)。
三、删除运算
线性表的删除运算是指将表中第 i 个元素从线性表中删除,使原表长为 n 的线性表:
(a1, a2,···,ai-1,ai,ai+1,···,an)
变成表长为 n-1 的线性表:
(a1, a2,···,ai-1,ai+1,···,an)
i 的取值范围为 1≤i≤n。
顺序表删除运算图形表示
在顺序表上完成删除运算,主要步骤如下:
- 将数据元素ai+1 ~ an依次向前移动一个位置,为新元素让出位置;
- 将len的值减1
(一)代码实现
int SequenList::Deleted(int i) { //删除顺序表的第i个数据元素
int j;
if((i<1) || (i>len)) { //若删除位置不合法
cout << "position is not correct!" << endl;
return 0;
} else {
for(j=i; j<len; j++)
data[j-1]=data[j]; //元素前移
len--; //表长度减 1
return 1;
}
}
本算法应注意以下问题。
(1)删除第 i 个数据元素,i 的取值为 1≤i≤n,否则第 i 个元素不存在。因此,要检查删除位置的有效性。
(2)删除ai之后,该数据不再存在;如果需要,可先取出ai,再做删除。
顺序表的删除算法的时间复杂度为O(n)。
四、按值查找
顺序表中的按值查找是指在线性表中查找与给定值 x 相等的数据元素。
在顺序表中完成该运算最简单的方法是:
从第一个元素a1起依次和 x 比较,直到找到一个与 x 相等的数据元素,则返回它在顺序表中的位置值(下标 +1);或者查遍整个表都没有找到与 x 相等的数据元素,则返回 0。
(一)代码实现如下
int SequenList::Locate(DataType x) {
//返回值为 x 的数据元素的位序值
int j=0;
while ((j<len) && (data[j]!=x)) j++;
if (j<len) return j+1;
else return 0;
}
该算法的时间复杂度为O(n)。
五、读取第 i 个数据元素的值
DataType SequenList::Get(int i) {
if ((i<1) || (i>len)) {
cout<<"position is not correct!"<<endl;
return NULL;
} else return data[i-1];
}
六、取得数据元素个数
int SequenList::Length() {
return len;
}