顺序表运算

一、顺序表的初始化

顺序表的初始化,就是构造一个数据元素为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

顺序表插入运算的图形表示
顺序表的插入

在顺序表上完成插入运算,主要步骤如下:

  1. 将数据元素ai ~ an依次向后移动一个位置,为新元素让出位置;
  2. 将x置入空出的新位置;
  3. 增加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;
	}
}

要注意的问题:

  1. 顺序表中数据区域有 MAXSIZE 个存储单元,所以在向顺序表中做插入操作时,首先检查表空间是否满了,在表满的情况下不能再做插入,否则产生溢出错误。

  2. 要检验插入位置的有效性,这里 i 的有效范围是 1≤i≤n+1,其中 n 为原表长。

  3. 注意数据的移动方向。

顺序表插入运算的时间复杂度为 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。

顺序表删除运算图形表示
顺序表删除运算

在顺序表上完成删除运算,主要步骤如下:

  1. 将数据元素ai+1 ~ an依次向前移动一个位置,为新元素让出位置;
  2. 将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;
}
用户头像
登录后发表评论